Tue, 2 Feb 1993 08:23:12 GMT

Related articles |
---|

Top-Down Parser Construction Conjectures bart@cs.uoregon.edu (1993-01-18) |

Automatic Transformation of CFG to LL/LR ramki@cs.du.edu (1993-01-29) |

Re: Automatic Transformation of CFG to LL/LR bart@cs.uoregon.edu (1993-02-02) |

Re: Automatic Transformation of CFG to LL/LR ramki@cs.du.edu (1993-02-03) |

Newsgroups: | comp.compilers |

From: | bart@cs.uoregon.edu (Barton Christopher Massey) |

Keywords: | parse, theory |

Organization: | University of Oregon Computer and Information Sciences Dept. |

References: | 93-01-122 93-02-010 |

Date: | Tue, 2 Feb 1993 08:23:12 GMT |

ramki@cs.du.edu (Ramki Thurimella) writes:

*> While testing to see if a given CFG is LL(1) or LR(1) simple and*

*> decidable, converting one is undecidable. Exercises 5.1.12 and 5.2.12 of*

*> Aho, A.V. and Ullman, J.D., "The Theory of Parsing, Translation,*

*> and Compiling," Vol. 1: Parsing, Prentice-Hall, Englewood Cliffs,*

*> N.J., 1972.*

*> raise the same issues as that of the previous posting.*

I'll check the ref, but note that detecting, much less eliminating, CFG

ambiguity is undecidable, which is sufficient to show that converting an

arbitrary CFG to a necessarily unambiguous LL(1) or LR(1) grammar is

undecidable. My conjectures thus were limited to unambiguous CFGs -- it

has been my experience that provably unambiguous grammars are easily

constructed for *most* interesting programming languages.

Bart Massey

bart@cs.uoregon.edu

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.