javascript/C言語/アセンブラを用い、 字句解析、構文解析、インタプリタ、コンパイラのプログラムをスクラッチから作りながら、 「プログラミング言語の作り方」を解説する。
グローバル変数、代入、変数参照に対応する。
グローバル変数、代入、変数参照に対応する。
変数に型はないので、整数、実数、文字列が代入できる。
変数の宣言をせず、初めて代入されると、変数定義される。 代入演算子としてイコール(=)を導入する。
変数を使ったら、変数に格納されている値を参照できるようにする。
これらの言語仕様は以下だ。
$ cat source.3 //代入演算子が連続したら、右側のb=3から処理する(右結合) a = b = 3; //文字列の代入 msg = "a="; //変数の値の表示 print(msg, a, ", b=", b);
グローバル変数に対応するため、globalsオブジェクトを導入し、 変数名と値の型を管理している。 文字列用には８バイト、数値用にはxmm*レジスタのサイズの16バイトを割り当てた。
代入演算子の箇所では、値の型によって、命令とレジストを切り替えている。
変数の中身を取り出す処理も同様だ。
$ 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 == "()"){
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が意図どおりに分割されているか、念のため表示しているので、確認しよう。
問題なく、自作プログラミング言語を実装できていることが分かる。
$ ./interpretor.js
$ ./interpretor.js
処理前tokens =[
'a', '=', 'b',
'=', '3', ';',
'msg', '=', '"a="',
';', 'print', '(',
'msg', ',', 'a',
',', '", b="', ',',
'b', ')', ';'
]
抽象構文木ast={
left: {
left: {
left: { left: 'a', op: '=', right: { left: 'b', op: '=', right: '3' } },
op: ';',
right: { left: 'msg', op: '=', right: '"a="' }
},
op: ';',
right: {
left: 'print',
op: '()',
right: {
left: {
left: { left: 'msg', op: ',', right: 'a' },
op: ',',
right: '", b="'
},
op: ',',
right: 'b'
}
}
},
op: ';',
right: undefined
}
a=3, b=3
コンパイラが出力したアセンブラ(source.s)を載せておく。
$ cat source.s #intel表記を使う .intel_syntax noprefix #エントリポイント .global _start _start: #.n1で定義されたリテラル数値取得 movdqu xmm0,.n1 #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 #popx スタックからxmmへコピー後、スタック縮める movdqu xmm0,[rsp] add rsp,16 #代入演算子 .ga=xmm0(数値) movdqu .ga,xmm0 #push スタック伸ばしてxmmを保存 sub rsp,16 movdqu [rsp],xmm0 #.s1で定義されたリテラル文字列取得 lea r10,[.s1] push r10 #アライメント8バイト伸ばす sub rsp,8 #アライメント8バイト戻し add rsp,8 pop r10 #代入演算子 .gmsg=r10(文字列) mov .gmsg,r10 push r10 #アライメント8バイト伸ばす sub rsp,8 #グローバル変数.gbを取得 movdqu xmm0,[.gb] #push スタック伸ばしてxmmを保存 sub rsp,16 movdqu [rsp],xmm0 #.s2で定義されたリテラル文字列取得 lea r10,[.s2] push r10 #アライメント8バイト伸ばす sub rsp,8 #グローバル変数.gaを取得 movdqu xmm0,[.ga] #push スタック伸ばしてxmmを保存 sub rsp,16 movdqu [rsp],xmm0 #グローバル変数.gmsgを取得 mov r10,.gmsg 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 #アライメント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 3 #文字列リテラル.s連番で定義 .s1: .string "a=" .s2: .string ", b=" #グローバル変数.g変数名のエリアを8 or 16バイト確保 .comm .gb, 16 .comm .ga, 16 .comm .gmsg, 8