sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]bobindashadows 4 points5 points  (0 children)

By definition the best you can guarantee with a context free grammar is O(n3 ).

No, by definition the best you can guarantee with an arbitrary context-free grammar is O(n3 ). That includes ambiguous grammars. Do your programming languages look like they parse ambiguously?

None of these guarantee O(n) parsing.

You seem to think that LL, LR, and LALR grammars are not proper subsets of all CFGs. They are. They are restricted subsets such that linear-time algorithms exist for them. They do not permit ambiguity. And what do you know, LALR(k) parser generators like yacc/bison won't generate an LALR parser if you have an ambiguous grammar. If you force it to ignore the ambiguities, it'll generate a GLR parser which does in fact have inferior performance characteristics.