javascript/C言語/アセンブラを用い、 字句解析、構文解析、インタプリタ、コンパイラのプログラムをスクラッチから作りながら、 「プログラミング言語の作り方」を解説する。
掛け算、割り算に対応しよう。
言語仕様として、掛け算、割り算を追加する。
掛け算、割り算がちゃんと計算できるか。 足し算より、掛け算が優先されるか。
$ cat source.3
//実数の割り算1.24÷2
a = 1.24 / 2 -1;
print("a = 1.24 / 2 - 1 = ",a);
//足し算より、乗算が優先されるか
b=5 - 2 * 3;
print("b = 5 - 2 * 3 = ",b);
コンパイラを作るにあたり、以下のファイル構成で実装した。
掛け算、割り算のアセンブラが出力されるように対応した。
足し算、引き算の時と同じ構成だが、 "*","/"演算子の際に、mulsd、divsd命令を使うように変更しているだけだ。
$ cat genasm.js
var {error} = require("./utils.js");
//浮動小数点かどうかで、命令やレジスタを使い分ける必要があるので
//値の型として、1:文字列、2:数値で、区別する。
//変数の型のことではない。
//グローバル変数の定義(globals[変数名]=値の型。1:文字列、2:数値)
var globals = {};
//リテラル数値の定義
var nums = [];
//リテラル文字列の定義
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#数値リテラル.n連番で定義");
nums.forEach((n,i)=>{
//.n連番: .double 数値
codes.push(".n"+(i+1)+": .double "+ n*1);
});
//文字列リテラル
codes.push("\n#文字列リテラル.s連番で定義");
strs.forEach((s,i)=>{
//.s連番: .string "文字列"
codes.push(".s"+(i+1)+": .string "+ s);
});
//グローバル変数のエリア確保
codes.push("\n#グローバル変数.g変数名のエリアを8 or 16バイト確保");
Object.keys(globals).forEach((g)=>{
//.comm .g変数名, 8
if(globals[g]==1){
//文字列 アドレス用8バイト確保
codes.push(".comm .g"+g+", 8");
}else{
//数値 xmm0用128bit=16バイト確保
codes.push(".comm .g"+g+", 16");
}
});
//最後に改行がないと、asが文句言う。
return codes.join("\n")+"\n";
}
//「おあずけ」をアセンブラでは、スタックを用いて表現する。
//スタック操作のpush/popのラッパ関数群。
//xmmレジスタには、push/popがないので、スタックポインタrspを直接操作。
//rspの値は、マイナス方向が伸びる、プラス方向が縮まる。
//push xmm0(数値)
//pushx(xmmレジスタ)
function pushx(x){
codes.push("\n#push スタック伸ばしてxmmを保存");
//保存用に16バイトスタックを伸ばす(-16)
codes.push("sub rsp,16");
//xmm*の値をスタックに16バイトコピーして保存
codes.push("movdqu [rsp],"+x);
}
//popx(xmmレジスタ)
function popx(x){
codes.push("\n#popx スタックからxmmへコピー後、スタック縮める");
//スタックから16バイトxmm0へコピーして取得
codes.push("movdqu "+x+",[rsp]");
//スタックもういらないので16バイト縮める(+16)
codes.push("add rsp,16");
}
//通常レジスタには、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に格納
//genの返り値で、値の型(1:文字列、2:数値)を、後工程に通知
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 1;
}
if(/\d/.test(a[0]) ){
//数値リテラルとして定義
nums.push(a);
//「.n連番(nums.length)」という名で定義されたリテラル数字を取得する
codes.push("\n#.n"+nums.length+"で定義されたリテラル数値取得");
//数値そのものを16バイトコピー
codes.push("movdqu xmm0,.n"+nums.length);
//push xmm0(数値) スタックに保管
pushx("xmm0");
//数値だと通知
return 2;
}
//global変数だったら、
if(globals.hasOwnProperty(a)){
if(globals[a] == 1){
//文字列変数
//アドレス「.g変数名」が変数
//文字列のアドレスが入っているのでアドレスコピーでok
codes.push("\n#グローバル変数.g"+a+"を取得");
codes.push("mov r10,.g"+a);
//push r10(文字列) スタックに保管
push("r10");
//文字列だと通知
return 1;
}else{
//数値変数
//アドレス「.g変数名」が変数
//アドレスの先に格納されている値が欲しい
codes.push("\n#グローバル変数.g"+a+"を取得");
codes.push("movdqu xmm0,[.g"+a+"]");
//push xmm0 スタックに保管
pushx("xmm0");
//数値だと通知
return 2;
}
}
//それ以外(変数名、関数名などのシンボル)ならそのまま返す
return a;
}else if(a.op == ";"){
gen(a.left) ; gen(a.right);
}else if(a.op == ","){
//カンマ区切りは、配列にする
//スタックを使うので逆順[right,left]にしている
return [gen(a.right),gen(a.left)].flat();
}else if(a.op == "="){
//グローバル変数に代入する
var name = gen(a.left);
var type = gen(a.right);
//未定義なら登録する
if(!globals[name]) globals[name] = type;
if(type == 1){
//文字列
//pop r10 スタックから取得
pop("r10");
//「.g変数名」に代入
codes.push("\n#代入演算子 .g"+name+"=r10(文字列)");
//アドレス8バイトを変数へコピー
codes.push("mov .g"+ name + ",r10");
//値を返すためpush
push("r10");
}else{
//数値
//pop xmm0 スタックから取得
popx("xmm0");
//「.g変数名」に代入
codes.push("\n#代入演算子 .g"+name+"=xmm0(数値)");
//16バイト数値そのものを変数へコピー
codes.push("movdqu .g"+ name + ",xmm0");
//値を返すためpush
pushx("xmm0");
}
}else if(a.op == "+"){
//この先でpushが呼ばれるので、left,rightの順
gen(a.left);
gen(a.right);
//pop xmm1(right) popは逆になる
popx("xmm1");
//pop xmm0(left) popは逆になる
popx("xmm0");
//足し算
codes.push("\n#足し算xmm0(数値left), xmm1(数値right)");
codes.push("addsd xmm0,xmm1");
//push xmm0 結果の格納
pushx("xmm0");
//数値を通知
return 2;
}else if(a.op == "-"){
//この先でpushが呼ばれるので、left,rightの順
gen(a.left);
gen(a.right);
//pop xmm1(right) popは逆になる
popx("xmm1");
//pop xmm0(left) popは逆になる
popx("xmm0");
//引き算
codes.push("\n#引き算xmm0(数値left), xmm1(数値right)");
codes.push("subsd xmm0,xmm1");
//push xmm0 結果の格納
pushx("xmm0");
//数値を通知
return 2;
}else (@if(a.op == "*"){
//この先でpushが呼ばれるので、left,rightの順
gen(a.left);
gen(a.right);
//pop xmm1(right) popは逆になる
popx("xmm1");
//pop xmm0(left) popは逆になる
popx("xmm0");
//掛け算
codes.push("\n#掛け算xmm0(数値left), xmm1(数値right)");
codes.push("mulsd xmm0,xmm1");
//push xmm0 結果の格納
pushx("xmm0");
//数値を通知
return 2;
}else if(a.op == "/"){
//この先でpushが呼ばれるので、left,rightの順
gen(a.left);
gen(a.right);
//pop xmm1(right) popは逆になる
popx("xmm1");
//pop xmm0(left) popは逆になる
popx("xmm0");
//割り算
codes.push("\n#割り算xmm0(数値left), xmm1(数値right)");
codes.push("divsd xmm0,xmm1");
//push xmm0 結果の格納
pushx("xmm0");
//数値を通知
return 2;
}@)else if(a.op == "()"){
var func = gen(a.left);
if( func == "print"){
//rightは、引数の型の配列(値ではなく型。1:文字列、2:数値)
//スタックは逆転するため、reverseしておく。
var argtypes = [gen(a.right)].flat().reverse();
//引数の型の配列をループして、１つずつ処理する
argtypes.forEach(m=>{
if(gen(m)==1){
//文字列
//スタックから、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");
}else{
//数値
//printf("%g",数値)の、.fmtgは"%g"で第一引数rdi
codes.push("\n#printfのフォーマット%g(数値用)");
codes.push("lea rdi,[.fmtg]");
//スタックから、printf("%g",数値)の第二引数xmm0へセット
//通常/xmmレジスタは別々で数えるので、２番目でも最初の実数なのでxmm0
popx("xmm0");
//実数をprintfするときはrax=1でないとエラー
codes.push("\n#数値をprintfするときは、rax=1でないとエラー");
codes.push("mov rax,1");
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が意図どおりに分割されているか、念のため表示しているので、確認しよう。
問題なく、自作プログラミング言語を実装できていることが分かる。
./compiler.js
処理前tokens =[
'a', '=',
'1.24', '/',
'2', '-',
'1', ';',
'print', '(',
'"a = 1.24 / 2 - 1 = "', ',',
'a', ')',
';', 'b',
'=', '5',
'-', '2',
'*', '3',
';', 'print',
'(', '"b = 5 - 2 * 3 = "',
',', 'b',
')', ';'
]
抽象構文木ast={
left: {
left: {
left: {
left: {
left: 'a',
op: '=',
right: {
left: { left: '1.24', op: '/', right: '2' },
op: '-',
right: '1'
}
},
op: ';',
right: {
left: 'print',
op: '()',
right: { left: '"a = 1.24 / 2 - 1 = "', op: ',', right: 'a' }
}
},
op: ';',
right: {
left: 'b',
op: '=',
right: {
left: '5',
op: '-',
right: { left: '2', op: '*', right: '3' }
}
}
},
op: ';',
right: {
left: 'print',
op: '()',
right: { left: '"b = 5 - 2 * 3 = "', op: ',', right: 'b' }
}
},
op: ';',
right: undefined
}
a = 1.24 / 2 - 1 = -0.38
b = 5 - 2 * 3 = -1
コンパイラが出力したアセンブラ(source.s)を載せておく。
$ cat source.s #intel表記を使う .intel_syntax noprefix #エントリポイント .global _start _start: #.n1で定義されたリテラル数値取得 movdqu xmm0,.n1 #push スタック伸ばしてxmmを保存 sub rsp,16 movdqu [rsp],xmm0 #.n2で定義されたリテラル数値取得 movdqu xmm0,.n2 #push スタック伸ばしてxmmを保存 sub rsp,16 movdqu [rsp],xmm0 #popx スタックからxmmへコピー後、スタック縮める movdqu xmm1,[rsp] add rsp,16 #popx スタックからxmmへコピー後、スタック縮める movdqu xmm0,[rsp] add rsp,16 #割り算xmm0(数値left), xmm1(数値right) divsd xmm0,xmm1 #push スタック伸ばしてxmmを保存 sub rsp,16 movdqu [rsp],xmm0 #.n3で定義されたリテラル数値取得 movdqu xmm0,.n3 #push スタック伸ばしてxmmを保存 sub rsp,16 movdqu [rsp],xmm0 #popx スタックからxmmへコピー後、スタック縮める movdqu xmm1,[rsp] add rsp,16 #popx スタックからxmmへコピー後、スタック縮める movdqu xmm0,[rsp] add rsp,16 #引き算xmm0(数値left), xmm1(数値right) subsd xmm0,xmm1 #push スタック伸ばしてxmmを保存 sub rsp,16 movdqu [rsp],xmm0 #popx スタックからxmmへコピー後、スタック縮める movdqu xmm0,[rsp] add rsp,16 #代入演算子 .ga=xmm0(数値) movdqu .ga,xmm0 #push スタック伸ばしてxmmを保存 sub rsp,16 movdqu [rsp],xmm0 #グローバル変数.gaを取得 movdqu xmm0,[.ga] #push スタック伸ばしてxmmを保存 sub rsp,16 movdqu [rsp],xmm0 #.s1で定義されたリテラル文字列取得 lea r10,[.s1] push r10 #アライメント8バイト伸ばす sub rsp,8 #アライメント8バイト戻し add rsp,8 pop rdi #文字列をprintfするときは、rax=0でないとエラー mov rax,0 #文字列表示 call printf #printfのフォーマット%g(数値用) lea rdi,[.fmtg] #popx スタックからxmmへコピー後、スタック縮める movdqu xmm0,[rsp] add rsp,16 #数値をprintfするときは、rax=1でないとエラー mov rax,1 #数値表示 call printf #改行コード.newline表示 lea rdi,[.newline] call printf #.n4で定義されたリテラル数値取得 movdqu xmm0,.n4 #push スタック伸ばしてxmmを保存 sub rsp,16 movdqu [rsp],xmm0 #.n5で定義されたリテラル数値取得 movdqu xmm0,.n5 #push スタック伸ばしてxmmを保存 sub rsp,16 movdqu [rsp],xmm0 #.n6で定義されたリテラル数値取得 movdqu xmm0,.n6 #push スタック伸ばしてxmmを保存 sub rsp,16 movdqu [rsp],xmm0 #popx スタックからxmmへコピー後、スタック縮める movdqu xmm1,[rsp] add rsp,16 #popx スタックからxmmへコピー後、スタック縮める movdqu xmm0,[rsp] add rsp,16 #掛け算xmm0(数値left), xmm1(数値right) mulsd xmm0,xmm1 #push スタック伸ばしてxmmを保存 sub rsp,16 movdqu [rsp],xmm0 #popx スタックからxmmへコピー後、スタック縮める movdqu xmm1,[rsp] add rsp,16 #popx スタックからxmmへコピー後、スタック縮める movdqu xmm0,[rsp] add rsp,16 #引き算xmm0(数値left), xmm1(数値right) subsd xmm0,xmm1 #push スタック伸ばしてxmmを保存 sub rsp,16 movdqu [rsp],xmm0 #popx スタックからxmmへコピー後、スタック縮める movdqu xmm0,[rsp] add rsp,16 #代入演算子 .gb=xmm0(数値) movdqu .gb,xmm0 #push スタック伸ばしてxmmを保存 sub rsp,16 movdqu [rsp],xmm0 #グローバル変数.gbを取得 movdqu xmm0,[.gb] #push スタック伸ばしてxmmを保存 sub rsp,16 movdqu [rsp],xmm0 #.s2で定義されたリテラル文字列取得 lea r10,[.s2] push r10 #アライメント8バイト伸ばす sub rsp,8 #アライメント8バイト戻し add rsp,8 pop rdi #文字列をprintfするときは、rax=0でないとエラー mov rax,0 #文字列表示 call printf #printfのフォーマット%g(数値用) lea rdi,[.fmtg] #popx スタックからxmmへコピー後、スタック縮める movdqu xmm0,[rsp] add rsp,16 #数値をprintfするときは、rax=1でないとエラー mov rax,1 #数値表示 call printf #改行コード.newline表示 lea rdi,[.newline] call printf #exit(0)で終了 end: mov rdi,0 call exit #printfで使う文字列リテラルを定義 .newline: .string "\n" .fmtg: .string "%g" #数値リテラル.n連番で定義 .n1: .double 1.24 .n2: .double 2 .n3: .double 1 .n4: .double 5 .n5: .double 2 .n6: .double 3 #文字列リテラル.s連番で定義 .s1: .string "a = 1.24 / 2 - 1 = " .s2: .string "b = 5 - 2 * 3 = " #グローバル変数.g変数名のエリアを8 or 16バイト確保 .comm .ga, 16 .comm .gb, 16