20 Dec 1996 17:15:38 -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: | 20 Dec 1996 17:15:38 -0500 |

Organization: | University of Oregon |

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

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

Frank Wilde <perle@cs.tu-berlin.de> wrote:

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

Right you are. Further, somebody sent me e-mail pointing out that I

didn't really try to prove the theorem that was requested. I tried to

prove that a reachable *production* that is both left and right

recursive renders a grammar ambiguous. They also helped me see the

right proof.

Sooo... let's do this one more time:

case 1)

There is a production for A of the form

A -> A b A

Assume that A derives some finite sentence a. Let the string

of symbols b derive some finite sentence s. Then if a is

nonempty, we have

A -*-> (a s a) s a = a s a s a

A -*-> a s (a s a) = a s a s a

otherwise my original proof is correct:

A -*-> a s (a s (a s a)) = s (s s) = s s s

A -*-> ((a s a) s a) s a = (s s) s = s s s

case 2)

There are productions for A of the form

A -> b A

A -> A c

Assume that A derives some finite sentence a. Let the string

of symbols b derive some finite sentence s, and c derive some

finite sentence t. Then if a, b, c are nonempty, we note that

A -*-> s (a t) = s a t

A -*-> (s a) t = s a t

We note that if a is the empty sentence, and s and t are

nonempty, then

A -*-> s (s ((a t) t)) = s (s (t t)) = s s t t

A -*-> ((s (s a)) t) t = ((s s) t) t = s s t t

If s or t is the empty sentence, then

A -*-> a

A -*-> s a = a

or

A -*-> a

A -*-> a t = a

Does this look better to everybody? My apologies for the online

theorem proving. I still hope I'm not doing somebody's homework :-).

Bart Massey

bart@cs.uoregon.edu

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.