3

我根据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 {}
      ;
4

1 回答 1

6

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

这是一个示例（我删除了重复部分）：

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)

我们可以看到状态 88 发生在WHILE表达式可以归约时（从.状态描述中的位置可以明显看出：

   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 中。

output从文件中也可以清楚地看出状态 1 中的移位/减少冲突：

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)

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

  1. 转移。exp是，因此ID [exp] OF exp最终结果将是：

    ID '[' exp ']' OF exp        --> exp    (rule 25)

  2. 减少. exp是左值ID[exp]，使用以下产生式：

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

为了使用第二种选择，解析器必须立即归约ID到，问题就在于此：解析器在看到以下匹配lvalue之前无法知道这两种可能性中的哪一种是正确的，但那是遥远的未来——事实上，它可能是任意数量的令牌。OF]

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

  1. 由于表达式只能是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

    将当前状态机与此更改后的状态机进行比较应该可以清楚地了解其工作原理（并且是学习自下而上解析的有用练习）。

  2. 如果你不想做所有这些工作，你可以简单地添加一个“明显多余”的产品，正如 Appel 在他的教科书中所建议的那样：

    lvalue: ID 
      | lvalue DOT ID 
      | lvalue LBRACK exp RBRACK
      | ID LBRACK exp RBRACK

    增加的生产lvalue显然会造成班次减少冲突；实际上，它与原始语法中的移位减少冲突完全相同。但这一次，冲突发生在 for 的两个不同产生式之间lvalue，默认的 shift 动作肯定是你想要在一个 bareID后跟 a的情况下采取的那个[。移位之后，lvalue产生式和exp产生式仍然可用，因此解析器不必做出决定，直到找到].

    这种解决方案的缺点是解析器生成器将继续报告移位减少冲突，因为显然存在一个。由于 shift-reduce 冲突通常被认为是语法可能不明确的标志，因此在代码中留下 shift-reduce 冲突将是一个长期维护问题：在每次语法更改后，都需要验证 shift-reduce减少冲突是良性的。

  3. 不幸的是，另一个解决方案也是使用 bison%glr-parser指令生成 GLR 解析器。GLR 算法能够通过同时有效地维护两个（或更多）不同的可能解析器堆栈来延迟归约决策。对于明确的文法，输入的长度仍然是 O(n)，但速度稍慢。（此外，此选项在许多其他 yacc 衍生产品中不可用。）

  4. 最后，您lvalue只需将其产品添加到exp. 然后，您需要泛化lvalue [ exp ]to exp [ exp ]，这意味着语法将识别原始语言的超集：它现在将接受某些无效的输入。但是，很容易检查相关产生式的语义动作以查看 an 是否具有 anexp的形式lvalue；如果不是，您可以在语义操作中生成语法错误。

于 2014-11-17T16:30:56.360 回答