Re: detecting ambiguous grammars

Thant Tessman <thant@acm.org> wrote:


> I'm questioning whether the advantage of being able to use a grammar
> that isn't necessarily LR(1) outweighs the disadvantage of knowing
> unambiguously whether a grammar is unambiguous.


In a programming language, the programmer must be able to express his
intentions in source code, other programmers must be able to read and
understand the source code, and the compiler must be able to read and
understand the source code.


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.


If the compiler doesn't detect that there is ambiguity then the
programmer has a real problem: You cannot trust the compiler, because
if you wrote an ambiguous program unintentionally the compiler could
recognise it different than you intended.


People often use a more or less complicated parser generator to parse
a language defined by a grammar. Most parser don't use backtracking,
instead the parser collects enough information to make a decision,
then makes that decision. Obviously if you have an ambiguous grammar
then even reading the whole program doesn't give the parser enough
information to decide how to parse the program, at least in some
cases. So a parser generator trying to create a parser without
backtracking for an ambiguous grammar will either fail to create the
parser, or will create a parser that can sometimes fail.


You could define LR(1) as the class of grammars for which a certain
parser generator will be able to create a parser. You could write a
parser generator that will succeed for a larger class of grammars, but
will fail for some grammars and will definitely fail for ambiguos
grammars. What you cannot do is write a parser generator that will
succeed for all unambigous grammars and that will stop and admit
failure for all ambiguous grammars.

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