Friday, June 16. 2006
a parser generator for PHP - *finally*
[Update: oops. I forgot that the server parses file named "whatever.php" when uploading things 
. The directory at pear.chiaraquartet.net/lemon (clickable link below) now contains both .phps and .php.txt files for downloading. sorry about that]
So, it's been a while since I wrote an entry, but I have not been idle (are you really all that surprised?) I took a hard look at the projects I am involved in, and realized rather quickly that the only thing really holding back several of them is a good parser generator. Here's the short list of projects that really need a parser generator:
- phpDocumentor. We use parsers for *everything*
- PHP_Parser. The name says it all
- Games_Chess/File_ChessPGN. For this team, we need a good parser for the PGN file format.
Recently, I completed a rather nice lexer for docblocks (documentation comments) and this is now available at http://pecl.php.net/docblock, for those who are interested. About three weeks ago, I looked at the state of the parser generator world out there for PHP, and it is pretty dismal. Antlr3 will theoretically support PHP 5 generation, but it's impossible to find any source in spite of several fruitless hours of googling.
I finally decided that if this is ever going to happen, I'll have to get off my butt and do it. So, two weeks ago, I grabbed the source of the Lemon parser generator from its website (conveniently compressed into two files: the generator and its template). Although the 4000+ lines may have scared me off, the code is very clearly written, making minimal use of pre-processor macros, and actually lends itself very easily to translation into PHP code. I spent about a week doing the actual transcription from C to PHP, removing all the malloc-related crap, converting the C implementation of associative arrays into PHP associative arrays, and finally I had something that works. In the past week, I've been scraping on the template, which was pretty complete, but didn't quite do everything I needed.
For one example, upon a syntax error, there was no easy way to retrieve a list of expected tokens. This turned out to be a very hard problem, until I broke down and yesterday added a generated array of expected tokens. Coupling this with a little reduce simulator, it is quite easy to grab the complete list of expected tokens based on the current token and the parser stack.
Another tricky problem was that if an unexpected token occurred right at a potential end-of-input moment, the parser simply reduced to an accept, and silently restarted parsing. This is a bad thing (TM). So, I implemented a simple "is this token possible in the current state of things?" function that catches these pesky errors.
In the process, I have a fully working PGN file parser that will make its way into a PEAR proposal as soon as I get around to integrating it with Games_Chess to do full validation of the contents of the PGN file. However, the parser works 100% even with some of the weirdest PGN things I could throw at it.
The parser generator works just like Lemon with a few small differences. I added a few line directives:
- %include_class - this works like %include, but puts stuff inside the generated parser class.
- %declare_class - this can be used to make the parser implement an interface, extend another class, etc. and is used like "%declare_class {extends blah} <-- note the lack of semi-colon, this is inserted between "class ParseyyParser" and "{"
The parser should be called with a loop similar to this:
$lexer = new File_ChessPGN_Lexer($lexer);
while ($lexer->advance($parser)) {
$parser->doParse($lexer->token, $lexer->value);
}
$parser->doParse(0, 0); // for end of input
To run it, save Main.php and Lempar.php in the same directory, and take a look at the bottom of Main.php for an example run. You can also just run it from the command line:
php Main.php /path/to/Parser.y
Parser.y is the fully-functioning PGN file parser that will be integrated into File_ChessPGN. I plan to test out the parser generator and split it into multiple files, then potentially propose it as a PEAR package. It should be noted that the original Lemon authors disclaim copyright to the code. This port to PHP, however, will be licensed under either PHP 3.01, new BSD or something along those lines.
You can grab the stuff from http://pear.chiaraquartet.net/lemon.
Related Links:
http://ren.dotgeek.org/expr/
http://ren.dotgeek.org/expr/expr.y
That being said, this parser generator sounds very interesting. I'd like to see it.
BTW, you ought to link to the lemon site: http://www.hwaci.com/sw/lemon/
And... (does it have unit tests?)
The generator itself can be somewhat slow, but I can generate the PHP parser (almost finished) for phpDocumentor in about 2 seconds on my computer. I haven't yet done any performance tests on the generated parser.
The best part about all of this is that it can be optimized, but it will perform at the level of Lemon.
What is the status for your work on lemon.
It appears that the linked files have not been completely looked through.
For instance, on Line 2787 of Main.php you have $this->{self::$options[$argv[$i][1]]['arg']}(substr($v, 2));
which is clearly an error because $v is a boolean.
I would like to look more into lemon, but first I will ensure that you have abandoned your work. Would be really stupid for me to looke at the code if you have made lots of updates and just forgot to upload them.
The parser has been released as an official PEAR package at http://pear.php.net/PHP_ParserGenerator
I've been using the code extensively for a number of parsers, including a parser for the PGN (chess) file format, a parser for PHP itself (working on that right now), a parser for docblocks in PHP, and there are others who have been using it as well for parsing lots of things.
Try that package out and see if it works for you.
I'll email you some more questions.
(sorry for br-tokens at end of lines. Seems like a bug in geshi)
%name Bug_<br />
%include {<br />
$parser = new Bug_yyParser;<br />
$tokens['-'] = Bug_yyParser::DASH;<br />
$tokens['1'] = Bug_yyParser::NUMBER;<br />
$tokens['|'] = Bug_yyParser::EOP;<br />
<br />
$str = "|1-1-1|";<br />
<br />
for($i=0; $i< strlen($str); $i++) {<br />
$token = $tokens[$str{$i}];<br />
$parser->doParse($token,$val);<br />
}<br />
}<br />
%syntax_error {<br />
die("Syntax error!\n");<br />
}<br />
start ::= EOP interval EOP.<br />
interval ::= NUMBER DASH NUMBER.<br />
Thx, admin!
Have you considered writing a tutorial, with a full lexer/parser so that lemon n00bs could start using this package? A link to a working example would be almost as helpful.
Calendar
|
March '10 | |||||
| Mon | Tue | Wed | Thu | Fri | Sat | Sun |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 15 | 16 | 17 | 18 | 19 | 20 | 21 |
| 22 | 23 | 24 | 25 | 26 | 27 | 28 |
| 29 | 30 | 31 | ||||
