LALR vs LL parser

Question

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

Answer 1

LR parsers are strictly more powerful than LL parsers, and in addition, LALR parsers can run in O(n) like LL parsers. So you won't find any functional advantages of LL over LR.

Thus, the only advantage of LL is that LR state machines are quite a bit more complex and difficult to understand, and LR parsers themselves are not especially intuitive. On the other hand, LL parser code which is automatically generated can be very easy to understand and debug.

Answer 2

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.