Comment by sb | Hacker News Reader

Comment by sb | Hacker News Reader

Parent Full thread

I am not so sure about the actual state-of-the-art (I have read some PEG papers and some OMeta stuff from vpri, plus used ANTLR, Bison, and Coco/R), but a very interesting comment on HN (http://news.ycombinator.com/item?id=1643715) points out that most production compilers use hand-written recursive-descent parsers, primarily due to practical reasons.

I have taken two compiler construction courses during my college years, one with LL(1) grammar using a recursive descent parser, the other one with LR(1) grammar using flex+bison tool-chain. I found the experience from the LL case helped me tremendously in the course of writing the LR-language compiler. I think that recursive-descent experience also helps understanding attribute grammars, too. Probably the best introduction to recursive-descent parsers is from Niklaus Wirth's compiler construction book (http://www-old.oberon.ethz.ch/WirthPubl/CBEAll.pdf).

What are the practical reasons? Dealing with non-uniform edge cases and other strange constraints? Integrating the stuff the compiler needs to do with the parser-generator?

I can imagine one practical reason is that a lot of stuff (e.g. type information, variable bindings) goes top-down, but bottom-up parsers reduce rules in the opposite direction and so it takes extra effort to make the mental model of programming fit with the reduction strategy of bottom-up parsers.

The comment I referenced mentions that the context available in recursive-descent parsers can be used for error recovery, e.g., phrase-level recovery. The excellent "Programming Language Pragmatics" by Michael Scott has a good chapter on this, so does "Modern Compiler Design" by Grune, Bal, Jacobs and Langendoen.

Vladimir Safonov's Trustworthy Compilers is another good reference on this subject, in addition to the books already mentioned here on HN. Safonov works through some examples of real-world languages, and argues why hand-written parsers are superior to Yacc-style parser generators. He gives examples of ALGOL-68 and FORTRAN.

I don't know of any definitive text that covers a wide range of practical examples that I've been totally satisfied with, though. Even Safonov waives his hand a little, saying the parser is the one part of the compiler to be written by the most experienced and best compiler engineer on the team, because it influences the performance of everything after.

Reply on news.ycombinator.com