具有相同令牌的bison移位/减少冲突出现在同一规则中

Question

给定以下bison规则，我不明白为什么INTO令牌可以在相同的bison状态下进行移位和减少，并导致1个移位/减少冲突。如何修复？首都都是象征。

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后面时，有两种可能性：

• 它是序列CCD_ 3中的第一个令牌。在这种情况下，它应该被移位（在减少from_clause之后）。

• 它是序列CCD_ 5中的第一个令牌。在这种情况下，在INTO移位之前，需要减少空的opt_into_table。

因此存在移位/减少冲突，因为在这一点上不知道是否需要减少空的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。

另一种（也有点难看）的可能性是通过创建将ε产物扩展为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; }

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

或者你可以让语法保持原样，使用%glr-parser。