1
$\begingroup$

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!

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\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$ – Abhilash Mishra Mar 6 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 Mar 6 at 14:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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