25 Sep 2004 13:09:16 -0400

Related articles |
---|

Proof of inherent ambiguity? dave_140390@hotmail.com (2004-09-24) |

Re: Proof of inherent ambiguity? nsanders@wso.williams.edu (Nathan Sanders) (2004-09-25) |

Re: Proof of inherent ambiguity? dido@imperium.ph (Rafael 'Dido' Sevilla) (2004-09-25) |

Re: Proof of inherent ambiguity? torbenm@diku.dk (2004-09-25) |

Re: Proof of inherent ambiguity? b.scott@csuohio.edu (Brian M. Scott) (2004-09-25) |

Re: Proof of inherent ambiguity? rdecker@hamilton.edu (Rick Decker) (2004-09-25) |

Re: Proof of inherent ambiguity? Michael.J.Fromberger@Dartmouth.EDU (Michael J. Fromberger) (2004-09-25) |

Re: Proof of inherent ambiguity? hmessinger@comcast.net (Harlan Messinger) (2004-10-02) |

From: | "Michael J. Fromberger" <Michael.J.Fromberger@Dartmouth.EDU> |

Newsgroups: | comp.compilers,comp.theory,sci.lang |

Date: | 25 Sep 2004 13:09:16 -0400 |

Organization: | Dartmouth College |

References: | 04-09-137 |

Keywords: | parse, theory |

Posted-Date: | 25 Sep 2004 13:09:16 EDT |

dave_140390@hotmail.com (Dave Ohlsson) wrote:

*> A context-free grammar is said to be ambiguous if at least one string*

*> in the context-free language defined by that grammar has more than one*

*> parse tree with that grammar.*

*>*

*> A context-free language is said to be inherently ambiguous if all the*

*> context-free grammars of that language are ambiguous.*

*>*

*> Now, I wonder how one can prove inherent ambiguity.*

*>*

*> Could anyone give an example of an inherently ambiguous context-free*

*> language AND the proof that that language is inherently ambiguous?*

Others have given you some examples of languages which are inherently

ambiguous. More generally, you might also find the following result

interesting:

W. G. Ogden, "A Helpful Result for Proving Inherent Ambiguity"

in Mathematical Systems Theory, Vol. 2, #3 (1969), pp. 191--194.

The abstract reads:

"It is shown that there is no `partial algorithm' (effective

procedure that may fail to terminate) by which, given a context free

grammar, one can always find an unambiguous context free grammar

generating the same language if such an unambiguous grammar exists.

The argument turns on the degree of unsovability of the inherent

ambiguity problem for context free languages."

The paper is available from ACM:

http://portal.acm.org/citation.cfm?id=800169.805417

Cheers,

-M

--

Michael J. Fromberger | Lecturer, Dept. of Computer Science

http://www.dartmouth.edu/~sting/ | Dartmouth College, Hanover, NH, USA

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.