Solve shift/reduce conflict across rules-CodePudding

I'm trying to learn bison by writing a simple math parser and evaluator. I'm currently implementing variables. A variable can be part of a expression however I'd like do something different when one enters only a single variable name as input, which by itself is also a valid expression and hence the shift reduce conflict. I've reduced the language to this:

%token <double> NUM
%token <const char*> VAR

%nterm <double> exp

%left ' '
%precedence TWO
%precedence ONE

%%

input:
  %empty
| input line
;

line:
  '\n'
| VAR '\n' %prec ONE
| exp '\n' %prec TWO
;

exp:
  NUM
| VAR %prec TWO
| exp ' ' exp   { $$ = $1   $3;      }
;

%%

As you can see, I've tried solving this by adding the ONE and TWO precedences manually to some rules, however it doesn't seem to work, I always get the exact same conflict. The goal is to prefer the line: VAR '\n' rule for a line consisting of nothing but a variable name, otherwise parse it as expression.

For reference, the conflicting state:

State 4

    4 line: VAR . '\n'
    7 exp: VAR .  [' ', '\n']

    '\n'  shift, and go to state 8

    '\n'      [reduce using rule 7 (exp)]
    $default  reduce using rule 7 (exp)

CodePudding user response：

Precedence comparisons are always, without exception, between a production and a token. (At least, on Yacc/Bison). So you can be sure that if your precedence level list does not contain a real token, it will have no effect whatsoever.

For the same reason, you cannot resolve reduce-reduce conflicts with precedence. That doesn't matter in this case, since it's a shift-reduce conflict, but all the same it's useful to know.

To be even more specific, the precedence comparison is between a reduction (using the precedence of the production to be reduced) and that of the incoming lookahead token. In this case, the lookahead token is \n and the reduction is exp: VAR. The precedence level of that production is the precedence of VAR, since that is the last terminal symbol in the production. So if you want the shift to win out over the reduction, you need to declare your precedences so that the shift is higher:

%precedence VAR
%precedence '\n'

No pseudotokens (or %prec modifiers) are needed.

This will not change the parse, because Bison always prefers shift if there are no applicable precedence rules. But it will suppress the warning.