Operator precedence

So what was the curious remark in the last blog? What is the interesting functionality that I have made? The title gives the area of the functionality away, 'Operator precedence'.

The problem with PHP, and most grammars in general, is that the operator precedence is usually ill-documented. There is some documentation in a table, but the real reference is the implementation itself. Martin has a really nice idea about how you can check two grammars on having the same operator precedence, simple yet elegant.
If you take two definitions of a grammar, for example one defined in YACC and one defined in SDF, you can extract what is allowed and what not. The process of extracting the precedence rules that encode the behavior from these formalisms is written down in the paper that is produced, but I am not sure whether or not this is put on the web before we know if it is accepted to LDTA 2007. I do not even know if I can explain this very clearly in one post. So I can not provide a link to the paper, but this might be an interesting subject to blog about for Martin. (Yes, this is a hint!)
After extracting the precedence-rules you have to rename constructs and filter extensions from the rules. Finding the exact rewrites that are necessary is easy if you first extract the production-rules that are possible. This reduces the set that you are looking at from 3000-5000 to 30-50 rules, which is much easier to examine. After the rewriting you can compare the two sets of precedence-rules by a simple diff, a built-in strategy.

So what did I do exactly? Well, I worked on the actual tools in order to get some result, and we definitely did! We found several (precedence) problems in C-Transformers and the SDF-library, which both target C. This demonstrates the great power of the tools, because I am not that familiar with C myself!

We also found some precedence problems in the PHC, which were fixed very shortly after the report was send in. I was aware of the fact that there are some problems in PHP-front regarding operator precedence. In fact, it was one of the reasons for making these tools. The number of about 400 precedence problems was a still bit overwhelming at first. But most of these problems are due to the same operators and just produce about 49 warnings because all of the other operators report an error on it. We still have a lot of work to do, but we now have tool-support for checking the precedence rules!

No comments: