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

これら2つの競合をどのように削除するか教えてもらえますか?

編集: これは mlyacc http://pastebin.com/2w26ytuVからの完全な .desc 出力です。これも 2 つの無害なシフト/リデュース エラーを示しているわけではありません

4

2 に答える 2

1

varDecl問題は、新しいルールでは、文法が aと anの違いを伝えるために任意の先読みを必要とすることexpStmtです。これは、式の二項演算子であり、パラメーター化された型のリストLTの開始を示すことから来ています。tyargs

考えられる修正の 1 つは、パラメーター化された型または関数を示す新しいキーワード (FUN関数型を導入するために現在使用されているキーワードなど) を導入することです。これにより、パーサーは aLTを演算子として扱うか型パラメーターとして扱うかを事前に知ることができます。リスト。したがって、代わりに次のような新しいルールを追加します。

ty: TYPE ID tyargs

callExpr: CALL ID tyargs LPAREN expList RPAREN

もう 1 つの可能性は、シンボル テーブルを介してレクサー フィードバックを使用することです。レクサーに型パラメーターを必要とする識別子を認識させ (シンボル テーブルで名前を検索することにより)、それらに対して別のトークンを返します。

%glr-parser3 つ目の可能性は、bison のオプションやbtyaccなど、より多くの先読みを処理できる強力なパーサー ジェネレーターを使用すること です。

于 2015-05-04T00:30:29.953 に答える