Re: Left and Right recursive non-terminals

<cowboy@vnet.ibm.com> wrote:
> 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).


bart@time.cirl.uoregon.edu (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
> easy...


> ["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:


                        A
/|\
                    / b \
A A
                  | /|\
x A b A
| |
x x


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:vonbrand@inf.utfsm.cl
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 comp.compilers page.
Search the comp.compilers archives again.