Как найти сдвиг / уменьшить конфликт в файле YACC - PullRequest
Новая
       27

Как найти сдвиг / уменьшить конфликт в файле YACC

0 голосов
/ 31 марта 2019

При компиляции моего файла yacc я получаю конфликт сдвиг / уменьшение. Я не могу решить, так как я могу найти это? Ошибка указывает на строку 73, которая является строкой для определения продукции auxVartSpec и, в частности, его второго производства auxVarSpec COMMA ID, но я уже установил приоритет для этих токенов. 

%

%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                
%%

1 Ответ

2 голосов
/ 01 апреля 2019

Сообщение об ошибке, которое вы видели, указывает на то, что в вашем файле есть 73 конфликта сдвига / уменьшения, а не на конфликте сдвига / уменьшения в строке 73. (Конфликты сдвига / уменьшения соответствуют состояниям синтаксического анализатора, а не номерам строк.можно определить, где находятся конфликты, путем создания файла отчета с параметром командной строки -v.

Из этих конфликтов 72 являются результатом простой опечатки.Ваша грамматика использует имена токенов NE, GE и LE в производствах для Expr, но ваши объявления приоритетов предназначены для токенов NEQ, GEQ и LEQ.Это выдает предупреждение о неиспользованных токенах.(Также не используются 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)

Конфликт сthe lookahead 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 (независимо от того, чтоis), тогда это должно быть ParseArgs.

Хотя конфликт не может быть разрешен в письменном виде, его можно избежать с помощью обычной техники отсрочки принятия решения о сдвиге / уменьшении.В частности, необходимо различать три случая: 

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

Один из способов сделать это - добавить явно избыточное производство: 

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