RE: syntactic completion

[Hans Aberg]

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.

>Another problem with LALR is that, compared to LR, it will join
>parser states that have the same items, without considering the
>lookahead tokens.
>
>Consequently, an LALR parser state may have spurious lookahead
>tokens, brought in from another LR state, that are really valid
>only if you get into the state through a different path at parse
>time. It happens relatively rarely, though.

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.

  Hans Aberg