Re: detecting ambiguous grammars

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

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