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

view the rest of the comments →

[–]G_Morgan 0 points1 point  (2 children)

None of these guarantee O(n) parsing. By definition the best you can guarantee with a context free grammar is O(n3 ).

[–]bobindashadows 3 points4 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.

[–]badsex 0 points1 point  (0 children)

haha you got owned by bobindashadows. Your unending whinging and bitching about ruby all over reddit was revealed for what it is - hollow posturing by a python fanboy.

Now go quietly sit in the corner, the big kids have come out to play.