c - 如何在 yacc 文件中查找 shift/reduce 冲突

Question

在编译我的 yacc 文件时，我遇到了移位/归约冲突。我似乎无法解决，那我怎么找呢？错误指向第 73 行，这是 auxVartSpec 生产定义的行，特别是它的第二个生产 auxVarSpec COMMA ID 但我已经为这些标记设置了 de precedences .

%

%token <value> SEMICOLON BLANKID PACKAGE RETURN AND ASSIGN STAR COMMA DIV EQ GE GT LBRACE LE LPAR LSQ LT MINUS MOD NE NOT OR PLUS RBRACE RPAR RSQ ELSE FOR IF VAR INT FLOAT32 BOOL STRING PRINT PARSEINT FUNC CMDARGS RESERVED ID INTLIT REALLIT STRLIT

%type <node> Program Declarations VarDeclaration VarSpec Type FuncDeclaration FuncHeader Parameters FuncBody VarsAndStatements Statement ParseArgs FuncInvocation Expr auxDeclarations auxVarSpec auxParameters auxStatement auxFuncInvocation opcType opcParameters opcExpr opcFuncInvocation 


%nonassoc   IFX
%nonassoc   ELSE

%left  COMMA
%right  ASSIGN
%left   OR
%left   AND
%left   EQ NEQ
%left   LT GT LEQ GEQ
%left   PLUS MINUS
%left   STAR DIV MOD
%right  NOT

%%

Program: PACKAGE ID SEMICOLON Declarations                  
       ;                                   

Declarations: auxDeclarations                       

auxDeclarations: %empty                             

           | auxDeclarations VarDeclaration SEMICOLON                
           | auxDeclarations FuncDeclaration SEMICOLON      
           ;

VarDeclaration: VAR VarSpec                     

          | ID auxVarSpec Type                  

        ;                                                               
VarSpec: ID auxVarSpec Type                                         
           ;
auxVarSpec: %empty                          
      | auxVarSpec COMMA ID                     
      ;

Type: INT                   

    | FLOAT32                   

    | BOOL                  

    | STRING                    

    ;

FuncDeclaration: FUNC FuncHeader FuncBody            
           ;
FuncHeader: ID LPAR opcParameters RPAR opcType            
       ;

opcType: %empty                 
    | Type                  
        ;

Parameters: ID Type auxParameters       

opcParameters: %empty               
         | Parameters           
         ;

auxParameters: %empty               

         | auxParameters COMMA ID Type  
         ;

FuncBody: LBRACE VarsAndStatements RBRACE             

VarsAndStatements: VarsAndStatements SEMICOLON            

         | VarsAndStatements VarDeclaration SEMICOLON 

         | VarsAndStatements Statement SEMICOLON      

         | %empty                         

         ;

Statement: ID ASSIGN Expr                   


     | LBRACE auxStatement RBRACE               

     | IF Expr LBRACE auxStatement RBRACE %prec IFX     

     | IF Expr LBRACE auxStatement RBRACE ELSE LBRACE auxStatement RBRACE       


         | FOR opcExpr LBRACE auxStatement RBRACE       


     | RETURN opcExpr                       

     | FuncInvocation                   

     | ParseArgs                        

     | PRINT LPAR Expr RPAR                 

     | PRINT LPAR STRLIT RPAR               

     ;

opcExpr: %empty                 
       | Expr                   
       ;

auxStatement: %empty                               
        | auxStatement Statement SEMICOLON                 
        ; 

ParseArgs: ID COMMA BLANKID ASSIGN PARSEINT LPAR CMDARGS LSQ Expr RSQ RPAR 


FuncInvocation: ID LPAR opcFuncInvocation RPAR  

auxFuncInvocation: %empty               
         | COMMA Expr           
         ;

opcFuncInvocation: %empty           
         | Expr auxFuncInvocation     
         ;

Expr: Expr OR Expr              

    | Expr AND Expr             


    | Expr LT  Expr             


    | Expr GT  Expr             


    | Expr EQ  Expr             


    | Expr NE  Expr             


    | Expr LE  Expr             


    | Expr GE  Expr             


    | Expr PLUS  Expr               

    | Expr MINUS  Expr              


    | Expr DIV  Expr                


    | Expr MOD  Expr                


    | NOT Expr                  


    | MINUS Expr                


    | PLUS Expr                 


    | INTLIT                    


    | REALLIT                   


    | ID                    

    | FuncInvocation                

    | LPAR Expr RPAR                
%%

Answer 1

您看到的错误消息表明您的文件中有 73 个移位/归约冲突，而不是第 73 行有移位/归约冲突。(移位/归约冲突对应于解析器状态，而不是行号。你可以通过使用 -v 命令行选项生成报告文件来查看冲突的位置。)

在这些冲突中，有 72 起是简单的拼写错误造成的。您的语法在 Expr 的产生式中使用标记名称 NE、GE 和 LE，但您的优先级声明是标记 NEQ、GEQ 和 LEQ。这会产生有关未使用 token 的警告。 (同样未使用的还有 STAR 和 RESERVED。我猜你不小心漏掉了乘法的 Expr 规则。)

剩下的冲突在状态45，其项目是(来自报告文件):

State 45

    7 VarDeclaration: ID . auxVarSpec Type
   29 Statement: ID . ASSIGN Expr
   43 ParseArgs: ID . COMMA BLANKID ASSIGN PARSEINT LPAR CMDARGS LSQ Expr RSQ RPAR
   44 FuncInvocation: ID . LPAR opcFuncInvocation RPAR

(附加到每个生产的数字是生产编号，而不是行号。生产编号位于报告文件的顶部，但由于生产也被列出，因此它们在这里没有太大区别. 每个产生式中的. 表示先行点. 除非指定--report=itemset)

冲突与前瞻COMMA:

COMMA     shift, and go to state 68
COMMA     [reduce using rule 9 (auxVarSpec)]

因此在这种状态下，可以移动逗号以继续生产 43。或者可以使用规则 9 (auxVarSpec: %empty) 触发缩减。这种减少是可能的，因为有一个项目以 auxVarSpec 作为其下一个非终结符，并且 auxVarSpec 如果不为空则以逗号开头。

为了可能更清楚，问题是在列表 VarsAndStatements 中，可能有一个 VarDeclaration(这是一个声明)但也可能有一个 ParseArgs(这是一条语句)。所以ParseArgs和VarDeclaration都是可以的，而且都可以ID COMMA开头，但是其中一个需要减少一个空的权利- ID 和 COMMA 之间的手边。

如果没有额外的先行标记，则无法解决该冲突:如果逗号后跟另一个 ID，则解析器正在查看 VarDeclaration，而如果逗号后跟一个 BLANKID(无论是什么)，那么它必须是一个 ParseArgs。

虽然冲突不能像写的那样解决，但可以通过推迟移位/归约决策的常用技术来避免。特别需要区分三种情况:

ID Type                /* VarDeclaration */
ID COMMA ID ...        /* VarDeclaration */
ID COMMA BLANKID ...   /* ParseArgs */

一种方法是添加明显冗余的产生式:

VarDeclaration: VAR VarSpec
              | ID Type
              | ID COMMA ID auxVarSpec Type