bison shift/reduce 与相同的token冲突出现在相同的规则中

Question

鉴于以下野牛规则，我不明白为什么 INTO 令牌可以在相同的野牛状态下同时移动和减少并导致 1 shift/reduce 冲突。如何解决？首都都是代币。

select_condition: SELECT opt_select fields
                  FROM from_clause
                  opt_into_table
                  opt_into_graph
                  opt_where_expr

opt_into_table: { $$ = 0; }
              | INTO TABLE IDENTIFIER { $$ = 1; }

opt_into_graph: { $$ = 0; }
              | INTO GRAPH IDENTIFIER { $$ = 1; }

////// from the sqlparser.output //////////////////

INTO  shift, and go to state 66

INTO      [reduce using rule 31 (opt_into_table)]
$default  reduce using rule 31 (opt_into_table)

opt_into_table  go to state 67

Answer 1

这里的冲突是，当解析器看到INTO跟在from_clause后面时，有两种可能：

它是序列INTO TABLE IDENTIFIER中的第一个标记。在这种情况下，它应该被移动（在减少from_clause之后）。
它是序列INTO GRAPH IDENTIFIER中的第一个标记。在这种情况下，需要在移动 INTO 之前减少一个空的 opt_into_table。

因此存在 shift/reduce 冲突，因为此时不知道是否需要减少空的 opt_into_table 非终结符。再加上一个先行符号，答案就很清楚了，所以所写的文法是 LR(2)。不幸的是，bison 不生成 LR(2) 解析器。

随着语义规则的编写（在两种情况下都忽略 IDENTIFIER 的语义值），您可以使用一个简单的实用修复：将两个可选短语组合成一个非终结符，从而创建一个位掩码而不是两个单独的布尔值：

opt_intos: INTO TABLE IDENTIFIER { $$ = 1; }
         | INTO GRAPH IDENTIFIER { $$ = 2; }
         | INTO TABLE IDENTIFIER INTO GRAPH IDENTIFIER { $$ = 3; }

但这可能不是最好的解决方案，因为在某些时候您可能会关心 IDENTIFIERs。

另一种（也有点难看）的可能性是删除 epsilon 产生式，方法是将它们扩展为四个不同的产生式 select_condition:

select_condition: SELECT opt_select fields
                  FROM from_clause
                  into_table
                  into_graph
                  opt_where_expr
                | SELECT opt_select fields
                  FROM from_clause
                  into_graph
                  opt_where_expr
                | SELECT opt_select fields
                  FROM from_clause
                  into_table
                  opt_where_expr
                | SELECT opt_select fields
                  FROM from_clause
                  opt_where_expr

into_table      : INTO TABLE IDENTIFIER { $$ = 1; }

into_graph      : INTO GRAPH IDENTIFIER { $$ = 1; }

另一种选择是在词法分析器中将 INTO TABLE 和 INTO GRAPH 组合成单个标记。（对于类似 SQL 的语言，这可能不会在一般情况下起作用，因为关键字是上下文相关的。但在您的情况下它可能是可行的。）

或者您可以保留语法原样，并使用 %glr-parser.

bison shift/reduce 与相同的token冲突出现在相同的规则中

bison shift/reduce conflict with the same token appear in the same rule

reduce

bison

shift