edited by
9,565 views
28 votes
28 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

edited by

2 Answers

Best answer
66 votes
66 votes

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 .

Correct Answer: $C$

edited by
5 votes
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.

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

Related questions

2 votes
2 votes
0 answers
1
13 votes
13 votes
1 answer
2
Kathleen asked Sep 23, 2014
5,826 views
What will be the output of the following program assuming that parameter passing iscall by valuecall by referencecall by copy restoreprocedure P{x, y, z}; begin y:y+1; z:...
39 votes
39 votes
5 answers
3
Kathleen asked Sep 23, 2014
8,739 views
The number of articulation points of the following graph is$0$$1$$2$$3$
21 votes
21 votes
6 answers
4
Kathleen asked Sep 23, 2014
22,949 views
Which of the following is the most powerful parsing method?LL (1)Canonical LRSLRLALR