プログラミング言語をつくってみる②

実行関数を作る

パーサができたので、パーサを通して得られる抽象木をたどって、プログラムを実行する関数を作りました。パーサで得られる抽象木の節には、どのルールで作るられたかが文字列で記録されています。それをもとに処理方法を変える方針で作りました。

初めは一つの関数内で分岐しようかとも思ったのですが、今回は JavaScript でわりと自由なので、先に関数を設定してあとはその関数を呼んでいくだけという方式にしました。（まぁ、関数の設定は switch 文ですが）

SsEvalFactory 関数で、節の名前を見て、一つずつ eval 関数を設定していっています。

コード1: 実行関数

/** 評価関数を定義 */

var SsEnvironment = function () {
    this.Global = {};
};

SsEnvironment.prototype =
    {
        Get: function (key) {
            return this.Global[key];
        },
        Set: function (key, value) {
            this.Global[key] = value;
        }
    }

/**
 * 
 * @param {SsAST | SsASTLeaf} ast 
 */
function SsEvalFactory(ast) {
    if (ast instanceof SsASTLeaf) {
        ast.eval = SsEval_Token;
        ast.name = function (env) {
            var token = this.Token.Token;
            return token;
        };
    }
    else {
        switch (ast.Name) {
            case "statement":
                {
                    ast.eval = SsEval_statement;
                    break;
                }
            case "block":
                {
                    ast.eval = SsEval_block;
                    break;
                }
            case "factor":
                {
                    ast.eval = SsEval_factor;
                    break;
                }
            case "incdec":
                {
                    ast.eval = SsEval_incdec;
                    break;
                }
            case "primary":
                {
                    ast.eval = SsEval_primary;
                    break;
                }
            case "variable":
                {
                    ast.eval = SsEval_variable;
                    break;
                }
            case "declare_var":
                {
                    ast.eval = SsEval_declare_var;
                    break;
                }
            case "expr":
                {
                    ast.eval = SsEval_expr;
                    break;
                }
            default:
                {
                    ast.eval = function (env) {
                        for (var i = 0; i < ast.Children.length; i++) {
                            ast.Children[i].eval(env);
                        }
                        return null;
                    };

                    break;
                }
        }


        //右辺評価
        switch (ast.Name) {
            case "primary":
                {
                    ast.name = function (env) {
                        var first = this.Children[0];
                        if (first instanceof SsASTLeaf) {
                            var token = first.Token.Token;
                            if (token == "(") {
                                return this.Children[1].name(env);
                            }
                            //エラー
                            return null;
                        }
                        else {
                            return first.name(env);
                        }

                    }
                    break;
                }
            default:
                {
                    ast.name = function (env) {
                        if (ast.Children.length == 1) {
                            return ast.Children[0].name(env);
                        }
                    }
                    break;
                }
        }
    }

    for (var i = 0; i < ast.Children.length; i++) {
        SsEvalFactory(ast.Children[i]);
    }
}

/**
 * 
 * @param {SsEnvironment} env 
 */
function SsEval_Token(env) {
    console.log("SsEval_Token: " + this.Token.Token);
}

/**
 * 
 * @param {SsEnvironment} env 
 */
function SsEval_statement(env) {
    var first = this.Children[0];

    if (first instanceof SsASTLeaf) {
        var token = first.Token.Token;
        if (token == "if") {
            var condition = this.Children[2].eval(env);
            if (condition) {
                this.Children[4].eval(env);
            }
            else if (this.Children.length == 6) {
                this.Children[6].eval(env);
            }
        }
        else if (token == "while") {
            while (this.Children[2].eval(env)) {
                this.Children[4].eval(env);
            }
        }
        else if (token == "for") {
            //初期文
            var conditionIndex = 0;
            for (var i = 2; i < this.Children.length; i++) {
                if (this.Children[i] instanceof SsASTLeaf) {
                    if (this.Children[i].Token.Token == ";") {
                        conditionIndex = i + 1;
                        break;
                    }
                }
                else {
                    this.Children[i].eval(env);
                }
            }

            var stepIndex = conditionIndex + 2;
            var stBlockIndex = stepIndex + 1;
            for (var i = stepIndex; i < this.Children.length; i++) {
                if (this.Children[i] instanceof SsASTLeaf) {
                    if (this.Children[i].Token.Token == ")") {
                        stBlockIndex = i + 1;
                        break;
                    }
                }
            }

            while (this.Children[conditionIndex].eval(env)) {
                this.Children[stBlockIndex].eval(env);

                for (var i = stepIndex; i < this.Children.length; i++) {
                    if (this.Children[i] instanceof SsASTLeaf) {
                        if (this.Children[i].Token.Token == ")") {
                            break;
                        }
                    }
                    else {
                        this.Children[i].eval(env);
                    }
                }
            }


        }
        // エラー
    }
    else {
        first.eval(env);
    }

    return null;
}

/**
 * 
 * @param {SsEnvironment} env 
 */
function SsEval_block(env) {

    for (var i = 1; i < this.Children.length-1; i++) {
        this.Children[i].eval(env);
    }

    return null;
}


/**
 * 
 * @param {SsEnvironment} env 
 */
function SsEval_factor(env) {
    var first = this.Children[0];

    if (first instanceof SsASTLeaf) {
        var token = first.Token.Token;
        var second = this.Children[1];

        if (token == "-") {
            return -(second.eval(env));
        }
        else if (token == "!") {
            var res = second.eval(env);
            console.log(res);
            return !res;
        }


        return second;
    }
    else {
        return first.eval(env);
    }

    return null;
}

/**
 * 
 * @param {SsEnvironment} env 
 */
function SsEval_incdec(env) {
    var first = this.Children[0];
    var ret = first.eval(env);

    if (this.Children.length == 2) {
        var token = this.Children[1].Token.Token;
        if (token == "++") {
            ret++;
        }
        else if (token == "--") {
            ret--;
        }

        var key = first.name(env);
        if (key != null) {
            env.Set(key, ret);
        }
    }

    return ret;
}


/**
 * 
 * @param {SsEnvironment} env 
 */
function SsEval_primary(env) {
    var first = this.Children[0];

    if (first instanceof SsASTLeaf) {
        var token = first.Token.Token;
        if (token == "(") {
            return this.Children[1].eval(env);
        }

        if (first.Token.Type == SsTermSymbols.INT) {
            return parseInt(token);
        }
        else if (first.Token.Type == SsTermSymbols.FLOAT) {
            return parseFloat(token);
        }
        //本当は string かをチェックしないと
        return token;

    }
    else {
        return first.eval(env);
    }

    return null;
}


/**
 * 
 * @param {SsEnvironment} env 
 */
function SsEval_variable(env) {
    var first = this.Children[0];

    if (first instanceof SsASTLeaf) {
        var token = first.Token.Token;

        var variable = env.Get(token);

        if (variable != null) {
            //関数呼び出し
            if (this.Children.length == 2) {
                if (this.Children[1].Name == "arg_list") {
                    var args = this.Children[1];
                    var arg = [];
                    for (var i = 1; i < args.Children.length; i += 2) {
                        arg.push(args.Children[i].eval(env));
                    }
                    return variable.apply(env, arg)
                }
            }
            else {
                return variable;
            }
        } else {
            //変数がない
        }

    }

    return null;
}


/**
 * 
 * @param {SsEnvironment} env 
 */
function SsEval_declare_var(env) {
    var first = this.Children[0];

    if (this.Children[1] instanceof SsASTLeaf) {
        var varName = this.Children[1].Token.Token;

        var init = null;
        if (this.Children.length == 4) {
            init = this.Children[3].eval(env);
        }

        env.Set(varName, init);

    }

    return null;
}


/**
 * 
 * @param {SsEnvironment} env 
 */
function SsEval_expr(env) {

    if (this.Children.length == 3) {
        //代入系だけ特別
        var op = this.Children[1].Token.Token;
        if (op == "=" ||
            op == "+=" ||
            op == "-=" ||
            op == "/=" ||
            op == "*=") {

            var key = this.Children[0].name(env);

            var value = env.Get(key);
            var right = this.Children[2].eval(env);
            switch (op) {
                case "*=":
                    {
                        right = value * right;
                        break;
                    }
                case "/=":
                    {
                        right = value / right;
                        break;
                    }
                case "+=":
                    {
                        right = value + right;
                        break;
                    }
                case "-=":
                    {
                        right = value - right;
                        break;
                    }
            }
            env.Set(key, right);
            return right;
        }
    }

    var value = this.Children[0].eval(env);

    if (this.Children.length > 2) {
        var op = this.Children[1].Token.Token;
        var right = this.Children[2].eval(env);
        switch (op) {
            case "*":
                {
                    return value * right;
                }
            case "/":
                {
                    return value / right;
                }
            case "%":
                {
                    return value % right;
                }
            case "+":
                {
                    return value + right;
                }
            case "-":
                {
                    return value - right;
                }

            case ">":
                {
                    return value > right;
                }
            case ">=":
                {
                    return value >= right;
                }
            case "<":
                {
                    return value < right;
                }
            case "<=":
                {
                    return value <= right;
                }
            case "==":
                {
                    return value == right;
                }
            case "!=":
                {
                    return value != right;
                }
            case "&&":
                {
                    return value && right;
                }
            case "||":
                {
                    return value || right;
                }
        }
    }

    return value;
}

SsEnvironment クラスは、実行環境を入れておくためのクラスで、とりあえずグローバル変数を入れておくためのオブジェクトを一つ持たせています。そして、各評価関数（eval）関数は引数に SsEnvironment のオブジェクトを渡していくようにしています。

eval 関数は、式であれば単純にその式の評価結果値を返すようにしており、上位の式はその値をもとに計算して、更に値を返す感じです。文は、とりあえず null を返しています。

作ってみて、微妙な実装だなぁと思ったため、パーサジェネレータの生成するコードのところでファクトリーを通してオブジェクトを生成するような仕組みや、シンボル名を見て生成する節のクラスを変えるといった方式にしようかと思います。

実行してみる

以下のコードで、src 変数内のソースコードを実行できます。今回、出力系がまったくなく、結果の確認ができなかったため、SsEnvironment のオブジェクト env には、一つだけ、画面出力用の関数 print を設定しました。これで、最低限出力はできるようにしました。

 var cParser = new SumireScriptParser(src);
    try {
        var results = cParser.Parse();
		
        //実行
        var env = new SsEnvironment();
        $("#console-box").empty();
        env.Set("print", function (text) {
            var lines = text.split("\n");
            for (var i = 0; i < lines.length; i++) {
                $("#console-box").append($(document.createElement("span")).text(lines[i]));
                if(i < lines.length-1)
                {
                    $("#console-box").append("<br>");
                }
            }
        });
        for (var i = 0; i < results.length; i++) {
            results[i].eval(env);
        }

    } catch (ex) {
        if (ex instanceof SsUnexpectedException) {
            alert("予期せぬトークンです\n" +
                "\"" + ex.Token.Token + "\" " + (ex.Token.S_Line + 1) + "行 " + (ex.Token.S_Ch + 1) + "列");
        }
        else {
            console.error(ex);
        }
    }

以下のコードを実行してみると、うまくいきました。JavaScript じゃないですよ。今回作った言語です。

var a  = 10;
for(var i = 0; i < 10; i++)
{
	if(i % 3 == 0) print("はい! ");
    print("hello world: " + (a + i) + "\n");
}

実行結果は以下のとおりです。

はい! hello world: 10
hello world: 11
hello world: 12
はい! hello world: 13
hello world: 14
hello world: 15
はい! hello world: 16
hello world: 17
hello world: 18
はい! hello world: 19

ちゃんと、(a+i) も計算されていますし、意図通り文字列も結合されています。いい感じです。

ちなみに、とりあえず動くものを作ってみたかっただけのため、宣言していない変数の使用とかそういうエラーは一切出ません。そのうち、中間コードの生成をやってみようと思っていますので、そのときにちゃんと考えます。

とにかく、ここまで来るとかなり楽しいです。

あっ、break とか continue とか return とかできない…

さて、ここまで 2 週間でできる ! スクリプト言語を中心に読み進めながら作って来たのですが、この実装ですと、break などの構文を追加しようとするとうまくいかないことに気が付きました。ただ、残念ながらこちらの本では脱出構文に対応していませんでした。

そこで、いい方法はないものかと、もう一冊の方を読み返してみると、対応はしていたのですが、評価関数の戻り値に設定して一つずつ返していくという実装になっていました。ん～と思いつつ、これしか無いようですので、この方法を採用しました。

eval 関数は必ず SsResult 型のオブジェクトを返すようにし、ブロックや for 文、while 文で相応の処理をするようにしました。将来を見越して、return 文の下準備もしてあります。

コード2: SsResult 型

/**
 * 戻り値の種類
 */
var SsResultType =
{
    "Normal": 1,
    "Return": 2,
    "Break": 3,
    "Continue": 4,
};

/**
 * 評価関数の戻り値
 * @param {*} value 
 */
var SsResult = function (value) {
    this.Type = SsResultType.Normal;
    this.Value = value;
};

コード3: ブロックと while 文の処理

/**
 * ブロックの処理関数
 * @param {SsEnvironment} env 
 */
function SsEval_block(env) {

    for (var i = 1; i < this.Children.length - 1; i++) {
        var ret = this.Children[i].eval(env);
        if (ret != null) {
            //脱出
            if (ret.Type == SsResultType.Return ||
                ret.Type == SsResultType.Continue ||
                ret.Type == SsResultType.Break) {
                return ret;
            }
        }
    }

    return new SsResult(null);
}

// ～～～～～～～～～～～～～～

/* while文 */
        else if (token == "while") {
            while (this.Children[2].eval(env).Value) {
                var res = this.Children[4].eval(env);
                if (res.Type == SsResultType.Return) {
                    return res;
                } else if (res.Type == SsResultType.Break) {
                    break;
                }
                //continueは流すとそのままcontinueになる
            }
        }

これで、break と continue がうまく動作するようになりました。goto の実装予定はないですし、break 、continue 、return 以外に（例外処理を除いて）こういった命令を実装予定ありませんので、ひとまずこれで良さそうです。ラベル付きの break とかも、もうちょっと判断を細かくすれば対応できそうです（作る気は無いですが）。

まとめ

最低限の動作までできました。次は、関数を実装しようと思います。ブロックスコープとかそのへんもやってみようと思います。

プログラミング言語をつくってみる②

実行関数を作る

実行してみる

あっ、break とか continue とか return とかできない…

まとめ

目次

アウトライン