It has finally been done, PHP-Front has perfect operator precedence!
And why can this be written down as a fact? Because of the work of Martin! He has worked on the grammar-engineering-tools tool for generating SDF priorities. When I worked on them I ran into some problems because of the decisions that where made during the initial development (read: when the tools had to be finished yesterday). This resulted in a common format for PHP precedence rules that was neither YACC-like nor SDF-like. Martin has rewritten the tools to use most of SDF representation and this worked very good according to all the solved issues. The operator precedence is now encoded into PHP-Front as separate modules for both version 4 and version 5, both of them over 6k LOC.
The (technical) details about how these files are generated will probably make a long and interesting blog-post. Since Martin says it is hard to find such a subject, not to mention (again) that it is his work, who am I to take this subject away from him? Maybe he can find some time after preparing the LDTA-presentation for Thursday. I won't be able to make it, but if you are close to Delft you might want to sneak into the Research Colloqium. (If you do, please tape it!)
Besides bringing perfect precedence to PHP-Front, this work has also resulted in a new issue. It was not very hard to figure it out, I just misinterpreted the note in the documentation. So I immediately fixed it by removing a special case which did not have to exist, just to put the icing on the cake.
Showing posts with label Grammar Engineering Tools. Show all posts
Showing posts with label Grammar Engineering Tools. Show all posts
PHP Operator precedence
If you take a look in the PHP-manual regarding operator precedence you will find the following quote:
Although ! has a higher precedence than =, PHP will still allow expressions similar to the following: if (!$a = foo()), in which case the return value of foo() is put into $a.
This is not very informative, which expressions are similar to this expression?
The answer to this can be found in this (huge!) file. This file is made with a tool called 'generate-prec-rules', which was created this week. It does exactly what the name implies, it generates the precedence rules given a set of common-precedence rules. The file above is created with the precedence rules from the yacc-definition of PHP version 5.
But how can we interpret these rules? Let's take a look at an example rule:
This rule disallows a "/" on the second position of the '@'. Please note that this notation also counts the string-literal.
However, the expression @ 4 / 5 is not invalid, it can still be parsed and evaluated. The rule above just explains how PHP places the parenthesizes in the expression, in this case like this:
(@ 4 ) / 5.
Take a minute to think about the expression and how it is influenced by the above rule, it took me a while to figure it out.
It is nice to have all of the rules, they describe the operator precedence very precisely, but the size of the file is a bit problematic. Every operator, there are about 32, gets a rule for each other operator for each expression it has. The '*' alone already occurs in 82 rules.
So the next step that we will have to take is to combine rules without changing the semantics of the precedence relations. An example of this is the combination of these two rules:
into this rule:
Which means the same, but is a bit more compact and probably more understandable.
So when this tool is created, and some things are changed within SDF, we can incorporate the newly generated precedence rules into PHP-Front. This will solve some parsing problems and will give us an even better SDF-grammar for PHP. We will also try to generate a more understandable, one page list of the operator precedence within PHP to replace the quote in the current PHP-documentation.
A nice example of 'research meets real life' don't you think?
Although ! has a higher precedence than =, PHP will still allow expressions similar to the following: if (!$a = foo()), in which case the return value of foo() is put into $a.
This is not very informative, which expressions are similar to this expression?
The answer to this can be found in this (huge!) file. This file is made with a tool called 'generate-prec-rules', which was created this week. It does exactly what the name implies, it generates the precedence rules given a set of common-precedence rules. The file above is created with the precedence rules from the yacc-definition of PHP version 5.
But how can we interpret these rules? Let's take a look at an example rule:
context-free priorities
"@" Expr -> Expr
<1> >
Expr "/" Expr -> Expr
This rule disallows a "/" on the second position of the '@'. Please note that this notation also counts the string-literal.
However, the expression @ 4 / 5 is not invalid, it can still be parsed and evaluated. The rule above just explains how PHP places the parenthesizes in the expression, in this case like this:
(@ 4 ) / 5.
Take a minute to think about the expression and how it is influenced by the above rule, it took me a while to figure it out.
It is nice to have all of the rules, they describe the operator precedence very precisely, but the size of the file is a bit problematic. Every operator, there are about 32, gets a rule for each other operator for each expression it has. The '*' alone already occurs in 82 rules.
So the next step that we will have to take is to combine rules without changing the semantics of the precedence relations. An example of this is the combination of these two rules:
context-free priorities
Expr "*" Expr -> Expr
<2> >
Expr "+" Expr -> Expr
context-free priorities
Expr "*" Expr -> Expr
<0> >
Expr "+" Expr -> Expr
into this rule:
Expr "*" Expr -> Expr
> Expr "+" Expr -> Expr
Which means the same, but is a bit more compact and probably more understandable.
So when this tool is created, and some things are changed within SDF, we can incorporate the newly generated precedence rules into PHP-Front. This will solve some parsing problems and will give us an even better SDF-grammar for PHP. We will also try to generate a more understandable, one page list of the operator precedence within PHP to replace the quote in the current PHP-documentation.
A nice example of 'research meets real life' don't you think?
What's the deal with ... ?
What's the deal with the lack of updating of PHP-Sat?
The last few weeks were filled with all sorts of other interesting activities, at least for me. My days are mostly filled with doing research for my master thesis and writing my proposal. In the past two weeks my free time was filled with the SUD, the visit to Google and the Grammar Engineering Tools. So plenty of projects, but little time to work on PHP-Sat.
What's the deal with this thesis then?
The thesis is the final project/course I will have to finish before I graduate. I will do some research to validate a certain algorithm that will improve feedback in educational programs. A more detailed explanation of the subject/algorithm/approach will be put into a blog soon. It's a totally different subject, but still interesting for people in computer science as in education.
What's the deal with this Grammar Engineering Tools project?
As mentioned before, the paper that was the result of the project was already submitted. Some improvements are made and the tools are (going to be) updated. My work on this project was still in the interest of PHP-Sat though. We have gotten a great insight in which combinations of operators are valid and which are not. This information will be put on the web as soon as we have a reasonable format for it, so stay tuned!
What's the deal with those labels/link underneath the posts?
The new version of blogger allows you to have labels under a blog. I thought is would be nice to order the posts according to certain topics. People that only want to read about my thesis can look here, those that only want to read about PHP-Sat here. I hope that the people behind blogger will add a RSS-feed per label in the future, but I can only hope :)
The last few weeks were filled with all sorts of other interesting activities, at least for me. My days are mostly filled with doing research for my master thesis and writing my proposal. In the past two weeks my free time was filled with the SUD, the visit to Google and the Grammar Engineering Tools. So plenty of projects, but little time to work on PHP-Sat.
What's the deal with this thesis then?
The thesis is the final project/course I will have to finish before I graduate. I will do some research to validate a certain algorithm that will improve feedback in educational programs. A more detailed explanation of the subject/algorithm/approach will be put into a blog soon. It's a totally different subject, but still interesting for people in computer science as in education.
What's the deal with this Grammar Engineering Tools project?
As mentioned before, the paper that was the result of the project was already submitted. Some improvements are made and the tools are (going to be) updated. My work on this project was still in the interest of PHP-Sat though. We have gotten a great insight in which combinations of operators are valid and which are not. This information will be put on the web as soon as we have a reasonable format for it, so stay tuned!
What's the deal with those labels/link underneath the posts?
The new version of blogger allows you to have labels under a blog. I thought is would be nice to order the posts according to certain topics. People that only want to read about my thesis can look here, those that only want to read about PHP-Sat here. I hope that the people behind blogger will add a RSS-feed per label in the future, but I can only hope :)
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!
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!