ocamlyacc で parameterized parser を作る方法

ocamlyacc で parameterized parser を作る方法を紹介します。かなり裏技的 なのであまり利用はすすめられないですが、やろうと思えば出来ることを示せ ればと思います。もちろん ocamlyacc 自体にそのような機能が入ればいいので すが、ああいった開発体制ですからあまり期待しないほうがいいと思います。 ちなみに ocamlyacc の優秀な代替として Menhir というものがありま す。 ocamlyacc が LALR なのに対して Menhir が LR(1) なので、完全な代替 とはなりませんが、件の parameterized parser に加え、さまざまな便利機能 をサポートしていて非常におすすめです。何気に OMake もデフォルトでサポー トしてますし（MENHIR_ENABLED=trueと書くだけ）。

では本題に入ります。まず次のような AST を考えてください。

(* ast.ml *)
type expr = Int of int
            | Add of expr * expr
            | Sub of expr * expr
            | Mul of expr * expr
            | Div of expr * expr

見ての通り単純な四則演算式を定義しています。プログラミング言語をパース するときなど、通常はもっと巨大な AST になります。また、そのようなパーサー は、パース時のエラーメッセージなどを分かりやすくするために、以下のよう に各ノードにファイルの位置情報などを付加することがよくあります。

(* ast.ml *)
type pos = Lexing.position

type expr = Int of int * pos
            | Add of expr * expr * pos
            | Sub of expr * expr * pos
            | Mul of expr * expr * pos
            | Div of expr * expr * pos

ところでこの expr に型パラメータを加えてやれば、より汎用的になると思いませんか？

(* ast.ml *)
type 'a expr = Int of int * 'a
               | Add of expr * expr * 'a
               | Sub of expr * expr * 'a
               | Mul of expr * expr * 'a
               | Div of expr * expr * 'a

これにより、ユーザーは必要に応じて自分で利用するデータを各ノードに格納 することが可能になります。例えば、ノード ID であったり、演算後の結果で あったりです。

しかしながら、このような AST を構成するパーサー、つまり parameterized parser は、 ocamlyacc では（直接的）にはサポートしていません。具体的に どこで問題になるかと言えば、mly ファイル内の %type 宣言で問題になり ます。 %type 宣言では以下のように、どこに書いても一意になるように型を 記述する必要があります。

(* parser.mly *)
%type <Lexing.position expr> expr

つまり以下のような記述を受け入れないということです。

(* parser.mly *)
%type <'a expr> expr

考えてみれば当たり前の話ですが、なかなか不便ですね。 ocamlyacc にはその 他にも以下のような不便なポイントがありますが、個人的にこれが一番不便で す。

1. トークン定義だけ別に生成できない。その結果、 lexer が parser に依存 するという意味不明な状態になる。
2. Embedded action が書けない。 yacc なパーサーからポートするときは、自 分で空ルールを作ってそこにセマンティックアクションを埋め込むという不 毛な作業が必要になる。

それでこれをどうやって解決するかといいますと、まず ast.ml に以下のよ うなコードを追加します。

(* ast.ml *)
module type Annot = sig
  type t
  val of_pos : Lexing.position -> t
end

module Pos : Annot = struct
  type t = Lexing.position
  let of_pos pos = pos
end

Annot はノードに付与する注釈のシグネチャで、 Pos はデフォルトの付与 情報を表すモジュールです。次に、 parser.mly のヘッダとフッタに以下の ようなコードを追加します。

/* parser.mly */
%{
  module Make (A : Ast.Annot) = struct
    open Ast
  (* ... *)
%}
/* ... */
%%
end

これで生成される Parser モジュールが が Make ファンクタを持つように なります。そして肝心の %type 宣言を以下のように記述します。

%type <A.t expr> expr

これで生成される Parser モジュールが parameterized parser になりまし た。ただ、このままでは OMake などから利用したときにコンパイルエラーにな ります。その原因は ocamlyacc が生成する parser.mli が、 parser.ml の内容と一致していないためです。実は parser.mli は ocamlc -i parser.ml > parser.mli のように生成されているわけではなく、単純な テンプレートを使って生成されています。そのため、こういうハックを使うと 対処できなくなるわけです。そこでメイクルールにもハックを入れて、 ocamlc で parser.mli を生成するようにします。ちなみに ocamlyacc に mli ファイルを生成しないオプションがあれば事は単純なのですが、当然そ んな便利機能ないわけでして、手の届かなさが惚れ惚れしますね。

(* OMakefile *)
parser.mli: parser.ml
$(OCAMLC) -i $< > $@

parser.ml: parser.mly
$(OCAMLYACC) -bgen_parser $(OCAMLYACCFLAGS) $<
mv gen_parser.ml $@
rm gen_parser.mli

やってることは、まず ocamlyacc で gen_parser というベース名でパーサー を生成したのち、 gen_parser.ml を parser.ml に改名して、 gen_parser.mli というゴミを消してから、最後に ocamlc で parser.mli を生成します。実はこれ、 parser.ml が依存するモジュール をあらかじめコンパイルする意図を OMake に伝えることができてないのですが、 どうやればいいのか分からないのでこのままにしています。詳しい人がいれば 教えてください。

以上の手順を踏めば parameterized parser を作ることが可能になるはずです。 ついでにおまけコードを載せておきます。僕は大体こういうテンプレートを使 います。

(* parse.ml *)
module Make (A : Ast.Annot) = struct
  module Parser = Parser.Make (A)

  let parse_from_lexbuf lexbuf =
    Parser.expr Lexer.token lexbuf

  let parse_from_string s =
    parse_from_lexbuf (Lexing.from_string s)

  let parse_from_channel c =
    parse_from_lexbuf (Lexing.from_channel c)

  let parse_from_file file =
    let c = open_in file in
      try
        let ast = parse_from_channel c in
          close_in c;
          ast
      with e ->
        close_in c;
        raise e
end
include Make (Ast.Pos)

以下のような感じで使います。

# Parse.parse_from_string "1+2*3";;
- : Lexing.pos expr = ...

自分の注釈でパーサーをパラメータ化するには以下のように書きます。

module NodeID : Annot = struct
  type t = int
  let counter = ref 0
  let of_pos _ = incr counter; !counter
end

module MyParse = Parse.Make (NodeID)

使い方は先と同じです。

# MyParse.parse_from_string "1+2*3";;
- : int expr = ...

なかなか便利ですね。

最後に拙作の ocaml-lang-ruby と ocaml-lang-python を紹介し ておきます。前者は Ruby コードのパーサーとプリティプリンタを、 OCaml で 実装したライブラリで、後者はそれの Python 版です。両者とも今回言及した テクニックを使って parameterized parser を作っています。参考になるか分 かりませんが、何か分からない点があればコードを眺めてみると良いと思いま す。