How is this grammar LL(1)?

ignougroup
Question Detail: This is a question from the Dragon Book. This is the grammar:

$S to AaAb mid BbBa $
$A to varepsilon$
$B to varepsilon$

The question asks how to show that it is LL(1) but not SLR(1). To prove that it is LL(1), I tried constructing its parsing table, but I am getting multiple productions in a cell, which is contradiction. Please tell how is this LL(1), and how to prove it?

Asked By : Vinayak Garg
Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/6768

Answered By : Alex ten Brink

First, let’s give your productions a number.

1 $S to AaAb$
2 $S to BbBa$
3 $A to varepsilon$
4 $B to varepsilon$

Let’s compute the first and follow sets first. For small examples such as these, using intuition about these sets is enough. $$mathsf{FIRST}(S) = {a, b}\ mathsf{FIRST}(A) = {}\ mathsf{FIRST}(B) = {}\ mathsf{FOLLOW}(A) = {a, b}\ mathsf{FOLLOW}(B) = {a, b}$$ Now let’s compute the $LL(1)$ table. By definition, if we don’t get conflicts, the grammar is $LL(1)$. 

    a | b | ----------- S | 1 | 2 | A | 3 | 3 | B | 4 | 4 |

As there are no conflicts, the grammar is $LL(1)$. Now for the $SLR(1)$ table. First, the $LR(0)$ automaton. $$mbox{state 0}\ S to bullet AaAb\ S to bullet BbBa\ A to bullet\ B to bullet\ A implies 1\ B implies 5\ $$$$mbox{state 1}\ S to A bullet aAb\ a implies 2\ $$$$mbox{state 2}\ S to Aa bullet Ab\ A to bullet\ A implies 3\ $$$$mbox{state 3}\ S to AaA bullet b\ b implies 4\ $$$$mbox{state 4}\ S to AaAb bullet b\ $$$$mbox{state 5}\ S to B bullet bBa\ b implies 6\ $$$$mbox{state 6}\ S to Bb bullet Ba\ B to bullet\ B implies 7\ $$$$mbox{state 7}\ S to BbB bullet a \ a implies 8\ $$$$mbox{state 8}\ S to BbBa bullet \ $$ And then the $SLR(1)$ table (I assume $S$ can be followed by anything). 

    a     | b     | A | B | --------------------------- 0 | R3/R4 | R3/R4 | 1 | 5 | 1 | S2    |       |   |   | 2 | R3    | R3    | 3 |   | 3 |       | S4    |   |   | 4 | R1    | R1    |   |   | 5 |       | S4    |   |   | 6 | R4    | R4    |   | 7 | 7 | S8    |       |   |   | 8 | R2    | R2    |   |   |

There are conflicts in state 0, so the grammar is not $SLR(1)$. Note that if $LALR(1)$ was used instead, then both conflicts would be resolved correctly: in state 0 on lookahead $a$ $LALR(1)$ would take R3 and on lookahead $b$ it would take R4. This gives rise to the interesting question whether there is a grammar that is $LL(1)$ but not $LALR(1)$, which is the case but not easy to find an example of.