Re: disambiguating transformations

Jos Horsmeier <thinx!>
Mon, 27 Sep 1993 08:23:28 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: Jos Horsmeier <thinx!>
Keywords: parse, theory
Organization: Compilers Central
References: 93-09-099 93-09-120
Date: Mon, 27 Sep 1993 08:23:28 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. Does such a thing exist? If not, do we
|know why not? Any ideas or references would be appreciated.

Our moderator adds the following question:
|[Is this even decidable? -John]

No, it is not. The question whether or not a context free grammar is
ambiguous is an undecidable question. The proof is quite simple:

Given a Post Correspondence problem P = { v_1, ... v_n, w_1, ... w_n }
construct the following production rules for the grammar G:

S -> T | U
T -> v_i T i | v_i i
U -> w_i U i | w_i i

for i in [1 ... n]

Now, in order to decide whether or not this grammar is ambiguous, one
has to solve the embedded Post Correspondence problem P.

Does anybody mind if I say `Q.E.D.' now? ;-)

kind regards,

Jos aka aka thinx!

Post a followup to this message

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