Re: syntactic completion

[Vincent Zweije]

On Fri, Jul 30, 2004 at 07:11:26PM +0200, Hans Aberg 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.

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.