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

# 妹ちゃん（Miko）、スクリプト言語を作り始める

　妹ちゃん（Miko）「さーて、お兄ちゃん、今から30分で**スクリプト言語**作るから！」
　ワイ「**スクリプト言語**、ってJavaScriptとかRubyとかでしょ？30分で？？」
　妹ちゃん「そうよ」
　ワイ「いくら妹ちゃんが賢いからって、それは無理でしょ！」
　妹ちゃん「できらぁ！」
　ワイ「まじか」

かくして妹ちゃん、パソコンの前に座って何やら始めましたとさ。

# スクリプト言語とは

　**スクリプト言語**とは一般的には簡単に書けて実行できるプログラムのことです。
　そのため、**軽量言語**（**Lightweight Language**）と呼ばれることもあります。

　代表的なスクリプト言語としては、JavaScript、PHP、Ruby、Pythonなどです。

# スクリプト言語の実行環境

　**スクリプト言語**は一般的にそれを実行するための実行環境を持っています。これを**実行環境**（**ランタイム**）といいます。

　**実行環境**の形態としては

- インタプリタ型・・・ソースコードの一部のみを少しずつ解釈して実行する形式（BASIC、Pythonなど）
- VM型・・・プログラムの実行前に**コンパイル**という作業をして仮想マシン（VM）上で実行するもの

# スクリプト言語を開発するために必要なもの

　スクリプト言語は以下のようなステップで開発します。

1. **スクリプト言語**の仕様を考える
1. **実行環境**を決める
1. **コンパイラ**を（必要であれば）実装する　※インタプリタ型の場合は別の仕組みが必要
1. **実行環境**（**ランタイム**）を実装する

　今回は以下のような非常に簡単なスクリプト言語（VM型）を制作します。

```
a = 3 + 1;
print a;
```

【スクリプト言語MikoScriptの仕様】
- **セミコロン**（;）がきたら**文**の終了とする
- **文**は**ステートメント**または**代入文**
- **式**の結果を=で左辺の**変数**に代入できる（＝**代入文**）
- **式**は四則演算と整数のみ対応（**変数**、**式**は含められない）
- 唯一の**ステートメント**（**命令**）は「print文」で、画面に指定した変数の内容を出力する

# そもそも**コンパイラ**とは

 コンパイラは一般にソースコードに対し以下のような処理を行います。

```mermaid
graph LR
    A["字句解析"] --> B["構文解析"] --> C["意味解析"] --> D["コード生成"]
```

- **字句解析**（**パーサー**）・・・ソースコードの文字を１つずつ解析して意味のあるまとまり（**トークン**）にまとめる
- **構文解析**・・・**トークン**の**構造**を解析し、**ステートメント**（**命令**）として正しい順で**トークン**が並んでいるかチェックする
- **意味解析**・・・各**トークン**のまとまり（＝**ステートメント**）が意味のある解釈ができるかどうかチェックする
- **コード生成**・・・VM型であれば**中間コード**（＝**バイトコード**）を生成する

　ただ、今回はスクリプトの言語仕様が極めてシンプルなため、**構文解析**および**意味解析**は省略します。

# **コンパイラ**（**パーサー**）を作る

 では実際に**コンパイラ**をC#で実装していきます。

 bison/lexなどを使ってパーサーを自動生成することもできますが、今回はパーサーの仕組みを理解していただくため、原始的な方法で実装します。

- パーサーの状態を「**初期状態**」に設定する
- ソースコードを１文字読み込む
- 改行文字の場合はバッファからトークンに変換してバッファをクリア、「**初期状態**」に遷移する
- セミコロン（；）の場合はバッファからトークンに変換してバッファをクリア、「**初期状態**」に遷移する
- 状態に応じて、処理をする
    - **初期状態**のとき：　英文字がきたら「**変数orステートメント**」状態に遷移
    - **変数orステートメント状態**のとき：　英数文字ならバッファに追加、空白文字の場合は「**変数後**」または「**ステートメント後**」状態に遷移
    - **変数後**状態のとき：　「=」がくるまでスキップ、「=」がきたら「**式**」状態に遷移
    - **ステートメント後**状態のとき：　英文字がくるまでスキップ、英文字がきたら「**変数**」状態に遷移
    - **式**状態のとき：　**式**とみなせる文字（四則演算詞／数字／空白）であればバッファに追加

　以上の内容を実装したソースコードが以下になります。

```csharp:Parser.cs
namespace MikoVm
{
    class Parser
    {
        const int STATE_START       = 0x0001;     // 開始状態
        const int STATE_VARIABLE    = 0x0002;     // 変数
        const int STATE_POST_VAR    = 0x0004;     // 変数後
        const int STATE_STATEMENT   = 0x0008;     // ステートメント
        const int STATE_POST_STMT   = 0x0010;     // ステートメント後
        const int STATE_EXPRESSION  = 0x0020;     // 式

        public static Token[] Parse(string src)
        {
            var tokens = new List<Token>();
            var buffer = new StringBuilder();
            var state = STATE_START;

            // 改行コードを統一(CRLF/CR=>LF)
            src = src.Replace("\r\n", "\n").Replace('\r', '\n');

            // １文字ずつ処理
            int line = 0;
            foreach (char c in src)
            {
                // 改行処理
                if (c == '\n')
                {
                    line++;
                    state = STATE_START;
                    // バッファが空でなければトークンを追加
                    if (buffer.Length > 0)
                    {
                        tokens.Add(DetectToken(buffer.ToString()));
                        buffer.Clear();
                    }
                    continue;
                }

                // 文の終了処理(;)
                if (c == ';')
                {
                    // ;の場合は文終了なので[開始]状態に遷移
                    state = STATE_START;
                    // トークンを追加
                    if (buffer.Length > 0)
                    {
                        tokens.Add(DetectToken(buffer.ToString()));
                        buffer.Clear();
                    }
                    tokens.Add(new Token(Token.EnumTokenType.T_END_OF_STATEMENT, ";"));
                    continue;
                }

                // 状態毎の処理
                if (state == STATE_START)
                {
                    // 開始状態
                    if (IsAlphabet(c))
                    {
                        // アルファベットなら変数または文の開始
                        state = STATE_VARIABLE | STATE_STATEMENT;
                        buffer.Append(c);
                    }
                    else if (c != ' ')
                    {
                        throw new CompilerError($"パース失敗: {c} at line: {line}");
                    }
                }
                else if (state == (STATE_VARIABLE | STATE_STATEMENT) || state == STATE_VARIABLE)
                {
                    // 変数またはステートメントの場合
                    if (IsAlphabet(c) || IsNumber(c))
                    {
                        // アルファベットまたは数字ならバッファに追加
                        buffer.Append(c);
                    }
                    else if (c == ' ')
                    {
                        // 変数かステートメントかを判定
                        var token = DetectToken(buffer.ToString());
                        // 変数なら[変数後]状態に遷移、ステートメントなら[ステートメント後]状態に遷移
                        state = token.TokenType == Token.EnumTokenType.T_VARIABLE ? STATE_POST_VAR : STATE_POST_STMT;
                        // トークンを追加
                        tokens.Add(token);
                        buffer.Clear();
                    }
                    else
                    {
                        throw new CompilerError($"パース失敗: {c} at line: {line}");
                    }
                }
                else if (state == STATE_POST_VAR)
                {
                    // 変数の後
                    if (c == '=')
                    {
                        // =の場合は[式]状態に遷移
                        state = STATE_EXPRESSION;
                        // トークンを追加
                        buffer.Append('=');
                        tokens.Add(DetectToken(buffer.ToString()));
                        buffer.Clear();
                    }
                    else if (c != ' ')
                    {
                        throw new CompilerError($"パース失敗: {c} at line: {line}");
                    }
                }
                else if (state == STATE_POST_STMT)
                {
                    // ステートメント後
                    if (IsAlphabet(c))
                    {
                        // アルファベットの場合は[変数]状態に遷移
                        state = STATE_VARIABLE;
                        buffer.Append(c);
                    }
                    else if (c != ' ')
                    {
                        throw new CompilerError($"パース失敗: {c} at line: {line}");
                    }
                }
                else if (state == STATE_EXPRESSION)
                {
                    // 式
                    if (IsExpression(c))
                    {
                        // 式を構成する文字ならバッファに追加（式先頭の空白は無視）
                        if (c != ' ' || buffer.Length > 0)
                        {
                            buffer.Append(c);
                        }
                    }
                    else
                    {
                        throw new CompilerError($"パース失敗: {c} at line: {line}");
                    }
                }
                else
                {
                    throw new CompilerError($"パース失敗: {c} at line: {line}");
                }
            }

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

イレギュラーな文字がきた場合はすべてCompileErrorという例外クラスを投げます。
（別ファイルで定義）

IsAlphabet / IsNumber / IsExpressionメソッドはそれぞれ英文字、数字、式の文字かどうかを判定します。

```csharp
    class Parser
    {
        ...
        private static bool IsAlphabet(char c)
        {
            return c >= 'a' && c <= 'z' || c >= 'A' && c <= 'Z';
        }
        private static bool IsNumber(char c)
        {
            return c >= '0' && c <= '9';
        }
        private static bool IsExpression(char c)
        {
            return c >= '0' && c <= '9' || c == ' ' || c == '+' || c == '-' || c == '*' || c == '/';
        }
    }
```

Tokenクラスは**トークン**を表していて、四則演算子（＋－×÷）記号や**ステートメント**、**変数**など、意味のある最小限のまとまりを表しています。

```csharp:Token.cs
namespace MikoVm
{
    class Token
    {
        public enum EnumTokenType
        {
            T_UNKNOWN,              // 不明なトークン

            T_LIT_INTEGER,          // 整数定数
            T_EQUAL,                // =
            T_EXPRESSION,           // 式
            T_END_OF_STATEMENT,     // ;
            T_PRINT,                // print
            T_VARIABLE,             // 変数
        }

        public EnumTokenType TokenType { get; set; }
        public string TokenString { get; set; }

        public Token(EnumTokenType type, string str)
        {
            TokenType = type;
            TokenString = str;
        }

        public override string ToString()
        {
            return $"{TokenType}({TokenString})";
        }
    }
}
```

ToStringメソッドを**オーバーライド**することで、クラスのインスタンスを文字列出力できるようになります。

```csharp
var token = new Token(...);
Console.WriteLine($"token is {token}");
```

ちなみにPHPにもほぼ同じ意味の__toStringメソッドがあります。こちらはoverrideと書かなくていいので少しだけ楽ですね。

最後に、バッファからトークンへの変換メソッドです。

```csharp:Parser.cs
namespace MikoVm
{
    class Parser
    {
        ...
        private static Token DetectToken(string str)
        {
            var map = new Dictionary<string, Token>()
            {
                { "=", new Token(Token.EnumTokenType.T_EQUAL, str) },
                { ";", new Token(Token.EnumTokenType.T_END_OF_STATEMENT, str) },
                { "print", new Token(Token.EnumTokenType.T_PRINT, str) },
            };

            // 固定トークン
            if (map.ContainsKey(str))
            {
                return map[str];
            }

            // 正規表現で判定するトークン
            if (Regex.IsMatch(str, "^[0-9]+$"))
            {
                // 整数定数
                return new Token(Token.EnumTokenType.T_LIT_INTEGER, str);
            }
            if (Regex.IsMatch(str, @"^[0-9\+\-\*\/\s]+$"))
            {
                // 式
                return new Token(Token.EnumTokenType.T_EXPRESSION, str);
            }
            if (Regex.IsMatch(str, @"^[a-zA-Z]{1}[a-zA-Z0-9]*$"))
            {
                // 変数
                return new Token(Token.EnumTokenType.T_VARIABLE, str);
            }

            // 不明
            return new Token(Token.EnumTokenType.T_UNKNOWN, str);
        }
    }
}
```

まず最初に「=」「print」のような、固定のキーワードにマッチするかどうか調べて、マッチしないようなら順番に**正規表現**で**整数定数**、**式**、**変数**をチェックしています。

これで、パーサーは完成しました。
mainエントリポイントを実装して、コマンドラインからソースコードをコンパイルしてみましょう。

```csharp:Program.cs
namespace MikoVm
{
    class Program
    {
        static void Main(string[] args)
        {
            string src = @"
a = 3 + 1;
print a;
";
            var tokens = Parser.Parse(src);

            foreach(var tk in tokens)
            {
                Console.WriteLine($"{tk}");
            }
        }
    }
}
```

このプログラムを実行すると、以下のようなコンソール画面が表示されます。

```
T_VARIABLE(a)
T_EQUAL(=)
T_EXPRESSION(3 + 1)
T_END_OF_STATEMENT(;)
T_PRINT(print)
T_VARIABLE(a)
T_END_OF_STATEMENT(;)
```

トークンのタイプ、トークンの内容が順番に表示されているのが確認できると思います。

これで、超シンプルなコンパイラ（パーサー）が実装できました。

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

https://github.com/ROBOmindProject/MikoVm

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

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

次回は、コード生成部を作成し、実際にVM上で動かしてみます。

## まとめ

- **スクリプト言語**とは一般的には簡単に書けて実行できるプログラムのこと
- **スクリプト言語**の**実行環境**の形態としては、**インタプリタ型**と**VM型**がある
- **コンパイラ**とは、**字句解析**、**構文解析**、**意味解析**、**コード生成**を行うもの

## 最後に

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

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

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

### 次の記事

https://qiita.com/stk2k/items/4722643f4fca55cddb37

### 前の記事

https://qiita.com/stk2k/items/8b75f86bfaa794ca5044