in Compiler Design edited by
19,821 views
40 votes
40 votes

Consider the grammar shown below. 

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

This grammar is

  1. LL(1)
  2. SLR(1) but not LL(1)
  3. LALR(1) but not SLR(1)
  4. LR(I) but not LALR(1)
in Compiler Design edited by
19.8k views

3 Answers

79 votes
79 votes
Best answer

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.

edited by

4 Comments

check out the here for the explanation of

“An ϵ free LL(1) grammar is also SLR(1) and hence LALR(1) and LR(1) too”.

https://gateoverflow.in/144246/ll-1-and-lalr-1

And please correct me if anything is wrong there.

1
1
@Arjun sir, every LL(1) grammar is LR(1) as LR(1) is proper superset of LL(1)
0
0

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).
0
0
4 votes
4 votes

Answer is A 

by

2 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". 

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

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

Answer:

Related questions