PEGs: Parsing Expression Grammars

I read this paper not long ago as it was referenced in Ward Cunningham's interesting work in Exploratory Parsing [0]. It's a quick read and definitely interesting. If you're interested there's a yacc equivalent peg/leg [1]. The only thing that wasn't clear to me (and I'd appreciate enlightenment if anyone has any) is why Cunningham's Exploratory Parsing depends so much on PEGs? Is it simply the non-ambiguous nature of the parse tree?<p>0. <a href="http://c2.com/~ward/sao/TechIgnite-v1/" rel="nofollow">http://c2.com/~ward/sao/TechIgnite-v1/</a> 1. <a href="http://piumarta.com/software/peg/" rel="nofollow">http://piumarta.com/software/peg/</a>

I have to mention OMeta, a language based on PEGs (plus a few extensions): <a href="http://www.tinlizzie.org/ometa/" rel="nofollow">http://www.tinlizzie.org/ometa/</a><p>It's dead simple, and quite powerful: it helps implement all compilation phases, from parsing to code generation. And it compiles itself in about 400 lines of code.

It should be mentioned that this paper is from 2004, and that in the meantime there's even a Wikipedia article about PEG: <a href="http://en.wikipedia.org/wiki/Parsing_expression_grammar" rel="nofollow">http://en.wikipedia.org/wiki/Parsing_expression_grammar</a>

PEG.js has an online grammar creator:<p><a href="http://pegjs.majda.cz/online" rel="nofollow">http://pegjs.majda.cz/online</a>

There are some great PEG parsers in Ruby:<p>* Parslet: <a href="http://kschiess.github.com/parslet/" rel="nofollow">http://kschiess.github.com/parslet/</a><p>* Treetop: <a href="http://kschiess.github.com/parslet/" rel="nofollow">http://kschiess.github.com/parslet/</a>