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

Which of the following statements is false?

  1. An unambiguous grammar has same leftmost and rightmost derivation
  2. An LL(1) parser is a top-down parser
  3. LALR is more powerful than SLR
  4. An ambiguous grammar can never be LR(k) for any k
asked in Compiler Design by Veteran (59.5k points)
edited by | 3k views

5 Answers

+31 votes
Best answer

(A) is the answer.

(A) We can not have different Left Most Derivation and Right Most Derivation parse trees BUT we can certainly have different LMD and RMD for a given string.(LMD and RMD here refers to the order of various productions used for derivation which could be different.)

(D) is wrong w.r.t. question because IT IS TRUE that any LR(k) IS NEVER AMBIGUOUS and so an ambiguous can never be an LR(K) for any k, no matter how large k becomes.

(B) and (C) can not be the answer because LL(1) is TOP-DOWN parser and LALR is powerful than SLR. So both are TRUE.

answered by Loyal (7.6k points)
edited by
0
i have a small confusion, with the line "we can not have different left most derivation and Right Most Derivation parse trees", that means:

if we have two left most derivations, our grammar is ambiguous

if we have two right most derivations, our grammar is ambiguous

if we have one left most and one (different) right most, our grammar may or may not be ambiguous.

also here I mean if I have a derivation, I have a parse tree corresponding to it.

Please clarify this.
+1

Plz clarify wrt to Unambiguous Grammar in Ans  

 we can certainly have different LMD and RMD for a given string.

I think above is wrong quoted bcoz if it is possible then it should be ambiguous grammar. 

plz correct me!!

+33
@Rajesh, we will ALWAYS have different LMD and RMD for given string, but that does not make it ambiguous. If we have two PARSE TREES for given string that makes it ambiguous.
Either we have 2 parse trees or
2 LMD    or
2 RMD.
In either of three cases, we say it is ambiguous.
We can always drive a string using 3 methods - Parse tree, LMD and RMD. But if either of this have 2 instances then it is ambigious.

(If a grammar is regular then its LMD and RMD will be same.)
0
Thanks for correcting me @Sachin..

Till now I know  Only  One point that is..If we have atleast 2 PARSE TREES for given string then only it is ambiguous.

Can u plz give some examples for below points .

1.different LMD and RMD for given string

2. 2 LMD or 2 RMD of same string.
0
@sachin, can you please tell what is the difference in deriving the string with LMD/RMD and parse tree. When we draw the parse tree, every new branch we take is equivalent to the production in LMD/RMD, so a parse tree must belong to a given derivation in LMD or in RMD.
Or do they have separate existence?
0
A parse tree is obtained by applying LMD and RMD.

Suppose,

1 parse tree we have obtained from LMD, and then 2nd parse tree we have obtained from RMD. In this case we say grammar is ambiguous right?

if Yes, since it does not have 2LMD, can we say unambiguous also?

Please correct me if iam wrong
0
this is a nice point thanks sachin sir
0

If a grammar is regular then its LMD and RMD will be same

Reason is, we will always have at most one non-terminal on the RHS of the production so there is no choice, which one to replace.

+14 votes

A) An unambiguous grammar has same leftmost and rightmost derivation

This statement is false, let me take an example, suppose given unambiguous gammer is

S -> AB
A -> a
B -> b

Suppose our input string is ab

Left Most Derivation
S -> AB -> aB -> ab

Right Most Derivation
S -> AB -> Ab -> ab

Notice Left Most derivation and Right most derivation are not same, still gammer is unambiguous.

Here is the Derivation Tree

So for a given gammer, we can have same Left most derivation Tree and Right most derivation tree, but left most derivation and right most derivation may vary.

B) An LL(1) parser is a top-down parser : True

C) LALR is more powerful than SLR  : True

D) An ambiguous grammar can never be LR(k) for any k : True

So only False option is (a).

answered by Loyal (7.5k points)
0
Both the derivations are same. Why are you saying both are different?
+9 votes
We know that the LL(1) parser is top down parser. Option B is true.
Order of strength is LR < SLR < LALR.
So (B) and (C) are, true.
But an ambiguous grammar can’t be LR(K) for any K so option D is true.
So option (A) is false since an unambiguous grammar has unique right most derivation & left most derivations but both are not same.
Hence (A) is correct option
answered by Veteran (68.5k points)
edited by
0
So (B) and (C) are true

please correct it
+2 votes

an ambiguous grammar is a context-free grammar for which there exists a string that can have more than one leftmost derivation or parse tree, while an unambiguous grammar is a context-free grammar for which every valid string has a unique leftmost derivation or parse tree.

https://en.wikipedia.org/wiki/Ambiguous_grammar

answered by Loyal (7.9k points)
+2 votes
answered by (35 points)
+4

Important text in pdf 

  • If a grammar has more than one leftmost derivation for a single sentential form, the grammar is ambiguous.
  • If a grammar has more than one rightmost derivation for a single sentential form, the grammar is ambiguous.
  • The leftmost and rightmost derivations for a sentential form may differ, even in an unambiguous grammar


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

39,828 questions
46,802 answers
140,990 comments
58,948 users