Sat, 25 Sep 1993 00:13:06 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: | 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.