現在僕は趣味でStandard MLのサブセットの処理系を実装しようとしているのですが、皆さんのご存知の通り、Standard MLの構文解析は非常に難しい事が知られています。今回はML Kitの実装に関する文書を参考に構文解析器を実装した時の事について書きたいと思います。ちなみに、タイトルもその文書からの引用です。

何が難しいのか

言語仕様のpp.4-10を読むと分かる通り、アルファベットその他の列では終わらずにいくつかの記号（+、-など）のみからなる文字列も変数名に使う事もできます。加えてどの変数も二項演算子にできるわけですから、明らかに字句解析の段階ではどの変数が二項演算子なのか判別ができません。

さらに、どの変数が二項演算子なのかはもちろん、演算子の優先順位や結合性もプログラマーが自由に決められます。それもスコープに依存して。また、二項演算子として定義した変数の前に"op"と書けば一時的にキャンセルすることもできます。

従って、Standard MLでは以下のようなプログラムを書くことができます。

(* divisibleを左結合の二項演算子として用いる *)
infix divisible
fun n divisible m = n mod m = 0
(* 二項演算子なのでこういう使い方ができる *)
val hoge = 30 divisible 5
(* opで一時的にキャンセルできる *)
val hogehoge = op divisible (17, 2)
local
  (* nonfixでこれ以降キャンセルできる *)
  nonfix divisible
in
  val foo = divisible (42, 42)
end
(* スコープを出たので元に戻っている！ *)
val bar = 1 divisible 2

(* *は結合の強さが7で左結合の二項演算子とする *)
infix 7 *
(* +は結合の強さが6で左結合の二項演算子とする *)
infix 6 +
(* ::は結合の強さが5で右結合の二項演算子とする *)
infixr 5 ::

(* ((1 + (2 * 3) * 4) + 5) :: (1 + 2) :: []と解釈される！！ *)
val baz = 1 + 2 * 3 * 4 + 5 :: 1 + 2 :: []

lexとyaccだけでは荷が重そうです。

解法

最初に挙げた文書を参考に、yaccで生成する構文解析器は二項演算子の現われ得る部分についてはAtExpの列として残し、後でStandard MLで書いた構文解析器を用いてスコープを見ながら構文解析する事で解決しています。

実際のコードを見てみましょう。ML-Yaccで生成する構文解析器のソースコードはudon.grmに書かれています。この構文解析器はStandard MLのサブセットの二項演算子を除いた部分を構文解析し、concreteSyntax.smlに書かれている形式の構文木を出力します。

structure ConcreteSyntax = struct
  (* abstract syntax tree of expression *)
  datatype exp =
    (* constant *)
      CONST of Const.t
    (* variable *)
    | VAR of string
    (* non-infixed operator *)
    | OP of string
    (* if M then N_1 else N_2 *)
    | IF of exp * exp * exp
    (* fn x => M *)
    | ABS of string * exp
    (* let d in N end *)
    | LET of dec list * exp
    (* sequence of expression *)
    | SEQ of exp list
    (* ( M ) *)
    | PAREN of exp
    (* (M_1, ... , M_n) *)
    | TUPLE of exp list
    (* case M of (x_1, ... , x_n) => N *)
    | CASE of exp * string list * exp
  (* abstract syntax tree of declaration *)
  and dec =
    (* val x = M *)
      VAL of string * exp
    (* val rec f = M *)
    | VALREC of string * exp
    (* infix d vid_1 ... vid_n *)
    (* infixr d vid_1 ... vid_n *)
    | INFIX of Infixer.Assoc.assoc * int * string list
    (* nonfix vid_1 ... vid_n *)
    | NONFIX of string list
end

本来の意味での抽象構文木には括弧、opや列等の要素は必要無いはずですが、まだ完全には構文解析が終わっていないので残してあります。

後はスコープを意識しながら残りを構文解析する訳ですが、この処理はinfixer.smlとinfixing.smlに書かれてあります。関数適用は必ず二項演算子より優先順位が高いと決め打ちして再帰下降構文解析を行い、二項演算子はその環境での優先順位や結合性に従って演算子順位構文解析を行っています。この構文解析器の出力についてはsyntax.smlを参照して下さい。やたら引数の多い関数がありますが、Standard MLには第1級モジュールが無くてファンクタを使えなかったので泣く泣くこういうインターフェースになりました。

今後の方針

構文解析だけで無駄にエネルギーを使ってしまいました。この記事を書いた時点でCPSっぽい中間表現までは変換できたので、今後はSSAに落としてLLVMに食わせるなり中間表現の時点で末尾再帰の最適化をするなりしたいですね。

fetburner.core

コアダンプ

"Syntactically, SML is a nightmare"

何が難しいのか

解法

今後の方針