javascript/C言語/アセンブラを用い、 字句解析、構文解析、インタプリタ、コンパイラのプログラムをスクラッチから作りながら、 「プログラミング言語の作り方」を解説する。
構文解析と実行を分離する。
構文解析のアウトプットとして、抽象構文木(AST)として出力するように変更する。 実行部分ASTを渡すと、実行するrun.jsを実装することにする。
実装の前に、構文解析のアウトプットとなる、抽象構文木(AST)について、先にイメージをしておきたい。
javascriptでは、木構造は、オブジェクトで表す。
printという関数名をleftに、 関数呼び出しを表す演算子"()"をopに、 引数として渡す文字列"hello world"をrightにセットすると、以下のようになる。
//print("hello world")の場合の、ASTの例
{
left: "print",
op: "()",
right: "hello world"
}
このオブジェクト(tree構造のノード)を生成するコードは以下のように書けばよい。
//すでに変数に値が入っているとする
var left = "print";
var op = "()";
var right = "hello world";
//オブジェクトが生成される。
var obj1 = {left:left,op:op,right:right};
//変数名とkey名が同じであれば省略できる
var obj2 = {left,op,right};
コンパイラを作るにあたり、以下のファイル構成で実装した。
parserがastを作る処理は同じなので、コンパイラから、 インタプリタのparser.jsをそのまま利用している。
astをgenasmに渡し、アセンブラコードを受け取り、ファイルに書き出している。
外部asコマンド、ldコマンドで、実行ファイルexecにする。
利便性のため、実行ファイルexecも実行してすぐに結果が出るようにしている。
$ cat compiler.js
#!/usr/bin/node
//別ファイルに記述している処理を読み込む
var {exec,write,read,show,error} = require("./utils.js");
var lexer = require("./lexer.js");
var parser = require("./parser.js");
var genasm = require("./genasm.js");
//source.3から読み込む
var source = read("source.3");
var tokens = lexer(source);
//filter後、処理前のtokensを表示
show("処理前tokens =",tokens);
//構文解析し、抽象構文木astを取得
var ast = parser(tokens);
show("抽象構文木ast=",ast);
console.log("-------------");
//astにしたがってコンパイル
var asm = genasm(ast);
//コンパイル結果(アセンブラ)をファイルに保存。
write("source.s",asm);
//ここまででコンパイラ自体の処理は終わり。
//ここからは外部コマンドを実行する。
//asコマンドで、機械語(オブジェクトファイル)にする。
exec("as source.s -o source.o");
//ldコマンドで、libcを動的リンク、ローダーを指定して、実行ファイルexecにする。
exec("ld -lc --dynamic-linker /lib64/ld-linux-x86-64.so.2 -o exec source.o");
//execコマンドを実行し、結果を表示。
console.log(exec("./exec"));
astからアセンブラを出力するgenasm.jsを実装した。
インタプリタでのrun.jsと同じ構成で、astをたどっていき、 run.jsでは実行したが、genasm.jsではアセンブラを出力するようにしている。
また、「13-5*2」などの場合の「おあずけ」をインタプリタでは関数の途中で別の関数を 呼び出すことで実現したが、アセンブラでは、スタックを用いて表現する。
スタックでは、push/popを利用するが、 保留するため、13をいったん覚えておくためpushする。
それから、5*2を計算し、結果の10をpushする。
popすれば10が先に取れ、もういちどpopすると13が取れる。
popはpushした順番と逆になることに注意する必要があるが、 13と10を引き算して、2という結果を得る。
話は変わるが、libcのprintfでは、16バイトアライメントを 守らないとエラーになるため、push/popの前後で調整する処理が入っている。
printfにはもう一つ落とし穴があり、文字列を表示するときは、raxレジスタが0でないといけない。 逆に、浮動小数点を表示するときは、raxが1でないといけない。
$ cat genasm.js
var {error} = require("./utils.js");
//リテラル文字列の定義
var strs = [];
//アセンブラコードの配列
//コードだけでなく、アセンブラ上の「#コメント」を出力。
var codes = [];
//astからアセンブラへ変換
module.exports = function genasm(ast){
//intel表記
codes.push("\n#intel表記を使う");
codes.push(".intel_syntax noprefix");
//エントリポイント
codes.push("\n#エントリポイント");
codes.push(".global _start");
codes.push("_start:");
//変換開始
gen(ast);
//終了ステータス0でexit
codes.push("\n#exit(0)で終了");
codes.push("end:");
codes.push("mov rdi,0");
codes.push("call exit");
//printfで使う文字列リテラル
codes.push("\n#printfで使う文字列リテラルを定義");
codes.push('.newline: .string "\\n"');
codes.push('.fmtg: .string "%g"');
//文字列リテラル
codes.push("\n#文字列リテラル.s連番で定義");
strs.forEach((s,i)=>{
//.s連番: .string "文字列"
codes.push(".s"+(i+1)+": .string "+ s);
});
//最後に改行がないと、asが文句言う。
return codes.join("\n")+"\n";
}
//「おあずけ」をアセンブラでは、スタックを用いて表現する。
//スタック操作のpush/popのラッパ関数群。
//通常レジスタには、push/popはあるが、アライメント調整があるので関数化。
//printfは、アライメントを16バイトに揃えないとエラーになる。
//push(通常レジスタ名)
(@function push(r){
//pushでアライメントが8バイトずれる
codes.push("push "+r);
//スタックポインタrspをさらに-8バイト＝伸ばしてずれを16にする。pop時に戻す。
codes.push("\n#アライメント8バイト伸ばす");
codes.push("sub rsp,8");
}
//pop(レジスタ名)
function pop(r){
//push時に伸ばしておいたスタックポインタrspを、先に+8バイト＝縮めて戻しておく。
codes.push("\n#アライメント8バイト戻し");
codes.push("add rsp,8");
//さらに、popでアライメントが8バイトずれ戻り、16バイトにそろう。
codes.push("pop "+r);
}
@)
//astの階層をたどりながらアセンブラを出力。
//アセンブラコードは、codesに格納
function gen(a){
if(!a) return;
if(!a.op){
if(a[0] == '"'){
//文字列リテラルとして定義
strs.push(a);
//「.s連番(strs.length)」という名で定義されたリテラル文字列を取得する
codes.push("\n#.s"+strs.length+"で定義されたリテラル文字列取得");
//文字列本体ではなく、アドレスを計算
codes.push("lea r10,[.s"+strs.length+"]");
//push r10(文字列) スタックに保管
push("r10");
return;
}
//それ以外(変数名、関数名などのシンボル)ならそのまま返す
return a;
}else if(a.op == "()"){
var func = gen(a.left);
if( func == "print"){
//スタックは逆転するため、reverseしておく。
[gen(a.right)].flat().reverse().forEach(m=>{
//文字列
//スタックから、printf("文字列")の第一引数rdiへセット
pop("rdi");
//文字列をprintfするときはrax=0でないとエラー
codes.push("\n#文字列をprintfするときは、rax=0でないとエラー");
codes.push("mov rax,0");
codes.push("\n#文字列表示");
codes.push("call printf");
});
//最後に改行コードを表示する
//.newlineは"\n"
codes.push("\n#改行コード.newline表示");
codes.push("lea rdi,[.newline]");
codes.push("call printf");
}else{
error("未実装の関数呼び出し func=",func);
}
}else{
error("未実装の演算子 op=",a.op);
}
}
compiler.jsを実行する。
まず、tokensとASTが意図どおりに分割されているか、念のため表示しているので、確認しよう。
「hello world」と表示されており、問題ない。
$ ./compiler.js
処理前tokens =[ 'print', '(', '"hello world"', ')' ]
抽象構文木ast={ left: 'print', op: '()', right: '"hello world"' }
hello world
コンパイラが出力したアセンブラ(source.s)を載せておく。
$ cat source.s #intel表記を使う .intel_syntax noprefix #エントリポイント .global _start _start: #.s1で定義されたリテラル文字列取得 lea r10,[.s1] push r10 #アライメント8バイト伸ばす sub rsp,8 #アライメント8バイト戻し add rsp,8 pop rdi #文字列をprintfするときは、rax=0でないとエラー mov rax,0 #文字列表示 call printf #改行コード.newline表示 lea rdi,[.newline] call printf #exit(0)で終了 end: mov rdi,0 call exit #printfで使う文字列リテラルを定義 .newline: .string "\n" .fmtg: .string "%g" #文字列リテラル.s連番で定義 .s1: .string "hello world"