前回は,OCamlYaccとOCamlLexというツールを使って,簡単な独自プログラミング言語「MyC」の字句解析器と構文解析器を作ってみた。今回は,プログラムを実際にどのように実行するかについて解説したい。

前回,MyC言語には次の5種類の文があることを示した。

  • 「x = i」という形の定数代入
  • 「x = y + z」という形の足し算
  • 「while (x > y) 文」という形の繰り返し
  • 「{ 文1; 文2; …; 文n; }」という形の逐次実行
  • 「print x」という形の変数表示

 OCamlYaccとOCamlLexを使うと,テキスト・ファイルなどに書いたMyC言語のプログラムを読み込んで,OCamlで定義した代数データ型(Syntax.statement,Syntaxモジュールのstatement型)の値に変換できることを説明した。

 さて,プログラムを代数データ型の値に変換したら,次はそれを何らかの方法で実行したい。OCamlでは,パターンマッチングを利用してプログラムを解釈しながら実行する方法が最も簡単だ。Syntax.statementは,MyC言語の五つの構文に対応して,以下のように定義されていたことを思い出そう。

type var = string
type statement =
  | Const of var * int
  | Add of var * var * var
  | While of var * var * statement
  | Seq of statement list
  | Print of var

 一般に,このような代数データ型の値は,型の構造に従って処理するとうまくいくことが多い。「型の場合分け(ここではConstからPrintまでの5通り)に対してはパターンマッチング」「型の再帰(ここでは=の右辺のstatement型)に対しては再帰関数」といった具合である。ここでもその方針に従い,以下のようなinterpret関数を作成することにしよう。

let rec interpret s = match s with
  | Const(x, i) ->
      ... (* x = iを実行 *)
  | Add(x, y, z) ->
      ... (* x = y + zを実行 *)
  | While(x, y, s2) ->
      ... (* while (x > y) s2を実行 *)
  | Seq(ss) ->
      ... (* { s1; s2; …; sn; }を実行 *)
  | Print(x) ->
      ... (* print xを実行 *)

 各パターンマッチングの右辺を実装する前に,まず標準ライブラリHashtblを用いて,変数の値を記憶するためのハッシュ表tableを定義する。Hashtblライブラリの詳細についてはマニュアル(英語版または日本語訳)を参照してほしい。

let table = Hashtbl.create 10

 そのうえで,MyC言語の五つの構文それぞれについての処理を考えよう。まず,x = iという形の文は,変数xに整数定数iを代入するものだから,tableにxからiへの対応を追加すればよいはずだ(もしすでにxの値があればiで置き換える)。

  | Const(x, i) ->
      Hashtbl.replace table x i

 x = y + zは,変数yとzの値をtableから検索し,それらの和を変数xの値として登録する。

  | Add(x, y, z) ->
      Hashtbl.replace table x
        (Hashtbl.find table y +
           Hashtbl.find table z)

 while (x > y) s2だったら,xとyの値を比較する。もしxのほうが大きかったら,interpret関数の再帰呼び出しにより,まず1回だけs2を実行する。それから,またwhile全体を繰り返す。

  | While(x, y, s2) ->
      if Hashtbl.find table x >
        Hashtbl.find table y then
        (interpret s2;
         interpret s)

 { s1; s2; …; sn; }は,それぞれの文を順番に実行すればよい。ここでは,文の列はリストとして表されているので,リストの要素に順番に関数を適用するList.iterというライブラリ関数を利用する。

  | Seq(ss) ->
      List.iter interpret ss

 print xはxの値を出力すればいい。

  | Print(x) ->
      Printf.printf "%d\n"
        (Hashtbl.find table x)

 最後に,前回の字句解析器と構文解析器を標準入力に対して呼び出し,interpret関数を呼び出すmainルーチンを書く。インタプリタ全体は以下のようになる。

open Syntax

let table = Hashtbl.create 10

let rec interpret s = match s with
  | Const(x, i) ->
      Hashtbl.replace table x i
  | Add(x, y, z) ->
      Hashtbl.replace table x
        (Hashtbl.find table y +
           Hashtbl.find table z)
  | While(x, y, s2) ->
      if Hashtbl.find table x >
        Hashtbl.find table y then
        (interpret s2;
         interpret s)
  | Seq(ss) ->
      List.iter interpret ss
  | Print(x) ->
      Printf.printf "%d\n"
        (Hashtbl.find table x)

let main = (* 必ずunit型の値()になる *)
  let s =
    (* 標準入力を字句解析&構文解析する *)
    Parser.statement Lexer.token
      (Lexing.from_channel stdin) in
  interpret s

 このソースコードをinterpret.mlというファイル名で保存しよう。以下のようにすれば,めでたくMyC言語のインタプリタが動作する(前回のsyntax.ml,parser.mly,lexer.mll,sum.mycも使用している)。

> ocamlyacc parser.mly
> ocamllex lexer.mll
24 states, 1124 transitions, table size 4640 bytes
> ocamlc syntax.ml parser.mli parser.ml lexer.ml interpret.ml -o interpret
> ./interpret < sum.myc
55