Re: Grammar ambiguity

"Vassilis Kostakos" <ma9vk@bath.ac.uk> writes:


>Would it be correct to say that an ambiguous grammar is a "wrong" one?
>I believe that one language can be described by more than one grammar
>(at least that's what I was taught). Therefore, we can change our
>ambig grammar to an unambigious one. However, does this mean that
>any ambiguous grammar is "wrong"?


Not all ambiguous grammars can be rewritten to unambiguous grammars.
In other words, there are context free languages for which there exist
no unambiguous grammar. An example is the language


    {a^m b^m c^n | m,n>0} U {a^m b^n c^n | m,n>0}


where "a^m" means "'a' repeated m times".


>[Nope. You might have a situation where any of the ambiguous parses
>are acceptable, or external rules to choose which of a set of parses
>to use. -John]


The latter is often used with LR parser generators, where external
precedence rules are used to eliminate ambiguities in the parse
table. In this case, the grammar could be rewritten to an unambiguous
grammar, but it is more convenient to use rules instead: It makes the
grammar more readable and it is easier to change the precedence rules
later in the design.


Precedence rules must, however, be used with care. Not all conflicts
in parse tables are due to ambiguity, and eliminating all conflicts
may cause some legal strings to be rejected. Even when the conflicts
are caused by ambiguity, they can not always be resolved using simple
local rules. An example is the inherently ambiguous language above.


Torben Mogensen (torbenm@diku.dk)

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