構文木実装のいろいろ

忙しさにかまけてここの存在をしばらく忘れてしまっていました。
ここんとこ色々なコンパイラを読んだり書いたりしているのですが、構文木の実装にもいろいろなやり方がありおもしろかったので書いときます。読んだ処理系にだいぶ偏りがありますがご了承ください。

バリアントを使う

関数型言語で言語処理系を作るならやはりバリアントでしょう。
例えばocamlならば

type expression =
  { pexp_desc: expression_desc;
    pexp_loc: Location.t }

and expression_desc =
    Pexp_ident of Longident.t
  | Pexp_constant of constant
  | Pexp_let of rec_flag * (pattern * expression) list * expression
  | Pexp_function of label * expression option * (pattern * expression) list
...

これは式についての定義ですが、これが宣言やパターンや型などそれぞれについて定義されています。
また、同様にGHCならば

data Expr b	-- "b" for the type of binders, 
  = Var	  Id
  | Lit   Literal
  | App   (Expr b) (Arg b)		-- See Note [CoreSyn let/app invariant]
  | Lam   b (Expr b)
  | Let   (Bind b) (Expr b)		-- See [CoreSyn let/app invariant],
					-- and [CoreSyn letrec invariant]
  | Case  (Expr b) b Type [Alt b]  	-- Binder gets bound to value of scrutinee
					-- See Note [CoreSyn case invariants]
  | Cast  (Expr b) Coercion

のような感じになっています。

バリアントを使う事の意義は型を厳格につけられる、形式的な文法表現とコードが綺麗に対応する等でしょうか。
わかりやすさという点ではダントツだと思うので、言語処理系製作の入門としては適しているんじゃないかと思います。

厳格な型づけを嫌う人には構文要素の種類、中間言語の種類毎に型の定義とそれを操作する為の関数をかかなければならないというあたりが面倒くさいかもしれません。
また、これをC言語のstructやunionで真似はしないほうがいいです。なぜならパターンマッチがない言語で、ここまで階層化してしまうと

expr->function->body->loop->cond

みたいなアローの連鎖や2重3重にネストしたswitchやifだらけに陥りやすいからです。

継承を使う

オブジェクト指向言語では継承を使うという手があります。いわゆるCompositeパターンというやつです。
例えば、http://www.coins-project.org/では

/**
 *  If-statement.
**/
public interface
IfStmt extends Stmt
{
  ..
}

というようにインターフェースの継承により階層関係を表現しています。これとVisitorパターン等を組み合わせるとなかなかいい感じです。
高レベル中間言語での操作は木を辿りながらノードを書き換えていくというのが基本になりますから、Visitorパターンと仮想関数の組み合わせでいろいろできます。

struct,unionを使う

Cではパターンマッチなどの便利機能がないので安直に構文木を作ってしまうと実装が大変になります。
また、C固有の問題としてはメモリ等のリソース管理の手間が挙げられます。構造体の種類が多いと管理が大変になってしまいます。例えばGCCではコンパイラ内部でガベージコレクタが走っていますが、これを実装する上ではヒープ上のあらゆるものを一つの構造体として管理した方が楽になります。

GCCのtree.h(プリプロセッサで処理したもの)を読んでみると以下のように、定数も識別子も宣言も型もすべてのものが一つのunionに属しています。

union tree_node

{
  struct tree_base base;
  struct tree_common common;
  struct tree_int_cst int_cst;
  struct tree_real_cst real_cst;
  struct tree_fixed_cst fixed_cst;
  struct tree_vector vector;
  struct tree_string string;
  struct tree_complex complex;
  struct tree_identifier identifier;
  struct tree_decl_minimal decl_minimal;
  struct tree_decl_common decl_common;
...

また、unionの各フィールドを識別する為にはタグを埋め込む訳ですが、これは以下のようになっています。

enum tree_code {
PLUS_EXPR,
MINUS_EXPR,
MULT_EXPR,
POINTER_PLUS_EXPR,
TRUNC_DIV_EXPR,
CEIL_DIV_EXPR,
FLOOR_DIV_EXPR,

...

バリアントや継承を使う方法の場合には、通常「式」を表す型があってその中にオペレーションの種類を表すデータを格納する訳ですが、ここではオペレーションの情報をタグの中に直接埋め込んでいます。こうすれば一回のテストで「どういう種類の」式かまで判別できるので、パターンマッチのコストが減ります。階層構造を表現する為の情報は別に構造体中に埋め込んでやります。

enum tree_code_class {
  tcc_exceptional, /* An exceptional code (fits no category).  */
  tcc_constant,    /* A constant.  */
  /* Order of tcc_type and tcc_declaration is important.  */
  tcc_type,        /* A type object code.  */
};

S式

HugsはS式を利用した(といっていいかどうか分かりませんが)実装になっています。

これはHugsのyaccのコードですが、

infixExpa : infixExpa qop '-' exp10a	{$$ = gc4(ap(NEG,ap(ap($2,$1),$4)));}
	  | infixExpa qop exp10a	{$$ = gc3(ap(ap($2,$1),$3));}
	  | '-' exp10a			{$$ = gc2(ap(NEG,only($2)));}
	  | exp10a qop '-' exp10a	{$$ = gc4(ap(NEG,
						     ap(ap($2,only($1)),$4)));}
	  | exp10a qop exp10a		{$$ = gc3(ap(ap($2,only($1)),$3));}

/* apやonlyの定義 */
#define ap(f,x)      pair(f,x)
#define only(t)			 ap(ONLY,t)

つまり

-x => (NEG (ONLY x))
a + b => ((PLUS (ONLY a)) b)

のようにS式を利用して構文木を定義しています。