Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question
3  
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
add comment

3 Answers

up vote 5 down vote accepted

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.

share|improve this answer
    
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
add comment

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) = \{a,b\}$ while $\operatorname{FOLLOW}(B) = \emptyset$.

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

share|improve this answer
    
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
add comment

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).

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.