野牛移位/减少冲突 - 老虎编译器 - Bison shift/reduce conflict

我根据老虎书（附录A，老虎手册）写了一个yacc文件。

但仍存在一些转移/减少冲突。我不知道如何解决这些冲突。

% yacc --version
bison (GNU Bison) 3.0.2

您可以使用此 cmd 重现此问题：

% yacc -dvt tiger.y
tiger.y: warning: 37 shift/reduce conflicts [-Wconflicts-sr]

% cat tiger.y ：

%{
#include <stdio.h>
//#include "util.h"
//#include "errormsg.h"
int yylex(void); /* function prototype */
void yyerror(char *s)
{
    EM_error(EM_tokPos, "%s", s);
}
%}

%union {
    int pos;
    int ival;
    string sval;
}

%token <sval> ID STRING
%token <ival> INT
%token
  COMMA COLON SEMICOLON LPAREN RPAREN LBRACK RBRACK
  LBRACE RBRACE DOT
  PLUS MINUS TIMES DIVIDE EQ NEQ LT LE GT GE
  AND OR ASSIGN
  ARRAY IF THEN ELSE WHILE FOR TO DO LET IN END OF
  BREAK NIL
  FUNCTION VAR TYPE

%right ASSIGN
%left OR
%left AND
%nonassoc EQ NEQ LT LE GT GE
%left  PLUS MINUS
%left  TIMES DIVIDE
%left  UNARYMINUS
%precedence THEN
%precedence ELSE

%start program
%%
program:    exp {  }
       ;
exp:lvalue {  }
   |NIL    {  }
   |LPAREN explist RPAREN {  }
   |LPAREN         RPAREN {}
   |INT {}
   |STRING {}
   |MINUS exp %prec UNARYMINUS {}
   |ID LPAREN RPAREN {}
   |ID LPAREN arglist RPAREN {}
   |exp PLUS exp {}
   |exp MINUS exp {}
   |exp TIMES exp {}
   |exp DIVIDE exp {}
   |exp EQ exp {}
   |exp NEQ exp {}
   |exp LT exp {}
   |exp LE exp {}
   |exp GT exp {}
   |exp GE exp {}
   |exp AND exp {}
   |exp OR exp {}
   |ID LBRACE RBRACE {}
   |ID LBRACE idlist RBRACE {}
   |ID LBRACK exp RBRACK OF exp {}
   |lvalue ASSIGN exp {}
   |IF exp THEN exp ELSE exp {}
   |IF exp THEN exp {}
   |WHILE exp DO exp {}
   |FOR ID ASSIGN exp TO exp DO exp {}
   |BREAK {}
   |LET decs IN END {}
   |LET decs IN explist END {}
   ;
lvalue: ID {}
      | lvalue DOT ID {}
      | lvalue LBRACK exp RBRACK {}
      ;
explist: exp {}
       | explist SEMICOLON exp {}
       ;
arglist:exp {}
       |exp COMMA arglist {}
       ;
idlist:ID EQ exp {}
      |ID EQ exp COMMA idlist {}
      ;
decs:dec {}
       |decs dec {}
       ;
dec:tydec {}
   |vardec {}
   |fundec {}
   ;
tydec:TYPE ID EQ ty {}
     ;
ty:ID {}
  |LBRACK tyfields RBRACK {}
  |ARRAY OF ID {}
  ;
tyfields:/* NULL */
        |notnulltyfields {}
        ;
notnulltyfields:ID COLON ID {}
               |ID COLON ID COMMA notnulltyfields {}
               ;
vardec:VAR ID ASSIGN exp {}
      |VAR ID COLON ID ASSIGN exp {}
      ;
fundec:FUNCTION ID LPAREN tyfields RPAREN EQ exp {}
      |FUNCTION ID LPAREN tyfields RPAREN COLON ID EQ exp {}
      ;

通过查看使用 -v 标志生成的tiger.output文件，很容易发现 shift-reduce 冲突。

这里有一个例子（我编辑了重复）：

State 88
   11 exp: exp . PLUS exp
   12    | exp . MINUS exp
# ...
   29    | WHILE exp DO exp .
    PLUS    shift, and go to state 34
    MINUS   shift, and go to state 35
# ...
    PLUS      [reduce using rule 29 (exp)]
    MINUS     [reduce using rule 29 (exp)]
# ...
    $default  reduce using rule 29 (exp)

我们可以看到，当WHILE表达式可以减少时，就会发生状态 88（这从状态描述中.的位置可以明显看出：

   29    | WHILE exp DO exp .

如果此时的前瞻令牌是二元运算符，则解析器不知道是移动运算符，使WHILE表达式中的尾随exp更长，还是立即减少WHILE。显然（对我们来说，不是bison），解决方案是转移。 bison不知道这一点，因为生产exp: WHILE exp DO exp没有优先级。该生产的优先级将是其最后一个终端的优先级，即 DO ，因此简单的解决方案是定义DO的优先级。不出所料，它应该与ELSE的优先级相同，正如IF exp THEN exp ELSE exp .不会产生转移/减少冲突的事实所表明的那样。

状态 112 和 129 中也会出现类似的问题。

状态 1 中的移位/减少冲突在output文件中也很清楚：

State 1
    9 exp: ID . LPAREN RPAREN
   10    | ID . LPAREN arglist RPAREN
   23    | ID . LBRACE RBRACE
   24    | ID . LBRACE idlist RBRACE
   25    | ID . LBRACK exp RBRACK OF exp
   34 lvalue: ID .
    LPAREN  shift, and go to state 15
    LBRACK  shift, and go to state 16
    LBRACE  shift, and go to state 17
    LBRACK    [reduce using rule 34 (lvalue)]
    $default  reduce using rule 34 (lvalue)

在这里，解析器刚刚在可能减少exp的上下文中找到了一个ID，它面临着两种可能性：

班次。exp是ID [exp] OF exp，所以最终的结果将是：
```
ID '[' exp ']' OF exp        --> exp    (rule 25)
```

减少。exp是左值ID[exp]，使用以下作品：

ID                           --> lvalue (rule 34)
lvalue '[' exp ']'           --> lvalue (rule 36)
lvalue                       --> exp    (rule 2)

为了使用第二种选择，解析器必须立即将ID减少到lvalue，这就是问题所在：解析器无法知道这两种可能性中的哪一种是正确的，直到它看到匹配之后的OF]，但那是遥远的未来 - 事实上，它可能是任意数量的标记。

这里的解决方案是避免强制解析器在此时做出决定。有几种可能性。

由于表达式只能是ID [ exp ] OF的（而不是更复杂的），我们可以从冲突中ID分解：
```
exp   : ID
      | lvalue_not_id
      | ...
lvalue: ID
      | lvalue_not_id
lvalue_not_ID
      : lvalue DOT ID
      | ID            LBRACK exp RBRACK
      | lvalue_not_ID LBRACK exp RBRACK
```
将当前状态机与此更改后的状态机进行比较应该可以清楚地了解其工作原理（并且是学习自下而上解析的有用练习）。
如果你不想去做所有这些工作，你可以简单地添加一个"明显冗余"的作品，正如Appel在他的教科书中建议的那样：
```
lvalue: ID 
      | lvalue DOT ID 
      | lvalue LBRACK exp RBRACK
      | ID LBRACK exp RBRACK
```
添加到lvalue的生产显然会产生移位-减少冲突;事实上，这与原始语法中的移位-减少冲突完全相同。但是这一次，冲突发生在两个不同的制作之间 lvalue ，默认的 shift 动作绝对是你想要在裸ID后跟 [.移位后，lvalue生产和exp生产仍然可用，因此解析器在找到 ] 之后的令牌之前不必做出决定。
此解决方案的缺点是解析器生成器将继续报告移位-减少冲突，因为显然存在冲突。由于 shift-reduce 冲突通常被认为是语法可能不明确的标志，因此在代码中留下 shift-reduce 冲突将是一个长期的维护问题：每次语法更改后，有必要验证 shift-reduce 冲突是否是良性的。
另一种解决方案（不幸的是也保留了警告）是使用 Bison 的 %glr-parser 指令生成 GLR 解析器。GLR 算法能够通过同时有效地维护两个（或多个）不同的可能解析器堆栈来延迟缩减决策。对于明确的语法，这在输入的长度上仍然是 O（n），但它稍微慢一点。（此外，此选项在许多其他 yacc 衍生产品中不可用。
最后，您可以通过将其产品添加到exp来摆脱lvalue。然后你需要概括lvalue [ exp ] exp [ exp ]，这意味着语法将识别原始语言的超集：它现在将接受某些无效的输入。但是，很容易检查相关作品的语义动作，以查看exp是否具有lvalue的形式;如果不是，则可以在语义操作中生成语法错误。

野牛移位/减少冲突 - 老虎编译器

相关内容

最新更新

热门标签：