|
|
|
|
|
|
by earleybird
498 days 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. :-) |
|
|