仮想マシン3分クッキングその４（スクリプト言語を作るパート２）

# 妹ちゃんの通う小学校

　妹ちゃん「**パーサー**ができたら次は**コード生成器**ね」
　ワイ「なんかいろいろ難しいなぁ・・・」
　妹ちゃん「そう？**コード生成器**は**トークン順**に**中間コード**を生成するだけだから、そんなでもないと思う。情報処理の授業でも習うし」
　ワイ「！？妹ちゃんの通う学校って・・・」

# 今回のテーマ

- **コード生成器**（**ジェネレータ**）の実装
    - **中置記法**から**逆ポーランド記法**（**Reverse Polish Notation**）に変換する処理の実装
- **仮想マシン**の実装

# **コード生成器**（**ジェネレータ**）とは

　**コード生成器**（**ジェネレータ**）は、**パーサー**によって**トークン化**されたソースコードを順番に処理して**中間コード**（**バイトコード**）を出力するプログラムです。

　具体的には、**パーサー**と同じくグローバルなステート（状態）を１つ用意して

1. 状態を【**開始状態**】に設定
1. トークンを１つ取得
    - T_VARIABLE（**変数**）なら**変数**を**変数テーブル**に登録し【**代入文**】状態に遷移
        - トークンをさらに１つ取得
        - T_EQUAL（**=**）なら【**式**】状態に遷移
        - トークンをさらに１つ取得
        - T_EXPRESSION（**式**）ならトークン内容（数式）を**逆ポーランド記法**に変換
        - 数式部を順に**バイトコード生成**（右辺）
        - 代入文の**バイトコード生成**（左辺）
        - 文の終端トークン、T_END_OF_STATEMENT(**；**)を読む
        - 状態を【**開始状態**】に設定、１に戻る
    - T_PRINT（**print文**）なら【**print文**】状態に遷移
        - トークンをさらに１つ取得
        - T_VARIABLE（**変数**）なら**変数テーブル**から**変数**IDを取得後、**バイトコード生成**
        - 文の終端トークン、T_END_OF_STATEMENT(**；**)を読む
        - 状態を【**開始状態**】に設定、１に戻る
1. 不正なトークンがきた場合は文法エラーとする

のように処理します。

　**UML**の**アクティビティ図**で描くと以下のようになります。

![Untitled (14).png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/17003/daed71f6-1d90-131b-706a-e5b2e9a538af.png)


# **変数テーブル**とは

　**変数テーブル**とは、現在の**スコープ**（今回は**グローバルスコープ**しかありませんが）において有効な変数を登録するテーブルのことです。

　**コンパイラ**が**変数テーブル**で**変数**を管理することで、最終的な**バイトコード列**に**変数名**を含めなくてよくなります。

 今回、**変数テーブル**は変数名→変数ID(整数)へのマップ（**VariableTable**クラス）という形で実装しています。

# バイトコード

　今回作成するVMで使用可能な**バイトコード**は以下となります。

　　　　　　　　　　表１　MikoVm2のバイトコード
| オペコード | オペランド | 説明 |
|:--|:--|:--|
| PUSH | op1=整数値 | 指定した整数値をスタックにPush |
| PUSHV | op1=変数ID | 指定した変数の内容をスタックにPush |
| POPV | なし | スタックから値を１つPopして指定した変数にセット |
| ADD | なし | スタックから２つの値をポップして和を計算、結果をスタックにPush |
| SUB | なし | スタックから２つの値をポップして差を計算、結果をスタックにPush |
| MUL | なし | スタックから２つの値をポップして積を計算、結果をスタックにPush |
| DIV | なし | スタックから２つの値をポップして除算、結果をスタックにPush |
| PRINT | op1=変数ID | 指定した変数の内容をコンソールに出力する |


# CodeGeneratorクラス

　CodeGeneratorクラスは、パーサーのパース結果（つまり**トークン列**）を入力として**バイトコード列**を生成します。

　T_EXPRESSION（**数式**）についてはその中身を**中置記法**から**逆ポーランド記法**に変換してから**オペコード**、**オペランド**を出力します。

 **逆ポーランド記法**を用いる理由については、[**マインド・エンジンの全貌　～第４回～　仮想マシン3分クッキングその２**](https://qiita.com/stk2k/items/8b75f86bfaa794ca5044)に記載してあります。

　それでは実際のCodeGeneratorのコードについてみていきましょう。

```csharp

namespace MikoVm
{
    /**
     * 中間コード生成クラス
     */
    class CodeGenerator
    {
        const int STATE_START       = 0x0001;     // 開始状態
        const int STATE_ASSIGN      = 0x0002;     // 代入文
        const int STATE_EXPRESSION  = 0x0004;     // 式
        const int STATE_PRINT       = 0x0008;     // print文
        const int STATE_BEFORE_END  = 0x0010;     // 文終端（；）の前

        /**
         * バイトコードを生成
         */
        public static Bytecode[] GenerateCodes(Token[] tokens)
        {
            // 状態変数
            int state = STATE_START;

            // バイトコードバッファ
            var bytecode_buffer = new List<Bytecode>();

            // 変数テーブル
            var var_tbl = new VariableTable();

            // 代入先変数のID
            int assign_var_id = 0;

            // １トークンずつ処理
            foreach (var tk in tokens)
            {
                // 状態毎の処理
                if (state == STATE_START)
                {
                    if (tk.TokenType == Token.EnumTokenType.T_VARIABLE)
                    {
                        // 【開始】状態のとき変数が来たら、変数を変数テーブルに登録して【代入文】状態に遷移
                        assign_var_id = var_tbl.RegisterVariable(tk.TokenString);
                        state = STATE_ASSIGN;
                    }
                    else if (tk.TokenType == Token.EnumTokenType.T_PRINT)
                    {
                        // 【開始】状態のときprint文が来たら、【print文】状態に遷移
                        state = STATE_PRINT;
                    }
                    else
                    {
                        throw new SyntaxError($"Syntax error found at token({tk})");
                    }
                }
                else if (state == STATE_ASSIGN)
                {
                    if (tk.TokenType == Token.EnumTokenType.T_EQUAL)
                    {
                        // 【代入文】状態のときイコール（＝）が来たら、【式】状態に遷移
                        state = STATE_EXPRESSION;
                    }
                    else
                    {
                        throw new SyntaxError($"Syntax error found at token({tk})");
                    }
                }
                else if (state == STATE_EXPRESSION)
                {
                    if (tk.TokenType == Token.EnumTokenType.T_EXPRESSION)
                    {
                        // 【式】状態のとき式トークン（四則演算子or数字）が来たら、逆ポーランド記法に変換してバイトコード化する
                        WriteExpressionCode(tk.TokenString, bytecode_buffer);
                        // 代入文を出力
                        var bc = new Bytecode(Bytecode.EnumOpecode.opcPOPV, assign_var_id);
                        bytecode_buffer.Add(bc);
                        // 【終端前】状態に遷移
                        state = STATE_BEFORE_END;
                    }
                    else
                    {
                        throw new SyntaxError($"Syntax error found at token({tk})");
                    }
                }
                else if (state == STATE_PRINT)
                {
                    if (tk.TokenType == Token.EnumTokenType.T_VARIABLE)
                    {
                        // 【print文】状態のとき変数がきたら変数テーブルを検索してprint文のバイトコードを出力
                        int var_id = var_tbl.FindVariable(tk.TokenString);
                        var bc = new Bytecode(Bytecode.EnumOpecode.opcPRINT, var_id);
                        bytecode_buffer.Add(bc);
                        // 【終端前】状態に遷移
                        state = STATE_BEFORE_END;
                    }
                    else
                    {
                        throw new SyntaxError($"Syntax error found at token({tk})");
                    }
                }
                else if (state == STATE_BEFORE_END)
                {
                    if (tk.TokenType == Token.EnumTokenType.T_END_OF_STATEMENT)
                    {
                        // 【開始】状態に遷移
                        state = STATE_START;
                    }
                    else
                    {
                        throw new SyntaxError($"Syntax error found at token({tk})");
                    }
                }
            }

            return bytecode_buffer.ToArray();
        }
    }
}
```

　GenerateCodesメソッドの中身は、トークンを１つずつ読み込んで状態遷移と文法の確認、そして**バイトコード**の出力処理を行っています。

　**代入文**、つまり「a = 3 + 1」のような文が来た場合は**変数テーブル**に変数を登録し、その変数ID（整数）をassign_var_idに保存します。
　T_EQUAL(=)を経てT_EXPRESSION(**式**)が来ますので、**逆ポーランド記法**で計算した結果を変数に書き込みます。

　次に、**中置記法**から**逆ポーランド記法**に変換するメソッドです。

```csharp
namespace MikoVm
{
    class CodeGenerator
    {
        ...
        private static void WriteExpressionCode(string expr, List<Bytecode> buffer)
        {
            // RPNクラスを使って数式を逆ポーランド記法に変換
            List<string> rpn = RPN.Convert(expr);

            // 逆ポーランド記法の順で処理
            foreach(var e in rpn)
            {
                if (Regex.IsMatch(e, "^[0-9]+$"))
                {
                    // 数値の場合はPush
                    var bc = new Bytecode(Bytecode.EnumOpecode.opcPUSH, Int32.Parse(e));
                    buffer.Add(bc);
                }
                else if (e == "+")
                {
                    buffer.Add(new Bytecode(Bytecode.EnumOpecode.opcADD));
                }
                else if (e == "-")
                {
                    buffer.Add(new Bytecode(Bytecode.EnumOpecode.opcSUB));
                }
                else if (e == "*")
                {
                    buffer.Add(new Bytecode(Bytecode.EnumOpecode.opcMUL));
                }
                else if (e == "/")
                {
                    buffer.Add(new Bytecode(Bytecode.EnumOpecode.opcDIV));
                }
            }
        }
    }
}
```

　WriteExpressionCodeメソッド自体はRPNクラス（逆ポーランド記法変換クラス）が変換した字句のリストの順にバイトコードを出力するだけで、逆ポーランド記法への変換はRPNクラスで実装されています。

　こちらの実装内容は、[**マインド・エンジンの全貌　～第４回～　仮想マシン3分クッキングその２**](https://qiita.com/stk2k/items/8b75f86bfaa794ca5044)の「中置記法→逆ポーランド記法への変換」で記述した変換方法をC#で実装したものになります。

　CodeGeneratorクラスの使い方は

```csharp
var tokens = Parser.Parse(src);
Bytecode[] codes = CodeGenerator.GenerateCodes(tokens);
```

 のように、パーサーがパースした結果を渡すとバイトコードの配列を返します。

# VMの実装

　最後にVMですが、これは**表１**の内容に従って**オペコード**を実行していくだけになります。

```csharp

namespace MikoVm
{
    /**
     * 仮想マシン
     */
    class MikoVM
    {
        // 変数テーブルのサイズ
        const int VARTBLE_SIZE = 256;

        /**
         * バイトコードを実行
         */
        public static void Run(Bytecode[] codes)
        {
            // 実行時変数テーブル
            var var_tbl = new int[VARTBLE_SIZE];

            // 実行時スタック
            var stack = new Stack<int>();

            foreach(var bc in codes)
            {
                switch (bc.Opecode)
                {
                    case Bytecode.EnumOpecode.opcPUSH:            // 指定した整数値をスタックにPush：　オペランド(1)=>整数値
                        {
                            int data = bc.Operands[0];
                            stack.Push(data);
                        }
                        break;

                    case Bytecode.EnumOpecode.opcPUSHV:           // 指定した変数の内容をスタックにPush：　オペランド(1)=>変数ID
                        {
                            int data = var_tbl[bc.Operands[0]];
                            stack.Push(data);
                        }
                        break;

                    case Bytecode.EnumOpecode.opcPOPV:            // スタックから値を１つPopして指定した変数にセット：　オペランド(1)=>変数ID
                        {
                            if (stack.Count == 0)
                            {
                                throw new VmRuntimeError("Stack empty!");
                            }
                            var data = stack.Pop();
                            int var_id = bc.Operands[0];
                            var_tbl[var_id] = data;
                        }
                        break;

                    case Bytecode.EnumOpecode.opcADD:             // スタックから２つの値をポップして和を計算、結果をスタックにPush：　オペランドなし
                        {
                            if (stack.Count < 2)
                            {
                                throw new VmRuntimeError("Stack empty!");
                            }
                            var data1 = stack.Pop();
                            var data2 = stack.Pop();
                            stack.Push(data1 + data2);
                        }
                        break;

                    case Bytecode.EnumOpecode.opcSUB:             // スタックから２つの値をポップして差を計算、結果をスタックにPush：　オペランドなし
                        {
                            if (stack.Count < 2)
                            {
                                throw new VmRuntimeError("Stack empty!");
                            }
                            var data1 = stack.Pop();
                            var data2 = stack.Pop();
                            stack.Push(data2 - data1);
                        }
                        break;

                    case Bytecode.EnumOpecode.opcMUL:             // スタックから２つの値をポップして積を計算、結果をスタックにPush：　オペランドなし
                        {
                            if (stack.Count < 2)
                            {
                                throw new VmRuntimeError("Stack empty!");
                            }
                            var data1 = stack.Pop();
                            var data2 = stack.Pop();
                            stack.Push(data1 * data2);
                        }
                        break;

                    case Bytecode.EnumOpecode.opcDIV:             // スタックから２つの値をポップして除算、結果をスタックにPush：　オペランドなし
                        {
                            if (stack.Count < 2)
                            {
                                throw new VmRuntimeError("Stack empty!");
                            }
                            var data1 = stack.Pop();
                            var data2 = stack.Pop();
                            if (data1 == 0)
                            {
                                throw new VmRuntimeError("Divided by zero");
                            }
                            stack.Push(data2 / data1);
                        }
                        break;

                    case Bytecode.EnumOpecode.opcPRINT:           // 指定した変数の内容をコンソールに出力する：　オペランド(1)=>変数ID
                        {
                            int data = var_tbl[bc.Operands[0]];
                            Console.WriteLine(data);
                        }
                        break;
                }
            }
        }
    }
}
```

　Runメソッドの最初でまず必要な実行時変数テーブルとスタックを用意しています。

　実行時変数テーブルのサイズは固定長（256個）ですが、これはVMの制限というわけではなく実装をシンプルにするため限定してあります。

　opcDIVとopcSUBの２オペコードだけ、スタックに乗っている順番と演算の順番が逆になりますので注意してください。

　opcPRINTは単純にコンソールに文字を出力しています。

　以上で、超シンプルな**仮想マシンの実装**ができました。

　**数式**の変数対応とか、配列変数、クラスの実装など、足りない機能だらけですが、とりあえず独自のスクリプト言語のコンパイル＆実行環境を作る雰囲気だけでも味わってもらえれば光栄です。

　全体のソースコードは以下の場所にあります。

https://github.com/ROBOmindProject/MikoVm2

Visual Studioで実際にビルド、実行してみたい方は、こちらからcloneしてみてください。

```git
git clone git@github.com:ROBOmindProject/MikoVm2.git
```


## まとめ

- **コード生成器**（**ジェネレータ**）は、中間コード（バイトコード）を出力する
- **式**の出力には**逆ポーランド記法**を用いる
- **変数テーブル**を使って変数管理する
- **仮想マシン**（**VM**）は**バイトコード**を順番に実行する

## 最後に

　株式会社ロボマインドではこれまでにないAI、『マインド・エンジン』の制作に一緒に携わっていただける開発者の方を募集しています。下記に興味または実績がある方はふるってご応募ください。お待ちしています！

- ディープラーニングの知識または技術をお持ちの方
- ディープラーニングに詳しくなくても、AIの開発に興味のある方
- 自然言語処理の知識または技術をお持ちの方
- AI技術の応用（メタバースやロボット等）に関心のある方
- C#、Java等オブジェクト指向プログラミングの経験のある方

 ご応募は会社の[採用応募フォーム](https://robomind.co.jp/saiyoujouhou/)または私の[Twitter](https://twitter.com/stk2k)までDMをお願いします。

### 次の記事

執筆中

### 前の記事

https://qiita.com/stk2k/items/d258c50edc08bf5df80f