Re: Is a contextfree Grammar ambiguous ?

mickunas@cs.uiuc.edu (Dennis Mickunas,297D,3336351,0000000)
7 Nov 1998 01:25:02 -0500

          From comp.compilers
Related articles
Is a contextfree Grammar ambiguous ? mmeyer@rhso.de (Martin Meyer) (1998-10-30)
Re: Is a contextfree Grammar ambiguous ? clark@quarry.zk3.dec.com (Chris Clark USG) (1998-11-06)
Re: Is a contextfree Grammar ambiguous ? mickunas@cs.uiuc.edu (1998-11-07)
Re: Is a contextfree Grammar ambiguous ? mickunas@cs.uiuc.edu (1998-11-07)
Re: Is a contextfree Grammar ambiguous ? aycock@csc.uvic.ca (1998-11-07)
Re: Is a contextfree Grammar ambiguous ? dmr@plan9.bell-labs.com (1998-11-07)
Re: Is a contextfree Grammar ambiguous ? cfc@world.std.com (Chris F Clark) (1998-11-07)
Re: Is a contextfree Grammar ambiguous ? cfc@world.std.com (Chris F Clark) (1998-11-12)
Re: Is a contextfree Grammar ambiguous ? jmlake@unity.ncsu.edu (1998-11-15)
| List of all articles for this month |
From: mickunas@cs.uiuc.edu (Dennis Mickunas,297D,3336351,0000000)
Newsgroups: comp.compilers
Date: 7 Nov 1998 01:25:02 -0500
Organization: University of Illinois at Urbana-Champaign
References: 98-10-172
Keywords: parse, theory

Martin Meyer <mmeyer@rhso.de> writes:
>Does an algorithm to decide whether a context free grammar is
>ambiguous exist ?


No such algorithm exists. It is undecidable whether an arbitrary
context-free grammar G is ambiguous. See Aho & Ullman's "Theory of
Parsing, Translation, and Compiling, Volume I: Parsing" for a proof.


--
M. Dennis Mickunas
Department of Computer Science 1304 W. Springfield Ave.
University of Illinois Urbana, Illinois 61801
mickunas@cs.uiuc.edu (217) 333-6351

Post a followup to this message

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