Java 言語でつくるインタプリタ〜パーサ#2〜

「Go 言語でつくるインタプリタ」では、Monkey という小さな言語のインタプリタを Go で実装する過程が書かれています。

あくまで教育目的として、字句解析〜構文解析〜評価までをシンプルな実装で丁寧に解説しています。

Go言語でつくるインタプリタ

作者:Thorsten Ball
出版社/メーカー: オライリージャパン
発売日: 2018/06/16
メディア: 単行本（ソフトカバー）

ここでは、Go で写経するだけなのも面白みが無いので、「Go 言語でつくるインタプリタ」の流れを Java に変換しつつ紹介してみます。

前回

blog1.mammb.com

までで文の構文解析を実装したので、続いて式の構文解析に入っていきます。

式の構文解析

式の構文解析は単純ではありません。演算子ごとの優先順位を考慮しなければならないためです。

5 * 5 + 10 と 5 * (5 + 10) では結果が違いますし、-5 - 10 といった、前置演算子もあります(Monkey 言語では後置演算子は扱いません)。

さらに、add(add(2, 3), add(5, 10)) のような式もあります。

単純な例から少しづつ式の構文解析を実装していきましょう。

式文型の追加

x + 10; や foobar; といった、式から成る文を扱うため、以下の型を追加しておきましょう。

public class ExpressionStatement implements Statement {

    public final Token token;
    public final Expression expression;

    public ExpressionStatement(Token token, Expression expression) {
        this.token = token;
        this.expression = expression;
    }

    @Override
    public String tokenLiteral() {
        return token.literal;
    }

    @Override
    public String toString() {
        return Objects.isNull(expression) ? "" : expression.toString();
    }
}

単純に式をラップする Statement です。これを「式文」と呼びましょう。

識別子のパース

最初に、 foobar; のような識別子のみから成る文をパースすることを考えます。

テストケースは以下とします。

    @Test
    public void testIdentifierExpression() {
        String input = "foobar;";
        AstNode astNode = new Parser(new Lexer(input)).parse();

        assertThat(astNode.getStatements().get(0), is(instanceOf(ExpressionStatement.class)));
        ExpressionStatement s0 = (ExpressionStatement) astNode.getStatements().get(0);
        assertThat(s0.token.type, is(TokenType.IDENT));
        assertThat(s0.expression.tokenLiteral(), is("foobar"));
    }

テストを通す実装を考えていきます。

最初に、parseStatement() の中に式文を扱うメソッド呼び出しを追加します。

public class Parser {

    private Statement parseStatement()  {
        switch (curToken.type) {
        case LET:
            return parseLetStatement();
        case RETURN:
            return parseReturnStatement();
        default:
            return return parseExpressionStatement(); // 追加
        }
    }
}

Monkey言語の文は、「let文」「return文」だけで、それ以外はすべて「式文」となります。
以下のように3種類の Statement が生成されます。

let 文：LetStatement
return 文：ReturnStatement
その他の式文：ExpressionStatement

parseExpressionStatement() の中身は以下のようになります。

public class Parser {

    private ExpressionStatement parseExpressionStatement() {
        final Token token = curToken;
        final Expression expression = parseExpression();
        if (peekTokenIs(TokenType.SEMIC)) {
            nextToken();
        }
        return new ExpressionStatement(token, expression);
    }
}

parseExpression() で式を解析し、ExpressionStatement インスタンスを生成して返却する実装になります。

さて、式のパースは、トークンタイプに紐づくパーサを Map で管理することにします。

パーサは PrefixParser インターフェースを実装するものとして、以下のようになります。

public class Parser {

    private final Map<TokenType, PrefixParser> prefixParsers;

    public Parser(Lexer lexer) {
        this.prefixParsers = new HashMap<>();
        this.prefixParsers.put(TokenType.IDENT, identifierParser());
    }

    private Expression parseExpression() {
        return prefixParsers.containsKey(curToken.type)
                ? prefixParsers.get(curToken.type).parse()
                : null;
    }
}

今回の例では識別子を扱うので、TokenType.IDENT に紐づけた identifierParser を用意すれば良さそうです。

PrefixParser インターフェースを用意し、識別子用のパーサを取得する identifierParser() を用意します。

public class Parser {

    interface PrefixParser {
        Expression parse();
    }

    private PrefixParser identifierParser() {
        return () -> new Identifier(curToken, curToken.literal);
    }
}

これで識別子のパースは完了で、テストもグリーンとなります。簡単ですね。

整数リテラル

次に 5; のような整数リテラルを扱います。

以下のようなテストケースを考えます。

    @Test
    public void testIntegerLiteralExpression() {

        String input = "5;";
        AstNode astNode = new Parser(new Lexer(input)).parse();

        assertThat(astNode.getStatements().get(0), is(instanceOf(ExpressionStatement.class)));
        ExpressionStatement e0 = (ExpressionStatement) astNode.getStatements().get(0);
        assertThat(e0.token.type, is(TokenType.INT));
        assertThat(e0.expression.tokenLiteral(), is("5"));
    }

TokenType.INT に紐付けるパーサを定義します。

public class Parser {

    public Parser(Lexer lexer) {
        // ...
        this.prefixParsers.put(TokenType.INT,   integerLiteralParser()); // 追加
    }

    private PrefixParser integerLiteralParser() {
        return () -> {
            try {
                Integer val = Integer.parseInt(curToken.literal);
                return new IntegerLiteral(curToken, val);
            } catch (NumberFormatException e) {
                errors.add(String.format("could not parse %q as integer", curToken.literal));
            }
            return null;
        };
    }
}

対応はこれだけで完了です。

前置演算子

前置演算子は「!」と「-」で、-5;, !foobar;, 5 + -10; のように使われます。

<prefix operator><expression>; のような形になります。

前置演算の式を表現する PrefixExpression という型を定義します。

public class PrefixExpression implements Expression {

    public final Token token; // Prefix token(!, -, ...).
    public final String operator;
    public final Expression right;

    public PrefixExpression(Token token, String operator, Expression right) {
        this.token = token;
        this.operator = operator;
        this.right = right;
    }

    @Override
    public String tokenLiteral() {
        return null;
    }

    @Override
    public String toString() {
        return "(" + operator + right.toString() + ')';
    }
}

前置演算子の operator と、それに続く式で構成されます。

テストケースは以下のようにしておきます。

    @Test
    public void testParsingPrefixExpressions() {

        String input = "!5;" + "\n" + "-15;";

        AstNode astNode = new Parser(new Lexer(input)).parse();

        assertThat(astNode.getStatements().get(0), is(instanceOf(ExpressionStatement.class)));
        ExpressionStatement s0 = (ExpressionStatement) astNode.getStatements().get(0);
        assertThat(s0.expression, is(instanceOf(PrefixExpression.class)));
        PrefixExpression p0 = (PrefixExpression) s0.expression;
        assertThat(p0.operator, is("!"));
        assertThat(p0.right.tokenLiteral(), is("5"));

        assertThat(astNode.getStatements().get(1), is(instanceOf(ExpressionStatement.class)));
        ExpressionStatement s1 = (ExpressionStatement) astNode.getStatements().get(1);
        assertThat(s1.expression, is(instanceOf(PrefixExpression.class)));
        PrefixExpression p1 = (PrefixExpression) s1.expression;
        assertThat(p1.operator, is("-"));
        assertThat(p1.right.tokenLiteral(), is("15"));
    }

パーサの実装は今までの流れに沿い、以下のようになります。

public class Parser {
    public Parser(Lexer lexer) {
        // ...
        this.prefixParsers.put(TokenType.BANG,  prefixExpressionParser());
        this.prefixParsers.put(TokenType.MINUS, prefixExpressionParser());
    }
    
    private PrefixParser prefixExpressionParser() {
        return () -> {
            Token token = curToken;
            nextToken();
            final Expression right = parseExpression();
            return new PrefixExpression(token, token.literal, right);
        };
    }
}

ここまでは、前置演算子の処理を追加してきました。いずれも、トークン毎にパーサを紐づけて構文解析が実現できました。
続いて、中置演算子について見ていきます。

中置演算子

中置演算子は 5 + 5;, 5 > 5;, 5 == 5; のようなもので、<expression> <infix operator> <expression> という形になります。

前後にオペランドがあり、これらの式は「二項演算式」と呼びます。

前後の式にはどのような形の式でも置くことができます。

これまでのように型を定義していきましょう。

public class InfixExpression implements Expression {

    public final Token token;
    public final Expression left;
    public final String operator;
    public final Expression right;

    public InfixExpression(Token token, Expression left, String operator, Expression right) {
        this.token = token;
        this.left = left;
        this.operator = operator;
        this.right = right;
    }

    @Override
    public String tokenLiteral() {
        return null;
    }

    @Override
    public String toString() {
        return "(" + left.toString() + " " + operator + " " + right.toString() + ")";
    }
}

特別なことは何もなく、<expression> <infix operator> <expression> という形を表現するものとなります。

ではテストケースを作成していきます。

テーブルドリブンにしたくなってきたので、テストは JUnit5 に変えます。ついでに assertj にしておきます。

    @ParameterizedTest
    @CsvSource({
            "5 + 5;, 5, +, 5",
            "5 - 5;, 5, -, 5",
            "5 * 5;, 5, *, 5",
            "5 / 5;, 5, /, 5",
            "5 > 5;, 5, >, 5",
            "5 < 5;, 5, <, 5",
            "5 == 5;, 5, ==, 5",
            "5 != 5;, 5, !=, 5",
    })
    void testParsingInfixExpressions(String input, Integer left, String operator, Integer right) {

        AstNode astNode = new Parser(new Lexer(input)).parse();

        assertThat(astNode.getStatements().get(0)).isInstanceOf(ExpressionStatement.class);

        ExpressionStatement s0 = (ExpressionStatement) astNode.getStatements().get(0);

        assertThat(s0.expression).isInstanceOf(InfixExpression.class);
        InfixExpression e0 = (InfixExpression) s0.expression;
        assertThat(((IntegerLiteral) e0.left).value).isEqualTo(left);
        assertThat(e0.operator).isEqualTo(operator);
        assertThat(((IntegerLiteral)e0.right).value).isEqualTo(right);

    }

ちなみに Gradle の場合、依存は以下のようになります。

dependencies {
    testImplementation 'org.junit.jupiter:junit-jupiter-api:5.5.0'
    testRuntimeOnly 'org.junit.jupiter:junit-jupiter-engine:5.5.0'
    testImplementation 'org.junit.jupiter:junit-jupiter-params:5.5.0'
    testImplementation 'org.assertj:assertj-core:3.12.2'
}

test {
    useJUnitPlatform()
}

パーサの実装に入る前に、演算子の優先順位を定義付けられるようにしておきましょう。

優先順位を定義する以下の enum を作成します。

public enum Precedence {

    LOWEST,
    EQUALS(TokenType.EQ, TokenType.NOT_EQ),
    LG(TokenType.LT, TokenType.GT),
    SUM(TokenType.PLUS, TokenType.MINUS),
    PROD(TokenType.ASTER, TokenType.SLASH),
    PREFIX,
    CALL(TokenType.LPAREN),
    ;

    private final List<TokenType> tokenTypes;

    Precedence(TokenType... tokenTypes) {
        this.tokenTypes = Arrays.asList(tokenTypes);
    }

    public static Precedence of(TokenType type) {
        return Arrays.stream(Precedence.values())
                .filter(p -> p.tokenTypes.contains(type)).findFirst().orElse(LOWEST);
    }

    public boolean isGreaterThan(Precedence that) {
        return this.compareTo(that) > 0;
    }

    public boolean isLessThan(Precedence that) {
        return this.compareTo(that) < 0;
    }
}

enum の ordinal 、つまり宣言順序によって優先度を表現します。
最初に定義したものが優先度が低く、後に定義したものが優先度が高くなります。
enum は Comparable なので compareTo で直接比較できるので、優先度の定義にちょうどよいです。
ここでは、優先順に TokenType を紐づけて定義しました。 TokenType を紐づけているので、トークン間の優先順位がわかるようになっています。

では、パーサの実装に入りましょう。

前置演算子で行ったように、中置演算子用の Map を追加して TokenType を紐づけます。

public class Parser {

    private final Map<TokenType, InfixParser> infixParsers;

    public Parser(Lexer lexer) {
        this.infixParsers = new HashMap<>();
        this.infixParsers.put(TokenType.PLUS,   parseInfixExpression());
        this.infixParsers.put(TokenType.MINUS,  parseInfixExpression());
        this.infixParsers.put(TokenType.SLASH,  parseInfixExpression());
        this.infixParsers.put(TokenType.ASTER,  parseInfixExpression());
        this.infixParsers.put(TokenType.EQ,     parseInfixExpression());
        this.infixParsers.put(TokenType.NOT_EQ, parseInfixExpression());
        this.infixParsers.put(TokenType.LT,     parseInfixExpression());
        this.infixParsers.put(TokenType.GT,     parseInfixExpression());
    }
}

前置演算子用のものとは別で infixParsers という Map に定義しました。

InfixParser は、結合する左側の式を引数に取り、結果の式Expression を生成するインターフェースとしています。

public class Parser {
  
    interface InfixParser {
        Expression parse(Expression left);
    }
  
    private InfixParser parseInfixExpression() {
        return left -> {
            Token token = curToken;
            String operator = curToken.literal;
            Precedence precedence = Precedence.of(token.type);
            nextToken();
            Expression right = parseExpression(precedence);
            return new InfixExpression(token, left, operator, right);
        };
    }
}

parseExpression を以下のように変更します。

public class Parser {
    private Expression parseExpression(Precedence precedence) {

        Expression leftExp = prefixParsers.containsKey(curToken.type)
                ? prefixParsers.get(curToken.type).parse()
                : null;

        while (!peekTokenIs(TokenType.SEMIC) &&
                     precedence.isLessThan(Precedence.of(peekToken.type))) {
            if (infixParsers.containsKey(peekToken.type)) {
                InfixParser infix = infixParsers.get(peekToken.type);
                nextToken();
                leftExp = infix.parse(leftExp);

            } else {
                return leftExp;
            }
        }

        return leftExp;
    }
}

式の優先度が、続くトークンの優先度より低ければ、再帰的に式の解析を行っていく実装となります。

parseExpression() に引数を追加したので、既存の以下の箇所を変更しておきます。

public class Parser {
    private LetStatement parseLetStatement()  {

        // ...
        // Expression value = new IntegerLiteral(curToken, Integer.parseInt(curToken.literal));
        Expression value = parseExpression(LOWEST);
        // ...
    }
    
    private ReturnStatement parseReturnStatement() {
        // ...
        //Expression value = new IntegerLiteral(curToken, Integer.parseInt(curToken.literal));
        Expression value = parseExpression(Precedence.LOWEST);
        // ...
    }
  
    private PrefixParser prefixExpressionParser() {
        return () -> {
            // ...
            // final Expression right = parseExpression();
            final Expression right = parseExpression(Precedence.PREFIX);
            // ...
        };
    }
}

既存分は、固定定期に整数リテラルと仮定していましたが、これで式の解析が再帰的に行えるようになります。

テストの追加

今までの式のパースにより、優先順位が正しく扱えるかをテストしておきましょう。

    @ParameterizedTest
    @CsvSource({
            "-a * b, ((-a) * b)",
            "!-a, (!(-a))",
            "a + b + c, ((a + b) + c)",
            "a + b - c, ((a + b) - c)",
            "a * b * c, ((a * b) * c)",
            "a * b / c, ((a * b) / c)",
            "a + b / c, (a + (b / c))",
            "a + b * c + d / e - f, (((a + (b * c)) + (d / e)) - f)",
            "3 + 4; -5 * 5, (3 + 4)((-5) * 5)",
            "5 > 4 == 3 < 4, ((5 > 4) == (3 < 4))",
            "5 < 4 != 3 > 4, ((5 < 4) != (3 > 4))",
            "3 + 4 * 5 == 3 * 1 + 4 * 5, ((3 + (4 * 5)) == ((3 * 1) + (4 * 5)))",
    })
    void testOperatorPrecedenceParsing(String input, String expected) {
        AstNode astNode = new Parser(new Lexer(input)).parse();
        assertThat(astNode.toString()).isEqualTo(expected);
    }

私達のASTノードは、toString() で優先度に応じて ( ) で括るようにしたので、ASTの文字表現で正しく優先順位付けされたかどうかを見ることができます。

まとめ

今回は、式のパースを優先順位を考慮したものにすることができました。
ここでの構文解析は、Pratt 構文解析と呼ばれるアルゴリズムによるもので、実装をさらっと見ただけだと挙動がわかりにくいと思います。
「Go 言語でつくるインタプリタ」の中では、このアルゴリズムについて詳細に説明しているので、興味のある方は原本を参照いただくと良いと思います。
今回のソースコードは中途半端なので、次回、パーサ完成後の記事に載せます。

blog1.mammb.com