Search code examples
parsingantlryacclalrll-grammar

LALR vs LL parser

I've been using lex/yacc and now I'm trying to switch to ANTLR. The major concern is that ANTLR is an LL(*) parser unlike yacc which is LALR. I'm used to thinking bottom-up and I don't exactly know what the advantage of LL grammars is. People say that LL grammars are easier to understand and more popular these days. But it seems that LR parsers are more powerful e.g. LL parsers are incapable of dealing with left-recursions, although there seems to be some workarounds.

So the question is what is the advantage of LL grammars over LALR? I'd appreciate it if somebody could give me some examples. Links to useful articles would be great, too.

Thanks for your help in advance!

(I see this is a great resource: What advantages do LL parsers have over LR parsers?, but it would've been better with some examples.)

Solution

  • The greatest advantage I see to LL parsers is that they are so easy to understand and implement! You can hand write recursive descent parsers with code that closely matches the grammar.

    LR are generally considered more powerful and also much faster BUT there are a few trade offs that I know:

    • LR parsers can only use synthesized attributes; they can not pass inherited attributes.
    • Actions in an LR grammar can cause grammar nondeterminism but not in LL.

    However, you will find that LL(*) are also very powerful.