compiler-construction - 野牛移位/减少冲突-Tiger Compiler

Question

我已经根据Tiger Book（附录A，Tiger手册）编写了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 {}
      ;

Answer 1

通过查看使用tiger.output标志生成的-v文件，可以轻松地发现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 .

如果此时的超前标记是二进制运算符，则解析器将不知道是否要移位运算符，延长 exp表达式中的尾随 WHILE或立即减小 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)

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


转移。 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生产仍然可用，因此解析器不必做出决定，直到在[]之后找到令牌。

这种解决方案的缺点是解析器生成器将继续报告移位减少冲突，因为显然有一个冲突。由于通常认为移位减少冲突是语法可能不明确的标志，因此在代码中留下移位减少冲突将是长期的维护问题：每次语法更改后，都必须验证移位减少冲突是良性的。
不幸的是，另一个解决方案也是使用警告信息，该解决方案使用bison的 %glr-parser指令生成GLR解析器。 GLR算法能够通过有效地同时维护两个（或多个）不同的可能的解析器堆栈来延迟缩减决策。对于明确的语法，事实证明输入长度仍为O（n），但速度稍慢。 （此外，该选项在许多其他yacc派生工具中也不可用。）
最后，只需将其生产添加到 lvalue即可摆脱 exp。然后，您需要将 lvalue [ exp ]概括为 exp [ exp ]，这意味着语法将识别原始语言的超集：它现在将接受某些无效的输入。但是，很容易检查相关产品的语义动作，以查看 exp是否具有 lvalue的形式。如果不是，则可以在语义操作中生成语法错误。