ちょっとOCamlで Chained symbol table書いてみた
プログラミング言語の変数・関数名なんかを格納するシンボルテーブルをOCamlでちょろっと書いてみました。大学の課題で言語処理の作成(C言語で)だったのですが、OCamlで試しに書いた感じです。
変数へのアクセスは、スコープの内側で定義したシンボルから順に行います。このコードでは、ブロックごとにハッシュテーブルを格納しています。そして、シンボルの検索時には、ブロックの内側から順に検索するようにしています。enter/popは、現在のスコープの深さにあわせて保持しているシンボルテーブルの情報を更新するメソッドです。
- スコープに入る段階でシンボルを定義し(enterしてからシンボルをput)
- コード中でシンボル(変数)を参照(get)
- スコープから出るとき、1つ前の状態に戻す(pop)
ちなみにvartype/symbolで、シンボル情報を格納しています。このコードでは、グローバル変数やローカル変数などといった情報ですね。
type vartype = VarGlobal | VarGlobalArray | VarArg | VarLocal type symbol = { kind : vartype; pos : int } class environment = object(self) val mutable table : (string, symbol) Hashtbl.t list = [Hashtbl.create 0] method enter = let tbl : (string, symbol) Hashtbl.t = Hashtbl.create 0 in table <- tbl :: table; () method put name sym = match table with [] -> printf "env table is empty\n"; raise Not_found | h :: _ -> Hashtbl.add h name sym method pop = table <- match table with a :: tl -> tl | _ -> [] method get (s: string) = let rec find tbl key = match tbl with [] -> printf "no symbol %s\n" key; raise Not_found | h :: tl -> try Hashtbl.find h key with Not_found -> (find tl key) in find table s end