スポンサーサイト

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

F#で入門 コンパイラ、インタプリタ編 一行計算機 インタプリタ

 今回はLL1TokenizeAndParseクラスを利用して 1 - 2 - 3 ,1 + (-4) / 2等の四則演算を計算するインタプリタを作成します。 
 
まずは前々回作ったLL1TokenizeAndParseクラスおよび関連クラスのコードをF# Iteractiveに食わせます。 
 
(返答のみ) 
type LL1TokenizeAndParse = 
  class 
    new : inDefLst:(string * string) list * inStrLst:string list -> 
            LL1TokenizeAndParse 
    member GetEBASTtree : sourceLst:string list -> embodyST 
    member GetTokens : sourceLst:string list -> Token list 
  end 
 
トークン化ルールと構文規則は次の様に定義します。 
 
> let tnR = [("PLUS","\+"); 
           ("MINUS","\-"); 
           ("MUL","\*"); 
           ("DIV","\/"); 
           ("LPAR","\("); 
           ("RPAR","\)"); 
           ("NUM","\d+") 
           ] 
 
let grammersStrLst = 
   ["1:Program = Expression"; 
    "2:Expression = Expression1 Term Expression2"; 
    "3:UnaryOp = PLUS"; 
    "4:UnaryOp = MINUS"; 
    "5:Expression1 = EPSILON"; 
    "6:Expression1 = UnaryOp"; 
    "7:Expression2 = EPSILON"; 
    "8:AddOp = PLUS"; 
    "9:AddOp = MINUS"; 
    "10:Expression2 = AddOp Expression3 Term Expression2"; 
    "11:Expression3 = EPSILON"; 
    "12:Expression3 = UnaryOp"; 
    "13:Term = Factor Term1"; 
    "14:Term1 = EPSILON"; 
    "15:MulOp = MUL"; 
    "16:MulOp = DIV"; 
    "17:Term1 = MulOp Factor Term1"; 
    "18:Factor = NUM"; 
    "19:Factor = LPAR Expression RPAR" 
      ];; 
 
(返答略) 
 
UnaryOpというのは、符号です。FactorとTermがあるのは*/を+-より優先して計算するためです。 
 
では LL1TokenizeAndParseのインスタンスを一つ作成します。 
> let tp = new LL1TokenizeAndParse (tnR,grammersStrLst);; 
 
val tp : LL1TokenizeAndParse 
 
例えば1 - 2 - 3から作られる具象構文木は次のようになります。 
 
> (tp.GetEBASTtree ["1 - 2 - 3"]).dispStr 6;; 
val it : string = 
  "      (0)Z 
          (1)Program 
              (2)Expression 
                  (5)Expression1 
                      ε(1,1)の前 
                  (13)Term 
                      (18)Factor 
                          [NUM 1 (1,1)]  
                      (14)Term1 
                          ε(1,3)の前 
                  (10)Expression2 
                      (9)AddOp 
                          [MINUS - (1,3)]  
                      (11)Expression3 
                          ε(1,5)の前 
                      (13)Term 
                          (18)Factor 
                              [NUM 2 (1,5)]  
                          (14)Term1 
                              ε(1,7)の前 
                      (10)Expression2 
                          (9)AddOp 
                              [MINUS - (1,7)]  
                          (11)Expression3 
                              ε(1,9)の前 
                          (13)Term 
                              (18)Factor 
                                  [NUM 3 (1,9)]  
                              (14)Term1 
                                  ε(2,1)の前 
                          (7)Expression2 
                              ε(2,1)の前 
          [EOF EOF (2,1)]  
このような木を、スタックとスタックポインタを利用して評価します。 
 
スタックとスタックポインタを定義します。 
 
> let arr:int array = Array.zeroCreate 100 //スタックは配列を利用し、深さは100にします。 
let mutable  sp:int  = 0;; 
 
val arr : int array = 
  [|0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 
    0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 
    0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 
    0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0|] 
val mutable sp : int = 0 
 
さて、評価する関数ですが、つぎのような原則を頭においてコードを書くことにします。 
expressionNodeを評価したときには、評価前よりスタックポインタが一つ増えその場所にexpessionNodeを評価した値が置かれるようにする 
termNodeを評価したときには、評価前よりスタックポインタが一つ増えその場所にtermを評価した値が置かれるようにする 
FactorNodeを評価したときには..................... 
 
では木を評価してスタックとスタックポインタを変化させる関数のコードです。 
(式の計算結果はスタック配列内のスタックポインタの指す値となります。) 
 
> let rec eVal0  (eb:embodyST)  = 
    match eb with 
    //0: Z = Program EOF 
    |Node(0,_,pro::_)      
        ->  eVal0 pro  
    //1:Program = Expression 
    |Node(1,_,expNd::_)  
        -> eVal0 expNd 
    //2:Expression = Expression1 Term Expression2 
    //3:UnaryOp = PLUS 
    //4:UnaryOp = MINUS 
    //5:Expression1 = EPSILON 
    //6:Expression1 = UnaryOp 
    |Node(2,_,exp1Nd::termNd::exp2Nd::_)  
        -> eVal0 termNd  //これでtermNdの評価値がスタックの一番上に置かれスタックポインタはそれを指している 
           match exp1Nd with 
               |Node(5,_,_) -> ()  
               |Node(6,_,Node(3,_,_)::_)  -> () 
               |Node(6,_,Node(4,_,_)::_)  -> arr.[sp] <- (-1) * arr.[sp] 
               |_ -> failwith "never occruable error"  
           eVal0 exp2Nd  //これを呼ぶときにはExpression1 Termの結果(Termの値に符号を考え合わせたもの)が一番上に残っている 
    //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::_)  
        ->eVal0 termNd //先にExperrion3Nodeを評価してスタックの一番上に置いておく、(その下にはそれより前の評価値が置かれている) 
          match exp3Nd with //exp3Nodeによる符号変化を反映させておく 
               |Node(11,_,_) -> ()  
               |Node(12,_,Node(3,_,_)::_)  -> () 
               |Node(12,_,Node(4,_,_)::_)  -> arr.[sp] <- (-1) * arr.[sp] 
               |_ -> failwith "never occruable error"  
          match addOpNd with 
            |Node(8,_,_)  -> arr.[sp - 1] <- arr.[sp - 1] + arr.[sp]; sp <- (sp - 1) 
            |Node(9,_,_)  -> arr.[sp - 1] <- arr.[sp - 1] - arr.[sp]; sp <- (sp - 1) 
            |_ -> failwith "never occruable error"  
          eVal0 exp2Nd   
    //13:Term = Factor Term1 
    |Node(13,_,factorNd::term1Nd::_)  
        ->eVal0 factorNd 
          eVal0 term1Nd //これが呼ばれるときにはFatorNodeの評価が一番上に残っている 
    //14:Term1 = EPSILON 
    |Node(14,_,_)  
        -> () 
    //15:MulOp = MUL 
    //16:MulOp = DIV 
    //17:Term1 = MulOp Factor Term1 
    |Node(17,_,mulOpNd::factorNd::term1Nd::_)  
        ->eVal0 factorNd 
          match mulOpNd with 
            |Node(15,_,_)  -> arr.[sp - 1] <- arr.[sp - 1] * arr.[sp]; sp <- (sp - 1) 
            |Node(16,_,_)  -> arr.[sp - 1] <- arr.[sp - 1] / arr.[sp]; sp <- (sp - 1) 
            |_ -> failwith "never occruable error"  
          eVal0 term1Nd 
    //18:Factor = NUM 
    |Node(18,_,Leaf(tk)::_) 
        -> let num = System.Int32.Parse(tk.Img) 
           sp <- sp + 1;arr.[sp] <- num 
    //19:Factor = LPAR Expression RPAR 
    |Node(19,_,_::expNode::_::_)  
        -> eVal0 expNode 
 
    |_ -> failwith "never occruable error" ;; 
 
val eVal0 : embodyST -> unit 
 
では一つ計算してみます。 
 
> let tree = tp.GetEBASTtree(["2 * (1 + 8) / 3  "]) 
eVal0 tree 
printfn "%A pointer = %d" arr sp;; 
[|0; 6; 3; 8; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 
  0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 
  0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 
  0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0|] pointer = 1 
   
pointerの指すarr.[1]にある6が答えです。 
 
式を与えると答えを表示する関数を定義してみます。 
 
> let calcAndDisp (srcLst:list<string>) = 
   let tree = tp.GetEBASTtree srcLst  
   sp <- 0 
   eVal0 tree 
   printfn "%d" arr.[sp];; 
 
val calcAndDisp : string list -> unit 
 
(使用例) 
> calcAndDisp (["2 * (1 + 2) / 3  - 6/(2+1)- 10"]);; 
-10 
val it : unit = () 
 
> calcAndDisp (["9 * (-1 + 2) / 3  +5"]);; 
val it : unit = () 
 
次回はバーチャルマシン上で式の計算をするようにしてみます。
スポンサーサイト

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

プロフィール

T GYOUTEN

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

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

この人とブロともになる

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