The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+19 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 (52k points) | 2.4k 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

+36 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 Boss (30.6k 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.
what is the ambiguous string'?

S and S1 are same NON-Terminal or different?
Is the grammar left recursive or not?
If for a single string we can draw two or more different parse trees then the grammar is said to be ambiguous.
+3 votes
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 Junior (673 points)
How to test whether this grammar is context free or not?
+2 votes
it is ambiguous grammer answer c is correct
answered by (233 points)

Related questions

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
49,541 questions
54,094 answers
71,001 users