26 Dec 1996 14:11:36 -0500

Related articles |
---|

Left and Right recursive non-terminals cowboy@cv.lexington.ibm.com (1996-12-14) |

Re: Left and Right recursive non-terminals bart@time.cirl.uoregon.edu (1996-12-15) |

Re: Left and Right recursive non-terminals dlmoore@ix.netcom.com (David L Moore) (1996-12-15) |

Re: Left and Right recursive non-terminals perle@cs.tu-berlin.de (1996-12-18) |

Re: Left and Right recursive non-terminals bart@time.cirl.uoregon.edu (1996-12-20) |

Re: Left and Right recursive non-terminals vonbrand@inf.utfsm.cl (Horst von Brand) (1996-12-26) |

From: | Horst von Brand <vonbrand@inf.utfsm.cl> |

Newsgroups: | comp.compilers |

Date: | 26 Dec 1996 14:11:36 -0500 |

Organization: | Universidad Tecnica Federico Santa Maria |

References: | 96-12-089 96-12-115 |

Keywords: | parse, theory |

<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

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.