2日で作る電卓インタプリタ[2日目]

0日目は[こちら](https://qiita.com/admarimoin/items/b5a87ab7a9d603ded443)から.

[2日で作る電卓インタプリタ[1日目]](https://qiita.com/admarimoin/items/1079c698dc488ffdde9b)の続きです．

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

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

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

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

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

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

```C++: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`関数をつけときます(「コンパイル」はソースコードを他の言語に翻訳するという意味です)．

```C++: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があるとしましょう．

```
     +
    / \
   1   *
      / \
     2   3
```
この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 数値`命令
- 二項演算子ノードの場合は左辺→右辺→二項演算子の順番で見ていく 

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

```C++: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`関数をつけます．

```c++: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**といいます)に残ります．

### 実装する

```c++: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した右辺，左辺を足してスタックに戻してあげる処理を見てみます．

```c++:vm.cpp
        case OPCODE::ADD: {
            int r = vmstack.top(); vmstack.pop();
            int l = vmstack.top(); vmstack.pop();
            vmstack.push(l + r);
        } break;
```
スタックトップを右辺に代入し，スタックから値を取り出したら，スタックトップを左辺に代入し，スタックから値を取り出します．
そして，左辺と右辺の演算結果をスタックに積んでいます．
さて，VMの実装も終わったので実際に実行します．mainファイルを書きかえてあげて下さい．

```c++: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という実行ファイルが出来たら早速実行です．
![Screenshot from 2019-03-10 04-09-56.png](https://qiita-image-store.s3.amazonaws.com/0/253550/0c9513ce-1284-fc3d-127b-930cba486ccf.png)
![Screenshot from 2019-03-10 04-10-08.png](https://qiita-image-store.s3.amazonaws.com/0/253550/7cf8b66e-f076-c56c-eedf-0b0cdbe80f50.png)
**うお〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜**
ちゃんと実行できてますね．電卓インタプリタ製作はこれにて終了です．

```
$ ./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](https://github.com/k-mrm/vmcalc)に載っているので是非参照して下さい．
　このインタプリタは大体400行ぐらいで，電卓機能しかついてませんが，色々改良してforループやif文，変数などを実装してみるとどんどん「プログラミング言語」っぽくなっていって楽しいです．
　最後に宣伝です．趣味でmaxcというインタプリタ言語を作っています(リポジトリは[これ](https://github.com/k-mrm/maxc))．最近if文とかが処理できるようになって楽しいです．fizzbuzzとかが動くと何とも言えない感動を覚えます．**スターをつけてくれたら喜びます．**
　お疲れ様でした．

# 参考リンク集
- [低レイヤを知りたい人のためのCコンパイラ作成入門](https://www.sigbus.info/compilerbook/)
- [高階関数を持つ言語に対するスタックベースのVM型処理系の実装](https://alpha-kai-net.info/info_sp_2018/report.pdf)