プログラミング言語の作り方

javascript/C言語/アセンブラを用い、 字句解析、構文解析、インタプリタ、コンパイラのプログラムをスクラッチから作りながら、 「プログラミング言語の作り方」を解説する。

掛け算、割り算対応
javascript版プログラミング言語の作り方(コンパイラ開発)

掛け算、割り算に対応しよう。

ページメニュー

現時点の言語仕様

言語仕様として、掛け算、割り算を追加する。

自作言語で記述されたソース

掛け算、割り算がちゃんと計算できるか。 足し算より、掛け算が優先されるか。

$ 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);

コンパイラのファイル構成

コンパイラを作るにあたり、以下のファイル構成で実装した。

genasm.jsの実装

掛け算、割り算のアセンブラが出力されるように対応した。

足し算、引き算の時と同じ構成だが、 "*","/"演算子の際に、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

このページの目次へ戻るサイトの最上位へ戻る