25 Sep 2004 13:08:53 -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: | Rick Decker <rdecker@hamilton.edu> |

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

Date: | 25 Sep 2004 13:08:53 -0400 |

Organization: | Compilers Central |

References: | 04-09-137 |

Keywords: | parse, theory |

Posted-Date: | 25 Sep 2004 13:08:53 EDT |

Dave Ohlsson wrote:

*> 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?*

The canonical example is

{a^n b^n c^m d^m | n, m >= 0} \union {a^n b^m c^n d^m | n, m >= 0}

the proof is a bit tricky, but you shouldn't have trouble

finding references to it. I got 156,000 hits from Google on "inherent

ambiguity."

Regards,

Rick

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.