11,660 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

Correct Option: A
(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.

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.

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!!

@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.)
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.
@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?
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
this is a nice point thanks sachin sir

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.

@Sachin Mittal 1.......because all regular grammar is unambiguous.......rt?

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).

by

Both the derivations are same. Why are you saying both are different?
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
by

### 1 comment

So (B) and (C) are true

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

by

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

https://www.eecis.udel.edu/~cavazos/cisc471-672-spring2018/lectures/Lecture-09.pdf

you can find all the above 3 point in page no 12

For option D

An ambiguous grammar can never be LR(k) for any k, because LR(k) algorithm aren’t designed to handle ambiguous grammars. It would get stuck into undecidability problem, if employed upon an ambiguous grammar, no matter how large the constant k is.