Re: detecting ambiguous grammars

Christian Bau wrote:


[...]


> If you wrote a program in a language defined by an ambigous
> grammar, what can happen: Either the compiler will find all
> possible ways to parse your code (or at least find out if
> there are two or more ways to parse the code) or it won't.
> In the first case, you could still use the language for
> programming, as long as you avoid programs that are actually
> ambiguous. If the compiler actually detects and rejects all
> ambiguous programs then you have the strange effect that the
> language that it accepts is actually unambiguous, but
> different from the language defined by the grammar.


[...]


There is another option. In lex, if a string of letters matches more
than one rule, the rule that occurs first in the rule section is
chosen. A grammar specification could work the same way. Although
ambiguities wouldn't be explicitly enumerated, it is always clear how
to disambiguate.


The interesting question is whether such a grammar specification would
tend to match the programmer's intentions. A bigger worry is that
grammar ambiguities may be a sign that there are perfectly valid
semantic constructs within a language for which there may be no
syntactic expression. To rephrase my question: Does the advantage of
addressing ambiguities up front outweigh the advantage of potentially
more expressive grammars? (In practice, it doesn't seem like languages
are designed with these considerations in mind. Nevertheless it is the
argument I'm having with myself as I get my DFA-generating code into
shape...)


-thant
[I've used Earley parsers that preferred the derivation that used fewer
rules, so you could add special case rules that overrode general ones.
It worked OK. -John]

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