HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

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

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
leftnecessarybothambiguousrecursivegrammarforwhenandwhether

Problem

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!

Solution

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.

Context

StackExchange Computer Science Q#105208, answer score: 4

Revisions (0)

No revisions yet.