Saturday, June 24. 2006
PHP_ParserGenerator and PHP_LexerGenerator
Last week, I blogged about completing a port of the Lemon parser generator to PHP 5, which I thought was pretty cool.
However, in an email, Alex Merz pointed out that without a lexer generator to accompany lemon, it's pretty difficult to write a decent parser. The lexer in the example directory was generated using a program Alan Knowles ported from C# that was generating C# lexers. Alan modified the code to output PHP instead, and although I was able to get it to work some of the time, I had tremendous difficulty even getting C# to run on my computers when the original machine kicked the bucket. In addition, making changes to the output was really, really difficult as the output was completely uncommented and frankly made little sense. I kept running into bugs in the regular expression compilation, and so that was that.
After Alex's email, I started thinking about what it would take to write a lexer generator. Basically, a lexer generator requires parsing and compiling regular expressions, then scanning the source one character at a time to find matches. A lexer must also define precedence of the regular expressions so that the proper token is matched at the proper time. In addition, any lexer worth its salt has some support for different scanning states. For instance, different tokens are returned in the middle of a double-quoted string than are returned in global PHP code.
So, it occurred to me that perhaps simply combining regular expressions with sub-patterns could accomplish this task quite easily.
So, if you want to scan for the word "foo" followed by any grouping of letters, you could use this regular expression (Perl-compatible regular expression format):
/^(foo)|^([a-zA-Z]+)/
When used with preg_match() and specifying the optional third argument, it is possible to determine which token matched first simply by checking which is the 2nd array index. If this sounds like Greek to you, just check out the source of a generated lexer (more on that later).
Once this concept was discovered, the only task left was to decide on a format for the lexer. I've been a huge fan of re2c, partially because it makes it easy to write the patterns, and partially because the abstract lexer file itself still parses as valid C, simply because all lexer stuff is neatly contained within comments. Also, it's fast because of the way the code is generated. Implementing re2c directly in PHP is impossible simply because goto is not (yet) supported in existing PHP versions.
However, the benefit of having goto implemented in PHP would not make a faster lexer than directly using the preg functions. Why? Each opcode eats up lots more instruction cycles than the natively compiled preg matching. In other words, why re-invent the wheel when it will just be slower and bigger?
Once this decision was made, I was surprised to discover that a hand-written lexer for the new "lex2php" format was really easy to write, and did that in 1 day. Using the handy-dandy parser generator, I wrote a parser for the lexer generator that outputs the lexer (1 more day, truly demonstrating its ease of use and power). Finally, I ported the lexer for File_ChessPGN to the new format (1/2 day).
At this point, I thought it might be good to do a bit of benchmarking against the only generated lexer I had, the one for File_ChessPGN generated by csLex. Much to my delight and tremendous surprise, the newer lexer is consistently ~2.2 times faster lexing the same complex PGN file when profiled by Zend Studio (approximately 130 ms vs 285 ms).
So, today, I packaged up the PHP port of the Lemon Parser Generator as "PHP_ParserGenerator" and the lex2php lexer as "PHP_LexerGenerator" and have proposed them as additions to PEAR. Give them a whirl!
The PHP_LexerGenerator really needs a regular expression validator to catch things before it is too late, so I am working a few possibilities for that one. I'll probably end up writing a regular expression parser using PHP_Lexer/ParserGenerator, we'll see 
.
P.S. if you would like to get in on the action of developing these exciting packages, don't hesitate to drop a line. I'm pretty easy to work with!
One idea that struck me from reading this, was that it may be possible to generate PHP from flex - If you remember that php extension I showed you htmltokenizer, that used flex to generate a C file, then stripped it into it's component parts using a few simple perl routines. then put it back together so that it worked within another file.
Theory, is that Lex just overlays the data structures with a template -> changing the template, and slightly modifying the data structs might work...
Mind you hand written lexer's apparently (from what I've heard) tend to be faster anyway, especially if the grammer is simple
It also uses the approach with subpatterns - code
here
Don't know whether you'd consider adding something like that but what's a little different about this lexer is it comes with a stack machine. Marcus described it a little once here
That approach means much more state is handled by the lexer. For the purposes of doing something like a BBCode or wiki parser, which outputs HTML, to an extent the parser may be able to be "state free" - it simply responds to tokens by spitting out the corresponding HTML.
It seems that ANTLR v3 uses a stack in it's lexer and argues the value of that approach;
You can recognize complicated tokens such as HTML tags or "executable"
comments like the javadoc @-tags inside /** ... */ comments. The lexer
has a stack, unlike a DFA, so you can match nested structures such as
nested comments.
... but it's difficult to find decent discussion of the merits of this
approach. The most I've ever found is
here & here - "Deterministic Pushdown Finite Automata (DPDFA's)"
Somehow would need a different input format, to allow a hierarchy of patterns / states. Also when you have one pattern which is able to nest under many other patterns, needs some kind of short cut syntax (e.g. BBCode the {i}italic{/i} syntax might nest within {b/}, {url/}
and many others and ideally you'd only want to describe that once).
Anyway - waffling now.
One practical thought - in general for doing parsers, lexers in pure PHP, my feeling is the fewer function / method calls you have, the faster it's going to be based on Dokuwiki / XML_HTMLSax experiences - in general the most expensive part was executing callbacks etc. When you've got one callback per token, that's expensive.
This is also illustrated by the SAX extension vs. the XMLReader extension - with the latter, most of the function calls are happening within the extension - the calling PHP code could just be a procedural loop - basically the OPCODE argument you mentioned.
Haven't perfected the approach yet but seems the alternative is to have lexers / parsers which emit arrays of arrays, rather than executing callbacks. A naive implementation trades reduces the cost of executing user functions at the price of increased memory use (to store long arrays of tokens). The best next guess I have is delivering tokens in batches - e.g. 100 at a time...
while ( $tokens = $lexer->getNext(100) ) {<br />
switch($tokens['name']) {<br />
<br />
// Once case for each token - would be nice to have goto...<br />
<br />
}<br />
}<br />
Anyway - great stuff you've done here - got me provaricating
is the php4 equivalent of your lexer/parser generator still available?
looks great!
thanks
conrad
http://blog.oncode.info/2007/10/25/eine-eigene-programmiersprache-erschaffen-lexer-und-parser-in-php/
I hope that PHP_ParserGenerator will soon include a meaningful example...
Anyway, great work!
$this->token = Parser::TOK_CONST;
is just what I needed.
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 | ||||
