Precedence not working in shift/reduce error

Learning
1

I am trying to write grammar supporting array and pointer. Here is a minimal code that can produce shift/reduce error

%token Ident
%token True
%token False
%token L_paren R_paren (* "(" and ")" *)
%token L_bracket R_bracket (* "[" and "]" *)
%token Dot Arrow Star
%token Deref Explicit_parenthesis Arr_sub 

%left Star 
%right Deref
%nonassoc Arr_sub Arrow Dot

(* Return type is a placeholder *)
%type<int> lvalue

%start lvalue

%%

lvalue : 
  | ident = Ident; {}
  | Star; lv = lvalue; %prec Deref {}
  | lv = lvalue; L_bracket; e = exp; R_bracket; %prec Arr_sub {}
  | L_paren; lv = lvalue; R_paren;{}
;

exp :
  | True; {}
  | False; {}
;

%%

The array access [] has higher priority than dereference operator * in my grammar. However, there is error indicating the parser still cannot figure out what to do when stack is Star lvalue and lookahead is [. I am expecting it to shift because array access should be executed first, and then dereference.

You can use command menhir -v test.mly to generate this error, which is


** Conflict (shift/reduce) in state 11.
** Token involved: L_bracket
** This state is reached from lvalue after reading:

Star lvalue

** The derivations that appear below have the following common factor:
** (The question mark symbol (?) represents the spot where the derivations begin to differ.)

lvalue 
(?)

** In state 11, looking ahead at L_bracket, reducing production
** lvalue -> Star lvalue
** is permitted because of the following sub-derivation:

lvalue L_bracket exp R_bracket // lookahead token appears
Star lvalue . 

** In state 11, looking ahead at L_bracket, shifting is permitted
** because of the following sub-derivation:

Star lvalue 
     lvalue . L_bracket exp R_bracket

Is my precedence rule incorrect? I have no idea why it is not working at all :confused:

2

As far as I know, the %prec annotation is only used when considering a “reduce” conflict. When considering a “shift” conflict, the parser just looks at the next token.

In your case, the parser is trying to understand what to do with the sequence Star lvalue . L_bracket. It should either reduce with precedence Deref at the dot, or it should shift using token L_bracket. Since you have not told the parser how Deref and L_bracket are ordered, it does not know how it should solve the conflict.

In other words, the precedence Arr_sub is useless here because the corresponding production rule is the “shift” part of the conflict, not the “reduce” part. You should just give a precedence to L_bracket.

2 Likes
3

Thank you for you reply! I tried to provide precedence for L_bracket and it works!

For those who may encounter this issues in the future, I’d like to elaborate more for the solution. And thank @silene again for the great solution and explanation!

I thought I can associate each rule with a %prec so they can solve some conflicts. In fact, the original precedence for each rule is decided by the rightmost terminal. Once we set the %prec TOKEN, priority of this rule is changed to the priority of TOKEN. That’s why @silene says %prec is only used when considering a “reduce-reduce” conflict.

However, this does not mean the priority cannot be used to solve “shift-reduce” conflict. When the parser find both shift and reduce is legal, it will check the priority of reduce, which is determined by the right-most terminal, and the shift token. So once we add priority between these two, we can solve “shift-reduce” conflict. Bravo!