Re: disambiguating transformations

rad@cs.ucsb.edu (Ron Dolin)
Sat, 25 Sep 1993 00:13:06 GMT

          From comp.compilers
Related articles
disambiguating transformations MATT@waikato.ac.nz (Matt Melchert) (1993-09-22)
Re: disambiguating transformations bevan@computer-science.manchester.ac.uk (Stephen J Bevan) (1993-09-24)
Re: disambiguating transformations rad@cs.ucsb.edu (1993-09-25)
Disambiguating an arbitrary CFL (was: disambiguating transformations) markh@csd4.csd.uwm.edu (1993-09-25)
Re: disambiguating transformations bart@skinner.cs.uoregon.edu (Bart Massey) (1993-09-26)
Re: disambiguating transformations thinx!jos@relay.nluug.nl (Jos Horsmeier) (1993-09-27)
| List of all articles for this month |
Newsgroups: comp.compilers
From: rad@cs.ucsb.edu (Ron Dolin)
Keywords: parse, theory
Organization: University of California, Santa Barbara
References: 93-09-099
Date: Sat, 25 Sep 1993 00:13:06 GMT

Matt Melchert <MATT@waikato.ac.nz> writes:
> I am looking for an algorithm which will take a (possibly) ambiguous
> context-free grammar and perform transformations on it to yield an
> equivalent non-ambiguous context-free grammar.


Look in Hopcroft and Ullman -- "Introduction to Automata Theory,
Languages, and Computation": Theorem 8.9 states, "It is undecidable
whether an arbitrary CFG is ambiguous." In fact, section 4.7 is titled,
"The Existence of Inherently Ambiguous Context-Free Languages" -- any and
all grammars for such languages are ambiguous because the LANGUAGE is
ambiguous, so there's no way to transform the grammar to a non-ambiguous
CFG.


Ron
--

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.