Re: Ambiguities from Special-Case Productions

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

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