Mon, 27 Sep 1993 08:23:28 GMT

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) |

Newsgroups: | comp.compilers |

From: | Jos Horsmeier <thinx!jos@relay.nluug.nl> |

Keywords: | parse, theory |

Organization: | Compilers Central |

References: | 93-09-099 93-09-120 |

Date: | Mon, 27 Sep 1993 08:23:28 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. 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 jos@and.nl aka thinx!jos@convex.com

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.