スポンサーサイト

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

F#で入門 コンパイラ、インタプリタ編 抽象構文木

 前回で、構文規則 
0:Z = Program EOF 
1:Program = NUM Program2 
2:Program2 = PLUS Program 
3:Program2 = EPSILON   
に従ったトークン列 [NUM;PLUS;NUM;EOF]を 
具象構文木 
  Node 
    [Node [Leaf NUM; Node [Leaf PLUS; Node [Leaf NUM; Leaf EPSILON]]]; 
     Leaf EOF] 
に変換する方法を考えました。 
具象構文木は「それぞれの構文規則の左辺に対応するノード」から右辺の終端及び非終端記号の数だけ枝が出るので、少し冗長になります。そこで、無駄なものを省いてすっきりした木構造に直して、後の処理をすることが多くなります。このような木構造を抽象構文木(abstract syntax tree)といいます。構文木の構造は、コードを書く人に任せられているので、使いやすいようにデザインすることになります。cなどを使う場合は一種類のノードで共用体などを駆使してやっていくようですし、Javaやc#では基底ノードから何種類かのノードを派生させてこれを利用することが多いみたいです。F#の場合はdiscriminated unionを利用する場合が多いのではないかと思います。 
では今回は上の例を単純な2本木として表現してみます。 
 
> type TokenKind = 
    |NUM 
    |PLUS 
    |EPSILON 
    |EOF 
 
type AST = 
    |Leaf 
    |NullLeaf //ε対応  
    |AddNode of AST*AST 
 
//0:Z = Program EOF対応部分 
let rec z (remain:list<TokenKind>) = 
      let (rem2,madeNodeByProgram) = program remain        
      if rem2 <> [EOF] then  
        failwith "構文エラー" 
      else 
        madeNodeByProgram 
 
//1:Program = NUM Program2対応部分 
and program (remain:list<TokenKind>) = 
       match remain with 
       |NUM::rem2 -> let (rem3,madeNodeByProgram2) = program2 rem2 
                     (rem3,AddNode(Leaf,madeNodeByProgram2))  
       |_ ->  failwith "構文エラー" 
 
//2:Program2 = PLUS Program 
//3:Program2 = EPSILON 対応部分   
and program2 (remain:list<TokenKind>) = 
       match remain with 
       |PLUS::rem2 ->let (rem3,madeNodeByProgram) = program rem2 
                     (rem3,madeNodeByProgram)  
       |EOF::rem2    ->(EOF::rem2,NullLeaf) //εの場合は残りトークンの先頭はEOF 
       |_ ->  failwith "構文エラー";; 
 
(返答略) 
  
(実行例) 
> z [NUM;EOF];; 
val it : AST = AddNode (Leaf,NullLeaf) 
 
> z [NUM;PLUS;NUM;EOF];; 
val it : AST = AddNode (Leaf,AddNode (Leaf,NullLeaf)) 
 
> z [NUM;PLUS;NUM;PLUS;NUM;EOF];; 
val it : AST = AddNode (Leaf,AddNode (Leaf,AddNode (Leaf,NullLeaf))) 
 
 
εに対応するNullLeafがASTに現れるのが不細工なのでprogram部分の  
       |NUM::rem2 -> let (rem3,madeNodeByProgram2) = program2 rem2 
                     (rem3,AddNode(Leaf,madeNodeByProgram2))  
を 
       |NUM::rem2 -> let (rem3,madeNodeByProgram2) = program2 rem2 
                     if madeNodeByProgram2 = NullLeaf then 
                        (rem3,Leaf) 
                     else 
                        (rem3,AddNode(Leaf,madeNodeByProgram2))  
に直します。これで実行してみると、 
 
> z [NUM;EOF];; 
val it : AST = Leaf 
 
> z [NUM;PLUS;NUM;EOF];; 
val it : AST = AddNode (Leaf,Leaf) 
 
> z [NUM;PLUS;NUM;PLUS;NUM;EOF];; 
val it : AST = AddNode (Leaf,AddNode (Leaf,Leaf)) 
 
となります。 
 
では、実際に"1 + 3 + 5"などの文字列を計算できるようにしてみます。 
 
ここでは以前作ったTokenクラスを利用します。 
 
(利用例) 
> let tknz = (new TokenizerFactory ([("INT","\d+");("PLUS","\+")])).GetTokenizer();; 
val tknz : (string list -> Token list) 
 
> let testToken = tknz [" 1 + 2 + 3 + 10"];; 
val testToken : Token list = 
  [[INT   1  (1,2)] ; [PLUS   +  (1,4)] ; [INT   2  (1,6)] ; 
   [PLUS   +  (1,8)] ; [INT   3  (1,10)] ; [PLUS   +  (1,12)] ; 
   [INT   10  (1,14)] ] 
 
今回はLeafに値を保持させるのでASTの定義を次の様にします。 
 
> type AST = 
    |Leaf of int 
    |NullLeaf //ε対応  
    |AddNode of AST*AST 
 
    member this.eVal() = 
        match this with 
        |Leaf(i) -> i 
        |NullLeaf -> failwith "error" //作成されたASTにはNullLeafは残っていない 
        |AddNode(ln,rn) -> ln.eVal() + rn.eVal()//足算なので足す順序の考慮はしていない 
;; 
 
type AST = 
  | Leaf of int 
  | NullLeaf 
  | AddNode of AST * AST 
  with 
    member eVal : unit -> int 
  end 
 
今回はトークンクラスのインスタンスのリストを処理するので、マッチさせた後、Kindプロパティを調べることによってトークン種別を認識させています。 
またトークン列の最後にEOFがないので、そのことも考慮にいれています。 
(トークン列の最後にEOFを加えてもよかったかもしれません。) 
 
let rec z (remain:list<Token>) = 
      let (rem2,madeNodeByProgram) = program remain        
      if rem2 <> [] then  
        failwith "構文エラー" 
      else 
        madeNodeByProgram 
//1:Program = NUM Program2対応部分 
and program (remain:list<Token>) = 
       match remain with 
       |hd::rem2 when hd.Kind= "INT" ->  
                    let (rem3,madeNodeByProgram2) = program2 rem2 
                    let hdInt = Int32.Parse( hd.Img) 
                    if madeNodeByProgram2 = NullLeaf then 
                        (rem3,Leaf(hdInt)) 
                    else 
                        (rem3,AddNode(Leaf(hdInt),madeNodeByProgram2))  
       |_ ->  failwith "構文エラー" 
 
//2:Program2 = PLUS Program 
//3:Program2 = EPSILON 対応部分   
and program2 (remain:list<Token>) = 
       match remain with 
       |hd::rem2 when  hd.Kind = "PLUS" 
                    ->let (rem3,madeNodeByProgram) = program rem2 
                      (rem3,madeNodeByProgram)  
       |[]          ->([],NullLeaf) 
       |_ ->  failwith "構文エラー" 
        
 
使ってみます。 
 
> let tknz = (new TokenizerFactory ([("INT","\d+");("PLUS","\+")])).GetTokenizer();; 
val tknz : (string list -> Token list) 
 
> let testToken = tknz [" 1 + 2 + 3 + 10"];; 
val testToken : Token list = 
  [[INT   1  (1,2)] ; [PLUS   +  (1,4)] ; [INT   2  (1,6)] ; 
   [PLUS   +  (1,8)] ; [INT   3  (1,10)] ; [PLUS   +  (1,12)] ; 
   [INT   10  (1,14)] ] 
 
> let testAST = z testToken;; 
val testAST : AST = AddNode (Leaf 1,AddNode (Leaf 2,AddNode (Leaf 3,Leaf 10))) 
 
> testAST.eVal();; 
val it : int = 16 
 
それでは"2+3+5"のような文字列を評価する関数を定義します。 
 
let calc (str:string) = 
    let tknz = (new TokenizerFactory ([("INT","\d+");("PLUS","\+")])).GetTokenizer() 
    let testToken = tknz [str] 
    (z testToken).eVal() 
 
(実行例) 
> calc "2+5+9";; 
val it : int = 16 
 
> calc "2";; 
val it : int = 2 
スポンサーサイト

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

コメントの投稿

非公開コメント

プロフィール

T GYOUTEN

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

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

この人とブロともになる

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