Re: disambiguating transformations (Ron Dolin)
Sat, 25 Sep 1993 00:13:06 GMT

          From comp.compilers

Related articles
disambiguating transformations (Matt Melchert) (1993-09-22)
Re: disambiguating transformations (Stephen J Bevan) (1993-09-24)
Re: disambiguating transformations (1993-09-25)
Disambiguating an arbitrary CFL (was: disambiguating transformations) (1993-09-25)
Re: disambiguating transformations (Bart Massey) (1993-09-26)
Re: disambiguating transformations thinx! (Jos Horsmeier) (1993-09-27)
| List of all articles for this month |

Newsgroups: comp.compilers
From: (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 <> 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


Post a followup to this message

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