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.
Post a Comment