parsing - 为什么我的三元运算符会导致移位减少冲突？

Question

以下是我的语法:

arithmetic_expression : expression + expression
                      | expression - expression

expression            : constant
                      | ID
                      | arithmetic_expression
                      | ternary

ternary               : expression ? expression : expression

我在这种状态下收到一个 shift-reduce 错误:

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 .) ]

我认为冲突在于<​​/p>

true ? 1 : false ? 3 : 2

可以解释为 true 吗？ 1 : (false ? 3 : 2) 或 (true ? 1 : false) ? 3 : 2。

我已经将 + 和 - 的优先级设置为左结合并且比 ? 更高级别(我将其设置为右结合) .

我做错了什么？

Answer 1

如果我没理解错的话，你做了以下事情:

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

%%

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

那是行不通的，因为您还没有告诉 bison 三元 产生式的优先级是什么。

为了解决 shift-reduce 冲突，bison 比较可能被减少的产生式的优先级与可能被移动的终端的优先级。您已经在 arithmetic_expression 中声明了终结符“+”、“-”和“?”的优先级，以及两个产生式的优先级，但没有在 ternary< 中声明产生式的优先级.

引用野牛手册，重点补充:

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

这非常微妙，您不会是第一个没有注意到的人。

解决方案:声明终端的优先级 : 或将 %prec '?' 添加到 ternary 的产生式中。