GATE CSE 2005 | Question: 14

Question

The grammar $A \rightarrow AA \mid (A) \mid \epsilon$ is not suitable for predictive-parsing because the grammar is:

• A. ambiguous

• B. left-recursive

• C. right-recursive

• D. an operator-grammar

Comments

The given grammar is Ambiguous and left recursive....

But it's also not operator grammar

Because property is (NO two variable in right side or No null production).

What's correct answer??

---

Had it been a recursive descent parser (with backtracking), then this same grammar shall be suitable right?

Answer 1

both A and B can be answers but A is a better answer. Because we have standard procedure for removing left-recursion but ambiguity is not easy to remove. - checking if a given CFG is ambiguous is a undecidable problem.

Comments

Since ambiguity is undecidable problem so left recursion should be answer then, isn't it?

---

A->AA

both left recursive and right recursive??

---

@Abhisek Tiwari 4 yes

Answer 2

Any Grammar which is Left Recursive will cause any Predictive Parser to fall into an infinite loop. No matter if it is ambiguous or not, it won't be parsable. This is more stronger than saying it is ambiguous so fails.

Hence, answer = option B

Comments

It can not be parse when ambiguous. Ambiguous is more appropiate then left recursive as we can remove left recursion easily.

---

But in key answer is B

---

There is no official answer key before GATE 2011. Which key are you talking about?

Answer 3

Since given grammar can have more than 1  parse trees for string '(())', so grammar is ambiguous,

and also A → AA has left recursion.

For predictive-parsing, i.e. LL(1),    grammar should be:

• Free from ambiguity
• Free from left recursion
• Free from left factoring(Non Determinism)

Given grammar contains both ambiguity and left recursion, so it can not have a predictive parser. .We can remove left recursion easily but ambiguity of CFL is not easy to remove.(as it is undecidable)

option A is more appropriate. 

Answer 4

for checking if the given grammar is LL(1) or not first you will check if it's left reccursive or not(because it is easy to check) if its left recursive it is surely not LL(1) but if it's not left recursive then only you need to check for ambiguity . if it turn out to be ambiguous we can say grammar is surely not LL(1).

so answer should be B.. that it is left recursive..no need to check for ambiguity

note : even if grammar is not ambiguous we can't be sure that it is LL(1).

for finding that you have to make the LL(1) parsing table and if no two production collide in a same shell of the table you can say there is no conflict hence LL(1)

Comments

@Sneha negi

note : even if grammar is not ambiguous we can't be sure that it is LL(1).

but we can say the same for left recursion also , that if a grammar is not left recursive then also it may or may not be LL(1), as it may be either ambiguous(2 parse trees possible for some string) or not left factored.

so A is the correct one here.