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

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)

我们可以看到状态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中发生类似的问题.

状态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可能减少的上下文中找到了一个,它面临两种可能:

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显然会产生转移 - 减少冲突; 实际上,它与原始语法完全相同的shift-reduce冲突.但是这一次,冲突是在两个不同的制作之间进行的lvalue,默认的移动动作绝对是你想要在裸露的情况下ID接受的一个[.在转换之后,lvalue生产和exp生产仍然可用,因此解析器在找到令牌之后不必做出决定].

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

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

4. 最后,你可以lvalue通过添加它的产品来摆脱exp.然后,您需要概括lvalue [ exp ]为be exp [ exp ],这意味着语法将识别原始语言的超集:它现在将接受某些无效的输入.但是,很容易检查相关作品的语义动作,看看是否具有某种exp形式lvalue; 如果不是,则可以在语义操作中生成语法错误.