Re: syntactic completion

[Hans Aberg]

At 19:38 +0200 2004/07/30, Vincent Zweije wrote:
>> At 10:20 +0200 2004/07/30, Vincent Zweije wrote:
>> >> One problem with the LALR(1) algorithm is that rather
>> >> than indicating an error right away, it may introduce a
>> >> $default symbol, representing all remaining token in the
>> >> grammar. It will then reduce, and the error will be
>> >> discovered in a later state. This happens because of the
>> >> technique used to compact LR(1). It could happen that a
>> >> LR(1) parser is better for this kind of tweaks, but Bison
>> >> does not support that (yet).
>> >
>> >To be pedantic, I don't think the compaction problem had
>> >anything to do with LALR versus LR. Doesn't really matter for
>> >the problem at hand though.
>>
>> You say this, and on the same time, you indicate what might
>> cause a problem below.
>
>Yes. This is not a contradiction, because the LR->LALR
>compaction and the $default-symbol compaction are two different
>techniques.

So you merely wanted to point out that the $default-compaction technique as
such is not a part of LALR(1)-compaction. (I did not look too carefully at
this particular point; just assumed it was a part of LALR(1).)

We agree though, both (as you say below), that the LR(1) states are the
ones with the correct 1-lookahead sets for a completion, and only
compaction techniques that are able to restore that set will give formally
correct results. One may get an acceptable results also with other
algorithms, such as LALR(1) -- but be prepared if the enduser complains
that certain error tokens appear in the completion lists!

In general, though, there seems to be a growing need for more exact error
recovery, which suggests Bison would benefit to in the future support
LR(1). This completions request is just one in that batch.

>On the other hand, both rely on the fact that in LALR parsing,
>it is permissible to do reductions when the lookahead token in
>invalid, because it will not lead to accepting erroneous input.
>There's always a shift that remains to be done before the input
>is accepted -- reductions are not going to take away the
>errorneous lookahead token or make it valid.
>
>However, both will give problems for determining token
>completions. If you insist on correct completions only, LR
>parsing is your only choice. In the short term, LALR probably
>gives acceptable results.
>
>> So a state may have a set of lookahead tokens that for some
>> reason isn't really valid for the state. If it is an error
>> token, in LR(1), that will always be detected immediately,
>> but in LALR(1), due to compaction, the error may instead be
>> indicated be indicated as a valid token: Only in a later
>> state, a few reductions later, will one reach a state in
>> which it is labelled an error token.
>>
>> So if you are in such a state, and uses the valid lookahead
>> tokens to indicate the set of valid completions, in fact,
>> some of them obviously are not. A user who then enters a
>> seemingly valid token from the completion list, will get a
>> seemingly inexplicable error.
>
>Exactly.
>
>Ciao.                                                  Vincent.
>
>
>_______________________________________________
>address@hidden http://lists.gnu.org/mailman/listinfo/help-bison