Web備忘録 プログラミングを中心に技術的な事柄を忘れないように書き残します。

09 式の解析(識別子) [オリジナル言語インタプリタを作る]

09 式の解析(識別子) [オリジナル言語インタプリタを作る]
目次

式の構文解析に取り掛かる

これまでに文の解析、let文とreturn文についての構文解析を実装しました。これで Gorilla の実装における文は、基本的にこの2つのみです。ということで、ようやく式の解析に取り掛かります。

式の構文解析は、構文解析における本丸です。ここが一番厄介であり、面白い部分でもあります。

式の解析は一筋縄ではいかない

式の1つである四則演算による数式を考えます。

1 + 2 * 3

これはこれまで通りのやり方で単純に先読みするだけではうまくいきません。(1+2)*3 ではなく、1+(2*3)として計算する必要があるからです。つまり演算子の優先度を考慮するあります。

それから演算子の出現位置も考えなければなりません。

-1 - 1

上記の式は、(-1) - 1 と計算します。つまり最初のマイナス記号とあとのでは役割が異なります。前置演算子と中置演算子の違いです。前に来るか中間に来るか、あるいは後に来る後置演算子もあり得ます。

数式以外にも、識別子単体も式ですし、関数リテラルもifも式として扱います。とにかく様々な文脈を踏まえたうえで判断しなければうまく解析できません。

式文 AST の準備

式文は文字通り式からなる文です。1つの式をラップした文のことで、大抵のスクリプト言語だと、式文が有効です。

1 + 1;

このコードは Javascript だと有効です。しかしこのような式だけからなる文を許さない言語もあります。C#がまさにそうです。

Gorilla はスクリプト言語なので式文を用いて1つの式を1つの文として扱えるようにします。

ということで、まずは式文のASTを準備します。

Ast/Statements/ExpressionStatement.cs

using Gorilla.Lexing;

namespace Gorilla.Ast.Statements
{
    public class ExpressionStatement : IStatement
    {
        public Token Token { get; set; } // 式の最初のトークン
        public IExpression Expression { get; set; }

        public string ToCode() => this.Expression?.ToCode() ?? "";

        public string TokenLiteral() => this.Token.Literal;
    }
}

式のトークンプロパティは、最初のトークンです。Expressionはラップしている実際の式です。これで式文の定義は完了です。

Pratt構文解析器の実装

Prattパーサ – Wikipedia

構文解析の手法はいくつかの方法があります。いろいろと専門的な研究があるのですが、ここでは Pratt構文解析器 を実装していきます。Pratt構文解析器は、再帰下降構文解析の一種です。

Pratt構文解析器では、トークンの種類に応じて構文解析関数を関連付けます。トークンに遭遇する都度、適切な構文解析関数が呼び出されます。

トークンの種類ごとに最大2つの構文解析関数を関連付けます。トークンが前置で出現したか、中置で出現したかによって呼び分けられることになります。

最初はこの2種類の関数、前置構文解析関数(prefix parsing function) と 中置構文解析関数(infix parsing function) をそれぞれ型の別名として定義しておきます。

Parsing/Parser.cs


namespace Gorilla.Parsing
{
    using PrefixParseFn = Func<IExpression>;
    using InfixParseFn = Func<IExpression, IExpression>;

    // ..
}

どちらの関数も式の解析関数なので IExpression を返します。InfixParseFn は解析中の中置演算子の左側に来る式を引数として受け取る必要があります。PrefixParseFn は左側に何もないので引数が必要ありません。

意味がよくわからないかもですが、ひとまずこういうものとして定義しておき先に進みましょう。

これらの関数はトークンの種類に応じてそれぞれ定義される必要があります。ということでトークンの種類と解析関数の辞書をプロパティで管理しておきます。

public class Parser
{
    // ..
    public Dictionary<TokenType, PrefixParseFn> PrefixParseFns { get; set; }
    public Dictionary<TokenType, InfixParseFn> InfixParseFns { get; set; }
    // ..
}

これでこの解析器はトークンの種類がわかれば、適切な構文解析関数を呼び出せるようになりました。

識別子

もっとも簡単な式である識別子の解析を実装します。

識別子は束縛されている値を評価する式です。

まずはテストを書きます。

ParserTest.cs

[TestMethod]
public void TestIdentifierExpression1()
{
    var input = @"foobar;";

    var lexer = new Lexer(input);
    var parser = new Parser(lexer);
    var root = parser.ParseProgram();
    this._CheckParserErrors(parser);

    Assert.AreEqual(
        root.Statements.Count, 1,
        "Root.Statementsの数が間違っています。"
    );

    var statement = root.Statements[0] as ExpressionStatement;
    if (statement == null)
    {
        Assert.Fail("statement が ExpressionStatement ではありません。");
    }

    var ident = statement.Expression as Identifier;
    if (ident == null)
    {
        Assert.Fail("Expression が Identifier ではありません。");
    }
    if (ident.Value != "foobar")
    {
        Assert.Fail("ident.Value が foobar ではありません。");
    }
    if (ident.TokenLiteral() != "foobar")
    {
        Assert.Fail("ident.TokenLiteral が foobar ではありません。");
    }
}

行数は多いですがやってることはほかのテストとあまり変わりません。foobar; を構文解析し、正しく式のASTが生成できているかを確認しています。

テストは当然エラーです。ParseExpressionStatement() の実装がないため、式文を解析することができていません。

テストを通すために実装をしていきましょう。

Parsing/Parser.cs

public class Parser
{
    // ..
    public IStatement ParseStatement()
    {
        switch (this.CurrentToken.Type)
        {
            case TokenType.LET:
                return this.ParseLetStatement();
            case TokenType.RETURN:
                return this.ParseReturnStatement();
            default:
                return ParseExpressionStatement();
        }
    }
    // ..
    public IExpression ParseExpression(Precedence precedence)
    {
        return null;
    }
    // ..
    public ExpressionStatement ParseExpressionStatement()
    {
        var statement = new ExpressionStatement();
        statement.Token = this.CurrentToken;

        statement.Expression = this.ParseExpression(Precedence.LOWEST);

        // セミコロンを読み飛ばす(省略可能)
        if (this.NextToken.Type == TokenType.SEMICOLON) this.ReadToken();

        return statement;
    }
}

public enum Precedence
{
    LOWEST = 1,
    EQUALS,      // ==
    LESSGREATER, // >, <
    SUM,         // +
    PRODUCT,     // *
    PREFIX,      // -x, !x
    CALL,        // myFunction(x)
}

文の解析関数において、let, return 以外のトークンが来る場合にはすべて式文として解析するようにします。したがって default で式文解析関数 ParseExpressionStatement() を呼びます。

式文の解析は単純で現在のトークンをセットし、式の解析関数 ParseExpression() を呼びます。これは以前側だけ定義していたかもしれませんが、引数に優先度を追加しています。

Gorilla プログラミング言語における優先度は列挙体で定義することにしました。順序が重要なので正しく定義しましょう。今回は1から連番で順位を定義していますが、正しく比較できるのであれば値は何でも構いません。

では式の解析関数 ParseExpression() の中身の実装を行います。

public class Parser 
{
    // ..
    public IExpression ParseExpression(Precedence precedence)
    {
        this.PrefixParseFns.TryGetValue(this.CurrentToken.Type, out var prefix);
        if (prefix == null) return null;

        var leftExpression = prefix();
        return leftExpression;
    }   
    // ..
}

これは最初のバージョンです。まだ全然要件に満たない実装ですが、ひとまず識別子単体からなる式についてはこれで事足ります。

このメソッドでは現在のトークンの種類に関連つけられた解析関数を取り出します。

関連する解析関数が存在しなければ、解析結果として Null を返します。今のところ PrefixParseFns の中身が空なので常に Null が返ります。

関連する解析関数が存在すればそれを実行し、得られる式のASTを返します。

Parser のコンストラクタでトークンの種類と解析関数の組み合わせを登録して、正しく動作するようにしましょう。

public class Parser 
{
    // ..
    public Parser(Lexer lexer)
    {
        this.Lexer = lexer;

        // 2つ分のトークンを読み込んでセットしておく
        this.CurrentToken = this.Lexer.NextToken();
        this.NextToken = this.Lexer.NextToken();

        // トークンの種類と解析関数を関連付ける
        this.RegisterPrefixParseFns();
    }

    private void RegisterPrefixParseFns()
    {
        this.PrefixParseFns = new Dictionary<TokenType, PrefixParseFn>();
        this.PrefixParseFns.Add(TokenType.IDENT, this.ParseIdentifier);
    }
    // ..
    public IExpression ParseIdentifier()
    {
        return new Identifier(this.CurrentToken, this.CurrentToken.Literal);
    }
    // ..
}

まずは識別子の構文解析関数 ParseIdentifier() を用意します。これは現在の識別子トークンに対応する識別子のASTを生成して返します。これをコンストラクタ内で TokenType.IDENT に紐づけて登録しておきます。

こうすることで先ほど定義した ParseExpression() 内で関連する解析関数として呼び出されるようになります。

実装が完了するとテストが通るようになります。

テスト名:    TestIdentifierExpression1
テストの完全名:    UnitTestProject.ParserTest.TestIdentifierExpression1
テスト ソース:    E:\work\cs\Gorilla\UnitTestProject\ParserTest.cs : 行 103
テスト成果:    成功
テスト継続時間:    0:00:00.0025897

おめでとうございます！ これで最初の式の解析、識別子単体からなる式についての構文解析処理の実装が完了しました。

説明文が少し長くなりましたが、これでひと段落です。

ここまでのソース

mntm0/Gorilla at bf0e0130cd43a94b4118c1ef711749151f81e5da

整数リテラル

続けてもう1つだけ処理を追加します。整数リテラルの解析処理についてです。識別子が式であるように、整数リテラルもまた式なのです。

もちろん演算子を使わないリテラル値単体からなる式(123;のような式)の解析です。

識別子の解析とやるべきことは同じです。ということで必要な処理を追加していきましょう。

やることは以下の通りです。

  1. ASTの定義
  2. テストの作成
  3. 解析関数の定義

順番に行きましょう。

AST の定義

Ast/Expressions/IntegerLiteral.cs

using Gorilla.Lexing;

namespace Gorilla.Ast.Expressions
{
    public class IntegerLiteral : IExpression
    {
        public Token Token { get; set; }
        public int Value { get; set; }

        public string ToCode() => this.Token.Literal;
        public string TokenLiteral() => this.Token.Literal;
    }
}

IntegerLiteral は整数リテラルを構成するASTです。整数リテラルに対応するトークンとリテラルが表現する値を整数型で保持します。

式なので IExpression を実装するのをお忘れなく。ToCode() も TokenLiteral() もトークンのリテラル文字列を返してやるだけです。

このASTを返すのが解析関数の役割です。その前にテストを作成します。

テストの作成

[TestMethod]
public void TestIntegerLiteralExpression1()
{
    var input = @"123;";

    var lexer = new Lexer(input);
    var parser = new Parser(lexer);
    var root = parser.ParseProgram();
    this._CheckParserErrors(parser);

    Assert.AreEqual(
        root.Statements.Count, 1,
        "Root.Statementsの数が間違っています。"
    );

    var statement = root.Statements[0] as ExpressionStatement;
    if (statement == null)
    {
        Assert.Fail("statement が ExpressionStatement ではありません。");
    }

    var integerLiteral = statement.Expression as IntegerLiteral;
    if (integerLiteral == null)
    {
        Assert.Fail("Expression が IntegerLiteral ではありません。");
    }
    if (integerLiteral.Value != 123)
    {
        Assert.Fail("integerLiteral.Value が 123 ではありません。");
    }
    if (integerLiteral.TokenLiteral() != "123")
    {
        Assert.Fail("integerLiteral.TokenLiteral が 123 ではありません。");
    }
}

テストの内容は識別子の時と変わりません。識別子の名前ではなく整数値をテストしています。

念のためテストを動かしてみても、もちろん動きません。

ParseIntegerLiteral() の実装

整数リテラル式の解析関数 ParseIntegerLiteral() を実装していきます。

Parsing/Parser.cs

public class Parser
{
    private void RegisterPrefixParseFns()
    {
        this.PrefixParseFns = new Dictionary<TokenType, PrefixParseFn>();
        this.PrefixParseFns.Add(TokenType.IDENT, this.ParseIdentifier);
        this.PrefixParseFns.Add(TokenType.INT, this.ParseIntegerLiteral);
    }
    // ..
    public IExpression ParseIntegerLiteral()
    {
        // リテラルを整数値に変換
        if (int.TryParse(this.CurrentToken.Literal, out int result))
        {
            return new IntegerLiteral()
            {
                Token = this.CurrentToken,
                Value = result,
            };
        }

        // 型変換失敗時
        var message = $"{this.CurrentToken.Literal} を integer に変換できません。";
        this.Errors.Add(message);
        return null;
    }
}

識別子のときは単純に識別子のASTを生成していましたが、整数リテラルの場合はそのリテラル値がint型に変換可能かどうかをここでチェックしています。

int型に変換できなければエラーとしてメッセージを追加しています。

あとは TokenType.INT のときにこの関数を呼び出せるように関連付ければ完成です。これでいけるはず。

テストを動かしてみましょう。

テスト名:    TestIdentifierExpression1
テストの完全名:    UnitTestProject.ParserTest.TestIdentifierExpression1
テスト ソース:    E:\work\cs\Gorilla\UnitTestProject\ParserTest.cs : 行 103
テスト成果:    成功
テスト継続時間:    0:00:00.0026149

おめでとうございます。これで完成です。

長くなってきたのでここで終わります。

まとめ

ここまでのソース

mntm0/Gorilla at ce32e23050877ff22a75b3b19339d9a4a9ba8e17

トークンの種類について前置に関連つけられた構文解析関数を使って解析処理を呼び出すようにしました。まだ処理の全体がつかめずにいるかもしれませんが、気にせず実装を続けましょう。実装が進めばこの解析方法についての仕組みが見えてくるはずです。

次回は前置演算子 ! と - の解析を実装します。Gorilla プログラミングげんごには、この2種類の前置演算子が存在します。

以上。

開発いろいろカテゴリの最新記事