演算子順位構文解析

普段日常生活を営んでいると何となくコンパイラを作りたくなる事はありませんか？僕はあります。演算子順位構文解析を用いることでStandard MLで行なわれているような演算子の順序の入れ替えを実現できるのではないかと思い、試しに実装してみました。

Standard MLの文法は演算子の優先順位をプログラマが指定できる事から、非常に構文解析が難しい事が知られています。ある日何気なくTLを眺めているとMLKitの実装に関する論文が流れてきたんですが、その論文によると中置演算子の含まれた式の構文解析を後回しにし、2ステップで構文解析をするそうです。

括弧等の高レベルな文法はyaccなどで実装される第一のステップの構文解析器で処理される訳ですから、第二のステップで処理しなければならない文法は変数等と中置演算子からなる演算子順位文法であると考えられます。また、構文解析の対象の言語は演算子順位文法で生成されるため、構文解析は演算子順位構文解析で十分に処理できることでしょう。試しに演算子順位構文解析をOCamlで実装してみます。

(* Id.tは変数名等に使われる識別子 *)
module Id =
  struct
    type t = string 
  end

(*
 * 知っての通り字句解析器から渡されるトークンであり、構文解析の都合から木のような定義がされている
 * EOIは最後の入力を示す
 *)
module Token = 
  struct
    type t = Id of Id.t | BinOp of Id.t * (t * t) option | EOI
  end

(* 演算子の結合性 *)
module Assoc =
  struct
    type t = Left | Right
  end

(* 演算子の優先順位を表す順序関係に基づいてトークンの列を構文解析して項を作る *)
let rec parse ( < ) stack inputs =
  match stack, inputs with
  | [result; Token.EOI], [Token.EOI] -> Some (result)
  | b :: op1 :: stack', op2 :: inputs' ->
      if op1 < op2 then parse ( < ) (op2 :: stack) inputs'
      else
        begin match stack', op1 with
        | a :: stack'', Token.BinOp (x, None) ->
            parse ( < ) (Token.BinOp (x, Some (a, b)) :: stack'') inputs
        | _ -> None
        end
  | _ -> None

(* 演算子の優先順位の定義 *)
let op_spec =
  [("+", (6, Assoc.Left));
   ("-", (6, Assoc.Left));
   ("*", (7, Assoc.Left));
   ("/", (7, Assoc.Left));
   ("::", (5, Assoc.Right));
   ("@", (5, Assoc.Right))]

(* 演算子の優先順位を比較する順序関係 *)
let lt_prio op1 op2 =
  match op1, op2 with
  | _, Token.Id _ | Token.EOI, _ -> true
  | Token.Id _, _ | _, Token.EOI -> false
  | Token.BinOp (x, _), Token.BinOp (y, _) ->
      let (op1_prio, assoc) = List.assoc x op_spec in
      let (op2_prio, _) = List.assoc y op_spec in
      op1_prio < op2_prio || op1_prio = op2_prio && assoc = Assoc.Right

(* 例
parse lt_prio [Token.Id "x"; Token.EOI] [Token.BinOp ("+", None); Token.Id "y"; Token.BinOp ("+", None); Token.Id "z"; Token.EOI]
parse lt_prio [Token.Id "x"; Token.EOI] [Token.BinOp ("+", None); Token.Id "y"; Token.BinOp ("*", None); Token.Id "z"; Token.EOI]
parse lt_prio [Token.Id "x"; Token.EOI] [Token.BinOp ("::", None); Token.Id "y"; Token.BinOp ("::", None); Token.Id "z"; Token.EOI]
 *)

この実装では演算子の優先順位を結合の強さと結合性の情報から決定しているため、後からこれらの情報を追加することでStandard MLのような言語の構文解析に対応できることでしょう。

Standard MLの文法は結構綺麗なので、いつか自分で簡単な処理系を作ってみたいものです。その時にもOCamlで実装していると何とも締まらないのでStandard MLで書き直そうと思います。

fetburner.core

コアダンプ

演算子順位構文解析