|Left and Right recursive non-terminals firstname.lastname@example.org (1996-12-14)|
|Re: Left and Right recursive non-terminals email@example.com (1996-12-15)|
|Re: Left and Right recursive non-terminals firstname.lastname@example.org (David L Moore) (1996-12-15)|
|Re: Left and Right recursive non-terminals email@example.com (1996-12-18)|
|Re: Left and Right recursive non-terminals firstname.lastname@example.org (1996-12-20)|
|Re: Left and Right recursive non-terminals email@example.com (Horst von Brand) (1996-12-26)|
|From:||Horst von Brand <firstname.lastname@example.org>|
|Date:||26 Dec 1996 14:11:36 -0500|
|Organization:||Universidad Tecnica Federico Santa Maria|
> I'm sure I read somewhere that a non-terminal that is both left and right
> recursive renders the grammar ambiguous (I think for any k).
email@example.com (Barton C. Massey) writes:
> A reachable non-terminal that is both left and right recursive and
> which derives any nonempty string of terminals renders a grammar
> ambiguous, yes. I don't know a reference, but the proof is pretty
> ["Proof" assuming A -> A b A and A =>* empty]
A need not deliver the empty string.
As in the "proof" given, assume b=>* s, A=>* x, where both s and x are
strings of terminals (since A and the string b aren't useless). Take:
A =>* xbxbx =>* xsxsx
which you can get two different ways, the following (partial, schematic)
derivation tree and its mirror image:
/ b \
x A b A
Regardless of whether s and x are nonempty, the resulting parse trees for
the full string produced are different, i.e., the grammar is ambiguous.
Dr. Horst H. von Brand mailto:firstname.lastname@example.org
Departamento de Informatica Fono: +56 32 797499 x 431
Universidad Tecnica Federico Santa Maria Fax: +56 32 797513
Casilla 110-V, Valparaiso, Chile
Return to the
Search the comp.compilers archives again.