Hacker News Reader

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

View on HN

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

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

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.

Reply on news.ycombinator.com