23,302 views
37 votes
37 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

4 Answers

Best answer
72 votes
72 votes

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
15 votes
15 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

7 votes
7 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
4 votes
4 votes
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)
Answer:

Related questions

34 votes
34 votes
5 answers
2
31 votes
31 votes
2 answers
3
go_editor asked Nov 27, 2016
11,378 views
Consider the following expression grammar. The semantic rules for expression evaluation are stated next to each grammar production.$$\begin{array}{l|l} E\rightarrow numbe...
56 votes
56 votes
7 answers
4