shift-reduce与表达式的冲突

问题描述 投票：0回答：1

我正在为我自己设计的完整编程语言编写语法。该语言有几种类型的表达式，在不同的情况下以不同的方式组合。我非常清楚我希望它如何工作，但我在分解shift / reduce和减少/减少冲突方面遇到了麻烦。我在Xubuntu 16.04下使用Bison v3.0.4。完整的语法（包括* .output文件）可以在https://github.com/chucktilbury/Simple1的github中看到（参见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

expression grammar bison yacc shift-reduce-conflict
1个回答
0
投票

如果您还没有，请以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
...

“状态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)

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

首先，有许多行显示语法规则中的可能位置。句点（.）始终显示规则中的当前位置。当该时段处于规则的最后时，野牛可能会遵循所有终端令牌的[square括号]中的列表，该列表可能在该规则产生的非终端符号之后立即生效。

接下来是一个表格，其中给出了当前状态和输入流中的下一个标记，解析器将采取的操作。冲突显示为同一令牌的多个条目，在[square括号]中的第一个之后执行操作（表示该操作在给定模糊语法时有效，但解析器实际上永远不会采取该操作）。

所以在状态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)无效。

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.