Log In
27 votes

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

  1. ambiguous

  2. left-recursive

  3. right-recursive

  4. an operator-grammar

in Compiler Design 8.7k views
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??

5 Answers

57 votes
Best answer

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.

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

both left recursive and right recursive??
13 votes

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

nopes A is a better answer.
i think the precedence should go like

1) ambigious

2) left recursive

3) left factoring
how can it be parsed if it is ambiguous in the first place
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?
3 votes

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. 

edited by
2 votes
answer - B
1 vote
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 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)

Related questions

30 votes
2 answers
Consider the context-free grammar $E \rightarrow E + E$ $E \rightarrow (E * E)$ $E \rightarrow id$ where $E$ is the starting symbol, the set of terminals is $\{id, (,+,),*\}$, and the set of nonterminals is $\{E\}$. Which of the following terminal strings has more than one parse tree when parsed according to ... $id + (id* (id * id))$ $(id* (id * id)) + id$ $((id * id + id) * id)$
asked Nov 4, 2014 in Compiler Design Ishrat Jahan 3.2k views
24 votes
2 answers
Consider the following expression grammar. The semantic rules for expression evaluation are stated next to each grammar production. ... to $7$ Precedence of $+$' is higher than that of $\times$', and both operators are left associative; expression is evaluated to $9$
asked Nov 27, 2016 in Compiler Design jothee 5.9k views
43 votes
7 answers
Statement for Linked Answer Questions 83a & 83b: Consider the following expression grammar. The semantic rules for expression evaluation are stated next to each grammar production. ... of a shift over a reduce action It detects shift-reduce conflict, and resolves the conflict in favor of a reduce over a shift action
asked Sep 23, 2014 in Compiler Design Kathleen 11.8k views
20 votes
1 answer
Consider the grammar: $S \rightarrow (S) \mid a$ Let the number of states in SLR (1), LR(1) and LALR(1) parsers for the grammar be $n_1, n_2$ and $n_3$ respectively. The following relationship holds good: $n_1 < n_2 < n_3$ $n_1 = n_3 < n_2$ $n_1 = n_2 = n_3$ $n_1 \geq n_3 \geq n_2$
asked Sep 22, 2014 in Compiler Design Kathleen 7.3k views