15 Dec 1996 16:19:01 -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: | bart@time.cirl.uoregon.edu (Barton C. Massey) |

Newsgroups: | comp.compilers |

Date: | 15 Dec 1996 16:19:01 -0500 |

Organization: | University of Oregon |

References: | 96-12-089 |

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

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

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.

Assume further that there is a nonempty sentence s such that s is

derivable from b (this is informal, but you get the idea).

Consider parsing the sentence s s s with A. We can parse this

as

A -> A b A -> (A b A) b A -> ((A b A) b A) b A -*-> ((s) s) s

or as

A -> A b A -> (A b A) b A -> (A b A) b (A b A) -*-> (s) s (s)

In other words, we can have at least two parse trees for the

sentence s s s

s s

\ / \

s s s

\

s

Finally, we note that by the definition of A, A must recognize the

sentence s s s , therefore A is ambiguous.

Hope this helps, (and that I didn't just do your homework for you :-)!

Bart Massey

bart@cs.uoregon.edu

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.