13 構文解析器の拡張(式を括弧でグループ化する) [オリジナル言語インタプリタを作る]

式を括弧でグループ化する

式を括弧でくくって演算の優先度を調整することができます。一般的な計算式と同じ考えです。

例えば 1 + 2 * 3 この式は (1 + (2 * 3)) となります。

括弧を付けた式 (1 + 2) * 3 は ((1 + 2) * 2) とならないといけません。括弧内の式はより高い優先度で計算されます。

この違いを式の構文解析処理に実装します。優先度の実装は思っているほど難しくありません。というよりもASTを新しく作成することなく処理を実装できてしまいます。

素晴らしい … 。

テストを作成する

グループ化された式のテストを作成しましょう。新しいASTが不要なのでテストから入ります。

とはいえ、既存のテスト関数にテストケースを追加するだけです。

[TestMethod]
public void TestOperatorPrecedenceParsing()
{
    var tests = new[]
    {
        // ..
        ("(1 + 2) * 3", "((1 + 2) * 3)"),
        ("1 + (2 - 3)", "(1 + (2 - 3))"),
        ("-(1 + 2)", "(-(1 + 2))"),
        ("!(true == true)", "(!(true == true))"),
        ("1 + (2 - 3) * 4", "(1 + ((2 - 3) * 4))"),
        ("(1 + -(2 + 3)) * 4", "((1 + (-(2 + 3))) * 4)"),
    };
    // ..
}

括弧を使って計算順位を調整しています。その結果のASTが括弧無しの時と別の結果になります。

括弧が入れ子になるパターンもテストしておきましょう。

さてこの状態でテストするとどうなるでしょうか。

テスト名:    TestOperatorPrecedenceParsing
テストの完全名:    UnitTestProject.ParserTest.TestOperatorPrecedenceParsing
テスト ソース:    E:\work\cs\Gorilla\UnitTestProject\ParserTest.cs : 行 239
テスト成果:    失敗
テスト継続時間:    0:00:00.043795

結果  のスタック トレース:    
at UnitTestProject.ParserTest._CheckParserErrors(Parser parser) in E:\work\cs\Gorilla\UnitTestProject\ParserTest.cs:line 91
   at UnitTestProject.ParserTest.TestOperatorPrecedenceParsing() in E:\work\cs\Gorilla\UnitTestProject\ParserTest.cs:line 267
結果  のメッセージ:    Assert.Fail failed. 
LPAREN に関連付けられた Prefix Parse Function が存在しません。
RPAREN に関連付けられた Prefix Parse Function が存在しません。
ASTERISK に関連付けられた Prefix Parse Function が存在しません。

括弧 "(" に関連つけられた処理が登録されていないと言われています。

ParseGroupedExpression()

テストを通すために処理を追加します。

Parsing/Parser.cs

public class Parser
{
    // ..
    private void RegisterPrefixParseFns()
    {
        // ..
        this.PrefixParseFns.Add(TokenType.LPAREN, this.ParseGroupedExpression);
    }
    // ..
    public IExpression ParseGroupedExpression()
    {
        // "(" を読み飛ばす
        this.ReadToken();

        // 括弧内の式を解析する
        var expression = this.ParseExpression(Precedence.LOWEST);

        // 閉じ括弧 ")" がないとエラーになる
        if (!this.ExpectPeek(TokenType.RPAREN)) return null;

        return expression;
    }
}

これだけです。括弧 "(" が来たらそれ以降を1つの式として解析します。解析後は ")" が現在のトークンとなるので、これを読み飛ばします。閉じ括弧 ")" がなければ解析エラーです。

括弧で入れ子になった式も再帰的に呼び出されるのでうまく解析できます。どのようなからくりになっているかはソースコードを追えば見えてきます。

トークンに関連付けられた解析関数を呼ぶという仕組みによって、期待通りにくくられた形で出力されるようになりました。何も目新しい実装をしていないのにも関わらず！

まとめ

ここまでのソース

mntm0/Gorilla at bf38e0c098e103813319974a16281c566de306f8

短いですが今回はこれで終了です。今回の実装で括弧でグループ化された式の解析もできるようになりました。

次回はif式の実装です。

以上。