shift-reduce与表达式的冲突

Question

我正在为我自己设计的一种完整的编程语言编写语法。这种语言有几种类型的表达式，它们在不同的情况下以不同的方式组合在一起。我有一个很好的想法，我希望它如何工作，但我在分解shift/reduce和reduce/reduce冲突时遇到了麻烦。我使用的是Xubuntu 16.04下的Bison v3.0.4。完整的语法(包括*.output文件)可以在我的github的https://github.com/chucktilbury/Simple1上看到(参见expressions.y s.y和expressions.output)。

我已经用它走得相当远了。我知道这不是最好的，但我正在学习。如果有人能给我一些建议来帮助我摆脱困境，我将不胜感激。

以下是语法中给我带来问题的部分的片段：

%{
#include <stdio.h>
%}

%token OPAREN_TOK CPAREN_TOK OCURLY_TOK CCURLY_TOK OBOX_TOK CBOX_TOK
%token COMMA_TOK SCOLON_TOK DOT_TOK COLON_TOK 
%token CLASS_TOK FUNC_TOK PRIVATE_TOK PUBLIC_TOK PROTECTED_TOK
%token CREATE_TOK DESTROY_TOK IMPORT_TOK STRUCT_TOK

%token PLUS_TOK MINUS_TOK MULT_TOK DIV_TOK MODULO_TOK ASSIGN_TOK 

%token BIT_NOT_TOK BIT_OR_TOK BIT_AND_TOK BIT_XOR_TOK BIT_LSH_TOK BIT_RSH_TOK

%token INT_TOK FLOAT_TOK UNSD_TOK STRG_TOK
%token BOOL_TOK 

%token RETURN_TOK BREAK_TOK CONT_TOK IF_TOK ELSE_TOK WHILE_TOK
%token FOR_TOK SWITCH_TOK CASE_TOK 

%token OR_TOK AND_TOK NOT_TOK EQ_TOK GEQ_TOK LEQ_TOK
%token NEQ_TOK MORE_TOK LESS_TOK 

%token TRUE_TOK FALSE_TOK NOTHING_TOK

%token SYMBOL_TOK UNSIGNED_TOK INTEGER_TOK FLOATING_TOK STRING_TOK

%left MINUS_TOK PLUS_TOK
%left MULT_TOK DIV_TOK
%left NEGATION
%right CARAT_TOK    /* exponentiation        */

%%

expression
    : arithmetic_expression
    | boolean_expression
    | bitwise_expression
    ;

compound_symbol
    : SYMBOL_TOK
    | compound_symbol DOT_TOK SYMBOL_TOK
    ;

exponent_numeric_value
    : FLOATING_TOK
    | INTEGER_TOK
    ;

arithmetic_factor
    : INTEGER_TOK
    | FLOAT_TOK
    | UNSIGNED_TOK
    | exponent_numeric_value CARAT_TOK exponent_numeric_value
    | compound_symbol
    ;

arithmetic_expression
    : arithmetic_factor
    | arithmetic_expression PLUS_TOK arithmetic_expression
    | arithmetic_expression MINUS_TOK arithmetic_expression
    | arithmetic_expression MULT_TOK arithmetic_expression
    | arithmetic_expression DIV_TOK arithmetic_expression
    | MINUS_TOK arithmetic_expression %prec NEGATION
    | OPAREN_TOK arithmetic_expression CPAREN_TOK
    ;

boolean_factor
    : arithmetic_factor
    | TRUE_TOK
    | FALSE_TOK
    | STRING_TOK
    ;

boolean_expression
    : boolean_factor
    | boolean_expression OR_TOK boolean_expression
    | boolean_expression AND_TOK boolean_expression 
    | boolean_expression EQ_TOK boolean_expression 
    | boolean_expression NEQ_TOK boolean_expression 
    | boolean_expression LEQ_TOK boolean_expression 
    | boolean_expression GEQ_TOK boolean_expression 
    | boolean_expression MORE_TOK boolean_expression 
    | boolean_expression LESS_TOK boolean_expression 
    | NOT_TOK boolean_expression 
    | OPAREN_TOK boolean_expression CPAREN_TOK
    ;

bitwise_factor
    : INTEGER_TOK
    | UNSIGNED_TOK
    | compound_symbol
    ;

bitwise_expression
    : bitwise_factor
    | bitwise_expression BIT_AND_TOK bitwise_expression
    | bitwise_expression BIT_OR_TOK bitwise_expression
    | bitwise_expression BIT_XOR_TOK bitwise_expression
    | bitwise_expression BIT_LSH_TOK bitwise_expression
    | bitwise_expression BIT_RSH_TOK bitwise_expression
    | BIT_NOT_TOK bitwise_expression
    | OPAREN_TOK bitwise_expression CPAREN_TOK 
    ; 
%% 

这会产生102个shift-reduce和8个reduce-reduce冲突。我知道我在规则中重用了一些令牌，根非终端是人为设计的。我很难弄清楚如何组织它们，以便正确的(有时相同的)类型与正确的表达式类型相关联。我尝试过以各种方式重新组织。我想很明显我遗漏了什么。也许我的整个方法都是错的，但我不清楚正确的方法是什么。

有关我真正想做什么的更好(但非常不完整)的解释，请参阅此存储库上的自述文件：https://github.com/chucktilbury/toi

Answer 1

如果您还没有这样做，请以类似于bison -r all filename.y的形式运行bison，并查看额外的输出文件filename.output。在接近顶部的地方，这给了我

State 9 conflicts: 2 reduce/reduce
State 10 conflicts: 2 reduce/reduce
State 14 conflicts: 2 reduce/reduce
State 16 conflicts: 2 reduce/reduce
State 35 conflicts: 5 shift/reduce
State 38 conflicts: 8 shift/reduce
...

'State 9‘的下一个实例是

State 9

   10 arithmetic_factor: UNSIGNED_TOK .  [$end, CPAREN_TOK, PLUS_TOK, MINUS_TOK, MULT_TOK, DIV_TOK, OR_TOK, AND_TOK, EQ_TOK, GEQ_TOK, LEQ_TOK, NEQ_TOK, MORE_TOK, LESS_TOK]
   36 bitwise_factor: UNSIGNED_TOK .  [$end, CPAREN_TOK, BIT_OR_TOK, BIT_AND_TOK, BIT_XOR_TOK, BIT_LSH_TOK, BIT_RSH_TOK]

    $end         reduce using rule 10 (arithmetic_factor)
    $end         [reduce using rule 36 (bitwise_factor)]
    CPAREN_TOK   reduce using rule 10 (arithmetic_factor)
    CPAREN_TOK   [reduce using rule 36 (bitwise_factor)]
    BIT_OR_TOK   reduce using rule 36 (bitwise_factor)
    BIT_AND_TOK  reduce using rule 36 (bitwise_factor)
    BIT_XOR_TOK  reduce using rule 36 (bitwise_factor)
    BIT_LSH_TOK  reduce using rule 36 (bitwise_factor)
    BIT_RSH_TOK  reduce using rule 36 (bitwise_factor)
    $default     reduce using rule 10 (arithmetic_factor)

此输出表示实现解析算法的状态机中的一个可能的“状态”。

首先，有许多行显示了语法规则中可能的位置。句点(.)始终显示规则中的当前位置。当句号在规则的末尾时，bison可能会紧跟其后，在[方括号]中列出所有终端令牌，这些令牌可能在规则产生的非终端符号之后立即有效。

接下来，有一个表，其中列出了给定输入流中的当前状态和下一个令牌时解析器将采取的操作。冲突表现为同一令牌的多个条目，第一个条目之后的操作位于[方括号]中(表示给定不明确的语法，操作将是有效的，但解析器永远不会实际执行该操作)。

因此，在状态9的输出中，我们可以看到问题是，当UNSIGNED_TOK标记后面跟着解析器输入的末尾或CPAREN_TOK标记时，bison无法确定数字应该是arithmetic_factor还是bitwise_factor。对于输入的结尾，这可能无关紧要，这个问题可以通过摆弄根非终端来避免。但是闭括号的情况是一个问题。由于bison (默认情况下)使用LALR(1) grammar，因此在处理文本( 0u )中的前两个标记后，解析器需要仅使用单个前视标记)来决定如何处理0u。但是，如果它决定把它变成arithmetic_factor，输入是( 0u ) & 1u，那就错了；如果它决定把它变成bitwise_factor，输入是( 0u ) + 1u，那就错了。

要解决这样的问题，从语义操作的角度考虑语法规则通常是有帮助的(即使在使用语法只是为了确定输入是否有效而不会有任何语义操作的情况下)。解释器应该对表达式( 0u )执行什么操作？理想情况下，根本不需要:表达式应该与普通的0u具有相同的表示和效果。这使它与复合算术表达式和复合逐位表达式处于不同的类别，因为它们的用途更有限(至少在所示的语法中是这样)。

但是，如果我们想说例如( 0u )不是一个arithmetic_expression，那么我们似乎走向了一系列荒谬的规则，让arithmetic_expression列出所有可接受的操作数类型的叉积。我们可以通过对arithmetic_operand使用规则来避免这种情况，解析器将仅将其用于实际算术运算符(不包括圆括号)的子表达式。为了允许多个运算符，还可以将任何arithmetic_expression用作arithmetic_operand。

下面是你的语法的一个版本(在相同的标记声明之后)，没有reduce-reduce冲突：

%%

expression
    : int_constant
    | float_constant
    | bool_constant
    | string_constant
    | exponent_constant
    | symbol_parens
    | arithmetic_expression
    | boolean_expression
    | bitwise_expression
    ;

compound_symbol
    : SYMBOL_TOK
    | compound_symbol DOT_TOK SYMBOL_TOK
    ;

symbol_parens
    : compound_symbol
    | OPAREN_TOK symbol_parens CPAREN_TOK
    ;

int_constant
    : INTEGER_TOK
    | UNSIGNED_TOK
    | OPAREN_TOK int_constant CPAREN_TOK
    ;

float_constant
    : FLOAT_TOK
    | OPAREN_TOK float_constant CPAREN_TOK
    ;

bool_constant
    : TRUE_TOK
    | FALSE_TOK
    | OPAREN_TOK bool_constant CPAREN_TOK
    ;

string_constant
    : STRING_TOK
    | OPAREN_TOK string_constant CPAREN_TOK
    ;

exponent_operand
    : FLOATING_TOK
    | INTEGER_TOK
    ;

exponent_constant
    : exponent_operand CARAT_TOK exponent_operand
    | OPAREN_TOK exponent_constant CPAREN_TOK
    ;

arithmetic_operand
    : int_constant
    | float_constant
    | exponent_constant
    | symbol_parens
    | arithmetic_expression
    ;

arithmetic_expression
    : arithmetic_operand PLUS_TOK arithmetic_operand
    | arithmetic_operand MINUS_TOK arithmetic_operand
    | arithmetic_operand MULT_TOK arithmetic_operand
    | arithmetic_operand DIV_TOK arithmetic_operand
    | MINUS_TOK arithmetic_operand %prec NEGATION
    | OPAREN_TOK arithmetic_expression CPAREN_TOK
    ;

boolean_operand
    : bool_constant
    | int_constant
    | float_constant
    | exponent_constant
    | string_constant
    | symbol_parens
    | boolean_expression
    ;

boolean_expression
    : boolean_operand OR_TOK boolean_operand
    | boolean_operand AND_TOK boolean_operand 
    | boolean_operand EQ_TOK boolean_operand 
    | boolean_operand NEQ_TOK boolean_operand 
    | boolean_operand LEQ_TOK boolean_operand 
    | boolean_operand GEQ_TOK boolean_operand 
    | boolean_operand MORE_TOK boolean_operand 
    | boolean_operand LESS_TOK boolean_operand 
    | NOT_TOK boolean_operand 
    | OPAREN_TOK boolean_expression CPAREN_TOK
    ;

bitwise_operand
    : int_constant
    | symbol_parens
    | bitwise_expression
    ;

bitwise_expression
    : bitwise_operand BIT_AND_TOK bitwise_operand
    | bitwise_operand BIT_OR_TOK bitwise_operand
    | bitwise_operand BIT_XOR_TOK bitwise_operand
    | bitwise_operand BIT_LSH_TOK bitwise_operand
    | bitwise_operand BIT_RSH_TOK bitwise_operand
    | BIT_NOT_TOK bitwise_operand
    | OPAREN_TOK bitwise_expression CPAREN_TOK 
    ; 
%% 

102个shift-reduce冲突仍然存在，但它们都可以通过在boolean_expression和bitwise_expression规则中指定运算符的优先级和结合性来解决。

但需要注意的是:这可能是无意的，但是您的语法不允许混合来自不同“类别”的运算符。例如，输入(1 + 2 < 4)和(5 & 6 == 4)是无效的。