Fri, 24 Sep 1993 08:34:38 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) |

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: | Stephen J Bevan <bevan@computer-science.manchester.ac.uk> |

Keywords: | parse, theory |

Organization: | Compilers Central |

References: | 93-09-099 |

Date: | Fri, 24 Sep 1993 08:34:38 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.

Whilst not directly answering the above, the following seems relevant :-

"It has been proven that the problem of deciding whether an arbitrary

context free grammar is ambiguous or not is undecidable. The next

question one might ask is whether there exists an unambiguous grammar for

an arbitrary context free language. The answer is no. There are

languages for which _no_ unambiguous grammar exists; this was first shown

by Parikh[61]".

Compiler Construction For Digital Computers - David Gries - Wiley 1971 - pp 47

[61] Parikh, R. J. On context free languages JACM 13:570-581 Oct 1966

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.