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(); //引数の型の配列をループして、1つずつ処理する 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レジスタは別々で数えるので、2番目でも最初の実数なので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