100行で書く俺様プログラミング言語コンパイラAltJS編

プログラミングをしたことがあるひとなら、誰でも１度くらい自分の理想の言語を作ってみたいと思うのではないでしょうか。このテキストは、オリジナルのプログラミング言語のコンパイラ作成を通して、パーサコンビネータの使い方を紹介していくものです。

2分でわかる、俺の俺による俺のためのプログラミング言語を作る大まかな手順

自分のオリジナルなプログラミング言語を作るには、典型的には次のような手順を踏みます。

1. 既存のプログラミング言語を使ってみる
2. その既存の言語の気に入らないところを徹底的になじる（ただし心のなかで）
3. 己の内に秘める中二力を卍解し、最強プログラミング言語の仕様を妄想する
4. コンパイラを作る
5. その言語を教典とする宗教団体を設立し、慈悲深き終身の独裁者を名乗る
6. 自分の言語が思ったよりしょぼいことに気付く
7. 桶屋が儲かる

このテキストではこのうち手順 4 だけ、特にコンパイラのパーサ部分を解説します。

• このテキストを読むにあたって、構文解析についての知識はとくに不要です。正規表現を知っていると理解の助けになるかもしれません。

• このテキストで作ってみるプログラミング言語は、最近のお茶っぽいネーミングの流行に乗っかって BanchaScript と名づけました。あまり変な言語を作っても参考にならないので、言語仕様は C/Java/JavaScript の系統の比較的オーソドックスなものを採用しています。

• コーディングには JavaScript/TypeScript を使い、パーサを作成するのに Parsect というライブラリを利用します。これは Haskell の Parsec という構文解析を行うためのライブラリを筆者が JavaScript/TypeScript へといい加減に移植したりしなかったりしたもので、このテキストはそれの紹介も兼ねています。本文中のソースコードのほとんどは、JavaScriptとTypeScriptのどちらでも有効なコードで書かれています。

まずは3分でわかるコンパイラの構造

コンパイラの工程は、典型的には次のような段階を踏みます。らしいです。

1. 字句解析
2. 構文解析
3. 中間コード生成
4. 最適化
5. コード生成

筆者は大変な面倒くさがり屋なので、今回作るコンパイラではこれらの工程を大きく簡略化します。最適化については面倒くさいので省略します。最終的に出力するコードはJavaScriptのソースコードとします。このようなコンパイル形態をもつ言語は AltJS などと呼ばれていて、実行に関するあらゆる機能をJavaScriptエンジンに丸投げできるので、パーサさえうまくできればコンパイラを作るのがとても簡単になります。また、このような手法を採用することから中間的なデータ構造を作らなくても済むので、構文解析と同時に直接最終的なコードを出力していきます。コード生成部分に関しては、ほぼ等価なJavaScriptソースコードを文字列として生成しているだけなので、特に説明する内容はありません。

というわけで、4分くらいでわかる字句解析器と構文解析器とはなにか

今回作るコンパイラでは、工程としては字句解析器と構文解析器に分類はしますが、実はコード上では両者に区別はありません。字句解析器も構文解析器も、どちらも一種の関数とみなすことができます。どちらの解析器でも、入力する情報は次のふたつだけです。

• 構文解析の対象としている文字列
• 現在何文字目まで読み終えているか

また、解析器は入力に応じて次の情報を返してきます。

• 読み取りが成功したかどうか
• 成功した場合は、何文字目まで読み終えたかと、読み取った内容
• 失敗した場合は、何文字目まで読み終えたかと、期待していた内容

基本的にはたったこれだけです。コンパイルする対象の文字列の最小単位である『識別子』『演算子』などのトークンを読み取るのが字句解析器で、『関数の定義』『if文』など複数のトークンが組み合わさったものを読み取るのが構文解析器なのです。まずはトークンを読み取る字句解析器を作り、それらの字句解析器を組み合わせて構文解析器を作成していくことになります。ここでは、字句解析器も構文解析器をまとめて『パーサ』や『解析器』などと呼ぶことがあります。それぞれの解析器は基本的には状態を持ちません。入力に応じて決まった出力を行う、単なる関数です。

概念は5分くらいでわかるけど、実際に作るのには何時間もかかるんじゃないかと思えてくる字句解析器

字句解析器 (Lexer, Scanner, Token Parserなどともいいます)は、その言語の最小単位である『識別子』『リテラル』『予約語』などのトークンごとの読み取りを行うパーサです。注意しなければならないのは、トークンとトークンの間には空白文字やコメント文があるときもありますし、そのような区切りがなくて直後にいきなり次のトークンが現れるときもあることです。字句解析器はひとつトークンを読んだら、つねに次のトークンの直前まで読まなくてはならないものとします。たとえば、次のようなソースコードを解析しているものとします。

var hoge /* この変数はほげ */ = 42;

ここで、現在の読み取り位置は 4、つまり hoge の直前で、ここから識別子をひとつ読み取るパーサを作りたいとします。識別子の hoge の直後にはブロックコメントがありますが、コメントはトークンにはならないので、一度の読み取りでこれらのブロックコメントも含めて読み飛ばして = の直前まで来なければなりません。つまり、識別子の字句解析器は

• 入力文字列: var hoge /* この変数はほげ */ = 42;
• 現在の位置: 4

という入力から、

• 成功
• 現在の位置: 23
• 読み取った情報: "hoge"

というような結果を返すようプログラムされていなければなりません。また、次のように識別子と次のトークンに空白などの区切りがないときもあります。

var hoge=42;

このような場合でも、識別子の字句解析パーサは次のトークンである = の直前まで読み取り、以下のような結果を返さなければなりません。

• 成功
• 現在の位置: 8
• 読み取った情報: "hoge"

また、現在の位置に識別子が存在しない場合もあります。先ほどと同じ var hoge=42; というソースコードの9文字目、42の直前の位置で識別子の字句解析器を使ったなら、そこには識別子は存在しないので、次のような結果を返さなければなりません。

• 失敗
• 現在の位置: 9
• 期待していたもの: a-z, A-Z, _, $ のいずれかひとつ

こういった機能をもつ字句解析パーサを、『識別子を読み取るパーサ』『数値リテラルを読み取るパーサ』『文字列リテラルを読み取るパーサ』『予約語を読み取るパーサ』『括弧を読み取るパーサ』などと、その言語のソースコードに出現しうるすべてのトークンの種類ごとに定義しなければなりません。それほど難しくはなさそうですが、これでは作業量としてはかなりのの量になりそうです。やれやれ。

実際には10数行で書ける字句解析器

というわけで字句解析器を構成するのはとても大変なので、ライブラリに付属している 字句解析器を自動で構成してくれる機能 を使います。関数 makeTokenParser は『コメントを開始する記号/終了する記号』『予約語』などの情報をオブジェクトのプロパティとして定義して渡すだけで自動で字句解析器を構成してくれます。ほとんどのプログラミング言語の字句解析はこの機能で十分構成できます。BanchaScriptの場合は次のようになっています。

var lexer = Parsect.makeTokenParser({
    commentStart:       '/*',   // ブロックコメントの開始記号
    commentEnd:         '*/',   // ブロックコメントの終了記号
    commentLine:        '//',   // 行コメントの開始記号
    nestedComments:     true,   // ネストされたブロックコメントを許可するかどうか
    identStart:         /[_$a-zA-Z]/,   // 識別子の最初の文字
    identLetter:        /[_$a-zA-Z0-9]/,    // 識別子の2文字目以降
    opStart:            /[+\-*\/=!$%&\^~@?_><:|\\.]/,   // 演算子の最初の文字
    opLetter:           /[+\-*\/=!$%&\^~@?_><:|\\.]/,   // 演算子の２文字目以降
    reservedNames:      ["def", "return", "operator", "infix", "infixl", "infixr", "prefix", "postfix", "var"],　// 予約語
    reservedOpNames:    [],     // 予約された演算子 
    caseSensitive:      true    // 大文字小文字を区別するかどうか
});

これだけでBanchaScriptの字句解析器は 完成 です。この一覧表をいじれば、プログラミング言語の見た目を自由に調節できます。たとえば行コメントの開始を # にしたければ、commentLine プロパティの値を #　に変えるだけです。

makeTokenParser が返してくるオブジェクト lexerはいろいろな字句解析パーサをプロパティとして持っています。たとえば、lexer.identifier は識別子の字句解析を行ってくれるパーサです。たとえば、

var hoge /* この変数はほげ */ = 42;

というソースコードの4文字目まで読み終わった状態から　lexer.identifier を実際に使ってみましょう。この字句解析器を実際に使うには、parse という関数を使います。parse はパーサと入力となる State オブジェクトを渡すと、そのパーサの解析の結果を Reply オブジェクトとして返してくれます。ソースコードは次のようになります。

var state = new Parsect.State("var hoge /* この変数はほげ */ = 42;", 4);   // state は現在の状態
var reply = Parsect.parse(lexer.identifier, state);                     // reply は解析の結果
console.log("成功したかどうか: " + reply.success);
console.log("現在の位置: "    + reply.state.position);
console.log("読み取った情報: " + reply.value);

これを実行すると、次のような出力を得られます。

成功したかどうか: true
現在の位置: 23
読み取った情報: hoge

さきほどコメントして /* から */ までの間をコメントにするように指定しましたが、識別子 hoge を読み取ったあと、このコメント部分もちゃんと読み飛ばし、次のトークン = の直前で停止したことがおわかりになると思います。他にも数値リテラルを字句解析する lexer.naturalOrFloat や、文字列リテラルを読み取る lexer.stringLiteral 、予約語を読み取る lexer.reserved や任意の単純なパーサをこの言語における字句解析パーサに変換する lexer.lexeme などが自動的に作成されます。便利便利。これじゃあ全然構文解析の勉強になりませんが、とにかく楽なのでよしとしましょう。カレーを作るのにジャガイモの育て方から知る必要はない、みたいなのと同じです。

8行で書ける変数宣言の構文解析

字句解析器ができたので、手始めに次のような変数の宣言の文を構文解析してみましょう。

var hoge = 42;

この式を読み取って、読み取った情報を var hoge=42; というようなJavaScriptのソースコードとして返すようなパーサを構成してみます（BanchaScriptの変数宣言とJavaScriptの変数宣言はほぼ同じなので、ほぼ同じコードにコンパイルされます）。このような文を字句解析器で構文解析するには、『予約語varを読み取るパーサ』『識別子を読み取るパーサ』『=を読み取るパーサ』などの各種のパーサを lexer から呼び出して、順番に適用していきます。このようにいろんなパーサを順番に使用するときは、Parsect では Parsect.seq という関数を使うと次のように直感的に書くことができます。

var varStatement = Parsect.seq(function(s){       // 変数の宣言とは
                s( lexer.reserved("var") );         // まず予約語 var があって、
    var name =  s( lexer.identifier      );         // 変数名となる識別子があり(その識別子をnameとする)、
                s( lexer.reservedOp("=") );         // 代入を示す = の記号、
    var value = s( lexer.naturalOrFloat  );         // 代入する値(その値をvalueとする)、
                s( lexer.semi            );         // 最後にセミコロン。
    return "var " + name + "=" + value + ";";       // return で結果の値を返す
});

seqから受け取った s という関数に順に実行したいパーサを渡すのがポイントです。このとき、変数 name には lexer.identifier で読み取った文字列が代入されます。これは先ほど parse 関数を使って返ってきた Reply オブジェクトの reply.value の値と同じもので、seqが内部で適当にparseを呼び出してくれているのです。また、value には lexer.naturalOrFloat で読み取った数値が代入されます。あとは return でこのパーサ varStatement で返したいオブジェクトを返せば OK です。この新たなパーサ varStatement は次のように使うことができます。

var state = new Parsect.State("var hoge = 42;", 0);
var reply = Parsect.parse(varStatement, state); 
console.log("成功したかどうか: " + reply.success);          // true
console.log("現在の位置: "    + reply.state.position);   // 14 
console.log("読み取った情報: " + reply.value);             // "var hoge=42;""

（seqが渡してくる s という謎の関数オブジェクトは、パーサを実行しつつ値を取り出すための Parsect 特有の仕組みです。本家 Parsec だと Haskell 特有の言語機能(do記法)を使ってすっきりと書くことができるのですが、この言語機能は他の言語には存在しないので、このあたりは移植版それぞれで違う書き方になっています。Parsect では Parsec での書き方に似せるためにこの seq 関数を導入していますし、Java版 jparsec やRuby版 rparsec はまた違った方法で書くようになっています。Parsectと同じく JavaScript版の jsparsec も Parsec に似せようとはしてるようですが、Parsect とはまったく違う設計になっています。

この seq 関数を使うパースですが、このコールバック関数内にブレークポイントを仕掛けると、その時点でパースを一時停止することができたりします。このとき、nameやargに代入されている値を調べたり、s関数の s.suceess で現在パースが成功しているかどうか、s.peekで現在読み取ろうとしている文字列部分の情報を取得してデバッグに使うことができます。s.peek をウォッチしながらステップ実行していくと、入力が少しづつ読まれている様子が確認できます。）

何日かかっても書けそうにない、演算子式の解析

（ここの節は意味がわからなくていいです。演算子式の構文解析はやたらと難しいということだけわかってください。なるほど、まったくわからん、となるのが目標です）

プログラミング言語というからには、計算ができてなんぼのものでしょう。こんどは加算や減算などの演算子が組み合わさった式をどのように処理するかを見ていきます。まずはもっとも単純に、加算と数値しかない演算子式を考えます。『式』とはどんなものかというと、数値は『式』ですし、『式』と『式』を + でつないだものもやはり『式』です。このとき、数値を NUMBER、『ふたつのうちどちらか』というのを | という記号で表すとすると、式 expr は次のように表現することができます。

expr = NUMBER | expr + expr

『式は、数値か、式と式を + で結んだもの』ということです。これを対応するソースコードにすればいいのでしょうか？この形のパーサで 1 + 2 という式を解析しようとすると、まず 1 というトークンが NUMBER と expr + expr のどちらかに一致するかを調べますが、この定義では NUMBER のほうが左側にあるのでこっちを先に試します。すると 1　は NUMBER に一致するので 1 が式だということがわかり、めでたく解析は成功……といいたいところですが、実はまだ + 2 という部分が残っています。これでは 1 + 2 という式を読み取ったことになりません。ここで解析が終わってしまってはまずいのです。

先程は expr + expr より先に NUMBER であるかどうかを調べてしまったのが失敗でした。では、今度は NUMBER と expr + expr を入れ替えて、次のような定義で解析してみてはどうでしょうか。

expr = expr + expr | NUMBER

この場合は、NUMBER より先に　expr + expr にトークン 1 が一致するかを調べます。この expr は expr + expr | NUMBER のことですから、1 が expr + expr に一致するかどうかを調べるには、| の左側の expr + expr に一致するかを調べないといけないわけで、その expr + expr に一致するかを調べるにはその　expr が何かを調べなければならないわけで……

expr = expr + expr
     = (expr + expr) + expr
     = ((expr + expr) + expr) + expr
     ...

というように、1 が expr に一致するかを調べていこうとしてもひたすら展開を繰り返してしまうばかりで、1 が expr に一致するのかどうかは一向にわかりません。このように無限に再帰し続けてしまうような形式を 左再帰 といいます。本テキストで採用している『再帰下降構文解析』では加算のような単純な式でも、『式 + 式』という直感的な文法では構成できないのです。そのため、このような左再帰を含む文法をどうやって含まない文法に変形するか、というのが再帰下降構文解析では必須の話題になります。演算子式の構成が難しいのは再帰下降構文解析最大の欠点だとも言えるかもしれません。他の解析法だと左再帰を含んでも処理できる場合があるのですが、それはそれでまた別に面倒なアルゴリズムが必要になります。

さらに、* は + よりも優先順位が高いので、優先して結合するように処理しなくてはなりません。また、同じ順位でも結合の方向によって結合のしかたが変わってきます。さらに、演算子は中置演算子だけじゃなくて前置演算子や後置演算子もあります。さらには三項演算子や関数呼び出しのような構文、キャストの構文も入り混じり、とにかくもう複雑で、構成するのがひたすらに難しくて面倒くさいのが、この演算子式なのです。もはや何が面倒くさいのかを説明するのすら面倒くさいというレベル。思いつきでパーサを書き始めた人は、 だいたいここで挫折 します。

実際は10行にも満たない、演算子式の解析器

というわけで式の解析はとても大変なので、ライブラリに付属している 演算子式のパーサを自動的に構成してくれる機能 を使います。使い方は簡単で、演算子の一覧表と作るのと、式の木構造における末端の項を解析するパーサを用意するだけです。まずは演算子の表をどのように定義するかを見てみます。字句解析器で作った lexer の lexer.prefix、lexer.postfix、lexer.binary は、それぞれ前置演算子、後置演算子、中置演算子を表すオブジェクトを作成する関数です。最初の引数には演算子の記号を文字列で、ふたつめの引数は、その演算子の両辺の式の値（両辺の位置の式をパーサで解析したときの値）を受け取ってその演算子式の値を返す関数です(紙幅の都合で、無名関数リテラルの代わりに => というアロー関数式を使って書いています。)
。中置演算子はさらに３つ目の引数として結合方向を表す引数もとります。

var opTable = [                                                                                         
    [lexer.prefix("-", x=>"-"+x), lexer.prefix("+", x=>x)],                                             
    [lexer.binary("*",  (x,y)=>x+"*"+y,  Parsect.Assoc.Left), lexer.binary("/",  (x,y)=>x+"/"+y,  Parsect.Assoc.Left)], 
    [lexer.binary("+",  (x,y)=>x+"+"+y,  Parsect.Assoc.Left), lexer.binary("-",  (x,y)=>x+"-"+y,  Parsect.Assoc.Left)], 
    [lexer.binary("<",  (x,y)=>x+"<"+y,  Parsect.Assoc.Left), lexer.binary(">",  (x,y)=>x+">"+y,  Parsect.Assoc.Left)],
    [lexer.binary("==", (x,y)=>x+"=="+y, Parsect.Assoc.Left), lexer.binary("!=", (x,y)=>x+"!="+y, Parsect.Assoc.Left)]
];

この演算子の一覧表 opTable のうち、先頭の方の配列に含まれる演算子ほど優先順位が高くなります。上記の表の場合、単項の +, - がもっとも優先順位が高く、次に *, / 、その次に +, - という順序になることがわかります。演算子を追加したければ、この表にさらに追加すればいくらでも演算子を増やすことができます。この実装では、それぞれの演算子式は単に同じ意味の文字列を作って返すようになっています。

次に、各演算の末端の項となるパーサを用意します。ここでは簡単のために数値と識別子のみが項となるとしましょう。あるふたつのパーサのうちどちらかということを表すには、Parsect.or を使います。

var term = Parsect.or(
    lexer.naturalOrFloat,                           // 数値リテラルか、
    lexer.identifier                                // 識別子
);

ここでは説明のためにかなり簡略化していますが、他にもこの term を他の種類の項に対応させれば、文字列リテラルや括弧で囲まれた式、関数呼び出しの式なども項として書けるように拡張できます。詳しくはあとで紹介する実際のソースコードを見てください。

最後に、関数 buildExpressionParser に演算子の表と項のパーサを渡すだけです。

var expr = Parsect.buildExpressionParser(opTable, term);

これで任意の演算子式を解析できるパーサ expr が完成しました。先ほどの変数宣言のパーサにこれを組み込み、変数を初期化するときに任意の式を書けるようにしてしまいましょう。

var varStatement = Parsect.seq(function(s){ 
                s( lexer.reserved("var") ); 
    var name =  s( lexer.identifier      ); 
                s( lexer.reservedOp("=") );  
    var value = s( expr                  );       // NEW!
                s( lexer.semi            );  
    return "var " + name + "=" + value + ";";     
});

これで四則演算などの式でも変数を初期化することができるようになりました。

var state = new Parsect.State("var hoge = 1 + 2 * 42;", 0);
var reply = Parsect.parse(varStatement, state); 
console.log("成功したかどうか: " + reply.success);          // true
console.log("現在の位置: "    + reply.state.position);   // 22
console.log("読み取った情報: " + reply.value);             // var hoge=1+2*42;

やっぱり全然構文解析の勉強にはなりませんが、とりあえず簡単なのはいいことです。左再帰の除去が必要になる言語仕様は普通はこの演算子式くらいなので、ここさえ凌げばあとの構文解析は素直に書いていくだけでなんとかなります。これでパーサ最大の山は越えました。buildExpressionParser という抜け穴で回避しただけですけど。

5分でわかるパーサコンビネータ

BanchaScriptでは、先ほどの変数宣言の文を次のように何度でも繰り返すことができます。

var hoge = 42;
var piyo = 10;
var foo = 256;

このようなある構文の繰り返しというのは many という関数にパーサを渡すことで構成する事ができます。例えば、さきほどの varStatement が任意の個数繰り返すことができるなら、

var statements = Parsect.many(varStatement);

とするだけで、その変数宣言が任意の個数繰り返されるテキストを解析するパーサを作れるのです。正規表現の * 量化子みたいなものです。このとき、パーサ全体が読み取った値は、varStatement が読み取った値の配列になります。このように、他のパーサを受け取って別のパーサを作り出す関数を パーサコンビネータ といいます。先ほど出てきた seq や or もコンビネータですが、他にもコンビネータは次のようにたくさんあります。

• many(p) pの0回以上の繰り返し(正規表現の p* に相当)
• many1(p) 1回以上の繰り返し(正規表現の p+ に相当)
• optional(p) 0回か1回 (正規表現の p? に相当)
• or(p, q, r) p, q, r のうちどれかひとつ (正規表現の p|q|r に相当)
• lookAhead(p) 肯定先読み(正規表現の (?=p) に相当)
• notFollowedBy(p) 否定先読み(正規表現の (?!p) に相当)
• repeat(n,m,p) pのn回以上m回以下の繰り返し(正規表現の p{n,m} に相当、Parsecにはない)

これらは正規表現にも見られるようなものばかりです。さらに、

• sepBy(p, q) qで区切られたp。 sepBy("p", ",") なら p,p,p,p などにマッチ
• between(p, q, r) p,q,rで順番に読み取るが、真ん中のqの値だけ返す (Parsecと引数の順序が異なる)

などなどの各種のコンビネータがあります。

パーサコンビネータは Haskell や OCaml のような関数型言語の界隈でよく使われてきましたが、けっして関数型言語の専売特許というわけではありません。メジャーな手続き型言語でももちろん使うことができますし、正規表現で手におえないような複雑な構文解析をするときにはとても役に立つものです。また、昔から構文解析に使われてきた yacc/lex (bison/flex) や ANTLR のようなパーサジェネレータよりずっと柔軟でお手軽です。なにしろただのライブラリなので、構文定義専用の特別な DSL を覚えたり、事前にツールを実行してパーサのソースコードを生成したりという手順が必要ないからです。

100行ちょっとで書けるBanchaScriptコンパイラの完成

ここまでで変数の宣言の式や演算子式を構文解析できるようになりました。あとは、基本的には同じ調子で関数定義やら何やらの文のパーサを定義して、Parsect.or や Parsect.many のコンビネータでつなぎ合わせるだけです。BanchaScript の関数定義はつぎのようなものです。

def hoge(k){
    var x = k * 2;
    return x;
}

これを読み取る関数定義のパーサも、先ほどの変数宣言と同じように seq を使ってトークンや式が出現する順番でひとつづつパーサを適用して読み取っていくだけです。まずdefという予約語があって、識別子（関数名）、括弧で囲まれてカンマで区切られた識別子（引数）の列、中括弧で囲まれた文の列。これを seq で順番に読んでいきます。

// 関数の定義
var func = p.seq(s=>{                       
    // 最初に予約語 def があって、
    s( lexer.reserved("def") );  

    // 関数名
    var name = s( lexer.identifier );       

    // コンマで区切られた識別子が、括弧で囲まれたものがあって（これが引数 args）
    var args = s( lexer.parens(p.sepBy(lexer.identifier, lexer.comma)) );   

    // 複数の文が中括弧で囲まれたものがある
    var body = s( lexer.braces(p.many(p.or(func, returnStatement, varStatement, exprStatement))) );     
    
    // 対応するJavaScriptコードを返す
    return s.success && ["function ", name, "(", args.join(','), "){", body.join(""), "}"].join('');    
});

筆者が BanchaScript のためにこれまでに実装したコードは 100行強ですが、以下の様な機能が実現できました。

• 関数の定義
• 関数の呼び出し
• 変数の定義
• if文
• 四則演算
• ネストできるコメント

まだ for 文などの制御文すらありませんが、ひとまず四則演算はできますし、関数だけあればあとはなんとかなる気がしないでもないので、ひとまずこれだけの言語仕様に留めておきます。

10分くらいでわかるBanchaScriptのユーザ定義演算子

せっかくなのでBanchaScriptにはあまり他の AltJS 系の言語では見られない珍しい機能をつけようと思い、 演算子のユーザ定義 を盛り込むことにしました。これは C++ や C# にあるような『演算子オーバーロード』ではなくて、優先順位と結合方向を指定した演算子をユーザが任意に記号を組み合わせて定義できるというものです。HaskellやSML、OCaml、Scalaあたりにはこの機能があります。BanchaScriptでは前置、後置、中置や優先順位、結合方向をすべて指定できますが、ここまでできる言語はかなり稀だと思います。たとえば、BanchaScriptでは次のような文でベクトルの加算を行う新たな演算子 =+= を定義することができます。

operator =+= infixl 2 = addVectors;

infixl 2 というのは新たな演算子 =+= が優先順位が2で左結合の中置演算子であることを示します。このとき、関数 addVectors の別名として =+= が定義され、 a =+= b という式は addVectors(a, b) という式へとコンパイルされます。BanchaScriptでのユーザ演算子は単なる他の関数の別名です。ベクトル演算をするときはかなり複雑な計算式になることが多く、これを関数呼び出しやメソッド呼び出しで書こうとすると括弧だらけになってとてもつらいのです。

BanchaScriptではもっとフリーダムな演算子も定義できます。次の前置演算子 |^_^|< は標準出力する関数 log の別名です。

// 演算子の定義
operator |^_^|< prefix 5 = log; 

// こうやってつかいます
|^_^|< "わたしです";

ユーザ定義演算子があるということは事前に構文を書き下すことができないので、この機能がある言語は構文解析がかなり難しくなってしまいます。特に、事前にパーサを生成してしまうパーサジェネレータの類でこれを実現するのは困難です。BanchaScriptコンパイラでは、演算子の定義を見つけると、それと同時にパーサの一部をその場で書き換えて次の行から新しいパーサで構文解析を継続することで、１パスで構文解析を済ませるようになっています。BanchaScriptコンパイラには、次のような topLevelStatement という変数があり、現在の演算子テーブルからパーサを構成する buildStatementParser　という関数を呼び出すことで初期化されています。

var topLevelStatement = buildStatementParser();

パーサ全体はトップレベルのステートメントをパースしようとするたびに適宜この変数を参照し、この変数に代入されているパーサのオブジェクトを呼び出しながらながらパースを行っています。関数 buildStatementParser は現在の演算子テーブルをもとにパーサを構成しますが、そのパーサは演算子の定義を見つけると次のように演算子テーブルに演算子を追加し、新たなパーサを再構築して先ほどの topLevelStatement に代入しています。

opTable[precedence].push(newOperator);
topLevelStatement = buildStatementParser();

パーサを動的に書き換えるといっても、単に変数をひとつ書き換えているだけで難しいことは何もしていません。パーサコンビネータでは動的にパーサの構成を変化させることができるので、このような無茶な言語仕様でも簡単に構文解析できるのです。

ソースコード

BanchaScriptコンパイラは Parsect のサンプル　として一緒に github で公開してますので、覗いてみたい方はどうぞ。Parsectにはまだあまりちゃんとマニュアルが書かれていないので、同梱されているサンプルコードを参考にしたり、本家 Parsec の解説を参考にしてみるといいかもしれません。かなり古くなっていますが、readmeも多少は参考になります。

kontan/Parsect

おまけですが、BanchaScriptのコンパイルと実行をブラウザで試せる Playground を作ってみました。でも機能が足りなさすぎてアレです。

BanchaScript Playground

その他のパーサコンビネータ実装

先程も簡単に触れましたが、パーサコンビネータの実装は案外たくさんあります。

• Haskell, Parsec
• Java, jparsec
• Python, pyparsing
• Ruby, rparsec
• Perl, Parse::RecDescent
• JavaScript, jsparsec(jshaskell)
• C++, boost Spirit
• Objective-C, Parcoa
• Scala, scala.util.parsing.combinator
• C#, NParsec, Parseq
• PHP, Loco
• Clojure, fnparse

探せばどの言語でもひとつくらいは見つかりそうです。Perl使いやRuby使いは正規表現(？)で何でも構文解析してそうですけど、パーサコンビネータも意外とあるものです。自分のよく使う言語のものを探して使ってみると良いのではないでしょうか。makeTokenParser や buildExpressionParser相当の機能があるライブラリは特に便利です。筆者のおすすめはやはり遅延評価やdo記法があるHaskellのParsecです。切れ味が違います。

まとまっていないまとめ

• 自分の理想の言語を作る → 楽しい三(^q^)三
• パーサコンビネータを使えば複雑な構文解析も楽勝
• よく訓練されたParsec使いはPerl6の完全なパーサを15分で書けるらしい。なにそれこわい

関連資料

• プログラミング言語を作る 昔ながらの yacc/lex による手法
• 「なぜ作ったのか？」、オレ様言語作った人々
• コンパイラの構造を解説