25 Sep 2004 11:30:11 -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: | torbenm@diku.dk (Torben Ęgidius Mogensen) |

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

Date: | 25 Sep 2004 11:30:11 -0400 |

Organization: | Department of Computer Science, University of Copenhagen |

References: | 04-09-137 |

Keywords: | parse, theory |

Posted-Date: | 25 Sep 2004 11:30:11 EDT |

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

The intersection of L1 and L2 is {a^m b^m c^m | m>0}. Any string in

the intersection will, obviously, have two syntax trees by the above

grammar, but this does not prove inherent ambiguity.

However, {a^m b^m c^m | m>0} is not a context free language, so you

can argue that no context free grammar can decide which way to parse

strings in the intersection, so there will always be ambiguity. This

is not a stringent proof, but a formal proof can follow the same idea.

Torben

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.