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

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

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

how is LR checking done?

---

if it is LL(1), it is LR(1) -easy.

Otherwise, we have to do LR table.

---

@arjun sir nice one.

---

@Gate Keeda intersection of First() is Phi but we also check intersection of first(S) and Follow(S)  here a is intersection result.

---

take First(S). and do intersection between the result, what does it mean for intersection with the result?

First(S) = {a,b,c} now what to take intersection with?

---

 @iarnav Taking first will ensure that in parsing table there is not conflict seeing any terminal in the production thus under $ you can accept the string while parsing while getting any terminal {a,b,c} reduce it appropriately with the respective production.

---

those first(S)=a,b,c places its respective prod rule to its column

i.e a will have entry aSa, b will have entry bS and c has entry c, a intersection b intersection  c has phi, so it's LL

Suppose, if we have episilon prod instead of 'c', for epsilon, we add follow of S, i.e a will come to picture and make it not LL(1).

---

First(aSa) = a
First(bS) = b
First(c) = c
All are mutually disjoint i.e no common terminal 
between them, the given grammar is LL(1).

---

@Arjun sir if grammar is LR(0) we can say it is slr, clr n all coz reduce entries will be less than LR(0). But LL(1) is top down parser and the parsing algorithm also differ, then how can we say if it is LL1 then it is LR1

---

How to check LR(1)?

------->  CLR(1) is also called as LR(1)?

-------> Every Grammar which is LL(1), then it is definitely  LALR(1)?

---

every LL(1) is also LALR (1) grammar and hence LR(1). CLR(1) grammar is also called LR(1).

LALR (1) is subset of CLR(1).

---

@Arjun Sir how LR(1) table is drawn

---

@ anchitjindal07 , here no need to check for LR(1). why because it's LL(1) so obviously LR(1).

---

@Raju Kalagoni, I know here in this example it is not needed, but if some language is not LL(1), then we have to check for LR(1)

---

@ anchitjindal07 , there is a procedure for finding LR(1) items and then we need to check for conflicting operations like Reduce - Reduce / Shift - Reduce conflict. please check below link..

https://www.tutorialspoint.com/compiler_design/calculations_of_set_of_lr1_items.asp

https://stackoverflow.com/questions/14103199/lr1-item-dfa-computing-lookaheads

---

i think every LALR is CLR but  every CLR is not LALR so every LL(1) is LR(1) but not LALR

---

It is not always true

---

Can anyone explain if it is LL(1) then how it is LR(1)?

---

That is proved in any Compiler text. Any LL(x) grammar is also LR(x).

---

i.e every LL(1) is also LR(0) ?

---

Yes,

LL grammars are strict subset of LR grammar.

---

Go through this link once & observe the given figure also.

https://en.wikipedia.org/wiki/LL_grammar#Relation_to_other_grammar_classes

---

@amarsharma  bro that's not true.

---

@Raju Kalagoni

every LL(1) is also LALR (1) grammar and hence LR(1)

I think this statement is incorrect. 

Reference: https://stackoverflow.com/questions/6487588/example-for-ll1-grammar-which-is-not-lalr/6492798#6492798

---

You are right, @Shiva Sagar Rao, LL(1) grammar may not be subset of LALR(1).

stackoverflow.com/questions/49493005/is-every-ll1-grammar-also-a-lalr1-grammar

---

According to first and follow rules , we only find first and follow of non terminals . Here, non terminal is only S, so why we are including a and b while finding first and follow of S ?

Can somebody explain.

---

LL(1) , LR(0) , SLR(1) , LALR(1) all are proper subject of CLR(1)

---

@Abhrajyoti00  Check this.

 the line from the best answer.

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

This is an incorrect statement. This is not enough to say whether the given grammar is LL(1) or not. I think ans need some correction. 

---

@raja11sep Can you give a counter example?

---

@gatecse 

S→ aSa | $\epsilon$

---

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