2 ms·
I used to use PEGs because they possibly compose better than other grammars - it may be the case that you can combine two PEGs and get a PEG that still makes se
by chrisseaton 7y ago
I used to use PEGs because they possibly compose better than other grammars - it may be the case that you can combine two PEGs and get a PEG that still makes sense. I'm not sure if this is a property of other approaches to parsing.
- vidarh 7y agoThat's true,but the point is PEGs translate directly to recursive descent in a very straight forward way, and it is only when you do that blindly with grammars that are structured in quite pathological ways that packrat parsing buys you much. Basically any recursive descent created from a PEG with deep lookahead can usually have the lookahead reduced by recognising any shared prefix to any set of choices first, and then the remainder of the choices. Most of the remaining interesting cases are usually solved by trivial restructuring of the parse tree afterwards. That may not always be enough, but it is enough for most real use-cases. Packrat parsing is appealing because it saves people from thinking about how to structure a PEG in a way that minimize the worst case lookahead, but the effort needed to reduce the lookahead is rarely particularly hard, and most real-life examples I've seen where composing parsers is useful have tended to diverge quickly enough to require very little lookahead.