# Can any PEG grammar be parsed in linear time?

On the Wikipedia for PEG it is claimed:

Any PEG can be parsed in linear time by using a packrat parser, as described above.

However, packrat parsers can't handle left recursion.

You can eliminate any left recursion to create another grammar that recognizes the same language as the left-recursive one, however, those grammars are not equivalent because they do not result in the same derivation (e.g. a left-associative expr -> expr '+' expr becomes right-associative after left recursion elimination).

After doing some research I found a resource that can parse (indirect) left-recursive PEG, but it's not linear time.

So, is the claim on Wikipedia incorrect, or is there a linear time algorithm that can parse any PEG?

• The same article claims that "PEGs cannot express left-recursive rules", so it is at least consistent. – Peter Taylor Sep 16 '15 at 20:54
• @PeterTaylor: It's not just wikipedia. Bryan Ford's original thesis says (p. 25) "In TDPL, while right recursion works in much the same way as it does in a CFG, a left-recursive definition is considered erroneous, because its interpretation under TDPL rules leads to a degenerate self-reference." (TDPL is top-down parsing language, aka PEGs). – rici Sep 17 '15 at 0:03
• The claim was indeed incorrect - I have rewritten the paragraph in question. Ford's article explicitly distinguishes PEGs without left recursion (calling them well-formed PEGs) and his master's thesis suggests that well-formed PEGs cannot recognize all languages that arbitrary PEGs can recognize, but doesn't do into the matter in great detail. The Wikipedia article claims that all left recursion can be eliminated, but even if this is true, it may not be a linear-size expansion. – reinierpost Sep 17 '15 at 8:49
• @reinierpost The expansion size does not matter for the linear time requirement, because the runtime is measured in terms of the input string, not the size of the grammar. The main problem with eliminating left recursion is that the derivation tree is not the same before eliminating left recursion. – orlp Sep 17 '15 at 10:29
• Hmm ... good point. – reinierpost Sep 17 '15 at 10:46