# 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, 2012 at 14:44
• @Nejc: Yes it does seems like that! Nov 19, 2012 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. Nov 20, 2012 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, 2012 at 21:19
• Happy to be here!! Answered your request and I think I gave a thorough explanation! Dec 3, 2012 at 22:04
• Thanks! Note that we can use LaTeX here, as I did edit in for your maths.
– Raphael
Dec 3, 2012 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. Dec 4, 2012 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! Dec 5, 2012 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).