patternMinor
Whether it's necessary for a grammar to be ambiguous when it is both left recursive and right recursive
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!
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.
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.