0日目はこちらから.

2日で作る電卓インタプリタ[1日目]の続きです．

はい最終日です(はやい！)．前回で式から抽象構文木を得るところまで実装したので，今回は抽象構文木から実行コードを生成し，そのコードを元に実行するVM(仮想機械)を作るところまでやります．
前回と同様にリポジトリに全部コードが上がってるんで，そこも参照しつつ見ていってください．

実行コード生成器

　抽象構文木(AST)を辿ってVM用の実行コードを生成します．

実行コードの文法を定義

　まず，実行コードの命令を定義をします．今回このvmcalcで必要な命令は以下の5つです．

数をスタックに積む命令
スタックから数を取り出して足し算する命令
スタックから数を取り出して引き算する命令
スタックから数を取り出して掛け算する命令
スタックから数を取り出して割り算する命令

その命令をそれぞれPUSH, ADD, SUB, MUL, DIVとして，コードに落とし込みます．

vmcalc.h

enum class OPCODE {
    PUSH,
    ADD,
    SUB,
    MUL,
    DIV,
};

ADD, SUB, MUL, DIVはスタックを見ながら実行すればいいのですが，PUSH命令についてはそうは行きません．PUSHは単体では生きることができないのです．なので，PUSH 5みたいに引数をつけてやる必要があります．実行コードの型であるvmcode_t構造体を作ります．

vmcalc.h

struct vmcode_t {
    OPCODE type;
    int value;     //PUSH命令の引数

    //初期化用
    vmcode_t(OPCODE t): type(t) {}
    vmcode_t(OPCODE t, int v): type(t), value(v) {}
};

構造体のメンバ変数を初期化するためのコンストラクタを書いてるといつも思うんですけど，関数のオーバーロードってすごい．

実行コードクラスをつくる

　一つの式あたり実行コードは複数存在する(場合が多い)ので，vmcode_t型の可変長配列を用意します．また，ASTを与えて実行コード列が返ってきてほしいので，それをするcompile関数をつけときます(「コンパイル」はソースコードを他の言語に翻訳するという意味です)．

vmcalc.h

class VMcode {
    public:
        std::vector<vmcode_t> compile(AST *);
        std::vector<vmcode_t> codes;
        void show();
    private:
        void emit_number(AST *);
        void emit_binary(AST *);
};

他のメンバ関数については後で．

シミュレートしてみる

　実際にシミュレートして，コードが生成される過程を見ていきます．こんなASTがあるとしましょう．

このASTを文字通り「辿って」いきます．最初読まれるのは一番上の+ですよね．
二項演算子ノードの場合，まずは左辺を見ます．
ただの1の数値ノードなので，ここはスタックに数値を積むPUSH 1という命令が生成されて終了です．

PUSH 1

次．
お次は右辺を見ます．なんと右辺も二項演算子ノードです．なのでその左辺を見ます．すると2(数値ノード)なのでPUSH 2，右辺を見ると3(数値ノード)なのでPUSH 3と生成されていきます．

PUSH 1
PUSH 2
PUSH 3

左辺，右辺と生成されていったら二項演算子の種類を見ます．*は掛け算なのでMUL命令が生成されますね．

PUSH 1
PUSH 2
PUSH 3
MUL

まだここで終わりではありません．今辿った二項演算子ノードは二項演算子ノードの右辺です(話がややこしくなってきた)．最初に読まれた一番上の二項演算子ノードの左辺，右辺と生成が終わったので，先程同様種類を見ます．+は足し算なのでADD命令が生成されますね．
こんな感じでASTを辿って実行コードが生成されていきます．

PUSH 1
PUSH 2
PUSH 3
MUL
ADD

こう順々と考えていくと確かにその通りなんですが，なんか魔法じみたものを感じてしまいます．

実際に作る

　前項で行った処理をまとめます．　

数値ノードの場合はPUSH 数値命令
二項演算子ノードの場合は左辺→右辺→二項演算子の順番で見ていく

これをプログラムに落とし込みます．

vmcode.cpp

#include "vmcalc.h"

std::vector<vmcode_t> VMcode::compile(AST *ast) {
    switch(ast->get_ndtype()) {
        case NODE::NUMBER:
            emit_number(ast); break;    //数値ノードのコード生成
        case NODE::BINARY:
            emit_binary(ast); break;    //二項演算子ノードのコード生成
    }

    return codes;
}

//数値ノードの場合は PUSH 数値 命令
void VMcode::emit_number(AST *ast) {
    auto n = (Node_number *)ast;
    codes.push_back(vmcode_t(OPCODE::PUSH, n->value));
}

//二項演算子ノードの場合は左辺→右辺→二項演算子の順番で見ていく
void VMcode::emit_binary(AST *ast) {
    auto b = (Node_binary *)ast;

    compile(b->left);    //左辺のノードをコンパイル
    compile(b->right);   //右辺のノードをコンパイル

    if(b->op == "+") {
        codes.push_back(vmcode_t(OPCODE::ADD)); return;
    }
    if(b->op == "-") {
        codes.push_back(vmcode_t(OPCODE::SUB)); return;
    }
    if(b->op == "*") {
        codes.push_back(vmcode_t(OPCODE::MUL)); return;
    }
    if(b->op == "/") {
        codes.push_back(vmcode_t(OPCODE::DIV)); return;
    }
}

全くそのまんまです．
では，生成したコードを実行するVMを実装します．ついにここまできました．

VM

　ついに...ついにここまで来ました．

VMクラスを作る

VMに必要なのは，数値演算をするときに使うスタックです．今回はスタックに積む数値が整数型だけなのでint型のスタックを用意します．C++にはstd::stackという便利なものがあるので使っていきましょう．
メンバ関数については，実行コード列を受け取って実行結果を返したいので，それをするrun関数とコードを実行するexec関数をつけます．

vmcalc.h

class VM {
    public:
        int run(std::vector<vmcode_t>);
        void exec(vmcode_t);
    private:
        std::stack<int> vmstack;
};

計算する手順

　VMで計算する手順を考えます．1 + 2の実行コードは，

PUSH 1
PUSH 2
ADD

になります．PUSHはそのままですよね．スタックに積みます．

|__2__|
|__1__|

問題はADD命令です．どうやってこのスタックを操作するのでしょうか．
答えは簡単です．スタックからpopした右辺，左辺を足してスタックに戻してあげるだけです．
演算した結果は常にスタックの一番上(topといいます)に残ります．

実装する

vm.cpp

#include "vmcalc.h"

int VM::run(std::vector<vmcode_t> vmcodes) {
    if(vmcodes.empty()) {    //コード列の中身が虚無だったら実行中止
        fprintf(stderr, "no codes"); return -1;
    }
    //forループで命令ごとに実行
    for(auto code: vmcodes)
        exec(code);
    //演算結果(スタックトップ)を返す
    return vmstack.top();
}

void VM::exec(vmcode_t c) {
    switch(c.type) {
        case OPCODE::PUSH: {
            vmstack.push(c.value);
        } break;
        case OPCODE::ADD: {
            int r = vmstack.top(); vmstack.pop();
            int l = vmstack.top(); vmstack.pop();
            vmstack.push(l + r);
        } break;
        case OPCODE::SUB: {
            int r = vmstack.top(); vmstack.pop();
            int l = vmstack.top(); vmstack.pop();
            vmstack.push(l - r);
        } break;
        case OPCODE::MUL: {
            int r = vmstack.top(); vmstack.pop();
            int l = vmstack.top(); vmstack.pop();
            vmstack.push(l * r);
        } break;
        case OPCODE::DIV: {
            int r = vmstack.top(); vmstack.pop();
            int l = vmstack.top(); vmstack.pop();
            vmstack.push(l / r);
        } break;
        default:
            puts("???");
    }
}

スタックからpopした右辺，左辺を足してスタックに戻してあげる処理を見てみます．

vm.cpp

        case OPCODE::ADD: {
            int r = vmstack.top(); vmstack.pop();
            int l = vmstack.top(); vmstack.pop();
            vmstack.push(l + r);
        } break;

スタックトップを右辺に代入し，スタックから値を取り出したら，スタックトップを左辺に代入し，スタックから値を取り出します．
そして，左辺と右辺の演算結果をスタックに積んでいます．
さて，VMの実装も終わったので実際に実行します．mainファイルを書きかえてあげて下さい．

main.cpp

#include "vmcalc.h"

int main(int argc, char **argv) {
    if(argc != 2) {
        puts("error"); exit(1);
    }
    std::string src = std::string(argv[1]);
    Token token;
    Lexer lexer;
    token = lexer.run(src);
    token.show();
    Parser parser;
    AST *ast;
    ast = parser.run(token);
    parser.show(ast); puts("");
    VMcode vmcode;
    VM vm;
    int stacktop = vm.run(vmcode.compile(ast));
    printf("%d\n", stacktop);
}

g++ -o vmcalc main.cpp lexer.cpp token.cpp parser.cpp vmcode.cpp vm.cpp

でvmcalcという実行ファイルが出来たら早速実行です．

うお〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜
ちゃんと実行できてますね．電卓インタプリタ製作はこれにて終了です．

$ ./vmcalc '1 - 2 * 3'
Number( 1 )
Symbol( - )
Number( 2 )
Symbol( * )
Number( 3 )
End(  )
(- 1 (* 2 3 ))
-5

$ ./vmcalc '1 - 2 * 3 * 32'
Number( 1 )
Symbol( - )
Number( 2 )
Symbol( * )
Number( 3 )
Symbol( * )
Number( 32 )
End(  )
(- 1 (* 2 (* 3 32 )))
-191

たのしい．

おわりに

　表記揺れが激しい下手くそな文章ですいません，完全なソースコードはvmcalcに載っているので是非参照して下さい．
　このインタプリタは大体400行ぐらいで，電卓機能しかついてませんが，色々改良してforループやif文，変数などを実装してみるとどんどん「プログラミング言語」っぽくなっていって楽しいです．
　最後に宣伝です．趣味でmaxcというインタプリタ言語を作っています(リポジトリはこれ)．最近if文とかが処理できるようになって楽しいです．fizzbuzzとかが動くと何とも言えない感動を覚えます．スターをつけてくれたら喜びます．
　お疲れ様でした．

参考リンク集