[earleybird]

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.

[Rusky]

> 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 | ε)

[earleybird]

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. :-)

[nsajko]

Pratt's method only targets the operator precedence languages, not the DCFL. So much less powerful than LR parsing.

[Rusky]

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.

[klik99]

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

[upghost]

Thanks, I've been looking for this for a long time!

[froh]

tell me more about your use name :-)