2 ms·
That'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
by vidarh 7y ago
That'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.