スポンサーサイト

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

F#で入門 コンパイラ、インタプリタ編 Whitespace(8)

 前回でプログラムの特定の場所をマークしてラベルをつけることができるようになりました。 
今回はそれを使用してジャンプ命令を実装していきます。 
 
まず「ラベルとプログラムカウンタの対応表」と「プログラムカウンタ(エラー表示用)」と「ラベル」を渡して、ラベルからプログラムカウンタを返す関数を定義しておきます。 
 
> let getPC (labelMap:Map<string,int>) (pc:int) (label:string) = 
    let findRes = Map.tryFind label labelMap 
    if findRes.IsSome then 
        findRes.Value 
    else 
        failwith (sprintf "index:%d 対応するラベルがありません。" pc);; 
 
val getPC : Map<string,int> -> int -> string -> int 
 
テストしてみます。 
> getPC (Map.ofList [("tssn",3);("stn",8)]) 17 "stn";; 
val it : int = 8 
 
> getPC (Map.ofList [("tssn",3);("stn",8)]) 17 "sttn";; 
System.Exception: index:17 対応するラベルがありません。 
.... 
エラーのため停止しました 
 
では準備がそろったところでジャンプ命令を実装していきます。 
ジャンプ命令には次の3種類があります。 
 
nsnラベル   無条件でラベルへジャンプします。 
ntsラベル   スタックのトップの数が0ならラベルへジャンプします。 
nttラベル   スタックのトップの数が負ならラベルへジャンプします 
 
追加変更場所はいつも通り4か所です。 
 
(1)Command Type への追加 
名前はNJump,NJumpZero,NJumpNegaとします 
 
type Command = 
    |SPush of int 
    ........... 
    |NJump of string 
    |NJumpZero of string 
    |NJumpNega of string 
 
(2)ComKindLstへの追加 
 
      ( new Regex("^nsn(?<str_part>(s|t)+n)"), 
        (fun (rg:Regex) str -> createFromString "str_part" rg str (fun str -> NJump(str)))); 
      ( new Regex("^nts(?<str_part>(s|t)+n)"), 
        (fun (rg:Regex) str -> createFromString "str_part" rg str (fun str -> NJumpZero(str)))); 
      ( new Regex("^ntt(?<str_part>(s|t)+n)"), 
        (fun (rg:Regex) str -> createFromString "str_part" rg str (fun str -> NJumpNega(str)))); 
 
(3)対応する関数の追加 
 
> let do_NJump (labelMap:Map<string,int>) (label:string) ((pc,stcLst,heapMap,rIndexLst):WState) = 
    let next_pc = getPC labelMap pc label 
    (next_pc,stcLst,heapMap,rIndexLst);; 
 
val do_NJump : 
  Map<string,int> -> 
    string -> 
      int * int list * Map<int,int> * int list -> 
        int * int list * Map<int,int> * int list 
 
条件付きジャンプは補助関数を定義して、それを部分適用することで定義します。 
 
> let do_NJumpCondSub (f:int->bool) (labelMap:Map<string,int>) (label:string)  
                    ((pc,stcLst,heapMap,rIndexLst):WState)   = 
    match stcLst with 
    |v::rem -> if f v then  
                  let next_pc = getPC labelMap pc label 
                  (next_pc,rem,heapMap,rIndexLst) 
               else 
                  (pc+1,rem,heapMap,rIndexLst) 
    |_      -> failwith(sprintf "index:%d スタックが空なので条件ジャンプできません。" pc)  ;; 
 
val do_NJumpCondSub : 
  (int -> bool) -> 
    Map<string,int> -> 
      string -> 
        int * int list * Map<int,int> * int list -> 
          int * int list * Map<int,int> * int list 
 
> let do_NJumpZero = do_NJumpCondSub (fun i -> i = 0);; 
 
val do_NJumpZero : 
  (Map<string,int> -> string -> WState -> 
     int * int list * Map<int,int> * int list) 
 
> let do_NJumpNega = do_NJumpCondSub (fun i -> i < 0);; 
 
val do_NJumpNega : 
  (Map<string,int> -> string -> WState -> 
     int * int list * Map<int,int> * int list) 
 
(4)processCmdへの追加 
 
        |NJump(lb)    -> do_NJump labelMap lb t     |> processCmdSub 
        |NJumpZero(lb)-> do_NJumpZero labelMap lb t |> processCmdSub 
        |NJumpNega(lb)-> do_NJumpNega labelMap lb t |> processCmdSub 
 
 
ではテストしてみます。 
 
無条件ジャンプ 
> processCmd [|SPush(7);NJump("tstn");SPush(3);NMark("tstn");SPush(10);FExit|] (0,[],Map.empty,[]);; 
ラベル::pc対応Map map [("tstn", 3)] 
(0, [], map [], []) 
SPush 7 
(1, [7], map [], []) 
NJump "tstn" 
(3, [7], map [], []) 
NMark "tstn" 
(4, [7], map [], []) 
SPush 10 
(5, [10; 7], map [], []) 
FExit 
 
条件付きジャンプ 
 
> processCmd [|SPush(0);NJumpZero("tstn");NJump("tttn"); 
             NMark("tstn");SPush(10);FExit; 
             NMark("tttn");SPush(17);FExit|]  
             (0,[],Map.empty,[]);; 
ラベル::pc対応Map map [("tstn", 3); ("tttn", 6)] 
(0, [], map [], []) 
SPush 0 
(1, [0], map [], []) 
NJumpZero "tstn" 
(3, [], map [], []) 
NMark "tstn" 
(4, [], map [], []) 
SPush 10 
(5, [10], map [], []) 
FExit 
val it : unit = () 
 
> processCmd [|SPush(1);NJumpZero("tstn");NJump("tttn"); 
             NMark("tstn");SPush(10);FExit; 
             NMark("tttn");SPush(17);FExit|]  
             (0,[],Map.empty,[]);; 
ラベル::pc対応Map map [("tstn", 3); ("tttn", 6)] 
(0, [], map [], []) 
SPush 1 
(1, [1], map [], []) 
NJumpZero "tstn" 
(2, [], map [], []) 
NJump "tttn" 
(6, [], map [], []) 
NMark "tttn" 
(7, [], map [], []) 
SPush 17 
(8, [17], map [], []) 
FExit 
val it : unit = ()  
 
> processCmd [|SPush(-7);NJumpNega("tstn");NJump("tttn"); 
             NMark("tstn");SPush(10);FExit; 
             NMark("tttn");SPush(17);FExit|]  
             (0,[],Map.empty,[]);; 
ラベル::pc対応Map map [("tstn", 3); ("tttn", 6)] 
(0, [], map [], []) 
SPush -7 
(1, [-7], map [], []) 
NJumpNega "tstn" 
(3, [], map [], []) 
NMark "tstn" 
(4, [], map [], []) 
SPush 10 
(5, [10], map [], []) 
FExit 
val it : unit = () 
 
ここまでの全コードは次の通りです。 
 open System.Text.RegularExpressions 
 
////////////////正規表現用の補助関数/////////////// 
 
let myReplace (regStr:string) (repStr:string) (oriSrcStr:string)= 
    (new Regex(regStr)).Replace(oriSrcStr,repStr) 
 
///////////////視覚化関数////////////////////////// 
 
let visualize (src:string) = 
    src 
    |> myReplace "[^\s]" "" 
    |> myReplace " " "s" 
    |> myReplace "\t" "t" 
    |> myReplace "\n" "n" 
 
/////////////s,t,nによる数値表現をintに変換する関数// 
 
let wToNum (str:string) = 
    let strbiNum = 
        str.Substring(1) 
        |> myReplace "s" "0" 
        |> myReplace "t" "1" 
    let absPart10 = System.Convert.ToInt32 (strbiNum,2) 
    //printfn "%A" (str.Substring(0)) 
    if str.Substring(0,1) = "s" then absPart10 
    elif str.Substring(0,1) = "t" then (-1)*absPart10 
    else failwith "数値表現エラー" 
 
/////////////プログラムの中核をなすコマンド型/////// 
 
type Command = 
    |SPush of int 
    |SDup 
    |SCopy of int 
    |SSwap 
    |SDiscard 
    |SSlide of int 
    |TSAdd 
    |TSSub 
    |TSMul 
    |TSDiv 
    |TSMod 
    |TTStore 
    |TTRetrieve 
    |NMark of string 
    |NJump of string 
    |NJumpZero of string 
    |NJumpNega of string 
    |FExit 
 
/////////////正規表現で切り出す補助関数群///////// 
 
let createFromInt (partStr:string) (rg:Regex) (str:string) (creInt:int->Command) = 
         let wholeMatch = rg.Match(str) 
         let partMatch = wholeMatch.Groups.[partStr] 
         if partMatch.Value.Length > 0 then 
            Some(creInt(wToNum partMatch.Value),wholeMatch.Length) 
         else 
            None 
 
let createFromNothing (rg:Regex) (str:string) (cre:unit->Command) = 
        let wholeMatch = rg.Match(str) 
        if wholeMatch.Success = true then 
               Some(cre(),wholeMatch.Length) 
        else None 
 
let createFromString (partStr:string) (rg:Regex) (str:string) (creStr:string->Command) = 
         let wholeMatch = rg.Match(str) 
         let partMatch = wholeMatch.Groups.[partStr] 
         if partMatch.Value.Length > 0 then 
            Some(creStr( partMatch.Value),wholeMatch.Length) 
         else 
            None 
 
 
/////////////正規表現での切り出し対応タプルリスト// 
 
let ComKindLst = 
     [(new Regex("^ss(?<num_part>(s|t)(s|t)+)n"), 
        (fun (rg:Regex) str -> createFromInt "num_part" rg str (fun num -> SPush(num)))); 
      ( new Regex("^sns"), 
        (fun (rg:Regex) str -> createFromNothing rg str (fun () -> SDup))); 
      ( new Regex("^sts(?<num_part>(s|t)(s|t)+)n"), 
        (fun (rg:Regex) str -> createFromInt "num_part" rg str (fun num -> SCopy(num)))); 
      ( new Regex("^snt"), 
        (fun (rg:Regex) str -> createFromNothing rg str (fun () -> SSwap))); 
      ( new Regex("^snn"), 
        (fun (rg:Regex) str -> createFromNothing rg str (fun () -> SDiscard))); 
      ( new Regex("^stn(?<num_part>(s|t)(s|t)+)n"), 
        (fun (rg:Regex) str -> createFromInt "num_part" rg str (fun num -> SSlide(num)))); 
      ( new Regex("^tsss"), 
        (fun (rg:Regex) str -> createFromNothing rg str (fun () -> TSAdd))); 
      ( new Regex("^tsst"), 
        (fun (rg:Regex) str -> createFromNothing rg str (fun () -> TSSub))); 
      ( new Regex("^tssn"), 
        (fun (rg:Regex) str -> createFromNothing rg str (fun () -> TSMul))); 
      ( new Regex("^tsts"), 
        (fun (rg:Regex) str -> createFromNothing rg str (fun () -> TSDiv))); 
      ( new Regex("^tstt"), 
        (fun (rg:Regex) str -> createFromNothing rg str (fun () -> TSMod))); 
      ( new Regex("^tts"), 
        (fun (rg:Regex) str -> createFromNothing rg str (fun () -> TTStore))); 
      ( new Regex("^ttt"), 
        (fun (rg:Regex) str -> createFromNothing rg str (fun () -> TTRetrieve))); 
      ( new Regex("^nss(?<str_part>(s|t)+n)"), 
        (fun (rg:Regex) str -> createFromString "str_part" rg str (fun str -> NMark(str)))); 
      ( new Regex("^nsn(?<str_part>(s|t)+n)"), 
        (fun (rg:Regex) str -> createFromString "str_part" rg str (fun str -> NJump(str)))); 
      ( new Regex("^nts(?<str_part>(s|t)+n)"), 
        (fun (rg:Regex) str -> createFromString "str_part" rg str (fun str -> NJumpZero(str)))); 
      ( new Regex("^ntt(?<str_part>(s|t)+n)"), 
        (fun (rg:Regex) str -> createFromString "str_part" rg str (fun str -> NJumpNega(str)))); 
      ( new Regex("^nnn"), 
        (fun (rg:Regex) str -> createFromNothing rg str (fun () -> FExit))); 
     ] 
 
 
////////上のComKindLstの要素の型の別名///////////////////////// 
 
type CKL = System.Text.RegularExpressions.Regex * 
                         (System.Text.RegularExpressions.Regex -> string -> (Command * int) option) 
 
///////下のmakeCLSubの補助関数///////////////////////////////// 
 
let rec tryApply (cmdLst:list<CKL>) (str:string) = 
    match cmdLst with 
    | [] -> None 
    | (rg,f)::tl -> let res = f rg str 
                    if res.IsSome then 
                        res 
                    else 
                        tryApply tl str 
///////下のmakeCArrayの補助関数///////////////////////////////// 
 
let rec makeCASub (cmdLst:list<CKL>) (str:string) (index:int) (res:list<Command>) = 
    if str.Length = 0 then  
        res 
    else 
        let matchRes = tryApply cmdLst str 
        if matchRes = None then 
            failwith (sprintf "%d文字目からの部分でマッチするものが見つかりません" index) 
        else 
            let (com,len) = matchRes.Value 
            makeCASub cmdLst (str.Substring(len)) (index + len) (com::res)  
 
//////"stss.."等のstringから [|SDup; SPush 5...|]のような配列を作る関数//////////////////////                  
 
let makeCArray (cmdLst:list<CKL>) (src:string) = 
    makeCASub cmdLst src 0 [] 
    |> List.rev 
    |> Array.ofList 
 
/////[|SDup; NMark "ttn";..|]のような配列から、map [("ttn",1;..]というような対応表を作る関数/// 
 
let makeLabelMap (cmdArr:Command[]) = 
    let rec makeLabelMapSub cmdLst index res = 
        match cmdLst with 
        | [] -> res 
        |NMark(label)::tl ->makeLabelMapSub tl (index+1) (Map.add label index res) 
        |hd::tl           ->makeLabelMapSub tl (index+1)  res 
    makeLabelMapSub (List.ofArray cmdArr) 0 (Map.empty)     
 
////////ラベルからプログラムカウンタを返す関数////////////////////////// 
////////引数のプログラムカウンタはエラー表示用////////////////////////// 
 
let getPC (labelMap:Map<string,int>) (pc:int) (label:string) = 
    let findRes = Map.tryFind label labelMap 
    if findRes.IsSome then 
        findRes.Value 
    else 
        failwith (sprintf "index:%d 対応するラベルがありません。" pc) 
 
///////状態を表すタプルの別名//////////////////////////////////// 
 
type WState = int*list<int>*Map<int,int>*list<int> 
 
///////それぞれの命令に対応する関数群//////////////////////////// 
 
let do_SDup ((pc,stcLst,heapMap,rIndexLst):WState) = 
    if List.length stcLst = 0 then failwith(sprintf "index:%d スタックが空でDupできません。" pc) 
    (pc+1,(List.head stcLst)::stcLst,heapMap,rIndexLst) 
 
let do_SSwap((pc,stcLst,heapMap,rIndexLst):WState) = 
    match stcLst with 
    |h1::h2::tl -> (pc+1,h2::h1::tl,heapMap,rIndexLst) 
    | _-> failwith(sprintf "index:%d スタックの要素の個数が1以下です" pc) 
   
let do_SDiscard ((pc,stcLst,heapMap,rIndexLst):WState) = 
    if List.length stcLst = 0 then failwith(sprintf "index:%d スタックが空でDiscardできません。" pc) 
    (pc+1,(List.tail stcLst),heapMap,rIndexLst) 
 
let do_SPush (num:int) ((pc,stcLst,heapMap,rIndexLst):WState) = 
    (pc+1,num::stcLst,heapMap,rIndexLst) 
 
let do_SCopy (n:int) ((pc,stcLst,heapMap,rIndexLst):WState) =     
    if (List.length stcLst) <= n then  failwith(sprintf "index:%d スタックの要素数がたりずにSCopyできません。" pc) 
    let tempArr = Array.ofList stcLst 
    (pc+1,(tempArr.[n])::stcLst,heapMap,rIndexLst) 
     
let do_SSlide (n:int) ((pc,stcLst,heapMap,rIndexLst):WState) = 
    if (List.length stcLst) <= n then  failwith(sprintf "index:%d スタックの要素数がたりずにSSlideできません。" pc) 
    let tempArr = Array.ofList stcLst 
    let slicedArr = tempArr.[(n + 1) ..] 
    let newStcLst = (List.head stcLst)::(List.ofArray slicedArr) 
    (pc+1,newStcLst,heapMap,rIndexLst) 
 
let do_OpSub (op:int->int->int) ((pc,stcLst,heapMap,rIndexLst):WState) = 
    match stcLst with 
    |v1::v2::rem -> (pc+1,(op v2 v1)::rem,heapMap,rIndexLst) 
    | _     ->failwith(sprintf "index:%d スタックの要素数がたりずに演算できません。" pc) 
     
let do_TSAdd (t:WState) =  
    do_OpSub (+) t   
 
let do_TSSub (t:WState) =  
    do_OpSub (-) t   
 
let do_TSMul (t:WState) =  
    do_OpSub (*) t   
 
let do_TSDiv (t:WState) =  
    do_OpSub (/) t   
 
let do_TSMod (t:WState) =  
    do_OpSub (%) t   
 
let do_TTStore ((pc,stcLst,heapMap,rIndexLst):WState) = 
    match stcLst with 
    |v1::v2::rem -> (pc+1,rem,Map.add v2 v1 heapMap,rIndexLst) 
    |_    ->failwith(sprintf "index:%d スタックの要素数がたりずにStoreできません。" pc) 
 
let do_TTRetrieve ((pc,stcLst,heapMap,rIndexLst):WState) = 
    match stcLst with 
    |v::rem -> let retreivedVal = Map.tryFind v heapMap 
               if retreivedVal.IsSome then 
                    (pc+1,retreivedVal.Value::rem,heapMap,rIndexLst) 
               else failwith(sprintf "index:%d 指定されたアドレスにデータがないためRetrieveできません。" pc) 
    |_    ->failwith(sprintf "index:%d スタックの要素数がたりずにRetrieveできません。" pc) 
 
let do_NMark (label:string) ((pc,stcLst,heapMap,rIndexLst):WState) = 
    (pc+1,stcLst,heapMap,rIndexLst) 
 
let do_NJump (labelMap:Map<string,int>) (label:string) ((pc,stcLst,heapMap,rIndexLst):WState) = 
    let next_pc = getPC labelMap pc label 
    (next_pc,stcLst,heapMap,rIndexLst) 
 
let do_NJumpCondSub (f:int->bool) (labelMap:Map<string,int>) (label:string)  
                    ((pc,stcLst,heapMap,rIndexLst):WState)   = 
    match stcLst with 
    |v::rem -> if f v then  
                  let next_pc = getPC labelMap pc label 
                  (next_pc,rem,heapMap,rIndexLst) 
               else 
                  (pc+1,rem,heapMap,rIndexLst) 
    |_      -> failwith(sprintf "index:%d スタックが空なので条件ジャンプできません。" pc)   
 
let do_NJumpZero = do_NJumpCondSub (fun i -> i = 0) 
 
let do_NJumpNega = do_NJumpCondSub (fun i -> i < 0) 
 
let do_FExit ((pc,stcLst,heapMap,rIndexLst):WState) =     
    () 
 
 
////////命令を解釈しながら状態を変化させていく中心の関数//////////////// 
 
let rec processCmd (cmds :Command[]) (startWState:WState) = 
    let labelMap = makeLabelMap cmds //ジャンプ命令で使用する  
    printfn "ラベル::pc対応Map %A" labelMap //デバック用 
    let rec processCmdSub  ((pc,stcLst,heapMap,rIndexLst) as t:WState) = 
        if pc < 0 || pc >= Array.length cmds then failwith (sprintf "index:%d pcが領域外です" pc) 
        printfn "%A" t  //デバック用 
        let cur_cmd = cmds.[pc] //現在のプログラムカウンタにある命令をとってくる 
        printfn "%A" cur_cmd //デバック用 
        match cur_cmd with 
        |SPush(num)   -> do_SPush num t  |> processCmdSub 
        |SDup         -> do_SDup t       |> processCmdSub 
        |SCopy (n)    -> do_SCopy n t    |> processCmdSub 
        |SSwap        -> do_SSwap t      |> processCmdSub 
        |SDiscard     -> do_SDiscard t   |> processCmdSub 
        |SSlide (n)   -> do_SSlide n t   |> processCmdSub 
        |TSAdd        -> do_TSAdd t      |> processCmdSub 
        |TSSub        -> do_TSSub t      |> processCmdSub 
        |TSMul        -> do_TSMul t      |> processCmdSub 
        |TSDiv        -> do_TSDiv t      |> processCmdSub 
        |TSMod        -> do_TSMod t      |> processCmdSub 
        |TTStore      -> do_TTStore t    |> processCmdSub 
        |TTRetrieve   -> do_TTRetrieve t |> processCmdSub 
        |NMark(lb)    -> do_NMark lb t   |> processCmdSub 
        |NJump(lb)    -> do_NJump labelMap lb t     |> processCmdSub 
        |NJumpZero(lb)-> do_NJumpZero labelMap lb t |> processCmdSub 
        |NJumpNega(lb)-> do_NJumpNega labelMap lb t |> processCmdSub 
        |FExit       -> do_FExit t 
    processCmdSub startWState 
 
スポンサーサイト

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

コメントの投稿

非公開コメント

プロフィール

T GYOUTEN

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

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

この人とブロともになる

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