18 Dec 1996 00:12:14 -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: | perle@cs.tu-berlin.de (Frank Wilde) |

Newsgroups: | comp.compilers |

Date: | 18 Dec 1996 00:12:14 -0500 |

Organization: | Technical University of Berlin, Germany |

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).*

Barton C. Massey <bart@cs.uoregon.edu> wrote:

*>Consider a such nonterminal A, with production*

*> A -> A b A*

*>where b is any string of terminals and nonterminals (need a*

*>Greek keyboard :-).*

*>*

*>Now, for there to be any finite-length strings recognizable by A, it*

*>must be that it is possible to derive the empty sentence e from A.*

Non sequitur. There must be another production for A for a derivation

of A to be able to terminate, but you only have to be able to derive some

terminal string from it; it does not neccessarily have to be empty.

Of course, this says nothing about abiguousity, because

A b A b A can obviously be (A b A) b A or A b (A b A) .

Ciao,

Perle

--

Frank Wilde | perle@cs.TU-Berlin.DE | +49 30 3454141

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.