The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+17 votes
2k views

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 (59.7k points) | 2k views
+3
for the string " ibtibtaea " it is ambiguous
+1
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.
0
0
in this grammar where does it contain both left and right recurssion ?

3 Answers

+35 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.9k points)
edited by
+7
Is it dangling else ambiguity?
i here represents "If"
C here represents "Condition"
t means "then"
S means "statement"

e means "else"
0
how parse tree prove tht it is ambiguous like if we want to generate ictae it will give unique parse tree
0
If there is atleast one string in language which shows ambiguity then we can say grammar is ambiguous.
0
what is the ambiguous string'?

S and S1 are same NON-Terminal or different?
0
Is the grammar left recursive or not?
0
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)  

PS.

1) Surely its not left recursive .

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

3) It is context free .
answered by Junior (647 points)
+2 votes
it is ambiguous grammer answer c is correct
answered by (233 points)
Answer:

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

44,149 questions
49,639 answers
163,316 comments
65,808 users