Re: Grammar ambiguity

Hi Vassilis,


It is better to say that an ambiguous grammar may not be suited,
rather than is wrong.


In language teory, an ambiguous grammar is just as useful as an
unambiguous one, that's because we want to describe a language and not
to apply the right interpretation to its instance strings.


Moreover, there are some context free languages that are inhenrently
ambiguous, that is, there is no unambiguous grammar to describe that
language.


The best known example is the language L below:


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


Pratically, ambiguity is more related to the parsing method you use
than the grammar itself. A unambiguous language may generate
conflicts if submited to a lr(1) parser generator, for instance. That
means that the language is not lr(1) and may not be useful in that
context.


However, sometimes the ambiguity of a grammar, regarding the parsing
method, does not denies its use. A well known example is the dangling
else construct which commonly is resolved in the expected way.


Best regards,
Rodrigo Augusto.


Vassilis Kostakos wrote:
>
> 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"?
> [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]


--
Rodrigo Augusto B. Ferreira
Computer Science Graduate, UFMG/BRAZIL

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