スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

F#で入門 コンパイラ、インタプリタ編 簡易言語 (VM版)

 今回は前回の言語のVM版を作ります。 
 
実行場面は次のようになります。 
 
1018-1.jpg 
トークン、文法の定義は前回と同じですが、VMに解釈実行させる命令を次のように定義します。 
 
type CommandCode  = 
    |ADD        //s[p-1] = s[p-1] + s[p]; p <- p - 1   
    |SUB        //s[p-1] = s[p-1] - s[p]; p <- p - 1 
    |MUL        //s[p-1] = s[p-1] * s[p]; p <- p - 1 
    |DIV        //s[p-1] = s[p-1] / s[p]; p <- p - 1 
    |NEG        //s[p] = -s[p] 
    |LDI of int //s[p] <- int値; p <- p + 1 
    |STOP       //プログラムを正常終了 
    |LOD of int //int番地の内容をスタックにいれる s[++p] = 番地内容 
    |DISP       //s[p]を表示;p <- p - 1 
    |LDA of int //int番地そのものをスタックに入れる s[++p] = 番地  
    |ASS        //番地、さらにその上に値が載った状態で実行すると値を番地の示すところへ移す s[p-1]番地=s[p] ;p <- p - 2 
    |NULL 
 
    override  this.ToString() = 
        match this with 
        |ADD        -> "ADD"   
        |SUB        -> "SUB" 
        |MUL        -> "MUL" 
        |DIV        -> "DIV" 
        |NEG        -> "NEG" 
        |LDI(intNum)-> sprintf "LDI %d" intNum 
        |STOP       -> "STOP"  
        |LOD(intAdr)-> sprintf "LOD adr(%d)" intAdr 
        |DISP       -> "DISP" 
        |LDA(intAdr)-> sprintf "LDA adr(%d)" intAdr 
        |ASS        -> "ASS"     
        |NULL       -> "  " 
 
構文木をトラバースしてメモリ配列と記号表を返す関数を次の様に定義します。 
 
let makeSymbolTB (in_eb:embodyST)= 
    let memArr :int[]= Array.zeroCreate 100 
    let varCnt = ref 0 
    let symbolDic = new System.Collections.Generic.Dictionary<string,int>() 
  
    let rec makeSymbolTB_Sub (eb:embodyST) = 
        match eb with 
        //0: Z = Program EOF 
        |Node(0,_,proNd::_)      
            ->  for i in [0 .. ((Array.length memArr) - 1)] do memArr.[i] <- 0 
                varCnt :=  0 
                symbolDic.Clear()   
                makeSymbolTB_Sub  proNd  
        //1:Program = DeclStmts Stmts 
        |Node(1,_,decStmsNd::_) 
            -> makeSymbolTB_Sub  decStmsNd  
        //21:DeclStmts = DeclStmt SEMI DeclStmts2 
        |Node(21,_,declStmNd::_::declStm2Nd::_) 
            -> makeSymbolTB_Sub declStmNd  
               makeSymbolTB_Sub declStm2Nd  
        //22:DeclStmts2  = EPSILON 
        |Node(22,_,_) 
            -> () 
        //23:DeclStmts2  = DeclStmts 
        |Node(23,_,declStmtsNd::_) 
            -> makeSymbolTB_Sub declStmtsNd 
        //24:DeclStmt = INT VarDefs 
        |Node(24,_,_::varDefsNd::_) 
            -> makeSymbolTB_Sub varDefsNd 
        //25:VarDefs = ID EQ NUM VarDefs2 
        |Node(25,_,Leaf(id_tk)::_::Leaf(num_tk)::varDefs2Nd::_) 
            ->symbolDic.Add(id_tk.Img,!varCnt) //例えばx -> 1となる(1はアドレス=配列の添え字) 
                                              //2重登録はここでエラー  
              memArr.[!varCnt] <- System.Int32.Parse(num_tk.Img) //memへの初期値登録                                  
              varCnt :=  !varCnt + 1 
              makeSymbolTB_Sub varDefs2Nd 
        //26:VarDefs2 = COMMA ID EQ NUM VarDefs2 
        |Node(26,_,_::Leaf(id_tk)::_::Leaf(num_tk)::varDefs2Nd::_) 
             ->symbolDic.Add(id_tk.Img,!varCnt)  
               memArr.[!varCnt] <- System.Int32.Parse(num_tk.Img) //memへの初期値登録    
               varCnt := !varCnt + 1 
               makeSymbolTB_Sub varDefs2Nd 
        
        //27:VarDefs2 = EPSILON 
        |Node(27,_,_)  
            -> () 
        |_ -> () 
 
    makeSymbolTB_Sub in_eb 
    (memArr,symbolDic) 
 
この関数を補助関数として使い、構文木からコード配列とメモリ配列と記号表を返す関数を次のように定義します。 
 
let makePLArr (in_eb:embodyST) = 
    let pccArr:CommandCode[] = Array.create 200 NULL 
    let ccaIndex = ref 0 
    let (memArr,symbolDic) = makeSymbolTB in_eb  
 
    let rec eVal1  (eb:embodyST)  = 
        match eb with 
        //0: Z = Program EOF 
        |Node(0,_,pro::_)      
            ->  eVal1 pro  
        //1:Program = DeclStmts Stmts 
        |Node(1,_,_::stmtsNd::_)  
            -> eVal1 stmtsNd 
        //2:Expression = Expression1 Term Expression2 
        //3:UnaryOp = PLUS 
        //4:UnaryOp = MINUS 
        //5:Expression1 = EPSILON 
        //6:Expression1 = UnaryOp 
        |Node(2,_,exp1Nd::termNd::exp2Nd::_)  
            -> eVal1 termNd   
               match exp1Nd with 
                   |Node(5,_,_) -> ()  
                   |Node(6,_,Node(3,_,_)::_)  -> () 
                   |Node(6,_,Node(4,_,_)::_)  -> pccArr.[!ccaIndex] <- NEG ; ccaIndex := !ccaIndex + 1 
                   |_ -> failwith "never occruable error"  
               eVal1 exp2Nd   
        //7:Expression2 = EPSILON 
        |Node(7,_,EPS_Leaf(_)::_)  
            -> ()  
        //8:AddOp = PLUS 
        //9:AddOp = MINUS 
        //10:Expression2 = AddOp Expression3 Term Expression2 
        //11:Expression3 = EPSILON 
        //12:Expression3 = UnaryOp 
        |Node(10,_,addOpNd::exp3Nd::termNd::exp2Nd::_)  
            ->eVal1 termNd  
              match exp3Nd with  
                   |Node(11,_,_) -> ()  
                   |Node(12,_,Node(3,_,_)::_)  -> () 
                   |Node(12,_,Node(4,_,_)::_)  -> pccArr.[!ccaIndex] <- NEG ; ccaIndex := !ccaIndex + 1 
                   |_ -> failwith "never occruable error"  
              match addOpNd with 
                |Node(8,_,_)  -> pccArr.[!ccaIndex] <- ADD ; ccaIndex := !ccaIndex + 1 
                |Node(9,_,_)  -> pccArr.[!ccaIndex] <- SUB ; ccaIndex := !ccaIndex + 1 
                |_ -> failwith "never occruable error"  
              eVal1 exp2Nd   
        //13:Term = Factor Term1 
        |Node(13,_,factorNd::term1Nd::_)  
            ->eVal1 factorNd 
              eVal1 term1Nd  
        //14:Term1 = EPSILON 
        |Node(14,_,_)  
            -> () 
        //15:MulOp = MUL 
        //16:MulOp = DIV 
        //17:Term1 = MulOp Factor Term1 
        |Node(17,_,mulOpNd::factorNd::term1Nd::_)  
            ->eVal1 factorNd 
              match mulOpNd with 
                |Node(15,_,_)  -> pccArr.[!ccaIndex] <- MUL ; ccaIndex := !ccaIndex + 1 
                |Node(16,_,_)  -> pccArr.[!ccaIndex] <- DIV ; ccaIndex := !ccaIndex + 1 
                |_ -> failwith "never occruable error"  
              eVal1 term1Nd 
        //18:Factor = NUM 
        |Node(18,_,Leaf(tk)::_) 
            -> let num = System.Int32.Parse(tk.Img) 
               pccArr.[!ccaIndex] <- LDI(num) ; ccaIndex := !ccaIndex + 1 
        //19:Factor = LPAR Expression RPAR 
        |Node(19,_,_::expNode::_::_)  
            -> eVal1 expNode 
        //20:Factor = ID 
        |Node(20,_,Leaf(tk)::_) 
            -> let adr =  symbolDic.[tk.Img] 
               pccArr.[!ccaIndex] <-  LOD(adr) ;ccaIndex := !ccaIndex + 1 
        //29:Stmts = PrintStmt SEMI Stmts 
        |Node(29,_,printStmtNd::_::stmtsNd::_) 
            ->eVal1 printStmtNd 
              eVal1 stmtsNd 
        //30:PrintStmt = EX VarRefs 
        |Node(30,_,_::varRefsNd::_) 
            ->eVal1 varRefsNd 
        //31:VarRefs = Expression VarRefs2 
        |Node(31,_,expNd::varRefs2Nd::_) 
            ->eVal1 expNd //これでスタックに評価値がのる 
              pccArr.[!ccaIndex] <- DISP ;ccaIndex := !ccaIndex + 1 
              eVal1 varRefs2Nd 
        //32:VarRefs2 = COMMA Expression VarRefs2 
        |Node(32,_,_::expNd::varRefs2Nd::_) 
            ->eVal1 expNd //これでスタックに評価値がのる 
              pccArr.[!ccaIndex] <- DISP ;ccaIndex := !ccaIndex + 1 
              eVal1 varRefs2Nd 
        //34:Stmts = AssignStmt SEMI Stmts 
        |Node(34,_,assStmtNd::_::stmtsNd::_) 
            ->eVal1 assStmtNd 
              eVal1 stmtsNd 
        //35:AssignStmt = ID EQ Expression  
        |Node(35,_,Leaf(tk)::_::expNd::_) 
            -> pccArr.[!ccaIndex] <- LDA(symbolDic.[tk.Img]);ccaIndex := !ccaIndex + 1//memの書き込み番地をスタックにのっける 
               eVal1 expNd //これでスタックに評価値がのる 
               pccArr.[!ccaIndex] <- ASS; ccaIndex := !ccaIndex + 1 
    
        //21:DeclStmts = DeclStmt SEMI DeclStmts2 
        //22:DeclStmts2  = EPSILON 
        //23:DeclStmts2  = DeclStmts 
        //24:DeclStmt = INT VarDefs 
        //25:VarDefs = ID EQ NUM VarDefs2 
        //26:VarDefs2 = COMMA ID EQ NUM VarDefs2 
        //27:VarDefs2 = EPSILON 
        //28:Stmts = EPSILON 
        //33:VarRefs2 = EPSILON 
        |_ -> ()  
 
    eVal1 in_eb 
    pccArr.[!ccaIndex] <- STOP  
    (pccArr,memArr,symbolDic) 
     
解釈実行部分はコードの終わりのあたりのoneStepExec ()関数をみてください。 
次回はこの言語のMSAM版コンパイラをやります。 
 
今回の全コードは以下の通りです。 

続きを読む

スポンサーサイト

テーマ : プログラミング
ジャンル : コンピュータ

プロフィール

T GYOUTEN

Author:T GYOUTEN
F#と英単語とフリーソフトと読書に興味があります。
ホームページでフリーソフトも公開しています。どぞ御贔屓に。

最新記事
最新コメント
最新トラックバック
月別アーカイブ
カテゴリ
フリーエリア
フリーエリア
blogram投票ボタン
検索フォーム
RSSリンクの表示
リンク
ブロとも申請フォーム

この人とブロともになる

QRコード
QRコード
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。