1

我为具有以下语法的语言创建了一个编译器，由 ML-Yacc 定义（起始符号是底部定义的“程序”）：

%nonassoc       FUN VAR ASSIGN PLUSASSIGN MINUSASSIGN TIMESASSIGN DIVIDEASSIGN
%right          ELSE
%left           OR
%left           AND
%nonassoc       EQ NEQ GT LT GE LE
%left           PLUS MINUS
%left           TIMES DIVIDE
%left           UNARY
%left           LPAREN

%%

const: INT                                                              
     | FLOAT                                                            
     | BOOL                                                         
     | STRING                                                       

ty: ID                                                          
  | FUN LPAREN typeList RPAREN ARROW ty                         

typeList: typeList'                                                     
        |                                                               

typeList': ty COMMA typeList'                                               
         | ty                                                           

exp: primaryExp                                                     
   | callExp                                                        
   | boolExp                                                        
   | opExp                                                          
   | assignExp                                                      

assignExp: ID ASSIGN exp                                                    
         | ID PLUSASSIGN exp                                                
         | ID MINUSASSIGN exp                                           
         | ID TIMESASSIGN exp                                           
         | ID DIVIDEASSIGN exp                                          

tyargs: LT typeList' GT                                                 

callExp: exp LPAREN expList RPAREN                                      

boolExp: exp AND exp                                                        
       | exp OR exp                                                 

opExp: ID PLUSPLUS                                                      
     | ID MINUSMINUS                                                    
     | PLUSPLUS ID                                                  
     | MINUSMINUS ID                                                    
     | exp PLUS exp                                                 
     | exp MINUS exp                                                    
     | MINUS exp %prec UNARY                                            
     | BANG exp %prec UNARY                                         
     | exp TIMES exp                                                    
     | exp DIVIDE exp                                               
     | exp EQ exp                                                   
     | exp NEQ exp                                                  
     | exp GT exp                                                   
     | exp LT exp                                                   
     | exp GE exp                                                   
     | exp LE exp                                                   

expList: expList'                                                       
       |                                                                


expList': exp COMMA expList'                                                
        | exp                                                           

primaryExp: ID                                                              
          | const                                                           
          | lambdaExp                                                       
          | LPAREN exp RPAREN                                                                                                   

varDecl: ty ID ASSIGN exp                                               
       | ty ID                                                          
       | VAR ID ASSIGN exp                                              


expStat: exp SEMICOLON                                                  
       | SEMICOLON                                                      


statList: stat statList                                                 
        |                                                               

compoundStat: LBRACE statList RBRACE                                            

selectionStat: IF LPAREN exp RPAREN stat ELSE stat                              
             | IF LPAREN exp RPAREN stat                                        


jumpStat: RETURN exp                                                        
        | RETURN                                                        
        | BREAK                                                         

iterationStat: WHILE LPAREN exp RPAREN stat                                 
             | FOR LPAREN SEMICOLON SEMICOLON RPAREN stat                   
             | FOR LPAREN SEMICOLON SEMICOLON exp RPAREN stat               
             | FOR LPAREN SEMICOLON exp SEMICOLON RPAREN stat               
             | FOR LPAREN SEMICOLON exp SEMICOLON exp RPAREN stat           
             | FOR LPAREN varDecl SEMICOLON SEMICOLON RPAREN stat           
             | FOR LPAREN varDecl SEMICOLON SEMICOLON exp RPAREN stat       
             | FOR LPAREN varDecl SEMICOLON exp SEMICOLON RPAREN stat       
             | FOR LPAREN varDecl SEMICOLON exp SEMICOLON exp RPAREN stat   
             | FOR LPAREN exp SEMICOLON SEMICOLON RPAREN stat               
             | FOR LPAREN exp SEMICOLON SEMICOLON exp RPAREN stat           
             | FOR LPAREN exp SEMICOLON exp SEMICOLON RPAREN stat           
             | FOR LPAREN exp SEMICOLON exp SEMICOLON exp RPAREN stat       

stat: expStat                                                           
    | compoundStat                                                  
    | selectionStat                                                 
    | iterationStat                                                 
    | jumpStat SEMICOLON                                            
    | varDecl SEMICOLON                                                                 

declList: declList'                                                     
        |                                                               

declList': varDecl COMMA declList'                                          
         | varDecl                                                                                                          

functionDecl: FUN ID LPAREN declList RPAREN ARROW ty compoundStat           

lambdaExp: LPAREN declList RPAREN ARROW ty compoundStat                 

declarations: varDecl SEMICOLON declarations                                    
            | functionDecl declarations                                     
            |                                                               

program: declarations

这个语法很好，但是现在我想引入参数多态性，因此在语法中添加了以下产生式：

tyargs: LT typeList' GT

ty: ID tyargs

callExp: exp tyargs LPAREN expList RPAREN

idList: ID COMMA idList                                                 
      | ID

tyvars: LT idList GT

functionDecl: FUN ID tyvars LPAREN declList RPAREN ARROW ty compoundStat

现在我遇到了以下 2 个减少/减少冲突，我不知道如何解决

error:  state 75: reduce/reduce conflict between rule 46 and rule 5 on GT
error:  state 75: reduce/reduce conflict between rule 46 and rule 5 on COMMA

谁能告诉我如何消除这两个冲突？

编辑：这是来自 mlyacc http://pastebin.com/2w26ytuV的完整 .desc 输出。并不是说这个也显示了 2 个良性移位/减少错误

4

2 回答 2

1

好吧，没有人回答，但你把语法弄得非常模棱两可。有两种可能的产生：

LT ID GT
ID LT ID GT

举几个例子：

<a>
b<a>

这些是atyargs还是tyvarsa 的开始callExp？你的语法说他们可以两者兼而有之。因此，如果不对您使用的语言或规则进行一些更改，就很难使用 ml-yacc 之类的工具进行解析。

如果不进一步解释语言结构，您将很难用 ml-yacc 编译它。有人可能会向您展示一种更好的方式来构建语法规则以保持在此类工具的约束范围内。

于 2014-12-28T21:53:40.607 回答
1

问题在于，使用新规则时，语法需要任意前瞻才能区分 avarDecl和 an expStmt。这LT既是表达式的二元运算符，又表示tyargs参数化类型的列表的开始。

一种可能的解决方法是引入一个新的关键字来表示参数化类型或函数（就像FUN当前用于引入函数类型的关键字一样），这将允许解析器提前知道是将 aLT视为运算符还是类型参数列表。因此，您将改为添加新规则，例如：

ty: TYPE ID tyargs

callExpr: CALL ID tyargs LPAREN expList RPAREN

另一种可能性是通过符号表使用词法分析器反馈——让词法分析器识别需要类型参数的标识符（通过在符号表中查找名称）并为它们返回不同的标记。

第三种可能性是使用更强大的解析器生成器，可以处理更多的前瞻，例如野牛的 %glr-parser选项，或btyacc

于 2015-05-04T00:30:29.953 回答