|Top-Down Parser Construction Conjectures firstname.lastname@example.org (1993-01-18)|
|Automatic Transformation of CFG to LL/LR email@example.com (1993-01-29)|
|Re: Automatic Transformation of CFG to LL/LR firstname.lastname@example.org (1993-02-02)|
|Re: Automatic Transformation of CFG to LL/LR email@example.com (1993-02-03)|
|From:||firstname.lastname@example.org (Barton Christopher Massey)|
|Organization:||University of Oregon Computer and Information Sciences Dept.|
|Date:||Tue, 2 Feb 1993 08:23:12 GMT|
email@example.com (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.
Return to the
Search the comp.compilers archives again.