Shift/reduce conflict despite precedence rules

Question

The language I'm writing a parser for has three constructs that are relevant here: the ord operator, represented by TOK_ORD, which casts character expressions into integer expressions, and [ ] and ., which are used for index and field access, respectively, just like in C.

Here's an excerpt from my precedence rules:

%right TOK_ORD
%left  PREC_INDEX PREC_MEMBER

My grammar has a nonterminal expr, which represents expressions. Here's some relevant snippets from the grammar (TOK_IDENT is a regular expression for identifiers defined in my .l file):

expr     : TOK_ORD expr                         { /* semantic actions */ }
         | variable                             { /* semantic actions */ }
         ;
variable : expr '[' expr ']' %prec PREC_INDEX   { /* semantic actions */ }
         | expr '.' TOK_IDENT %prec PREC_MEMBER { /* semantic actions */ }
         ;

Here's information about the shift/reduce conflict from the bison output file:

state 61

42 expr: expr . '=' expr
43     | expr . TOK_EQ expr
44     | expr . TOK_NE expr
45     | expr . TOK_LT expr
46     | expr . TOK_LE expr
47     | expr . TOK_GT expr
48     | expr . TOK_GE expr
49     | expr . '+' expr
50     | expr . '-' expr
51     | expr . '*' expr
52     | expr . '/' expr
53     | expr . '%' expr
57     | TOK_ORD expr .
72 variable: expr . '[' expr ']'
73         | expr . '.' TOK_IDENT

'['  shift, and go to state 92
'.'  shift, and go to state 93

'['       [reduce using rule 57 (expr)]
'.'       [reduce using rule 57 (expr)]
$default  reduce using rule 57 (expr)

States 92 and 93, for reference:

state 92

72 variable: expr '[' . expr ']'

TOK_FALSE      shift, and go to state 14
TOK_TRUE       shift, and go to state 15
TOK_NULL       shift, and go to state 16
TOK_NEW        shift, and go to state 17
TOK_IDENT      shift, and go to state 53
TOK_INTCON     shift, and go to state 19
TOK_CHARCON    shift, and go to state 20
TOK_STRINGCON  shift, and go to state 21
TOK_ORD        shift, and go to state 22
TOK_CHR        shift, and go to state 23
'+'            shift, and go to state 24
'-'            shift, and go to state 25
'!'            shift, and go to state 26
'('            shift, and go to state 29

expr       go to state 125
allocator  go to state 44
call       go to state 45
callargs   go to state 46
variable   go to state 47
constant   go to state 48


state 93

73 variable: expr '.' . TOK_IDENT

I don't understand why there is a shift/reduce conflict. My grammar clearly defines index and field access to have higher precedence than ord, but that doesn't seem to be enough.

In case you're wondering, yes, this is homework, but the assignment has already been turned in and graded. I'm going back through and trying to fix shift/reduce conflicts so I can better understand what's going on.

Answer 1

Precedence resolution of shift/reduce conflicts works by comparing the precedence of a production (or reduction, if you prefer) with the precedence of a token (the lookahead token).

This simple fact is slightly obscured because bison sets the precedence of a production based on the precedence of the last token in the production (by default), so it appears that precedence values are only being assigned to tokens and the precedence comparison is between token precedences. But that's not accurate: the precedence comparison is always between a production (which might be reduced) and a token (which might be shifted).

As the bison manual says:

…the resolution of conflicts works by comparing the precedence of the rule being considered with that of the lookahead token. If the token's precedence is higher, the choice is to shift. If the rule's precedence is higher, the choice is to reduce.

Now, you define the precedence of the two variable productions using explicit declarations:

variable : expr '[' expr ']' %prec PREC_INDEX   { /* semantic actions */ }
         | expr '.' TOK_IDENT %prec PREC_MEMBER { /* semantic actions */ }

But those productions never participate in shift/reduce conflicts. When the end of either of the variable rules is reached, there is no possibility of shifting. The itemsets in which those productions can be reduced have no shift actions.

In the state which contains the shift/reduce conflict, the conflict is between the potential reduction:

 expr: TOK_ORD expr

and the possible shifts involving lookahead tokens . and [. These conflicts will be resolved by comparing the precedence of the TOK_ORD reduction with the precedences of the lookahead tokens . and [, respectively. If those tokens do not have declared precedences, then the shift/reduce conflict cannot be resolved using the precedence mechanism.

In that case, though, I would expect there to be a large number of shift/reduce conflicts in other states, where the options are to reduce a binary operator (such as expr: expr '+' expr) or to shift the ./[ to extend the rightmost expr. So if there are no such shift/reduce conflicts, the explanation is more complicated and I'd need to see a lot more of the grammar to understand it.