Lot 49: Greg Beaver's blog

Just a few moments ago, I uploaded a new release of the docblock lexer extension for PECL at http://pecl.php.net/docblock. This release fixes two edge case bugs that I discovered while writing a docblock parser using the docblock extension. Otherwise, it's the same as the initial release.

the docblock extension takes a T_DOC_COMMENT like so:

and scans it for tokens. This is useful in several ways, not the least of which will be found in the 1.4.x series of phpDocumentor, a true docblock parser with support for some of the more unusual stuff like:

Enjoy!

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!

PHP_LexerGenerator proposal

PHP_ParserGenerator proposal

[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:

1. phpDocumentor. We use parsers for *everything*
2. PHP_Parser. The name says it all
3. 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:

1. %include_class - this works like %include, but puts stuff inside the generated parser class.
2. %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:

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.