2.3k views

A grammar that is both left and right recursive for a non-terminal, is

1. Ambiguous

2. Unambiguous

3. Information is not sufficient to decide whether it is ambiguous or unambiguous

4. None of the above

edited | 2.3k views
0
+2
0
wiki says, "A common way for computer language grammars to be ambiguous is if some nonterminal is both left- and right-recursive"
https://en.wikipedia.org/wiki/SLR_grammar

http://cs.txstate.edu/~ch04/webtest/teaching/courses/5318/lectures/slides2/s4-amb-assoc-prec.pdf
+8
The answer is right and it may or may not be ambiguous . option C is valid here and not option A .
0
can u explain why??
0
0
is it both for terminal and non terminal ?
+4
@set2018 how a terminal can be left or right recursive?

obviously it is for non-terminals.

Let grammar is like this :
$S \rightarrow a$
$A \rightarrow AbA$
This grammar is left as well as right recursive but still unambiguous.. A is useless production but still part of grammar..
A grammar having both left as well as right recursion may or may not be ambiguous ..

Let's take a grammar say

$S\rightarrow SS$

Now, according to the link https://en.wikipedia.org/wiki/Formal_grammar

For a grammar G, if we have L(G) then all the strings/sentences in this language can be produced after some finite number of steps .

But, for the grammar $$S\rightarrow SS$$

Can we produce any string after a finite number of steps ? NO, and hence language of this grammar is empty set {} .

Hence, If a grammar is having both left and right recursion, then grammar may or may not be ambiguous .

edited by
0
you mean ambiguity is a property of strings, or their coincidence with grammars and not a property of grammars solely?
+3
+1
Variable A is not reachable from Start Symbol so it is useless Symbol.

And still it is part of grammar.
0
Can such  a gammer  be ambagious?Answer does not provide example for this
0
Means if a grammar is both left and right recursive and is producing empty set, then the grammar is unambiguous?

Information is insufficient ie C would be the correct option.

Grammar that is both left recursive and right recursive can be ambiguous.
Consider the grammar,

E -> E - E | T
T -> T / T | F
F -> num | ( E )

There can be 2 parse trees for "5-3-2"
1) one with correct associativity ((5-3)-2)
2) one with wrong associativity (5-(3-2)).

So its clear that B can never be the correct option.

Source: http://pages.cs.wisc.edu/~fischer/cs536.s08/course.hold/html/NOTES/3.CFG.html#exp


1
2