Re: Grammar ambiguity

Rodrigo Augusto Barbato Ferreira <rodrigo.ferreira@dcc.unicamp.br>
11 Mar 2000 13:31:09 -0500

          From comp.compilers

Related articles
[10 earlier articles]
Re: grammar ambiguity world!cfc@uunet.uu.net (Chris F Clark) (2000-02-27)
Re: Grammar ambiguity joachim.durchholz@halstenbach.com.or.de (Joachim Durchholz) (2000-02-27)
Re: grammar ambiguity joachim.durchholz@halstenbach.com.or.de (Joachim Durchholz) (2000-02-27)
Re: Grammar ambiguity j.coulmance@itecor.com (Jocelyn Coulmance) (2000-03-03)
Grammar ambiguity ma9vk@bath.ac.uk (Vassilis Kostakos) (2000-03-06)
Re: Grammar ambiguity torbenm@diku.dk (2000-03-11)
Re: Grammar ambiguity rodrigo.ferreira@dcc.unicamp.br (Rodrigo Augusto Barbato Ferreira) (2000-03-11)
| List of all articles for this month |
From: Rodrigo Augusto Barbato Ferreira <rodrigo.ferreira@dcc.unicamp.br>
Newsgroups: comp.compilers
Date: 11 Mar 2000 13:31:09 -0500
Organization: Institute of Computing, University of Campinas, SP, Brazil
References: 00-03-057
Keywords: parse

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





Post a followup to this message

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