ちょっとOCamlで Chained symbol table書いてみた

 プログラミング言語の変数・関数名なんかを格納するシンボルテーブルをOCamlでちょろっと書いてみました。大学の課題で言語処理の作成(C言語で)だったのですが、OCamlで試しに書いた感じです。

 変数へのアクセスは、スコープの内側で定義したシンボルから順に行います。このコードでは、ブロックごとにハッシュテーブルを格納しています。そして、シンボルの検索時には、ブロックの内側から順に検索するようにしています。enter/popは、現在のスコープの深さにあわせて保持しているシンボルテーブルの情報を更新するメソッドです。

  1. スコープに入る段階でシンボルを定義し(enterしてからシンボルをput)
  2. コード中でシンボル(変数)を参照(get)
  3. スコープから出るとき、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