25 May 1997 13:28:24 -0400

Related articles |
---|

ambiguity kauer@paxp01.mipool.uni-jena.de (Stefan Kauer) (1997-05-22) |

Re: ambiguity mickunas@mickunas.cs.uiuc.edu (1997-05-25) |

From: | mickunas@mickunas.cs.uiuc.edu (Dennis Mickunas) |

Newsgroups: | comp.compilers |

Date: | 25 May 1997 13:28:24 -0400 |

Organization: | University of Illinois at Urbana |

References: | 97-05-270 |

Keywords: | parse, theory, bibliography |

Stefan Kauer <kauer@paxp01.mipool.uni-jena.de> writes:

*>Hello,*

*>I have a rather theoretical question, for which I found no answer in*

*>several standard books on compiler writing.*

*>I have a context free, unambigious grammar, which contains left*

*>recursion. When the left recursion is removed (by any well known*

*>standard algorithm), is always the case, that the new grammar is also*

*>unambigious?*

*>If not, I'd like to see an example. If yes, I'd like to see the proof*

*>(or a reference to a book or paper).*

Even better--cover grammars. From a tech report by Anton Nijholt:

A. Nijholt

"A Survey of Normal Form Covers For Context Free Grammars"

Informatica Rapport 49

Vrije Universiteit

(February, 1979)

"Any e-free CFG G (cycle-free, no useless symbols) can be

transformed to a NLR [non left-recursive] grammmar G' such that

G'[r/r]G and G'[l/r]G. This result first appeared in Nijholt [7].

Soisalon-Soininen [11] gave a more simple proof of this result. One

of the transformations which is used in the latter paper is based on

an idea of Kurki-Suonio [5]. This trick can also be used for a

transformation presented in Wood [14] and which is due to J.M.

Foster."

[5] Kurki-Suonio, R., "On top-to-bottom recognition and left

recursion," CACM 9 (1966), pp. 527-528.

[7] Nijholt, A., "On the covering of left-recursive grammars," 4th

POPL (1977), pp. 86-96.

[11] Soisalon-Soininen, E., "On the covering problem for

left-recursive grammars," Theor. Comput. Science 8 (1979), pp. 1-12.

[14] Wood, D., "The normal form theorem -- another proof," Computer

Journal 12 (1966), pp. 139-147.

--

M. Dennis Mickunas

Department of Computer Science 1304 W. Springfield Ave.

University of Illinois Urbana, Illinois 61801

mickunas@cs.uiuc.edu (217) 333-6351

http://www-sal.cs.uiuc.edu/~mickunas

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.