Re: detecting ambiguous grammars

"David Pereira" <davidpereira@home.com>
17 Feb 2001 01:32:35 -0500

          From comp.compilers
Related articles
detecting ambiguous grammars thant@acm.org (Thant Tessman) (2001-02-15)
Re: detecting ambiguous grammars davidpereira@home.com (David Pereira) (2001-02-17)
Re: detecting ambiguous grammars cfc@world.std.com (Chris F Clark) (2001-02-23)
Re: detecting ambiguous grammars joachim_d@gmx.de (Joachim Durchholz) (2001-03-01)
Re: detecting ambiguous grammars henry@spsystems.net (2001-03-04)
Re: detecting ambiguous grammars thant@acm.org (Thant Tessman) (2001-03-04)
Re: detecting ambiguous grammars davidpereira@home.com (David Pereira) (2001-03-08)
Re: detecting ambiguous grammars dlester@cs.man.ac.uk (2001-03-10)
[14 later articles]
| List of all articles for this month |
From: "David Pereira" <davidpereira@home.com>
Newsgroups: comp.compilers
Date: 17 Feb 2001 01:32:35 -0500
Organization: Excite@Home - The Leader in Broadband http://home.com/faster
References: 01-02-080
Keywords: parse, theory
Posted-Date: 17 Feb 2001 01:32:34 EST

It is quite possible that your approach works only on the certain
restricted class of grammar that you have tried it on. Mathematically,
the problem of detecting whether a grammar is ambiguous is
*undecidable* (that's why you're on a wild goose chase; you can't
fight a mathematical proof.. Sorry). You can pick up any good book on
grammars for an explanation, but no matter which way you cut it.. you
*won't* be able to come up with an algorithm that works sucessfully on
all grammars.


DP.


> Is there a general algorithm for detecting whether a grammar is
> ambiguous? I've read posts that suggest the answer is no, but could
> someone point me at the reason why?

Post a followup to this message

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