4 ms·

Use an Earley parser. A properly implemented Earley parser will do unambiguous grammars with left/right/mutual recursion in linear time. The worst case ambigu

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.

upghost 2y ago
Thanks, I've been looking for this for a long time!
Rusky 2y ago
> 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 | ε)
- nsajko 2y ago
  Pratt's method only targets the operator precedence languages, not the DCFL. So much less powerful than LR parsing.
  - Rusky 2y ago
    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.
- earleybird 2y ago
  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. :-)
froh 2y ago
tell me more about your use name :-)
klik99 2y ago
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 2y ago

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

Rusky 2y ago

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

nsajko 2y ago
Pratt's method only targets the operator precedence languages, not the DCFL. So much less powerful than LR parsing.
- Rusky 2y ago
  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.
earleybird 2y ago
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. :-)

froh 2y ago

tell me more about your use name :-)

klik99 2y ago

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