スポンサーサイト

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

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

 Whitespaceは「空白」「タブ」「改行」の三種類の文字から構成されたソースを読み込んで、動作するよう定義された、プログラミング言語でした。これのソースを目に見えるように変換する関数visualizeを前回定義しました。 
「空白タブ改行で構成されたソース」----visualize ----> 「s,t,nで構成された文字列」 
 
Whitespceは記憶用途のものとして、一つのスタックと、ヒープ領域(アドレスを指定して値を書き込んだり、読み込んだりできるメモリ)を使用するのでした。 
 
Whitespaceでは、ソースを命令文の連結したものだとして解釈し 
命令文の種類としては 
 ■ スタック操作 
 ■ 演算 
 ■ ヒープアクセス 
 ■ フロー制御 
 ■ I/O(input/output) 
 
の5種類があるのでした。 
 
今回はスタック操作関連の命令文を紹介します。 
次のような命令文があります。 
 
(1)ss数値表現->スタックに数値を積む。 
 例ssststn->スタックに5を積む 
 
(2)sns->スタックの一番上の値と同じ値をさらにもう一個積む 
 
(3)sts数値表現->スタックの上から数値番目の値と等しい値を一個積む。 
 
(4)snt->スタックの上から0番目の値と1番目の値を入れ替える 
 
(5)snn->スタックの一番上の値を取り除く 
 
(6)stn数値表現->スタックの上から1番目の値から数値番目までの値を取り除く 
 
stnで構成された文字列から、正規表現を利用してそれぞれの命令を切り出していくのですが、ワンクッションおいてこれをDiscriminated Union型の値に一度変換したいと思います。 
 
次のような型を定義します。 
 
type Command = 
    |SPush of int   //(1)に対応 
    |SDup            //(2)に対応 
    |SCopy of int   //(3)に対応 
    |SSwap          //(4)に対応 
    |SDiscard       //(5)に対応 
    |SSlide of int  //(6)に対応 
 
(1)のタイプである「ss数値表現」にマッチする正規表現は 
"^ss(?<num_part>(s|t)(s|t)+)n" 
となります。ここで、new (regex("^ss(?<num_part>(s|t)(s|t)+)n")と文字列を引数にして、ちゃんとマッチするとSome(Spush(?),マッチした長さ)という値を、マッチが空ならNoneを返す関数とタプルにして登録しておきます。 
分かりにくいので実際に定義してみます。 
 
> let exp1 = 
      ( new Regex("^ss(s|t)(?<num_part>(s|t)+)n"), 
        (fun (rg:Regex) str -> let wholeMatch = rg.Match(str) 
                               let partMatch =  wholeMatch.Groups.["num_part"]  
                               if partMatch.Value.Length > 0 then 
                                    Some(SPush(wToNum partMatch.Value),wholeMatch.Length) 
                               else None) 
      );; 
 
val exp1 : Regex * (Regex -> string -> (Command * int) option) = 
  (^ss(s|t)(?<num_part>(s|t)+)n, <fun:exp@14>) 
   
 
> (snd exp1) (fst exp1) "ssststn";; 
"ssts" 
val it : (Command * int) option = Some (SPush 5, 7) 
 
> (snd exp1) (fst exp1) "stssstsn";; 
val it : (Command * int) option = None 
 
(2)のタイプ「sns」これは簡単です。 
 
> let exp2 = 
      ( new Regex("^sns"), 
        (fun (rg:Regex) str -> let wholeMatch = rg.Match(str) 
                               if wholeMatch.Success = true then 
                                    Some(SDup,wholeMatch.Length) 
                               else None))  
;; 
 
val exp2 : Regex * (Regex -> string -> (Command * int) option) = 
  (^sns, <fun:exp2@7>) 
   
> (snd exp2) (fst exp2) "sns";; 
val it : (Command * int) option = Some (SDup, 3) 
 
あとのタイプも同様なので、いっきに定義してリストにしてしまいます。(同じようなコードが多いので、補助の関数を定義して短くした方がよいかとも思いますが、それは後においといて、とりあえずこのままいってしまいます。) 
 
> let ComKindLst = 
     [( new Regex("^ss(?<num_part>(s|t)(s|t)+)n"), 
        (fun (rg:Regex) str -> let wholeMatch = rg.Match(str) 
                               let partMatch =  wholeMatch.Groups.["num_part"]  
                               if partMatch.Value.Length > 0 then 
                                    Some(SPush(wToNum partMatch.Value),wholeMatch.Length) 
                               else None) 
      ); 
      ( new Regex("^sns"), 
        (fun (rg:Regex) str -> let wholeMatch = rg.Match(str) 
                               if wholeMatch.Success = true then 
                                    Some(SDup,wholeMatch.Length) 
                               else None) 
      );  
     ( new Regex("^sts(?<num_part>(s|t)(s|t)+)n"), 
        (fun (rg:Regex) str -> let wholeMatch = rg.Match(str) 
                               let partMatch =  wholeMatch.Groups.["num_part"]  
                               if partMatch.Value.Length > 0 then 
                                    Some(SCopy(wToNum partMatch.Value),wholeMatch.Length) 
                               else None) 
      ); 
      ( new Regex("^snt"), 
        (fun (rg:Regex) str -> let wholeMatch = rg.Match(str) 
                               if wholeMatch.Success = true then 
                                    Some(SSwap,wholeMatch.Length) 
                               else None) 
      );  
      ( new Regex("^snn"), 
        (fun (rg:Regex) str -> let wholeMatch = rg.Match(str) 
                               if wholeMatch.Success = true then 
                                    Some(SDiscard,wholeMatch.Length) 
                               else None) 
      );  
     ( new Regex("^stn(?<num_part>(s|t)(s|t)+)n"), 
        (fun (rg:Regex) str -> let wholeMatch = rg.Match(str) 
                               let partMatch =  wholeMatch.Groups.["num_part"]  
                               if partMatch.Value.Length > 0 then 
                                    Some(SSlide(wToNum partMatch.Value),wholeMatch.Length) 
                               else None) 
      )];; 
 
val ComKindLst : (Regex * (Regex -> string -> (Command * int) option)) list = 
  [(^ss(?<num_part>(s|t)(s|t)+)n, <fun:ComLst@15>); (^sns, <fun:ComLst@22-1>); 
   (^sts(?<num_part>(s|t)(s|t)+)n, <fun:ComLst@28-2>); 
   (^snt, <fun:ComLst@35-3>); (^snn, <fun:ComLst@41-4>); 
   (^stn(?<num_part>(s|t)(s|t)+)n, <fun:ComLst@47-5>)] 
 
上のComKindLstの要素の型に別名をつけておきます。 
 
> type CKL = System.Text.RegularExpressions.Regex * 
                         (System.Text.RegularExpressions.Regex -> string -> (Command * int) option) 
;; 
 
type CKL = Regex * (Regex -> string -> (Command * int) option) 
 
さて今回最後に"snssssstsn"というような文字列から[|SDup;SPush(5)|]というような、Commandeの配列を生成する関数を定義しておきます。 
 
準備として 
CKL型のリストと文字列を引数にして、リストの要素を使って次々にマッチするかどうかを試みて、マッチすればSome(SDunp)というような値、すべての要素でマッチしなければNoneを返す関数を定義します。 
(準備してある正規表現はすべて文字列の先頭とのマッチですので、文字列の先頭部分のマッチを調べることになります。) 
 
> 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;; 
 
val tryApply : CKL list -> string -> (Command * int) option 
 
テストしてみます。 
 
> tryApply ComKindLst "snssssstsn";; 
val it : (Command * int) option = Some (SDup, 3) 
 
> tryApply ComKindLst "stttssssssstsn";; 
val it : (Command * int) option = None 
 
ではこれを利用して文字列の最初から、どんどん文字列を切り取ってCommand型のリストにする関数を定義します。 
 
> let rec makeCLSub (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 
            makeCLSub cmdLst (str.Substring(len)) (index + len) (com::res) ;; 
 
val makeCLSub : CKL list -> string -> int -> Command list -> Command list 
 
> makeCLSub ComKindLst "snsssststn" 0 [];; 
val it : Command list = [SPush 5; SDup] //逆順に出てきます 
 
> makeCLSub ComKindLst "snsttsstsn" 0 [];; 
System.Exception: 3文字目からの部分でマッチするものが見つかりません 
   場所 FSI_0012.makeCLSub(FSharpList`1 cmdLst, String str, Int32 index, FSharpList`1 res) 
   場所 <StartupCode$FSI_0014>.$FSI_0014.main@() 
エラーのため停止しました 
  
では最後の仕上げに目的の「"snssssstsn"というような文字列から[|SDup;SPush(5)|]というような、Commandeの配列を生成する関数」を定義します。 
 
> let makeCArray (cmdLst:list<CKL>) (src:string) = 
    makeCASub cmdLst src 0 [] 
    |> List.rev 
    |> Array.ofList;; 
 
val makeCArray : CKL list -> string -> Command [] 
 
使ってみます。 
 
> makeCArray ComKindLst "snsssststn";; 
val it : Command [] = [|SDup; SPush 5|] 
スポンサーサイト

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

コメントの投稿

非公開コメント

プロフィール

T GYOUTEN

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

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

この人とブロともになる

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