スポンサーサイト

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

F#入門基本編落穂拾い その24 ツリー構造(4) AST

Abstract Syntax Tree (AST)とは、抽象構文木と訳され、プログラムの文法構造をツリーの形で表したものです。ここでは、簡単な式の計算を取り上げます。
 
例えば1+2はASTでは
 
   1
  /
 +
  \
   2
   
と表現され
 
(1+2)*3 
 
    1
   /
  +
 / \
*   2 
 \ 
  3
  
と表現されます。
 
それでは、演算を和、差、積、型をint型に限定してASTを作っていきます。
まず型定義は例えば次のようになります。
 
type Ast0 =
    |Val of int
    |Multi of Ast0 * Ast0
    |Plus of Ast0 * Ast0
    |Minus of Ast0 * Ast0
 
例 1+2のAST表現 
> let ex1 = Plus(Val(1),Val(2));;
val ex1 : Ast0 = Plus (Val 1,Val 2)
 
例 3-5のAST表現
> let ex2 = Minus(Val(3),Val(5));;
val ex2 : Ast0 = Minus (Val 3,Val 5)
 
例 (1+2)*(3-5)のAST表現
> let ex3 = Multi(ex1,ex2);;
val ex3 : Ast0 = Multi (Plus (Val 1,Val 2),Minus (Val 3,Val 5))
 
さてこのASTを計算する関数eValを定義します。
 
let rec eVal exp  =
    match exp with
    |Val(v) 
        -> v
    |Multi(right,left) 
        -> (eVal right) * (eVal left)
    |Plus (right,left)
        -> (eVal right) + (eVal left)
    |Minus (right,left)
        -> (eVal right) - (eVal left) 
 
実行例
> eVal ex1 ;;
val it : int = 3
> eVal ex2 ;;
val it : int = -2
> eVal ex3 ;;
val it : int = -6
スポンサーサイト

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

コメントの投稿

非公開コメント

プロフィール

T GYOUTEN

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

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

この人とブロともになる

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