时间戳

首页 > 解决方案 > shift-reduce 与表达式的冲突

expression - shift-reduce 与表达式的冲突

问题描述

我正在为我自己设计的完整编程语言编写语法。这种语言有几种表达方式，它们在不同的情况下以不同的方式组合在一起。我对我希望它如何工作有一个很好的想法，但是我在分解 shift/reduce 和 reduce/reduce 冲突时遇到了麻烦。我在 Xubuntu 16.04 下使用 Bison v3.0.4。完整的语法（包括 *.output 文件）可以在我的 github 中看到，网址为https://github.com/chucktilbury/Simple1 （请参阅expressions.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

标签： expressiongrammarbisonyaccshift-reduce-conflict

解决方案

如果您还没有，请以类似的形式运行 bison bison -r all filename.y，然后查看额外的输出文件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
...

“状态 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 无法确定该数字是否应该是 anarithmetic_factor或bitwise_factor。对于输入的结束，也许这并不重要，并且可以通过摆弄根非终端来避免这个问题。但是右括号的情况是个问题。由于野牛（默认情况下）使用LALR(1) 语法，在处理文本中的前两个标记之后( 0u )，解析器需要决定0u只使用单个前瞻标记做什么)。但是，如果它决定将其设为 anarithmetic_factor并且输入为( 0u ) & 1u，那就错了；如果它决定将其设为 abitwise_factor并且输入为( 0u ) + 1u，那就错了。

为了解决这样的问题，从语义动作的角度考虑语法规则通常很有帮助（即使在使用语法来确定输入是否有效并且不会有任何语义动作的情况下）。口译员应该对表达采取什么行动( 0u )？理想情况下，根本没有：表达式应该具有与 plain 相同的表示和效果0u。这使它与复合算术表达式和复合位表达式都属于不同的类别，因为它们的用途更有限（至少在所示的语法中）。

但是，如果我们想说例如( 0u )is NOT an arithmetic_expression，似乎我们可能会朝着arithmetic_expression列出所有可接受操作数类型的叉积的荒谬规则前进。我们可以通过使用 a 的规则来避免这种情况，arithmetic_operand解析器将仅将其用于实际算术运算符的子表达式（不包括括号）。为了允许多个运算符，anyarithmetic_expression也可以用作arithmetic_operand.

因此，这是您的语法版本（在相同的标记声明之后），没有减少-减少冲突：

%%

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_expressionandbitwise_expression规则中的运算符指定优先级和关联性来解决。

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

推荐阅读