Re: Proof of inherent ambiguity?

Rafael 'Dido' Sevilla <dido@imperium.ph>
25 Sep 2004 11:29:58 -0400

          From comp.compilers
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)
| List of all articles for this month |
From: Rafael 'Dido' Sevilla <dido@imperium.ph>
Newsgroups: comp.compilers
Date: 25 Sep 2004 11:29:58 -0400
Organization: Compilers Central
References: 04-09-137
Keywords: parse, theory
Posted-Date: 25 Sep 2004 11:29:58 EDT
X-Operating-System: Linux morgoth 2.4.26-gentoo-r9

On Fri, Sep 24, 2004 at 12:26:52AM -0400, Dave Ohlsson wrote:
> Could anyone give an example of an inherently ambiguous context-free
> language AND the proof that that language is inherently ambiguous?


Do you have access to a copy of the original 1979 edition of the
Cinderella Book (Introduction to Automata Theory, Languages, and
Computation, by John Hopcroft and Jeffrey Ullman)? If memory serves
correctly, at the end of the chapter on CFL's and PDA's Hopcroft and
Ullman present an inherently ambiguous CFL and a proof of inherent
ambiguity. I'm not sure, but I'm afraid that it may have been one of
the things cut out in the 2000 edition of the Cinderella Book (it's
already in a starred "optional" section in the old edition).


--
dido
Te capiam, cuniculus sceleste!


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.