Re: Ambiguities from Special-Case Productions

Hans-Peter Diettrich <DrDiettrich@compuserve.de>
17 Sep 2005 13:55:38 -0400

          From comp.compilers

Related articles
Ambiguities from Special-Case Productions drikosv@otenet.gr (Evangelos Drikos) (2005-09-14)
Re: Ambiguities from Special-Case Productions cleos@nb.sympatico-dot-ca.remove (Cleo Saulnier) (2005-09-15)
Re: Ambiguities from Special-Case Productions boldyrev@cgitftp.uiggm.nsc.ru (Ivan Boldyrev) (2005-09-17)
Re: Ambiguities from Special-Case Productions DrDiettrich@compuserve.de (Hans-Peter Diettrich) (2005-09-17)
Re: Ambiguities from Special-Case Productions drikosv@otenet.gr (Evangelos Drikos) (2005-09-22)
| List of all articles for this month |

From: Hans-Peter Diettrich <DrDiettrich@compuserve.de>
Newsgroups: comp.compilers
Date: 17 Sep 2005 13:55:38 -0400
Organization: Compilers Central
References: 05-09-049
Keywords: parse

Evangelos Drikos wrote:


> I found this grammar in a popular compilers book (Ambiguities from
> Special-Case Productions):
>
> E -> E sub E sup E
>
> E -> E sub E
>
> E -> E sup E
>
> E -> { E }
>
> E -> c
>
> I think according to this grammar the string "c sub c sup c" has three
> interpretations (3 parse trees).
>
> Which GLR Parser should I select to take all the correct interpretations of
> such a string?


IMO the first question should be: what are "correct" interpretations, in
contrast to "possible" interpretations?


As long as you don't specify the semantics of the grammar, it doesn't
matter how a parser interprets the sentence, because it only has to
decide whether the sentence is accepted (has at least one derivation),
or is rejected.


If you want different semantics, then you'll have to disambiguate the
grammar, or you must be prepared to handle multiple parse trees. The
procedures and the parser generator have to be selected accordingly.


Apart from this example, in real life you should consider what you want
to do with the output of the parser. It should be obvious that the
number of possible parse trees explodes with the length of the input
sequence, so that the practical goal will impose some restrictions on
the procedures. In most cases one would try to disambiguate the grammar,
whereas a robot should answer an ambigous entry with "Sorry, I don't
understand what you mean" - with no need to produce all possible parse
trees before ;-)


DoDi


Post a followup to this message

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