# 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?

• I am not very fammiliar with grammars, but it seems that language of this grammar is finite. $L=\{ab,ba\}$ – Nejc Nov 19 '12 at 14:44
• @Nejc: Yes it does seems like that! – Vinayak Garg Nov 19 '12 at 14:45

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.

• Thanks! I had constructed the First & Follow correctly, but I made a mistake in constructing the table. – Vinayak Garg Nov 20 '12 at 5:44

If you are not asked, you don't have to construct the LL(1) table to prove that it is an LL(1) grammar. You just compute the FIRST/FOLLOW sets as Alex did:

\qquad \begin{align} \operatorname{FIRST}(S)&={a,b} \\ \operatorname{FIRST}(A)&={ε} \\ \operatorname{FIRST}(B)&={ε} \\ \operatorname{FOLLOW}(A)&={a,b} \\ \operatorname{FOLLOW}(B)&={a,b} \end{align}

And then, by definition an LL(1) grammar has to:

1. If $A \Rightarrow a$ and $A \Rightarrow b$ are two different rules of the grammar, then it should be that $\operatorname{FIRST}(a) \cap \operatorname{FIRST}(b) = \emptyset$. Hence, the two sets haven't any common element.
2. If for any non-terminal symbol $A$ you have $Α \Rightarrow^* ε$, then it should be that $\operatorname{FIRST}(A) \cap \operatorname{FOLLOW}(A) = \emptyset$. Hence, if there is a zero production for a non-terminal symbol, then the FIRST and FOLLOW sets can't have any common element.

So, for the given grammar:

1. We have $\operatorname{FIRST}(AaAb) \cap \operatorname{FIRST}(BbBa) = \emptyset$ since $\operatorname{FIRST}(AaAb) = \{a\}$ while $\operatorname{FIRST}(BbBa) = \{b\}$ and they don't have any common elements.
2. $\operatorname{FIRST}(A) \cap \operatorname{FOLLOW}A) = \emptyset$ since $\operatorname{FIRST}(A) = \{a,b\}$ while $\operatorname{FOLLOW}(A) = \emptyset$, and now $\operatorname{FIRST}(B) \cap \operatorname{FOLLOW}(B) = \emptyset$ since $\operatorname{FIRST}(B) = \{ε\}$ while $\operatorname{FOLLOW}(B) = \{a,b\}$.

As for the SLR(1) analysis I think it is flawless!

• Welcome! In order to improve this answer, why don't you apply what you state to the grammar at hand? – Raphael Dec 3 '12 at 21:19
• Happy to be here!! Answered your request and I think I gave a thorough explanation! – Ethan Dec 3 '12 at 22:04
• Thanks! Note that we can use LaTeX here, as I did edit in for your maths. – Raphael Dec 3 '12 at 22:23
• Wow Thanks! this is a great explanation. But I think there is some mistake in the application. Isn't First(A) = {epsilon}? I think you swapped the FIRST and FOLLOW. – Vinayak Garg Dec 4 '12 at 5:59
• FIRST(A) is indeed epsilon but since you are looking to calculate the whole right member's FIRST set, A -> ε just shows that we have an empty production and the first terminal symbol you see (and therefore the FIRST set of it) is terminal symbol a. Hope this helped! – Ethan Dec 5 '12 at 10:33

Search for a sufficient condition which makes a grammar LL(1) (hint: look at the FIRST sets).

Search for a needed condition which all SLR(1) grammars must meet (hint: look at the FOLLOW sets).