GATE CSE 2001 | Question: 1.18

Question

Which of the following statements is false?

• A. An unambiguous grammar has same leftmost and rightmost derivation
• B. An LL(1) parser is a top-down parser
• C. LALR is more powerful than SLR
• D. An ambiguous grammar can never be LR(k) for any k

Comments

Self Note :  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 refer to the order of various productions used for derivation which could be different.)

Answer 1

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 refer 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, 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 a top-down parser, and LALR is more powerful than SLR. So both are TRUE.

Comments

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.

---

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.

A grammar is Ambiguous if it has

1. more than one parse tree OR
2. more than one LMD tree OR
3. more than one RMD tree.

Infact we have bijection in between these sets. Which means, for every parse tree we have LMD and RMD. 

Given a parse tree, if you go  left-to-right depth-first traverse then you will get LMD. And  one right-to-left depth-first traverse will result in RMD. (take a parse tree and try doing it)

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? 

---

Either you do left most derivation or rightmost derivation the end parse tree will look same for unabmigous grammar if  the parse tree looks different then it is ambigious

---

How if a grammar is regular then it's LMD and RMD are same?

---

@Manisha Jaishwal please read the whole discussion. 

If the grammar is regular it is either left linear grammar or right linear grammar . So in either case you will have only one non terminal on RHS i,e only one non terminal for replacing . Therefore no chance of ambiguity.

---

Is there any difference between leftmost derivation tree and parse tree ?

Please tell me.

If I get one leftmost derivation tree and one rightmost derivation tree, is it ambiguous ?

---

$S\implies aS|a|\varepsilon$
This is a regular grammar
But "a" has two parse trees possible therefore ambiguous.
 

Answer 2

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

Comments

Both the derivations are same. Why are you saying both are different?

---

It's all about the order of execution.. Not about the structure

---

check the Sentencial Form but not the yield of the tree

Answer 3

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

Comments

So (B) and (C) are true

please correct it

Answer 4

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

Answer 5

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

Comments

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

---

link is change-

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

Answer 6

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.