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

Question

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.

Thanks in advance!

Answer 1

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.