edited by
17,886 views

6 Answers

Best answer
48 votes
48 votes

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.

edited by
39 votes
39 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).

10 votes
10 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
edited by
Answer:

Related questions

20 votes
20 votes
2 answers
1
Kathleen asked Sep 14, 2014
3,573 views
Remove left-recursion from the following grammar: $S \rightarrow Sa \mid Sb \mid a \mid b$Consider the following grammar: $S \rightarrow aSbS\mid bSaS \mid �...