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?