Re: grammars

Buddy wrote:


> Can all ambiguous grammars be changed into unambiguous grammars?
>
> [Well, sure, you can delete stuff until it's not ambiguous any more.
> But I presume the question you're asking is whether there's always an
> unambiguous grammar that recognizes the same language as an ambigous
> one. -John]


And if that's what Buddy meant and if he's talking about context-free
grammars, then the answer is no. An example is given by the following
context-free grammar for the language of all strings comprising some
'a's followed by some 'b's followed by some 'c's subject to the
constraint that either the number of 'a's is equal to the number of
'b's or the number of 'b's is equal to the number of 'c's (or possibly
all three numbers are equal).


                S = AB, C | A, BC;
                AB = | `a`, AB, `b`;
                C = | C, `c`;
                A = | A, `a`;
                BC = | `b`, BC, `c`;


Languages like this are called inherently ambiguous. They are all
likely to have this kind of flavour, because the problem arises from
the very limited ability of a push-down automaton to count.


In parser design, what tends to matter more than the theory is the
amount of effort involved in trying to find an unambiguous grammar for
awkward constructs that may or may not be inherently ambiguous
theoretically. In practice, it is typically acceptable to parse using
a grammar for a slightly larger language (in the above example the
language you get by dropping the numerical constraints) and then check
that the phrase you parsed belongs to the desired sublanguage after
parsing.


Rob.

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