Return to the
comp.compilers page.
Search the
comp.compilers archives again.
| 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
--
Return to the
comp.compilers page.
Search the
comp.compilers archives again.