The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+23 votes

Consider the grammar shown below. 

$S \rightarrow C \ C$

$C \rightarrow c \ C \ | \ 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 (59.6k points)
edited by | 3.9k views

2 Answers

+33 votes
Best answer

ans is A


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

note : if we have $A \rightarrow B/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 (31.7k points)
edited by
@Sachin Mittal 1

I have a small doubt ::

Statement 1 : For every DCFL there exits a LR(0) or a LR(1) grammer.

Statement 2 : For every DCFL there exits a  LR(1) grammer.

Which is true??

According to me first one.But the discussion and other links, points that second one is true.

I am confused a bit.Can you provide some reference on this.

@Arjun sir:-

IS the following statement true?

 If a grammar is LL(1) and not containing ϵϵ, then it is SLR(1) and so LALR(1) and LR(1). 

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

Is this true Arjun sir?

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]

So what is the confusing part ?

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

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

Answer is A 

answered by (413 points)

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

40,880 questions
47,536 answers
62,300 users