2 Oct 2004 01:11:29 -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: | Harlan Messinger <hmessinger@comcast.net> |

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

Date: | 2 Oct 2004 01:11:29 -0400 |

Organization: | Compilers Central |

References: | 04-09-137 04-09-143 |

Keywords: | parse, theory |

Posted-Date: | 02 Oct 2004 01:11:29 EDT |

torbenm@diku.dk (Torben Ęgidius Mogensen) wrote:

*>dave_140390@hotmail.com (Dave Ohlsson) writes:*

*>*

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

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

*>*

*>The standard example of a language with inherent ambiguity is*

*>*

*> L = L1 U L2, where*

*> L1 = {a^m b^m c^n | m,n>0}*

*> L2 = {a^m b^n c^n | m,n>0}*

*>*

*>This is clearly context free, e.g. by the grammar*

*>*

*> S -> S1 | S2*

*> S1 -> A1 C*

*> S2 -> A B1*

*> A1 -> a b | a A1 b*

*> B1 -> b c | b B1 c*

*> C -> c | c C*

*> A -> a | a C*

Rather, A -> a | a A, correct?

--

Harlan Messinger

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.