Re: detecting ambiguous grammars

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 */

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