The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+15 votes

Consider the grammar with non-terminals $N=\left\{S,C,S_1\right\}$, terminals $T=\left\{a, b, i, t, e\right\}$, with $S$ as the start symbol, and the following set of rules:

$S \rightarrow iCtSS_1 \mid a$

$S_1 \rightarrow eS \mid \epsilon$

$C \rightarrow b$

The grammar is NOT LL(1) because:

  1. it is left recursive

  2. it is right recursive

  3. it is ambiguous

  4. it is not context-free

asked in Compiler Design by Veteran (69k points) | 1.3k views
for the string " ibtibtaea " it is ambiguous
Ambiguous grammars mainly contain productions of the form “A -> AαA | β“, in
which both left recursion and right recursion, occurs simultaneously either direct or
indirect after some non-terminal replacement.
in this grammar where does it contain both left and right recurssion ?

3 Answers

+32 votes
Best answer

here, we can expand any one of $S_1$ to $\in$ and other to $ea$, but which one will it be need not matter, coz in the end we will still get the same string.

this means that the Grammar is Ambiguous. LL(1) cannot be ambiguous. Here's a Proof for that.

answer = option C

answered by Veteran (31k points)
edited by
Is it dangling else ambiguity?
i here represents "If"
C here represents "Condition"
t means "then"
S means "statement"

e means "else"
how parse tree prove tht it is ambiguous like if we want to generate ictae it will give unique parse tree
If there is atleast one string in language which shows ambiguity then we can say grammar is ambiguous.
+2 votes
it is ambiguous grammer answer c is correct
answered by (233 points)
+1 vote
It is left factored version of the dangling else grammar. As we know,left factoring eliminates non determinism,but can not eliminate ambiguity,So ans should be (C)  


1) Surely its not left recursive .

2) Right recursion is not an issue for LL(1) .

3) It is context free .
answered by Active (1.5k points)

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

33,646 questions
40,193 answers
38,664 users