LoginSignup
10
9

More than 1 year has passed since last update.

@stk2k(Katsuki Shuto)in株式会社ロボマインド

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

Last updated at Posted at 2022-05-20

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

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

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

スクリプト言語とは

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

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

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

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

　実行環境の形態としては

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

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

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

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

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

a = 3 + 1;
print a;

【スクリプト言語MikoScriptの仕様】

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

そもそもコンパイラとは

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

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

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

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

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

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

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

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

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メソッドはそれぞれ英文字、数字、式の文字かどうかを判定します。

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

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メソッドをオーバーライドすることで、クラスのインスタンスを文字列出力できるようになります。

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

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

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

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エントリポイントを実装して、コマンドラインからソースコードをコンパイルしてみましょう。

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

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

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

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

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

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

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

まとめ

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

最後に

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

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

ご応募は会社の採用応募フォームまたは私のTwitterまでDMをお願いします。

次の記事

前の記事

10
9
1

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
10
9