2時間でコンパイラを作った話
※注意：この記事を読む前に異世界の難解プログラミング言語「lex」の紹介を読むことをお勧めします。
まへがき
私は電車に揺られながらオフ会会場へと向かっていた。
移ろいゆく景色を眺めながら、そこはかとなく
あーコンパイラ作らないとな
と思った。
What’s happened?
とあるオフ会にてスライド発表をしよう！ということになりました。
それで私はせっかくプログラミング言語の仕様を作ったのにこれを用いない手はない！
と思ったんですよ。
それで、以下を用意する手はずだったんです。
- スライド
- コンパイラ(或いはインタプリタ)
- 気合
当日の朝。なにも用意できませんでした。
おはようございます。
あえて言うならば気合だけは用意できました。
そこで、何が何でも発表するため、スライドはhsjoihs氏に用意してもらえることになったので、私は行きの電車内の2時間でコンパイラを作成することにした。
ほんぶん
コンパイラ(インタプリタ)を作る言語
2時間で作れる規模のコンパイラを作るにあたり、私が手癖で書ける言語といえばJavaScriptしかありませんでした。(それが後々功を奏した)
というわけでまずはindex.htmlとindex.jsを作成します。
CSSだァ？そんなもの要るわけねぇだろ！
HTMLに必要なものは
- コード書く場所
- 出力する場所
- 実行ボタン ぐらいなので、これだけ書いてさっさとJavaScriptに移りましょう。(※実物のコードにインデントは無い)
<!DOCTYPE html>
<html>
<head>
<meta charset="UTF-8">
<script src="index.js"></script>
</head>
<body>
program:<br>
<textarea id="program" rows="10" cols="64"></textarea><br>
output:<br>
<textarea id="output" rows="10" cols="64"></textarea><br>
<input type="button" onclick="/*あとで*/" value="run">
</body>
</html>
インタプリタの仕様
インタプリタは大体以下の構造で動きます。ちなみにコンパイラとインタプリタの違いは出力先がruntimeか機械語かの違いです(ほんまか？)。
しかし、ここでは2時間で仕上げるために以下を削ります。
簡単な言語なのでtokenizerはString.prototype.splitに任意長の空白を意味する正規表現を流すだけで区切れます。
const tok = src.split(/\s+/);
また、これから作る「lex」言語はプログラムの順番とIR(中間表現)の順番が大体同じという言語特徴を持っているので、パーサーとコードジェネレーターをくっつけることができます。
そして最適化は2時間クオリティに必要ありませんよね？
パーサー(兼コードジェネレーター)
この「lex」言語は、LL(1)文法で記述できる言語、という分類をされます。
これはどういうことかというと、言語を解析する際に遠くのトークン(激ウマギャグ)を読んだり既に読んだトークンを読み直したりしなくても、単純にトークンを1つずつ解析していくだけで読める言語だということです。単純ってことです。
コードを解析する方法としては再帰下降法を用います。
再帰下降とは、解析するコードの入れ子構造をパーサー側で再帰構造に見立てて解析していく方法です。
この方法の利点としては、構文木と関数呼び出しの形が同じになっていてパーサーのコードの見通しが良くなる点、また書きやすくなる点が挙げられます。
ではやっていきます。まずトークンを読み進める関数を作ります。
let step = 0; //現在のトークンの位置
let curtok = tok[0]; //現在のトークン
function next() {
if(curtok === "") throw "Reached EOF"; //最終トークン以降を読もうとするとエラー
step++;
curtok = tok[step];
if(typeof curtok === "undefined") curtok = ""; //最終トークンは0文字の文字列にする
}
これで、curtok変数を読むことで現在のトークンを取得し、next関数で読み進められるようになりました。
次に、どのように中間コードを出力するかを考えましょう。
今回の言語では、関数定義と実行する関数を出力したいので、以下の変数を用意しました。
const progs = {dec:{}, prog:[]};
decは関数名をキーとして関数定義(二重配列、後で説明)を値とするHashMapとなっています。
progは実行する関数の関数名の配列です。
具体的な言語仕様は先述の記事で読んでいただきたいのですが、二重配列にしたのは節ごとにコード列を区切りたかったからです。
節ごとにコードを保存する配列を変えるのは、ジャンプ処理を楽にするため(見る節を変える操作が配列のインデックスを変えるだけでよくなる)です。
さて、再帰下降を書いていきます。
コードの構造を記述する方法として、BNFというものがあります。
program ::= declare*
declare ::= "lex" funcdec | funcname "."
funcdec ::= funcname code* "."
code ::= "la"* "lex" | "lex" funcname | "elx" | "melx" | "pelx" | number
funcname ::= (任意の文字列)
number ::= (数値)
簡単に言うと*記号が繰り返しで、|記号が「または」を表します。
プログラムはdeclareの集合で、declareは"lex"+関数定義、または関数名+”.“で表せる、などと読みます。
実は再帰下降法はこれをそのまま関数に落とし込むだけなんです。
function program() {
while(curtok !== "") declare();
}
function declare() {
if(curtok === "lex") {
next();
funcdec();
} else {
next();
if(curtok !== ".") throw "Expected `.`";
next();
}
}
function funcdec() {
const funcname = curtok;
next();
while(curtok !== ".") code();
next(); //"."を読む用
}
//以下省略
現在のトークンを読んでBNF中のマッチする構造を解析していく。
コードを見るとBNFそのままであるように思えます。*はwhile文、|はif文で表せます。
今回はこの解析関数にコード生成を入れていきます。
まずdeclare関数を次のように変更します。
function declare() {
if(curtok === "lex") {
next();
progs.dec[curtok] = funcdek();
} else {
progs.prog.push(curtok);
next();
if(curtok !== ".") throw "Expected `.`";
next();
}
}
これからfuncdec関数に関数ごとのコード列を返させるので、ここで関数定義に登録しているわけですね！
ではfuncdec関数をやっていきます。
なお、code関数はコード生成の都合上funcdec関数に取り込まれました。特に関数を分けるメリットもないしね。
function funcdec() {
let sentences = [[]];
let cursent = sentences[0];
let sentstep = 0;
function nextsent(){
sentstep++;
cursent = sentences[sentstep] = [];
}
next(); //関数名を飛ばす
/* コード生成部分 */
return sentences;
}
まずsentencesという二重配列を用意して、現在の節を表す変数と、次の節(ジャンプ単位)に移る関数も用意したので、これで下準備は完了です。
次に関数定義本体をやります。
let dofn = false; //節中で関数を呼んでいるかどうか
let las = 0; //"la"* "lex"のlaの数
let maxlas = 0; //節中のlaの数の最大数
while(curtok !== ".") {
switch(curtok) {
case "la": //"la"* "lex"のla
if(dofn) throw "Cannot put `la` after function call";
las++;
if(maxlas < las) maxlas = las; //最大の更新
if(las > 3) throw "Too many `la`s more than 3 in the sentence";
break;
case "lex":
if(las > 0) { //"la"* "lex"のlex
cursent.push({type:"lex", value:las});
las = 0;
} else { //"lex" funcnameのlex
next();
cursent.push({type:"execute", value:curtok});
dofn = true;
}
break;
case "elx": //節を区切る奴たち
case "melx":
case "pelx":
dofn = false;
if(curtok !== "elx") cursent.push({type:curtok});
cursent.unshift({type:"pop", value:maxlas}); //節の頭にpopする命令を入れる。
maxlas = 0;
nextsent();
break;
default: //数値
cursent.push({type:"push", value:Number(curtok)});
break;
}
next();
}
cursent.unshift({type:"pop", value:maxlas}); //最後が"."で終わっているが、そこでも節は終了判定なのでpop命令を入れるべし
next(); //"."の読み飛ばし
IRの命令のデータ形式はtypeに命令の名前、valueに引数を入れています。
これで実際に実行するとき扱いやすくなります。
コード実行
解析して出力されたIRを実行していきましょう！
まず、この言語はスタック指向なのでスタックを作ります。
function runtime(src) {
let stack = [];
/* ここに定義された関数を実行する関数 */
/* ここに関数実行 */
}
簡単だね。
次に、定義された関数を実行をする関数を書いていきます。
function execute(fname) {
const func = src.dec[fname]; //関数本体
if(typeof func === "undefined") throw "Function `" + fname + "` is not defined";
for(let si = 0; si < func.length; si++) { //siは節の位置
const sent = func[si];
lex lexes = []; // la lexの置き場所
for(let op of sent) {
switch(op.type) {
case "pop":
//スタックからポップしたものをla lexの置き場所に入れていく
for(let i = 0; i < op.value; i++) lexes.push(stack.pop());
break;
case "push":
stack.push(op.value);
break;
case "lex":
stack.push(lexes[op.value-1]);
break;
case "execute":
if(op.value === "xel") { //標準出力のプリミティブ関数
document.getElementById("output").value += String.fromCharCode(stack.pop());
} else if(op.value === "ata") { //加算のプリミティブ関数
stack.push(stack.pop() + stack.pop());
} else { //ただの関数実行
execute(op.value);
}
break;
case "pelx":
si += stack.pop();
break;
case "melx":
let jump = stack.pop();
if(stack.pop() === 0) si += jump;
break;
}
}
}
}
基本的には命令を見ながらstackをpushしたりpopしたりして値や制御構造を制御していくだけです。
最後に、実行すべき関数の関数名をexecute関数に放り投げていき、プログラムを実行します。
src.prog.forEach(fname => execute(fname));
こういうとき関数型プログラミングって便利なのよね。
というわけでこれにてコードが実行できるようになりました！
仕上げ
HTMLのボタンを実行するコードをまだ書いてなかったなと思いつつ。
<input type="button" onclick="runtime(compile(document.getElementById('program').value))" value="run">
これで、書かれたプログラムを読み取り、コンパイルし、実行します！やったー！
さいごに
オフ会では無事発表を終えました。好評をいただいて何よりでした。わーい
皆さんも作ってみましょうコンパイラ(575)