Use an Earley parser. A properly implemented Earley parser will do unambiguous grammars with left/right/mutual recursion in linear time. The worst case ambiguous I've worked with is UBDA (Earley, 1970). UBDA produces the equivalent of all the permutations of a binary tree - which is Catalan(n). If you generate all the combinations as you parse it won't complete before the heat death of the universe for fairly short strings.
> A properly implemented Earley parser will do unambiguous grammars with left/right/mutual recursion in linear time.
It's not linear for all unambiguous grammars- only deterministic grammars, which can also be parsed with something faster like LR or even hand-written Pratt.
(An example of an unambiguous but nondeterministic grammar is this one for palindromes, which Earley parses in quadratic time: P -> 0 P 0 | 1 P 1 | ε)
Yes, you are correct. Nondeterministic grammars are not linear but quadratic. In the case of your palindrome example (thanks btw, added to my grimoire of grammars) I believe the quadratic is: (3n^2 + 6n)/4 (I wish HN did MathJax)
I need to do a bit more digging in to the distinction between ambiguous and nondeterministic.
When implementing parsers I enjoy the directness afforded by an Earley parser. No rejigging the grammar to suit LL, LR etc. No gotcha's with PEGs choice operator, etc.
Most grammars I end up using for practical applications are linear - so far, quadratic has been a spectre from afar. :-)
That's true as Pratt described it. I mentioned it because it's a good example of the general idea of extending recursive descent to handle more deterministic grammars than vanilla LL.
I came into comments to post this but I guess the earley bird gets the worm.
I have an Earley parser I’m very happy with which is in a project I’m going to open source soon, it’s nice to have a parser where you just don’t have to think about all those edge cases
