# Whether it's necessary for a grammar to be ambiguous when it is both left recursive and right recursive

I read somewhere that if a grammar is left recursive as well as right recursive, then it is not necessarily ambiguous.

I couldn't make up my mind on this statement. How can a grammar which is both left recursive as well as right recursive not have more than one parse tree for a single string.

Am I right? If not, please provide a counter example whereby my assumption can be proved wrong.

Do you mean a grammar with left and right recursive rules, or a single production rule with left and right recursive alternatives?

If a single production rule is both left and right recursive, the grammar is ambiguous. For example, the following rule

$$A \to \alpha A \mid A \alpha$$

has the following two (left-most) derivations:

$$A \Rightarrow \alpha A \Rightarrow \alpha A \alpha$$ corresponding to the grouping $$(\alpha (A\alpha)$$

$$A \Rightarrow A \alpha \Rightarrow \alpha A \alpha$$ corresponding to the grouping $$((\alpha A) \alpha)$$

But a grammar can have left recursive and right recursive rules in different production rules and that can be unambiguous. For example, the following grammar:

\begin{align*} S &\to X \mid Y \\ X &\to X b \\ Y &\to a Y \\ \end{align*}

In this grammar, $$X$$ and $$Y$$ are left and right recursive, respectively, but the grammar is unambiguous.

• Hi @Wickoo, thanks for the answer. I just had one more question... Can we have a case where there is only one production in the grammar, which can be both left recursive and right recursive, and this grammar is not ambiguous? – Abhilash Mishra Mar 6 '19 at 13:33
• You mean something like $A \to A \alpha A$? First of all, such a grammar is useless, as it doesn't produce anything, so you need a second alternative like $A \to b$ for example. In this case, yes, it is still ambiguous. It's like the case with 1+2+3, for the grammar $E \to E + E \mid digit$ which can be left or right associative. – Wickoo Mar 6 '19 at 14:35