19

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

Community
  • 1
  • 1
K J
  • 4,505
  • 6
  • 27
  • 45

2 Answers2

17

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.

Puppy
  • 144,682
  • 38
  • 256
  • 465
14

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.

Austin Henley
  • 4,625
  • 13
  • 45
  • 80
  • 1
    If somebody hands you the parser generator, by definition what it does is "easy to implement". In that case, you choose the parser generator which easily handles the largest class of languages, to minimize your efforts. From the perspective, IMHO, LR wins over LL pretty handily. GLR wins over LR pretty handily. – Ira Baxter Aug 29 '12 at 04:52
  • I agree, but nonetheless LL are still easy to implement. I was pointing out that LR usually requires using a tool. I find it very intriguing that you can hand write recursive descent and the code and grammar go hand-in-hand. – Austin Henley Aug 29 '12 at 04:56
  • 5
    Yes, its intriguing and people building parsers should know about them. As your grammars get big, it is inconvenient to force it into LL shape, and at some (pretty small) point convenience of LR wins over the conceptual simplicity in your head. LR is pretty easy to understand if you aren't building the parser generator, and it isn't like there aren't a lot of them around. – Ira Baxter Aug 29 '12 at 04:58
  • You are right, of course. Considering you are the resident compiler expert :) – Austin Henley Aug 29 '12 at 05:00
  • Thanks for the answer, Ira and Austin. I agree to Ira's opinion and I prefer LR to LL, but Austin's point on inherited attributes and actions was also helpful. :) – K J Aug 29 '12 at 07:17
  • As of version 4 ANTLR can deal with direct left recursion. – Weltraumschaf Jan 23 '17 at 21:20