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

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

asked in Compiler Design by Veteran (52k points)
edited by | 2.4k views
please explain anyone !!!
wiki says, "A common way for computer language grammars to be ambiguous is if some nonterminal is both left- and right-recursive"
The answer is right and it may or may not be ambiguous . option C is valid here and not option A .
can u explain why??
see the best answer , and check the thread link i have given ..
is it both for terminal and non terminal ?
@set2018 how a terminal can be left or right recursive?

obviously it is for non-terminals.

3 Answers

+36 votes
Best answer

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

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 .

Correct Answer: $C$

answered by Veteran (59.8k points)
edited by
you mean ambiguity is a property of strings, or their coincidence with grammars and not a property of grammars solely?
Variable A is not reachable from Start Symbol so it is useless Symbol.

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

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.

answered by Junior (747 points)
+4 votes
answer - C
answered by Loyal (8.7k 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,530 questions
54,139 answers
71,068 users