Re: Ambiguities from Special-Case Productions

Hi DoDi,


Hi all,


It was not my intention to further discuss the responses I received but DoDi
makes an interest point.


Before that, let me remind you that a program that decides whether a
sentence is accepted or rejected is called recognizer. (I think ;-)


DoDi wrote:
> It should be obvious that the number of possible parse trees
> explodes with the length of the input sequence


Yes it obvious but I believe we should try/be able to develop tools that are
capable to handle even the worst cases, as efficiently as possible.


Let me explain.


I said that according to the grammar stated, the string "c sub c sup c" has
three interpretations (3 parse trees).


If we extend the initial string to "c sub c sup c sub c" then it has seven
(7 parse trees; I think).


Now, the initial string is E (the five first tokens).


Thus, we get three of the seven trees due to the Item "E-> E . sub E" (the
E left of the dot represents the initial string).


We could represent then the tree instances of E with one, (in example as
children of one node; special node) and as a result we will end the parsing
process with 5 trees (I think). The idea is very old. So far we haven't
disambiguated the part of the string processed.


What is the gain of such improvements?


DoDi wrote:
> 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 ;-)


In a real world example the disambiguation may not be clear until we read a
whole sentence, or even worst, more sentences.


Probably, a Robot could then avoid dummy questions ;-)


Thanks.


Ev. Drikos


(Note for all: In my original question I forgot a detail. I am interested
in GLR parsers that support extensive BNF and therefore are capable to
handle variable length productions.)


"Hans-Peter Diettrich" <DrDiettrich@compuserve.de> wrote
> 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.