Re: detecting ambiguous grammars

Thant Tessman <thant@acm.org>
4 Mar 2001 01:37:56 -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)
Re: detecting ambiguous grammars thant@acm.org (Thant Tessman) (2001-03-12)
Re: detecting ambiguous grammars christian.bau@isltd.insignia.com (2001-03-22)
Re: detecting ambiguous grammars thant@acm.org (Thant Tessman) (2001-03-26)
Re: detecting ambiguous grammars joachim_d@gmx.de (Joachim Durchholz) (2001-03-26)
[10 later articles]
| List of all articles for this month |

From: Thant Tessman <thant@acm.org>
Newsgroups: comp.compilers
Date: 4 Mar 2001 01:37:56 -0500
Organization: XMission http://www.xmission.com/
References: 01-02-080 01-03-020
Keywords: parse
Posted-Date: 04 Mar 2001 01:37:56 EST

Thanks to everyone who's responded.


Joachim Durchholz wrote:


[...]


> Note that the Earley algorithm will parse any string against any
> context-free grammar, but it will not tell you whether the grammar
> is ambiguous, it will tell you whether that particular string can be
> parsed in an ambiguous manner (and give you all the relevant parse
> trees as well). [...]


Ah! This is what motivated my question. A few years ago, without
knowing the "right" way to parse a grammar (other than using lex and
yacc), I implemented exactly this. I was delighted because the
implementation was very concise--about two pages of Scheme code. But
its strength is its weakness. The ability to get all possible parse
trees is pretty cool, but of course there is also an advantage to
knowing absolutely that a given grammar isn't ambiguous.


The earlier responses I got to my original question convinced me to
revisit the dragon book (this time armed with a pot of coffee), but
the fact that there are production compilers that use an Earley parser
leads me to ask: Does the use of an Earley parser offend people's
sense of programming language design aesthetics if one is able and
required to make it explicit which parse tree is to be preferred?


-thant


Post a followup to this message

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