Hacker News Reader

Comment by earleybird | Hacker News Reader

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.

View on HN

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

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.

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

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

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

tell me more about your use name :-)

Reply on news.ycombinator.com