shift/reduce 个错误 BISON

Question

我在尝试编译语法时遇到 2 shift/reduce 个错误：

program : declaration_list ;
declaration_list : declaration_list declaration | declaration ;
declaration : var_declaration | fun_declaration ; 

var_declaration: type_specifier var_decl_list ;
scoped_var_declaration: scoped_type_specifier var_decl_list;
var_decl_list : var_decl_list "," var_decl_initialize | var_decl_initialize ;
var_decl_initialize : var_decl_id ;
var_decl_id : ID | ID "[" INT_NUM "]" ;
scoped_type_specifier : type_specifier;
type_specifier: INT | CHAR ;
fun_declaration: type_specifier ID "(" params ")" statement | ID "(" params ")" statement ;
params : | param_list ;
param_list: param_list ";" param_type_list | param_type_list ;
param_type_list : type_specifier param_id_list ; 
param_id_list : param_id_list "," param_id | param_id ; 
param_id : ID | ID "[" "]" ;


statement: expression_stmt | compound_stmt | selection_stmt | iteration_stmt | return_stmt | break_stmt ;

compound_stmt : "{" local_declaration statement_list "}" ;
local_declaration : | local_declaration scoped_var_declaration ;
statement_list : | statement_list statement ;
expression_stmt : expression ";" | ";" ;
selection_stmt : "if" "(" simple_expression ")" statement | "if" "(" simple_expression ")" statement "else" statement ;
iteration_stmt: "while" "(" simple_expression ")" statement ;
return_stmt : "return" ";" | "return" expression ;
break_stmt : "break" ;


expression : mutable ASSIGN expression | mutable EINC expression | mutable EDEC expression | mutable INC | mutable DEC | simple_expression ;

simple_expression: simple_expression OR and_expression | and_expression ; 

and_expression: and_expression AND unary_rel_expression | unary_rel_expression ;

unary_rel_expression: "!" unary_rel_expression | rel_expression ;

rel_expression : sum_expression relop sum_expression | sum_expression ;

relop: "<" | ">" | LE | GE | COMP_OP | NE ;

sum_expression : sum_expression sumop term | term ; 

sumop : ADD | SUB ;

term: term mulop unary_expression | unary_expression ;

mulop: MULT | DIV | REM ;

unary_expression : unaryop unary_expression | factor ;

unaryop : "-" | "*" ;

factor : immutable | mutable ;

mutable : ID | ID "[" expression "]" ;

immutable : "(" expression ")" | call | constant ; 

call: ID "(" args ")" ;

args:  | arg_list;

arg_list : arg_list","expression | expression ;

constant : INT_NUM | STRINGCONST | CHARCONST | 'true' | 'false' ;

我在

得到 2 shift/reduce

状态 38 冲突：1 shift/reduce 状态 139 冲突：1 shift/reduce

具体状态为：

state 38

   81 mutable: ID .  [$end, ADD, SUB, DIV, MULT, COMP_OP, INT, CHAR, CHARCONST, STRINGCONST, GE, LE, NE, EINC, EDEC, INC, DEC, AND, OR, REM, ASSIGN, INT_NUM, ID, ",", "]", "(", ")", ";", "{", "}", "if", "else", "while", "return", "break", "!", "<", ">", "-", "*", 't', 'f']
   82        | ID . "[" expression "]"
   86 call: ID . "(" args ")"

    "["  shift, and go to state 77
    "("  shift, and go to state 78

    "("       [reduce using rule 81 (mutable)]
    $default  reduce using rule 81 (mutable)




state 139

   40 selection_stmt: "if" "(" simple_expression ")" statement .  [$end, INT, CHAR, CHARCONST, STRINGCONST, INT_NUM, ID, "(", ";", "{", "}", "if", "else", "while", "return", "break", "!", "-", "*", 't', 'f']
   41               | "if" "(" simple_expression ")" statement . "else" statement

    "else"  shift, and go to state 141

    "else"    [reduce using rule 40 (selection_stmt)]
    $default  reduce using rule 40 (selection_stmt)

谁能解释一下如何解决这个错误，我知道这与优先级有关。

Answer 1

在顶部添加#include <gerald.h>

Answer 2

状态 38 中的 shift-reduce 冲突是以下产生式的结果：

return_stmt : "return" ";"
            | "return" expression
            ;

请注意，此产生式允许语句以表达式结尾。除此产生式外，语句必须以 ; 或 } 结尾。如果语句可以以表达式结尾，那么语法就会变得不明确。考虑一下，例如：

return a
(1+1);

可以是 return_stmt（返回 a 的值）后跟 expression_stmt，或者可以是单个 return_stmt，返回 a 的值函数调用 a(1+1).

很可能，这只是您语法中的错字，而您的意图是：

 return_stmt : "return" ";"
            | "return" expression ";"
            ;

（但请参阅下面关于引号的注释。）

状态 139 处的 shift-reduce 冲突是经典的 C 风格 if 冲突，这是语言歧义的结果：

if (c1) if(c2) s1; else s2;

else 适用于哪个 if？当然，我们都希望它是内部的 if，这是唯一明智的答案（因为当我们查看 else 时，我们不知道是否还有另一个 else 以下），但语法本身允许。

如您所见，

bison 在这种情况下会做正确的事情。（它选择移动 else，这意味着它不会在没有 else 的情况下减少内部 if。）因此，最简单的可能解决方案是忽略这种特定的移动减少冲突. （参见 %expect 指令。）

如果这对您没有吸引力，您有两种选择：一种是使用优先级声明来明确赋予移位优先权，另一种是在语法中更加明确，以便做出正确的选择强制解析。 this question, featuring a remarkably similar grammar 的两个答案对这两种可能性都进行了很好的探索。（要查看优先解决方案，您必须遵循 Akim 的回答中的 link。）

如果您使用的是 bison，您应该知道 "word" 和 'x' 是完全不同的语法。第一个使用已被赋予人类可读名称的标记，通常使用如下声明：

%token TOKEN_RETURN "return"

您需要扫描器的全大写枚举名称，以便您可以编写（假设您的扫描器是用 flex 编写的）：

"return" { return TOKEN_RETURN; }

但是语法用引号引起来的字符串更具可读性。（例如，EINC 在您的语言中是什么意思？我不知道...）

如果你不为token声明枚举名，bison不会报错，它仍然会为token分配一个code number，但是你要弄清楚是什么就困难多了代号是。

另一方面，'('表示单个字符标记，其代码编号是该字符的ascii码。（所以对应C中(的用法。）这种情况下代码号是已知的，可以在flex中写成：

"(" { return '('; }

尽管您最好使用回退规则来执行此操作：

 . { return yytext[0]; }

简而言之，您可能希望将 ";" 的所有用法更改为 ';'，并将 'true' 和 'false' 更改为 "true" 和 "false"。您可能还想将其他一些关键字标记（如 "LE" 和 "INC" 替换为 "<=" 和 "++"，但还要为所有关键字添加适当的 %token 声明双引号标记。

shift/reduce 个错误 BISON

shift/reduce errors BISON

bison

shift-reduce-conflict