Re: Proof of inherent ambiguity?

"Michael J. Fromberger" <Michael.J.Fromberger@Dartmouth.EDU>
25 Sep 2004 13:09:16 -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: "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.