Re:Why I don't use a parser generator
by barrkel on Wednesday September 11, 2013 @01:53PM
(#6368713)
Recursive descent parsers are linear in the size of the input, but they're also linear in the nesting depth of the grammar, unlike e.g. PDAs or operator precedence parsers, which is why they're a poor choice for things like math expressions.
And performance is not just time, but also space.
There are niches for most parsing algorithms, but PEGs are a poor fit for most tasks except lightweight ad-hoc use, especially implementation languages for which tool support is poor.
Backtracking + memoization is but one implementation technique for PEG parsers. Another such technique is akin to dynamic programming -- fill in a table with possible parsing outcomes as you go. No "backtracking" (which really, is moot in a memoized PEG parser) required.
Either way, the performance is identical to that of a recursive descent parser (linear in the size of the input and number of nonterminals).