GATE CSE 2010 | Question: 38

Question

The grammar $ S \to aSa \mid bS \mid c$ is 

• A. LL(1) but not LR(1)
• B. LR(1) but not LL(1)
• C. Both LL(1) and LR(1)
• D. Neither LL(1) nor LR(1)

Comments

We will take First(S) and try to find if any transition of terminals may cause more than one entry –below is the pictorial.

As all the terminal transition while determining the First(S) is unique so it’s LL(1) and subsequently we can deduce it’s LR(0). 

---

Every LL(k) is LR(k). Hence every LL(1) is LR(1).

Source: https://suif.stanford.edu/dragonbook/lecture-notes/Stanford-CS143/12-Miscellaneous-Parsing.pdf

---

Every LL(1) is LR(1)

Answer 1

The $\textsf{LL(1)}$ parsing table for the given grammar is:

$\begin{array}{|c|c|c|} \hline
& a&b&c \\ \hline
S& S\to aSa & S\to b & S \to c \\ \hline
\end{array}$

For any given input symbol $a,b$ or $c,$ the parser has a unique move from the start and the only state – so no conflicts.

As there is no conflict in $\text{LL(1)}$ parsing table, the given grammar is $\textsf{LL(1)}$ and since every $\textsf{LL(1)}$ is also $\textsf{LR(1)},$ the given grammar is $\textsf{LL(1)}$ as well as $\textsf{LR(1)}.$

Comments

 

the given grammar is LL(1) and since every LL(1) is also LR(1)

 

Is this true ? Here they have said, "every  ϵ  free LL1 is LR1. Does epsilon matter or not ? 

---

i still have the same doubt. and i think every ll(1) grammar is not lr(1) grammar.

---

Every LL(1) is not LALR(1) , but every LL(1) is LR(1) 

---

Where did you get it? Because I am not finding any resources for this?

Answer 2

Correct Option: C

For LL(1) take First(S). and do intersection between the result. if intersection is Phi then LL(1) else not.

Making a parsing table and checking if there are two or more entries under any terminal. If yes then neither LL(1) nor LR(1).

Comments

What's the intersection here?

---

{a} intersection {€} =Phi. Still It's not LL(1).

---

@raja11sep Yes, the line is wrong.

The correct line should be:-

1. If prod are of the form $A → \alpha_1| \alpha_2|...| \alpha_n| $ then if first set of atleast any 2 productions (not first(A) )have common elements → Grammar is not LL(1).
2. If prod are of the form $A → \alpha| \epsilon$ then if $First (\alpha)$ ∩ $Follow(A) ≠ ∅$ → Not LL(1)

 Whenever we have $\epsilon$ we should take intersection of first of every prod except null with follow of that variable (here S).

So, in S$→ aSa | \epsilon$

$First(aSa) $∩$ Follow(S) = {a} $∩$ {a} = {a} → Not LL(1)$