GATE CSE 2003 | Question: 57

Question

Consider the grammar shown below. 

• $S \rightarrow C \ C$
• $C \rightarrow c \ C \mid d$

This grammar is

• A. LL(1)
• B. SLR(1) but not LL(1)
• C. LALR(1) but not SLR(1)
• D. LR(I) but not LALR(1)

Comments

If a grammar is LL(1), then it is also usually LR(1), SLR(1), and LALR(1) —
but not necessarily LR(0).

LR(0)⊂SLR(1)⊂LALR(1)⊂LR(1)

---

If a grammar is LL(1), then it is also LR(1), SLR(1), and LALR(1) 

@jeets That is incorrect. If grammar is LL(1) then it will be LR(1). We cannot comment on LR(0), SLR(1) or LALR(1) 

 

---

@yoda https://chatgpt.com/s/t_690ea612b77081919770c3e85b1c157d

---

@jeets @yoda jeet, Yoda is correct

 

if only language is ll(0) then it is LR(0), SLR(1), LALR(1), and so on. 

Answer 1

ans is A

$First(S)=First(C)=\{c,d\}$

There are no multiple entries in single row of parsing table hence grammar is LL1

Note : If we have $A \rightarrow B\mid C,$ for grammar to be LL(1) first(B) intersection First(C) should be null otherwise grammar is not LL1. If First(B) contains $\epsilon$ then Follow(A) intersection First(C) should be null. Using this we can say grammar is LL(1) or not without constructing parsing table.

An $\epsilon$ free LL(1) grammar is also SLR(1) and hence LALR(1) and LR(1) too.

Comments

Can we say say like this?

1. If say we are able to develop a DFA for given grammar then it’s for sure that it’s LL(k).
2. If say we are able to develop a DPDA for given grammar then it’s for sure that it’s LR(k).

---

What about LR(0) grammar ?

---

@pranavbhosle_

Yes it is LR(0)

Answer 2

Answer is A 

Comments

Hi @Sachin Mittal 1, is this statement really true "every DCFL has an LR(1), an LALR(1) and even an SLR(1) grammar". Check this wiki link out https://en.wikipedia.org/wiki/LALR_parser, it says here "It was also proven that there exist LR(1) languages that are not LALR". 

---

how from S you derived d in LL(1) table S->CC and C is not containing epsilon

Answer 3

Ambiguous?

I think nope.

 

Left Recursive?

No.

 

Non-deterministic?

No.

 

For any $A\rightarrow \alpha \beta$ do the Firsts of $\alpha$ and  $\beta$ clash?

No.

 

So, this is LL(1).

 

Does it have $\epsilon$?

No.

Hence, this is SLR(1) and everything above it.

 

Option A