Bison代码中的shift/reduce冲突在哪里?

Question

我的bison代码中有一个Shit/reduce冲突:

expression : LBRACKET expression RBRACKET  {$$ = $2;}
       | fct_call                          {}
       | operand                           {}    
       | expression operator_arith expression   {$$ = new NBinaryOperation(*$1, $2, *$3);}
       ;

我可以这样写:

expression : LBRACKET expression RBRACKET compexp  // {$$ = $2;}
       | fct_call_in_exp compexp               {}
       | operand compexp                       {}
       ;
compexp : /* empty */     {/* Do smthg */}
    | operator_arith expression   {/* Do smthg */}

但是它需要在我的Node结构中做很多修改。因此，我正在寻找一种新的方法来解决它。你能帮我吗?

祝您愉快!

Answer 1

这是不明确的:

expression : expression operator_arith expression

的问题是，如果您有多个中缀运算符(例如:A + B * C)，它可以先解析左操作符(远离解析树的根)或先解析右操作符。

您需要决定如何解决该歧义，并将其添加到解析器中。通常的方法是定义优先级，说某些操作符的优先级比其他操作符高(因此它们应该总是首先被解析)，并且对于相同级别的操作符，左操作符或右操作符应该首先被解析(通常指左递归和右递归)。

有两种消除歧义的方法。您可以引入更多的非终结符(每个优先级一个)并使用它们来编写语法(有许多示例语法使用term和factor以及其他相关的东西来表示这些额外的级别)。或者，您可以使用在%left和%right声明中构建的bison来设置各种操作符标记的优先级，并为每个产品提供匹配的优先级(通过直接使用标记或使用%prec)。为了给它们不同的优先级，您至少需要为每个优先级级别提供单独的结果。

Bison的手册中有后一种样式的例子