Default reductions

[Akim Demaille]

Hi Paul,

I'm afraid we _have_ to return to this debate about default
reduction.  A student of mine reported the following problem: the
simple calculator example exhibits a problem in the GLR parsers.

If you compile the following source from Charles,

calc.y
Description: Text document

as follows:

/tmp % bison calc.y -o calc.c --report=al                        nostromo 13:47
/tmp % gcc calc.c -o calc  -lm                                   nostromo Err 1
calc.c:1251: warning: initialization makes integer from pointer without a cast
calc.c:1251: warning: braces around scalar initializer
calc.c:1251: warning: (near initialization for `YYLEFTMOST_STATE.yyposn')
calc.c:1251: warning: initialization makes integer from pointer without a cast
calc.c: In function `yyrecoverParseError':
calc.c:1574: warning: comparison is always true due to limited range of data 
type

(these warnings are not serious problems, but of course I'll fix
them).

then you'll have the following problem:

 /tmp % echo '2*3' | ./calc                                       nostromo 13:49
 Reduced stack 0 by rule #1. Now in state 1.
 Read token NUM
 Shifted token NUM. Now in state #3
 Reduced stack 0 by rule #5. Now in state 8.
 Read token '*'
 Shifted token '*'. Now in state #13
 Read token NUM
 Shifted token NUM. Now in state #3
 Reduced stack 0 by rule #5. Now in state 20.
 Read token '\n'
 parse error

If you look at state 20:

state 20

    6 exp: exp . '+' exp
    7    | exp . '-' exp
    8    | exp . '*' exp  ['-', '+', '*', '/', '\n', ')']
    8    | exp '*' exp .  ['-', '+', '*', '/', '\n', ')']
    9    | exp . '/' exp
   11    | exp . '^' exp

    '^'  shift, and go to state 15

    $default  reduce using rule 8 (exp)
    Conflict between rule 8 and token '-' resolved as reduce ('-' < '*').
    Conflict between rule 8 and token '+' resolved as reduce ('+' < '*').
    Conflict between rule 8 and token '*' resolved as reduce (%left '*').
    Conflict between rule 8 and token '/' resolved as reduce (%left '/').
    Conflict between rule 8 and token '^' resolved as shift ('*' < '^').

you can see that on $default, which includes \n, we should reduce 8.
Yacc.c does reduce here.  The lookaheads also clearly demonstrate that
`\n' is perfectly valid here.

In a following message, I will explain why I can't address it now :(