Re: Two problems with the GLR parsers

[Paul Hilfinger]

I have fixed the "Successful parse" problem.  However, for the problem
involving the location attributed to the error token, the behavior of
the yacc.c-derived parser looks awful suspicious to me.  

We see the following differences:

    18c18
    < line(address@hidden): error(@50) ';'
    ---
    > line(address@hidden): error(@30) ';'
    34c34
    < Freeing nterm line (address@hidden)
    ---
    > Freeing nterm line (address@hidden)

where the < line is what we are allegedly SUPPOSED to see.  The input
that is supposed to elicit this is

     x   x   x   x   x   x   ;
     0  10  20  30  40  50  60    
 
(locations are below).  The relevant part of the grammar is

    line:
          thing thing thing ';'
        | thing thing ';'
        | thing ';'
        | error ';'
        ;

    thing:   'x'

In other words, the first erroneous token is 30 and the last token thrown
away during recovery is 50.  Supposedly, it is the position of the
latter token that is supposed to be reported.  Why, exactly?  The
recovery algorithm is described as "pop the stack until error can be
pushed, push error, and then discard input until you can continue."
Why would that give 50 as the location of error, which was pushed
while at location 30?  

Examining yacc.c or turning on debugging output soon shows us why:

    ...
    state stack now 0 5 10
    Entering state 12
    Reading a token: Next token is token 'x' (address@hidden)
    Error: popping nterm thing (address@hidden)
    Error: state stack now 0 5 10
    Error: popping nterm thing (address@hidden)
    Error: state stack now 0 5
    Error: popping nterm thing (address@hidden)
    Error: state stack now 0
    Shifting error token, Entering state 1   ***
    Next token is token 'x' (address@hidden)
    Error: discarding token 'x' (address@hidden)
    Error: popping token error ()
    Error: state stack now 0
    Shifting error token, Entering state 1   ***
    Reading a token: Next token is token 'x' (address@hidden)
    Error: discarding token 'x' (address@hidden)
    Error: popping token error ()
    Error: state stack now 0
    Shifting error token, Entering state 1   ***
    Reading a token: Next token is token 'x' (address@hidden)
    Error: discarding token 'x' (address@hidden)
    Error: popping token error ()
    Error: state stack now 0
    Shifting error token, Entering state 1   ***
    Reading a token: Next token is token ';' ()
    Shifting token ';', Entering state 6
    Reducing by rule 6 (line 74), error ';' -> line
    ...

As the starred lines indicate, the error token is shifted 4 times!
Fortunately, the reduction is taken only once.  I'm not sure what to
make of this, so I'll ask around before I try to make glr duplicate
the behavior (or, of course, change input.at).

Paul Hilfinger