この連載では,第1回から前回まで,プログラミング言語Objective Caml(OCaml)の特徴について紹介してきた。その中でも触れたように,OCamlではネットワークやグラフィックスなどを利用して,様々なプログラムを簡単に開発できる。特にOCaml(ないし関数型言語一般)が得意とする分野の一つに,プログラミング言語処理系そのものの開発がある(プログラミング言語研究者が開発した言語なのだから,ある意味では当然かもしれない)。そこで今回から数回にわたり,OCamlを使って独自のプログラミング言語を開発してみよう。

プログラミング言語MyCの構文と直観的意味

 一般にプログラミング言語を開発するには,まず言語の構文(syntax)意味(semantics)を定義しなければならない。そのための理論についてはいずれ紹介するとして,ここではとりあえず,大ざっぱに次のような「文」を持つ架空の命令型言語「MyC」を例として考えてみよう。ただし,x,y,zは変数一般,iは整数定数一般を表すものとする。

構文 直観的な意味
x = i xにiを代入する
x = y + z yの値とzの値の和をxに代入する
while (x > y)文 xの値がyの値より大きい間,文を繰り返す
{ 文1; 文2; …; 文n; } 文1から文nまでを順番に実行する
print x xの値を画面(標準出力)に表示する

 例えば,1から10までの整数の総和を計算して表示するプログラムは,MyC言語では次のように書ける(これ以降,このプログラムはsum.mycというファイルにセーブされているものとする)。

{
  zero = 0;
  minus_one = -1;
  sum = 0;
  n = 10;
  while (n > zero) {
    sum = sum + n;
    n = n + minus_one;
  };
  print sum;
}

 このプログラムは,個々の行が先の構文と正確に対応していることに気をつけてほしい。例えば,「zero = 0」と「n > zero」は,単に「n > 0」と書きたいところだが,今回の言語には変数と定数を直接比較する構文がない(!)ので,このような書き方になっている。minus_oneについても同様だ。もちろん,このような制限はあくまで説明や実装を簡単にするための「手抜き」に過ぎないので,実用言語では任意の複雑な式を書けるようにすべきだろう(基礎研究では,本質を明確にするためにこうした「手抜き」が有用な場合もあるが)。

インタプリタとコンパイラ,字句解析と構文解析

 言語の構文と意味を定義したら,その言語のプログラムを実行するための処理系を作らなければならない。大まかに分類すると,言語処理系には,プログラムを解釈しながら実行するインタプリタと,プログラムを(より低レベルな)別の言語に変換するコンパイラの二つの種類がある。これはあくまで処理系の実装の問題であって,言語そのものの性質ではないことに注意したい。例えば,現存するC言語の処理系は,ほとんどがアセンブリ言語へのコンパイラだが,原理的にはC言語のインタプリタを開発することも不可能ではない(実際に教育などを目的としたC言語のインタプリタも存在する)。

 さて,インタプリタにせよコンパイラにせよ,通常の言語処理系で最初に必要となる処理は字句解析構文解析だ。字句解析とは,(コンピュータにとっては)ファイル等に書かれた単なる文字列に過ぎないソースコードを,トークンと呼ばれる単語の列に区切る処理のことである。例えば,上のプログラムの2行目であれば,

「z」「e」「r」「o」「 」「=」「 」「0」「;」

のような文字列を,

「zero」「=」「0」「;」

のようなトークン列に変換するわけだ。

 一方,構文解析とは,トークン列をさらに分析して,プログラムの構造を表す木(構文木)に変換する処理のことである。OCamlを含め,関数型言語では代数データ型を用いて構文木を表すのが一般的だ。例えば,今回のMyC言語の構文木を表すデータ型は,次のように定義できる(これらの定義はsyntax.mlというファイルに記述されているものとする)。

type var = string (* 「変数名」を表す型 *)

type statement = (* 「文」を表す代数データ型 *)
  | Const of var * int
      (* 「x = i」という形の文を表す *)
  | Add of var * var * var
      (* 「x = y + z」という形の文を表す *)
  | While of var * var * statement
      (* 「while (x > y) 文」という形の文を表す *)
  | Seq of statement list
      (* 「{ 文1; 文2; …; 文n }」という形の文を表す *)
  | Print of var
      (* 「print x」という形の文を表す *)

 statement型の各コンストラクタが,先の構文の定義と一つずつ対応していることに注意してほしい。例えば,「foo = bar + baz」という文は,Add("foo", "bar", "baz")という値により表される。コンストラクタがAddであれば,「=」や「+」などの記号は(この言語の構文では)固定されているので,含めなくてよい。

 このstatement型の値として,先のプログラム例(sum.myc)の構文木を表すと次のようになるはずだ。

Seq
 [Const ("zero", 0);
  Const ("minus_one", -1);
  Const ("sum", 0);
  Const ("n", 10);
  While ("n", "zero",
   Seq [Add ("sum", "sum", "n");
        Add ("n", "n", "minus_one")]);
  Print "sum"]