Why does my ternary operator cause a shift-reduce conflict?

Question

The following is my grammar:

arithmetic_expression : expression + expression
                      | expression - expression

expression            : constant
                      | ID
                      | arithmetic_expression
                      | ternary

ternary               : expression ? expression : expression

I receive a shift-reduce error in this state:

state 126

    (19) ternary -> expression QUESTION_MARK expression COLON expression .
    (27) arithmetic_exp -> expression . PLUS expression
    (28) arithmetic_exp -> expression . MINUS expression
    (19) ternary -> expression . QUESTION_MARK expression COLON expression

  ! shift/reduce conflict for PLUS resolved as shift
  ! shift/reduce conflict for MINUS resolved as shift
  ! shift/reduce conflict for QUESTION_MARK resolved as shift

    PLUS            shift and go to state 86
    MINUS           shift and go to state 88
    QUESTION_MARK   shift and go to state 85

  ! PLUS            [ reduce using rule 19 (ternary -> expression QUESTION_MARK expression COLON expression .) ]
  ! MINUS           [ reduce using rule 19 (ternary -> expression QUESTION_MARK expression COLON expression .) ]
  ! QUESTION_MARK   [ reduce using rule 19 (ternary -> expression QUESTION_MARK expression COLON expression .) ]

I believe the conflict is that

true ? 1 : false ? 3 : 2

can be interpreted as true ? 1 : (false ? 3 : 2) or (true ? 1 : false) ? 3 : 2.

I have set the precedence for +, and - as left associative and higher level than ? (which I set to right associativity).

What am I doing wrong?

Answer 1

If I understand you correctly, you did the following:

%left '+' '-'
%right '?'

%%

arithmetic_expression : expression + expression
                      | expression - expression
                      ;
ternary               : expression ? expression : expression
                      ;

That won't work, because you haven't told bison what the precedence of the ternary production is.

To resolve shift-reduce conflicts, bison compares the precedence of the production which might be reduced with the precedence of the terminal which might be shifted. You've declared the precedence of the terminals '+', '-' and '?', and the precedence of both productions in arithmetic_expression, but not the precedence of the production in ternary.

Quoting from the bison manual, emphasis added:

each rule gets its precedence from the last terminal symbol mentioned in the components.

That's very subtle and you won't be the first person who didn't notice.

Solutions: either declare the precedence of the terminal : or add %prec '?' to the production in ternary.

Answer 2

Exaclty - you didn't specify associativity.

In C, the grammar says:

conditional_expression = logical_or_expression [ '?' expression ':' conditional_expression ];

so I believe you want something like

conditional_expression = arithmetic_expression [ '?' expression ':' conditional_expression ];

if you want a C-like behavior (and thus right associativity, among other properties).