Re: Grammar ambiguity (Torben AEgidius Mogensen)
11 Mar 2000 13:28:30 -0500

          From comp.compilers

Related articles
[9 earlier articles]
Re: grammar ambiguity (2000-02-21)
Re: grammar ambiguity world! (Chris F Clark) (2000-02-27)
Re: Grammar ambiguity (Joachim Durchholz) (2000-02-27)
Re: grammar ambiguity (Joachim Durchholz) (2000-02-27)
Re: Grammar ambiguity (Jocelyn Coulmance) (2000-03-03)
Grammar ambiguity (Vassilis Kostakos) (2000-03-06)
Re: Grammar ambiguity (2000-03-11)
Re: Grammar ambiguity (Rodrigo Augusto Barbato Ferreira) (2000-03-11)
| List of all articles for this month |

From: (Torben AEgidius Mogensen)
Newsgroups: comp.compilers
Date: 11 Mar 2000 13:28:30 -0500
Organization: Department of Computer Science, U of Copenhagen
References: 00-03-057
Keywords: parse

"Vassilis Kostakos" <> 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 (

Post a followup to this message

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