3 ms·
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
by gchpaco 17y ago
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/ http://pyparsing.wikispaces.com/
- kragen 17y agoYou'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/15acbdd6f7108117fd0d2788f055cd4476ccfd95/peg.md 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.