The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+25 votes
5k views

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)
asked in Compiler Design by Veteran (52.1k points)
edited by | 5k views

2 Answers

+39 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.

answered by Boss (30.9k points)
edited by
0

wikki says-

 A ε-free LL(1) grammar is also a SLR(1) grammar. A LL(1) grammar with symbols that have both empty and non-empty derivations is also a LALR(1) grammar. A LL(1) grammar with symbols that have only the empty derivation may or may not be LALR(1).[5]

0
So what is the confusing part ?
+2

yes every LL(1) grammar in not LALR(1).

0
Still what is wrong with the given statement?
0
Can we say a grammar is also SLR(k),LALR(K),LR(k) if it is a epsilon free LL(k) grammar?
0

According to wiki - https://en.wikipedia.org/wiki/LL_grammar
A LL(1) grammar with symbols that have both empty and non-empty derivations is also a LALR(1) grammar. 

is it true? 

0

@Arjun sir @Pooja Palod mam.. please validate these statement

"A LL(1) grammar with symbols that have both empty and non-empty derivations is also a LALR(1) grammar."

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

0

@Arjun sir please explain these above two concepts

0
for a grammar to be LL1 it should be not have left recursion ,is there no left recursion here?
0

@Arjun LR(k) generate the same language as LR(k+1) for k > 0

But the above Venn diagram doesn't support this,right? LR(1) is shown as a subset of LR(k).

+2 votes

Answer is A 

answered by Junior (627 points)
Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,808 questions
54,475 answers
188,226 comments
74,360 users