スポンサーサイト

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

F#で入門 コンパイラ、インタプリタ編 LL(1)  LOGO風言語

 ここで一つ例としてミニ言語のインタープリタを作ってみたいと思います。 
これは結城浩さんの「Java言語で学ぶデザインパターン入門」に載っているものでタートルグラフィックの一種です。このミニ言語は、キャンバス上にある亀を制御するもので、goで1歩向いている方向に進み、その軌跡がキャンパス上に描かれます。rightで向きを90度右回転します。leftで向きを90度左回転します。このgo right leftの3つが基本命令で命令は並べて書くことができるとします。 
あとrepeatという予約語があり、repeat 回数 命令1 endで命令1を回数分繰り返すものとします。 
repeat .... endも命令として取り扱えるものとします。また全体をprogram とendではさむものとします。 
例(1) program go right go right end 
例(2) program repeat 3 go end end 
例(3) program go repeat 3 repeat 2 go right go left end end end (repeatのネスト(入れ子)) 
 
トークナイザーとしては、TokenizerFactoryを利用するとして 
let tknz = (new TokenizerFactory ([("NUM","\d+");("PROGRAM","program");("REPEAT","repeat");("EOF","eof"); 
                                   ("GO","go");("RIGHT","right");("LEFT","left");("END","end")                               
                        ])).GetTokenizer();; 
により得るものとします。 
 
この時、構文規則は例えば次の様に表せます。 
 
0: Z = program EOF 
1: Program = PROGRAM CommandList 
2: CommandList = Command END 
3: Command = ε 
4: Command = Command2 Command 
5: Command2 = RepeatCommand 
6: Command2 = PrimitiveCommand 
7: RepeatCommand = REPEAT NUM CommandList 
8: PrimitiveCommand = GO 
9: PrimitiveCommand = RIGHT 
10: PrimitiveCommand = LEFT 
 
3,4と5,6と 8,9,10の3つの部分で先読みにより場合分けが必要となるので前回作ったプログラムで構文解析表を見てみます。(この程度の文法なら、頭で考えた方が早いかとは思いますが。) 
 
1010-1.jpg 
1010-2.jpg 

 
Commandの部分では先読み記号がENDのときには3の文法、GO,LEFT,REPEAT,RIGHTの場合は4の文法を使って導出された形なので、そのように処理します。 
5,6と 8,9,10の部分も同様です。 
まずトークンを処理して具象抽象木を作ことから始めます。 
 
具象抽象木のノードは次の様に定義します。 
 
type embodyST = 
    |EPS_Leaf 
    |Leaf of Token //トークンを保持  
    |Node of int*list<embodyST> //intには文法番号を保持 
     
 
では具象抽象木を作る関数を定義します。 
 
//0  Z = program EOF 
let rec z (remain:list<Token>) =  
    let (rem2,madeNodeByProgram) = program remain 
    let shouldBeEofToken:Token = List.head rem2 //ここより後shouldBeをsbと略 
    if  shouldBeEofToken.Kind <> "EOF" then  
        failwith "構文エラー" 
    else 
        Node(0,[madeNodeByProgram;Leaf(shouldBeEofToken)]) 
 
//1  Program = PROGRAM CommandList 
and program (remain:list<Token>) = 
    match remain with 
    |sbProgramToken::tl when sbProgramToken.Kind = "PROGRAM" -> 
        let (rem2,madeNodeByCommandList) = commandList tl 
        (rem2,Node(1,[Leaf(sbProgramToken);madeNodeByCommandList])) 
    |_ ->  failwith "構文エラー 1" 
 
//2  CommandList = Command END 
and commandList (remain:list<Token>) = 
    let (rem2,madeNodeByCommand) = command remain 
    let sbEndToken:Token = List.head rem2 
    if sbEndToken.Kind <> "END" then 
        failwith "構文エラー 2" 
    else 
        (List.tail rem2,Node(2,[madeNodeByCommand;Leaf(sbEndToken)])) 
 
//3  Command = ε 
//4  Command = Command2 Command 
and command (remain:list<Token>) = 
    match remain with 
    |hd::tl when hd.Kind = "END" -> (remain,Node(3,[EPS_Leaf]))  
    |hd::tl when hd.Kind = "GO" || hd.Kind = "LEFT" || hd.Kind = "REPEAT" ||hd.Kind = "RIGHT" 
            -> let (rem2,madeNodeByCommand2) = command2 remain 
               let (rem3,madeNodeByCommand) = command rem2 
               (rem3,Node(4,[madeNodeByCommand2;madeNodeByCommand]))  
    | _ -> failwith "構文エラー 3 4 " 
 
//5Command2 = RepeatCommand 
//6Command2 = PrimitiveCommand 
and  command2  (remain:list<Token>) = 
    match remain with 
    |hd::_ when hd.Kind = "REPEAT"  
        -> let (rem2,madeNodeByRepeatCommand) = repeatCommand remain 
           (rem2, Node(5,[madeNodeByRepeatCommand])) 
    |hd::_ when hd.Kind = "GO" || hd.Kind = "LEFT" ||hd.Kind = "RIGHT" 
        -> let (rem2,madeNodeByPrimitiveCommand) = primitiveCommand remain 
           (rem2,Node(6,[madeNodeByPrimitiveCommand])) 
    | _ -> failwith "構文エラー 5 6" 
 
//7  RepeatCommand = REPEAT NUM CommandList 
and repeatCommand (remain:list<Token>) = 
    match remain with 
    |sbRepeatToken::sbNumToken::tl when sbRepeatToken.Kind = "REPEAT" && sbNumToken.Kind = "NUM" 
        -> let (rem2,madeNodeByCommandList) = commandList tl 
           (rem2,Node(7,[Leaf(sbRepeatToken);Leaf(sbNumToken);madeNodeByCommandList]))  
    | _ -> failwith "構文エラー 7" 
 
//8  PrimitiveCommand = GO 
//9  PrimitiveCommand = RIGHT 
//10 PrimitiveCommand = LEFT 
and primitiveCommand (remain:list<Token>) = 
    match remain with 
    |hd::tl when hd.Kind = "GO" -> (tl,Node(8,[Leaf(hd)])) 
    |hd::tl when hd.Kind = "RIGHT" -> (tl,Node(9,[Leaf(hd)])) 
    |hd::tl when hd.Kind = "LEFT" -> (tl,Node(10,[Leaf(hd)])) 
    | _ -> failwith "構文エラー 8 9 10" 
     
Token型とTokenizeOneLineResult型およびTokenizerFactory型が定義された状態で、テストしてみます。 
これらのクラスの定義コードは既出のものを最後にまとめて載っけておきます。 
 
ではテストしてみます。関数zから始めるので、ソースの最後にeofが必要となります。 
 
> let tknz = (new TokenizerFactory ([("NUM","\d+");("PROGRAM","program");("REPEAT","repeat");("EOF","eof"); 
                                   ("GO","go");("RIGHT","right");("LEFT","left");("END","end")                               
                        ])).GetTokenizer();; 
 
val tknz : (string list -> Token list) 
 
(実行例) 
> z (tknz ["program go right go right end eof"]);; 
val it : embodyST = 
  Node 
    (0, 
     [Node 
        (1, 
         [Leaf [PROGRAM   program  (1,1)]  {Col = 1; 
                                            Img = "program"; 
                                            Kind = "PROGRAM"; 
                                            Row = 1;}; 
          Node 
            (2, 
             [Node 
                (4, 
                 [Node (6,[Node (8,[Leaf [GO   go  (1,9)]  {Col = 9; 
                                                            Img = "go"; 
                                                            Kind = "GO"; 
                                                            Row = 1;}])]); 
                  Node 
                    (4, 
                     [Node 
                        (6, 
                         [Node 
                            (9,[Leaf [RIGHT   right  (1,12)]  {Col = 12; 
                                                               Img = "right"; 
                                                               Kind = "RIGHT"; 
                                                               Row = 1;}])]); 
                      Node 
                        (4, 
                         [Node 
                            (6,[Node (8,[Leaf [GO   go  (1,18)]  {Col = 18; 
                                                                  Img = "go"; 
                                                                  Kind = "GO"; 
                                                                  Row = 1;}])]); 
                          Node 
                            (4, 
                             [Node 
                                (6, 
                                 [Node 
                                    (9, 
                                     [Leaf 
                                        [RIGHT   right  (1,21)]  
                                          {Col = 21; 
                                           Img = "right"; 
                                           Kind = "RIGHT"; 
                                           Row = 1;}])]); Node (3,[EPS_Leaf])])])])]); 
              Leaf [END   end  (1,27)]  {Col = 27; 
                                         Img = "end"; 
                                         Kind = "END"; 
                                         Row = 1;}])]); 
      Leaf [EOF   eof  (1,31)]  {Col = 31; 
                                 Img = "eof"; 
                                 Kind = "EOF"; 
                                 Row = 1;}]) 
 
 
次にこの木を引数にして、動いていく点と方向を表示するようにしてみます。 
向きは0から3までの整数であらわすことにしてます。 
> let getDirecStr i =  
    if i = 0 then "RIGHT" 
    elif i = 1 then "DOWN" 
    elif i = 2 then "LEFT" 
    else "UP";; 
 
val getDirecStr : int -> string 
 
向きを変える関数はつぎのようになります。 
> let turnRight i = (i + 1) % 4 
let turnLeft  i = (i - 1) % 4;; 
 
val turnRight : int -> int 
val turnLeft : int -> int 
 
次の位置を返す関数は次です。(yは下方向が正の方向です。) 
> let getNextPos i (x,y) = 
    if i = 0 then (x + 1,y) 
    elif i = 1 then (x,y + 1) 
    elif i = 2 then (x - 1 ,y) 
    else (x, y - 1);; 
 
val getNextPos : int -> int * int -> int * int 
 
広域変数として、点の位置と方向を定義します。 
 
> let mutable GL_POS = (0,0) 
let mutable GL_DIR = 0;; 
 
val mutable GL_POS : int * int = (0, 0) 
val mutable GL_DIR : int = 0 
 
さて 
type embodyST = 
    |EPS_Leaf 
    |Leaf of Token //トークンを保持  
    |Node of int*list<embodyST> //intには文法番号を保持 
     
と定義されていたので。Nodeの文法番号で、これにより、list部分にどのようなノードが並んでいるかが分かるので、それぞれの処理を書いていきます。 
 
> let rec eVal1 (eb:embodyST) = 
    match eb with 
    //0  Z = program EOF 
    |Node(i,pro::_) when i = 0     
        -> GL_POS <- (0,0)//最初に点(0,0)にあるとする 
           GL_DIR <- 0    //最初右向きとする 
           eVal1 pro 
    //1  Program = PROGRAM CommandList 
    |Node(i,_:: cl :: _ ) when i = 1     
        -> eVal1 cl 
    //2  CommandList = Command END 
    |Node(i,cd ::_ ) when i = 2     
        -> eVal1 cd 
    //3  Command = ε 
    |Node(i,_ ) when i = 3     
        -> () 
    //4  Command = Command2 Command 
    |Node(i,cd2::cd::_) when i = 4     
        -> eVal1 cd2 
           eVal1 cd 
    //5  Command2 = RepeatCommand 
    |Node(i,rc::_) when i = 5     
        -> eVal1 rc 
    //6  Command2 = PrimitiveCommand 
    |Node(i,pc::_) when i = 6     
        -> eVal1 pc 
    //7  RepeatCommand = REPEAT NUM CommandList 
    |Node(i,_::Leaf(intStr)::cl::_) when i = 7     
        ->  let repeatNum = System.Int32.Parse(intStr.Img) 
            for  i = 1 to repeatNum do   
                eVal1 cl 
    //8  PrimitiveCommand = GO 
    |Node(i,_) when i = 8     
        -> let nextPos = getNextPos GL_DIR GL_POS 
           printfn "go %s from %A to %A" (getDirecStr GL_DIR) GL_POS nextPos 
           GL_POS <-  nextPos 
    //9  PrimitiveCommand = RIGHT 
    |Node(i,_) when i = 9    
        -> let nextDir = turnRight GL_DIR 
           GL_DIR <-  nextDir 
           printfn "turn Right now head for %A" (getDirecStr GL_DIR) 
    //10 PrimitiveCommand = LEFT        
    |Node(i,_) when i = 10    
        -> let nextDir = turnLeft GL_DIR 
           GL_DIR <-  nextDir 
           printfn "turn Left now head for %A" (getDirecStr GL_DIR) 
    |_ -> printfn "error";; 
 
val eVal1 : embodyST -> unit 
 
では使ってみます。 
(実行例1) 
> eVal1 (z (tknz ["program go right go right end eof"]));; 
 
go RIGHT from (0, 0) to (1, 0) 
turn Right now head for "DOWN" 
go DOWN from (1, 0) to (1, 1) 
turn Right now head for "LEFT" 
val it : unit = () 
 
(実行例2) 
> eVal1 (z (tknz ["program repeat 3 go end end eof"]));; 
 
go RIGHT from (0, 0) to (1, 0) 
go RIGHT from (1, 0) to (2, 0) 
go RIGHT from (2, 0) to (3, 0) 
val it : unit = () 
 
(実行例3) 
> eVal1 (z (tknz ["program go repeat 3 repeat 2 go right go left end end end eof"]));; 
 
go RIGHT from (0, 0) to (1, 0) 
go RIGHT from (1, 0) to (2, 0) 
turn Right now head for "DOWN" 
go DOWN from (2, 0) to (2, 1) 
turn Left now head for "RIGHT" 
go RIGHT from (2, 1) to (3, 1) 
turn Right now head for "DOWN" 
go DOWN from (3, 1) to (3, 2) 
turn Left now head for "RIGHT" 
go RIGHT from (3, 2) to (4, 2) 
turn Right now head for "DOWN" 
go DOWN from (4, 2) to (4, 3) 
turn Left now head for "RIGHT" 
go RIGHT from (4, 3) to (5, 3) 
turn Right now head for "DOWN" 
go DOWN from (5, 3) to (5, 4) 
turn Left now head for "RIGHT" 
go RIGHT from (5, 4) to (6, 4) 
turn Right now head for "DOWN" 
go DOWN from (6, 4) to (6, 5) 
turn Left now head for "RIGHT" 
go RIGHT from (6, 5) to (7, 5) 
turn Right now head for "DOWN" 
go DOWN from (7, 5) to (7, 6) 
turn Left now head for "RIGHT" 
val it : unit = () 
 
なお具象抽象木を作る関数は自動化できるので、次回はこれをやります。 
 
今回のコードは以下の通りです。 

続きを読む

スポンサーサイト

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

プロフィール

T GYOUTEN

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

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

この人とブロともになる

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