Re:Learning to write a compiler
by silentbicycle on Sunday August 29, 2010 @11:16AM
(#1643908)
Ierusalimschy's LPEG (a PEG parser for Lua[1]) also has some new developments. IIRC, he found a way to greatly improve the space performance of PEGs. I've used it a lot (it's a nice middle ground between REs and a full parsing framework, and Lua is one of my favorite languages), but I'm not familiar enough with Ford's PEG implementation to be more specific.
Also, here's a good blog post[2] in which the author discovered how using parsing tools to syntax-highlight text as it's being modified quickly led him to the frontiers of parsing research.
[1]: http://www.inf.puc-rio.br/~roberto/lpeg/lpeg.html
[2]: http://www.codekana.com/blog/2009/04/02/on-the-speed-of-ligh...
I certainly don't begrudge you using the existing tools, but speaking as someone writing a "baby yacc", I don't think parsing is quite the solved problem you make it out to be.
Yes there is TONS of literature on the subject, but new techniques and algorithms are being discovered all the time. ANTLR's LL(*) parsing hasn't been published yet (though I believe he's working on it) and only three years ago Frost, Hafiz and Callaghan published an algorithm for generalized top-down parsing in polynomial time. There's also the idea of PEG, published by Bryan Ford in 2004, a guy at UPenn who is carving out a set of languages between regular and push-down languages (http://www.cis.upenn.edu/~alur/nw.html).
All of this is to say; we're still discovering things about parsing. It's not a settled subject.