PEG is a really fascinating development in parsing--at the cost of some memory (sometimes a lot of memory), parse almost anything in linear time. The fact that it's different from a context free grammar is especially interesting; deterministic choice etc.

That said I'm not so hot on the sample script given here. Parsing is one of those situations where domain specific languages are a colossal win. Pyparsing is a little more verbose but seems to have an easier to understand syntax. http://pyparsing.wikispaces.com/

You're talking about packrat parsing of PEGs, not PEGs in general. I'm not yet sure that packrat parsing itself is a win, but I'm pretty sure PEGs are, just for expressiveness.

I did a simple PEG parser generator (66 lines, generates code in JavaScript, http://github.com/kragen/peg-bootstrap/blob/15acbdd6f7108117...) and since then I've been thinking about computing one-character follow-sets to speed up PEG parsing with predictive parsing.

What I think is really interesting is the OMeta work on things like program analysis and code generation using PEGs. I feel like there's a deeper connection between ML-style pattern-matching and PEG-parsing hiding somewhere in there, but I haven't been able to tase it out yet.

I notice that the grammar specified requires an else after every if. The wikipedia article also says that the dangling else problem doesn't exist because the grammar is never ambiguous, but doesn't say much more. So does this mean you can't use PEG to parse a language with an optional else? How would you specify it?

Edit: oh duh, now I see the part I just glanced over. The answer is that prioritization is implicit in a rule's productions.

That's pretty clever! The syntactic overhead of using Python for this is pretty minimal. It's not nonexistent, though, especially when you're concerned about readability as well as brevity.

what strikes me as particularly elegant here (pypeg) is the use of python code objects for defining the grammar: using functions and returns with code objects surely is one of the most elegant ways of expressing the desired grammar in the language itself...

EDIT: i did not advance to any comments before writing, kragen already posted a similar remark, mea culpa...