Re: detecting ambiguous grammars

dlester@cs.man.ac.uk (David Lester)
10 Mar 2001 16:00:09 -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)
Re: detecting ambiguous grammars cfc@world.std.com (Chris F Clark) (2001-03-27)
Re: detecting ambiguous grammars genew@shuswap.net (2001-03-27)
[8 later articles]
| List of all articles for this month |

From: dlester@cs.man.ac.uk (David Lester)
Newsgroups: comp.compilers
Date: 10 Mar 2001 16:00:09 -0500
Organization: Dept Computer Science, University of Manchester, U.K.
References: 01-02-080 01-03-020 01-03-032
Keywords: parse
Posted-Date: 10 Mar 2001 16:00:09 EST

Thant Tessman <thant@acm.org> writes:
> 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?


If you'd like a context-free grammar against which to try using your
system in deciding ambiguity, how about:


S -> A | B


A -> x A x | x


B -> B_0 B_0


...
B_i -> B_{i+1} B_{i+1}
...


B_n -> x


The language is: "x(xx)* | x^(2^(n+1))". The grammar is not ambiguous
(but not LR(1), or anything else useful either).


Notice that one subtle change, leads to ambiguity after 1+2^(n+1)
terminals have been considered.


S -> A | B


A -> x A x | x


B -> B_0 B_0 x /* change on this line */


...
B_i -> B_{i+1} B_{i+1}
...


B_n -> x


The initial sequence of an string with an ambiguous parse, grows
exponentially with the size of the grammar.


HTH


---
David Lester.


ps You could also have fun with B -> x B x | /* NULL */


Post a followup to this message

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