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!


1 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.

  • 1
    $\begingroup$ 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? $\endgroup$ Commented Mar 6, 2019 at 13:33
  • 2
    $\begingroup$ 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. $\endgroup$
    – Wickoo
    Commented Mar 6, 2019 at 14:35
  • $\begingroup$ @Wickoo why is the grammar abilash mishra asked is useless? It looks useless because the example you wrote looks useless but you made no sort of general argument against such a production rule. So to me (a non expert in PL) - it's unclear if it's useless. $\endgroup$ Commented Jul 1, 2021 at 13:04
  • $\begingroup$ Have you fully read my comment? I said why it’s useless, it cannot produce any sentence. You need at least one more alternative $\endgroup$
    – Wickoo
    Commented Jul 2, 2021 at 14:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.