Re: Is a contextfree Grammar ambiguous ?

Martin asked:


> Does an algorithm to decide whether a context free grammar is
> ambiguous exist ? If yes, can it state which productions lead the
> grammar to be ambiguous ?


There is a little semantic nit with this question, but for the
question you are trying to ask is probably yes.


The semantic nit is that by definition a context free grammar is
unambiguous. That is, if your grammar is ambiguous it is not a
context free grammar.


So, the question you are trying to ask is probably more like, is there
an algorithm to decide whether a grammar defined in [E]BNF is a
context free grammar (and thus unambiguous) or not.


To my knowledge that answer is still yes and no.


The classes of LL(k) and LR(k) grammars have well-known algorithms
that determine inclusion. If those algorithms accept your grammar,
you know that the grammar is unambiguous. If the algorithms do not
accept your grammar, they can report a conflict that gives the two
productions the grammars cannot resolve. Many of the conflicts will
be the result of your grammar having an ambiguity related to the
productions mentioned.


Unfortunately, some of the conflicts may be false-positives--in that
your grammar is not actually ambiguous, but is not parseable with the
technology that you are testing it with. Here, we need a precise
definition to make this clear. An ambiguous grammar is one which has
two parses for some sentence; visualize this as two parse trees. A
conflict is a report that the particular algorithm cannot generate a
finite-state machine to match some input to a single parse tree. Now,
if there are two parse trees, the reason for this is obvious.
However, sometimes the algorithm will not be able to generate an
appropriate FSM even when the grammar is unambiguous. The reason for
that is tied up with what steps the FSM is allowed to take and what
auxilliary data the FSM is allowed to use. The LL and LR algorithms
all generate FSM's that recognize the input left-to-right and there
are context free grammars that need right-to-left matching.


There are related classes, the LL(oo) and LR(oo) grammars, that
researchers are defining algorithms for, and in that sense still
defining what is meant by these names. In addition, there are other
approaches to generalized context free parsing. It is my belief that,
there is a definition of LR(oo) which will accept all conflict free
grammars, and report exactly the ambiguities in grammars which are
present in the grammar. However, I have been working on the algorithm
off-and-on for years and there are still problems in its memory
consumption, error reporting, et. al. that make it unsuitable for
naive use.


> If not, what is in case of epsilon-free grammars or/and in case of
> operator-grammars . . . .


I don't know whether either of these conditions on a grammar help
guarantee that a grammar is unambiguous or make it easier to test. My
gut feel is that they are irrelevant, but that's only from knowing one
approach to the problem. It is possible, that those conditions help
one transform a grammar into a normal form and using normal form to
test ambiguity. However, once one starts permutting the grammar, to
my mind one is not testing the original grammar for ambiguity, but
instead testing the language the grammar represents. There are nice
simple cases where an ambiguous grammar is used to represent an
unambiguous language and at times that makes a difference.


-Chris Clark
************************************************************************
Compiler Resources, Inc. email: cfc@world.std.com
3 Proctor St. http://world.std.com/~compres
Hopkinton, MA 01748 phone: (508) 435-5016
USA 24hr fax: (508) 435-4847

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