|Proof of inherent ambiguity? email@example.com (2004-09-24)|
|Re: Proof of inherent ambiguity? firstname.lastname@example.org (Nathan Sanders) (2004-09-25)|
|Re: Proof of inherent ambiguity? email@example.com (Rafael 'Dido' Sevilla) (2004-09-25)|
|Re: Proof of inherent ambiguity? firstname.lastname@example.org (2004-09-25)|
|Re: Proof of inherent ambiguity? email@example.com (Brian M. Scott) (2004-09-25)|
|Re: Proof of inherent ambiguity? firstname.lastname@example.org (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? email@example.com (Harlan Messinger) (2004-10-02)|
|From:||"Michael J. Fromberger" <Michael.J.Fromberger@Dartmouth.EDU>|
|Date:||25 Sep 2004 13:09:16 -0400|
|Posted-Date:||25 Sep 2004 13:09:16 EDT|
firstname.lastname@example.org (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
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:
Michael J. Fromberger | Lecturer, Dept. of Computer Science
http://www.dartmouth.edu/~sting/ | Dartmouth College, Hanover, NH, USA
Return to the
Search the comp.compilers archives again.