How is this grammar LL(1)?

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?

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.

StackExchange Computer Science Q#6768, answer score: 11