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

Java

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

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


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

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

  • 作者:Thorsten Ball
  • 発売日: 2018/06/16
  • メディア: 単行本（ソフトカバー）


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


前回 blog1.mammb.com までで文の構文解析を実装したので、続いて式の構文解析に入っていきます。



構文解析器の拡張

前回は、識別子, 整数リテラル, 前置演算子, 中置演算子 のパース実装までできました。

ここでは、残りのパース実装を行い、構文解析器を完成させていきます。



真偽値リテラル

真偽値リテラルは true; のようなリテラルです。


いつもと同様に、BooleanLiteral 型を定義していきます。

public class BooleanLiteral implements Expression {
    
    public final Token token;
    prublic final Boolean value;

    public BooleanLiteral(Token token, Boolean value) {
        this.token = token;
        this.value = value;
    }

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

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

単純に Boolean を持つだけの式として定義しました。


パーサの実装も簡単で、以下のようになります。

public class Parser {
    public Parser(Lexer lexer) {
        this.prefixParsers = new HashMap<>();
        // ...
        this.prefixParsers.put(TokenType.TRUE, parseBoolean());  // 追加
        this.prefixParsers.put(TokenType.FALSE, parseBoolean()); // 追加
    }
    
    private PrefixParser parseBoolean() {
        return () -> new BooleanLiteral(curToken, curTokenIs(TokenType.TRUE));
    }
}


テストは以下のようになります。

    @ParameterizedTest
    @CsvSource({
            "true, true",
            "false, false",
            "3 > 5 == false, ((3 > 5) == false)",
            "3 < 5 == true, ((3 < 5) == true)",
    })
    void testBooleanOperatorPrecedenceParsing(String input, String expected) {
        AstNode astNode = new Parser(new Lexer(input)).parse();
        assertThat(astNode.toString()).isEqualTo(expected);
    }

特に難しいことはありません。

次に進みましょう。



グループ化された式

今まで扱ってきた式は、演算子の優先順位を考慮しましたが、式は ( ) で結合順序を変更することができます。

(5 + 5) * 2; のような式は、15 ではなく、20 にならなくてはなりません。


テストを先に書いておきましょう。

    @ParameterizedTest
    @CsvSource({
            "1 + (2 + 3) + 4, ((1 + (2 + 3)) + 4)",
            "(5 + 5) * 2, ((5 + 5) * 2)",
            "2 / (5 + 5), (2 / (5 + 5))",
            "-(5 + 5), (-(5 + 5))",
            "!(true == true), (!(true == true))",
    })
    void testParenOperatorPrecedenceParsing(String input, String expected) {
        AstNode astNode = new Parser(new Lexer(input)).parse();
        assertThat(astNode.toString()).isEqualTo(expected);
    }

( ) で結合順序が変わることをテストしています。


Pratt 構文解析の実装でほとんど出来上がっているので、TokenType.LPAREN に対応するパーサを登録すれば作業は完了です。

public class Parser {
    public Parser(Lexer lexer) {
        this.prefixParsers.put(TokenType.LPAREN, parseGroupedExpression()); // 追加
    }
  
    private PrefixParser  parseGroupedExpression() {
        return () -> {
            nextToken();
            Expression exp = parseExpression(Precedence.LOWEST);
            if (!expectPeek(TokenType.RPAREN)) {
                return null; 
            }
            return exp;
        };
    }
}

これで、テストはグリーンになります。



if 式

Monkey 言語では、if は値を返す式となります。

よくある条件分岐があり、

if (x > y) { 
    return x;
}

以下のように値を返すこともできます。

let foobar = if (x > y) { x } else { y };


if式は if (<condition>) <consequence> else <alternative> という構成になります。



最初に <consequence> や <alternative> の内容を表現する BlockStatement を定義します。

public class BlockStatement implements Statement {

    public final Token token;
    public final List<Statement> statements;

    public BlockStatement(Token token, List<Statement> statements) {
        this.token = token;
        this.statements = Collections.unmodifiableList(statements);
    }

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

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        statements.forEach(sb::append);
        return sb.toString();
    }
}

BlockStatement はいくつかの文で構成されます。


この BlockStatement を使い、if 式は以下のように表現できます。

public class IfExpression implements Expression {

    public final Token token;
    public final Expression condition;
    public final BlockStatement consequence;
    public final Optional<BlockStatement> alternative;

    public IfExpression(Token token, Expression condition, BlockStatement consequence, BlockStatement alternative) {
        this.token = token;
        this.condition = condition;
        this.consequence = consequence;
        this.alternative = Optional.ofNullable(alternative);
    }

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

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("if");
        sb.append(condition.toString());
        sb.append(" ");
        sb.append(consequence.toString());
        alternative.ifPresent(bs -> sb.append("else " + bs.toString()));
        return sb.toString();
    }
}


IfExpression のパーサのためにテストケースを作成しておきましょう。

    @Test
    void testIfExpression() {
        String input = "if (x < y) { x } else { y }";
        AstNode astNode = new Parser(new Lexer(input)).parse();

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

        assertThat(es.expression).isInstanceOf(IfExpression.class);
        IfExpression e = (IfExpression) es.expression;

        assertThat(e.condition).isInstanceOf(InfixExpression.class);
        InfixExpression condition = (InfixExpression) e.condition;
        assertThat(condition.toString()).isEqualTo("(x < y)");

        assertThat(e.consequence.toString()).isEqualTo("x");
        assertThat(e.alternative.get().toString()).isEqualTo("y");
    }



ではパーサの実装に取り掛かります。


最初に BlockStatement のパース処理を実装します。

public class Parser {
  
    private BlockStatement parseBlockStatement() {
        final Token token = curToken;
        nextToken();
        List<Statement> statements = new ArrayList<>();
        while (!curTokenIs(TokenType.RBRACE) && !curTokenIs(TokenType.EOF)) {
            Statement stmt = parseStatement();
            if (stmt != null) {
                statements.add(stmt);
            }
            nextToken();
        }
        return new BlockStatement(token, statements);
    }
}

ブロックの中には様々な文が入るので、} が出現するまで、parseStatement() で文の解析を行い、BlockStatement を生成します。


では、if 式のパースを書きましょう。

public class Parser {
    private PrefixParser parseIfExpression() {
        return () -> {
            final Token token = curToken;
            if (!expectPeek(TokenType.LPAREN)) {
                return null;
            }
            nextToken();
            final Expression condition = parseExpression(Precedence.LOWEST);
            if (!expectPeek(TokenType.RPAREN)) {
                return null;
            }
            if (!expectPeek(TokenType.LBRACE)) {
                return null;
            }
            final BlockStatement consequence = parseBlockStatement();

            BlockStatement alternative = null;
            if (peekTokenIs(TokenType.ELSE)) {
                nextToken();
                if (!expectPeek(TokenType.LBRACE)) {
                    return null;
                }
                alternative = parseBlockStatement();
            }
            return new IfExpression(token, condition, consequence, alternative);
        };
    }
}

<condition>, consequence, alternative を順にパースしています。

alternative はその名の通り省略されることがあります。


最後に、TokenType.IF に紐づけて作成したパーサを登録すれば対応完了です。

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


これでテストがグリーンになります。



関数リテラル

続いて関数リテラルを扱います。


関数リテラルは以下のような形になります。

fn(x, y) { 
    return x + y; 
}


fn キーワードに続き、N個の引数、それから if 式 で見たような BlockStatement が続いています。

関数リテラルは fn <parameters> <block statement> のような形になります。


関数リテラルは以下のように使うこともできます。

let myFunction = fn(x, y) { return x + y; }


さらに、関数リテラルの return 文の中で、式として別の関数リテラルを使うこともできます。

fn() { 
    return fn(x, y) { return x > y; }; 
}


つまり、関数リテラルは式を書くことのできる どんな場所にも置くことができます。



関数リテラルを表すFunctionLiteral を定義しましょう。

public class FunctionLiteral implements Expression {

    public final Token token;
    public final List<Identifier> parameters;
    public final BlockStatement body;

    public FunctionLiteral(Token token, List<Identifier> parameters, BlockStatement body) {
        this.token = token;
        this.parameters = Collections.unmodifiableList(parameters);
        this.body = body;
    }

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

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append(tokenLiteral());
        sb.append("(");
        StringJoiner sj = new StringJoiner(", ");
        parameters.forEach(p -> sj.add(p.toString()));
        sb.append(sj.toString());
        sb.append(")");
        sb.append(body.toString());
        return sb.toString();
    }
}

FunctionLiteral は、パラメータリストと文のブロックにより構成されます。



FunctionLiteral のパーサのためにテストケースを作成しておきましょう。

    @Test
    void testFunctionLiteralParsing() {
        String input = "fn(x, y) { x + y; }";
        AstNode astNode = new Parser(new Lexer(input)).parse();

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

        assertThat(es.expression).isInstanceOf(FunctionLiteral.class);
        FunctionLiteral fl = (FunctionLiteral) es.expression;

        assertThat(fl.parameters.get(0).value).isEqualTo("x");
        assertThat(fl.parameters.get(1).value).isEqualTo("y");

        assertThat(((ExpressionStatement) fl.body.statements.get(0)).expression)
                .isInstanceOf(InfixExpression.class);
        InfixExpression ie = (InfixExpression) ((ExpressionStatement) fl.body.statements.get(0)).expression;
        assertThat(ie.toString()).isEqualTo("(x + y)");
    }



ではパーサの実装に取り掛かります。


パースはパラメータと文のブロックを処理します。

    private PrefixParser parseFunctionLiteral() {
        return () -> {
            final Token token = curToken;
            if (!expectPeek(TokenType.LPAREN)) {
                return null;
            }
            List<Identifier> parameters = parseFunctionParameters();
            if (!expectPeek(TokenType.LBRACE)) {
                return null;
            }
            BlockStatement body = parseBlockStatement();
            return new FunctionLiteral(token, parameters, body);
        };
    }


parseBlockStatement() は if 式 で実装済みなので、parseFunctionParameters() を実装していきます。

    private List<Identifier> parseFunctionParameters() {
        List<Identifier> identifiers = new ArrayList<>();
        if (peekTokenIs(TokenType.RPAREN)) {
            nextToken();
            return identifiers;
        }
        nextToken();

        identifiers.add(new Identifier(curToken, curToken.literal));
        while (peekTokenIs(TokenType.COMMA)) {
            nextToken();
            nextToken();
            identifiers.add(new Identifier(curToken, curToken.literal));
        }
        if (!expectPeek(TokenType.RPAREN)) {
            return null;
        }
        return identifiers;
    }

カンマで区切られたパラメータの識別子Identifier をパラメータ数分作成してリストとして返します。


作成したパース処理をTokenType.FUNC と紐付けます。

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


これでテストがグリーンになります。



呼び出し式

関数リテラルのパースができたので、今度は関数の呼び出し側を考えます。


関数の呼び出しは add(2 + 2, 3 * 3 * 3) のようなものです。

関数のパラメータには、callsFunction(2, 3, fn(x, y) { x + y; }); のように関数リテラルを置けたり、定義した関数リテラルをその場で呼び出す fn(x, y) { x + y; }(2, 3) のような書き方もできます。


つまり呼び出し式の構造は <expression>(<comma separated expressions>)のような形になります。


<expression> には識別子か関数リテラルが置け、引数にはカンマで区切られた式がきます。


呼び出し式を表す CallExpression を定義しましょう。

public class CallExpression implements Expression {
  
    public final Token token;
    public final Expression function;
    public final List<Expression> arguments;

    public CallExpression(Token token, Expression function, List<Expression> arguments) {
        this.token = token;
        this.function = function;
        this.arguments = arguments;
    }

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

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append(function.toString());
        sb.append("(");

        StringJoiner sj = new StringJoiner(", ");
        arguments.forEach(a -> sj.add(a.toString()));
        sb.append(sj.toString());

        sb.append(")");
        return sb.toString();
    }
}


そして、いつもの通り、テストを書いておきます。

    @Test
    void testCallExpressionParsing() {
        String input = "add(1, 2 * 3, 4 + 5);";
        AstNode astNode = new Parser(new Lexer(input)).parse();

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

        assertThat(es.expression).isInstanceOf(CallExpression.class);
        CallExpression ce = (CallExpression) es.expression;

        assertThat(ce.function).isInstanceOf(Identifier.class);
        Identifier identifier = (Identifier) ce.function;
        assertThat(identifier.value).isEqualTo("add");

        assertThat(ce.arguments.get(0).toString()).isEqualTo("1");
        assertThat(ce.arguments.get(1).toString()).isEqualTo("(2 * 3)");
        assertThat(ce.arguments.get(2).toString()).isEqualTo("(4 + 5)");

    }



呼び出し式は、は <expression> に続き、( が来て、その後にカンマ区切りのパラメータが続きます。

なので、パースは ( が中置されるものとして、以下のようにパーサを紐づけ登録します。

public Parser(Lexer lexer) {
    this.infixParsers.put(TokenType.LPAREN, parseCallExpression());
}


パース処理は( の左側の式を function として受け取り、CallExpression を生成するようにします。

    private InfixParser parseCallExpression() {
        return function -> {
            Token token = curToken;
            return new CallExpression(token, function, parseCallArguments());
        };
    }


パラメータは parseCallArguments() というメソッドを用意して以下のようになります。

    private List<Expression> parseCallArguments() {
        List<Expression> args = new ArrayList<>();
        if (peekTokenIs(TokenType.RPAREN)) { 
            nextToken();
            return Collections.emptyList(); 
        }
        nextToken();
        args.add(parseExpression(Precedence.LOWEST));
        for (peekTokenIs(TokenType.COMMA)) {
            nextToken();
            nextToken();
            args.add(parseExpression(Precedence.LOWEST));
        }
        if (!expectPeek(TokenType.RPAREN)) {
            return null; 
        }
        return args;
    }

カンマ区切りのパラメータを処理し、式のリストとして返します。


これでテストはグリーンになります。


優先順位が正しく処理されるかどうかもテストしておきましょう。

    @ParameterizedTest
    @CsvSource({
            "a + add(b * c) + d, ((a + add((b * c))) + d)",
            "'add(a, b, 1, 2 * 3, 4 + 5, add(6, 7 * 8))', 'add(a, b, 1, (2 * 3), (4 + 5), add(6, (7 * 8)))'",
            "add(a + b + c * d / f + g), add((((a + b) + ((c * d) / f)) + g))",
    })
    void testCallOperatorPrecedenceParsing(String input, String expected) {
        AstNode astNode = new Parser(new Lexer(input)).parse();
        assertThat(astNode.toString()).isEqualTo(expected);
    }


ここまでで一通りの構文解析処理は完成となります。



まとめ

3回に分けて構文解析(パーサ)の実装を見てきました。


ここまでのソースは以下のようになりました。少し長くなりますが、そのまま載せておきます。


Parser そのものです。

package monkey.ast;

import monkey.lexer.Lexer;
import monkey.token.Token;
import monkey.token.TokenType;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Parser {

    private final Lexer lexer;
    private Token curToken;
    private Token peekToken;
    private List<String> errors;

    private final Map<TokenType, PrefixParser> prefixParsers;
    private final Map<TokenType, InfixParser> infixParsers;


    public Parser(Lexer lexer) {
        this.lexer = lexer;
        this.curToken  = lexer.nextToken();
        this.peekToken = lexer.nextToken();
        this.errors = new ArrayList<>();

        this.prefixParsers = new HashMap<>();
        this.prefixParsers.put(TokenType.IDENT, identifierParser());
        this.prefixParsers.put(TokenType.INT,   integerLiteralParser());
        this.prefixParsers.put(TokenType.BANG,  prefixExpressionParser());
        this.prefixParsers.put(TokenType.MINUS, prefixExpressionParser());
        this.prefixParsers.put(TokenType.TRUE,  parseBoolean());
        this.prefixParsers.put(TokenType.FALSE, parseBoolean());
        this.prefixParsers.put(TokenType.LPAREN,parseGroupedExpression());
        this.prefixParsers.put(TokenType.IF,    parseIfExpression());
        this.prefixParsers.put(TokenType.FUNC,  parseFunctionLiteral());

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

        this.infixParsers.put(TokenType.LPAREN, parseCallExpression());
    }


    public AstNode parse() {
        AstNode root = new AstNode();
        while (curToken.type != TokenType.EOF) {
            Statement stm = parseStatement();
            if (stm != null) {
                root.add(stm);
            }
            nextToken();
        }
        return root;
    }


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


    private LetStatement parseLetStatement()  {

        final Token token = curToken;

        if (!expectPeek(TokenType.IDENT)) {
            return null;
        }

        Identifier name = new Identifier(curToken, curToken.literal);
        if (!expectPeek(TokenType.ASSIGN)) {
            return null;
        }

        nextToken();
        Expression value = parseExpression(Precedence.LOWEST);

        while (!curTokenIs(TokenType.SEMIC)) {
            nextToken();
        }

        return new LetStatement(token, name, value);
    }


    private ReturnStatement parseReturnStatement() {

        final Token token = curToken;

        nextToken();
        Expression value = parseExpression(Precedence.LOWEST);

        while (!curTokenIs(TokenType.SEMIC)) {
            nextToken();
        }

        return new ReturnStatement(token, value);
    }


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


    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;
    }


    private void nextToken() {
        curToken = peekToken;
        peekToken = lexer.nextToken();
    }


    private boolean curTokenIs(TokenType t) {
        return curToken.type == t;
    }


    private boolean peekTokenIs(TokenType t) {
        return peekToken.type == t;
    }


    private boolean expectPeek(TokenType t) {
        if (peekTokenIs(t)) {
            nextToken();
            return true;
        } else {
            peekError(t);
            return false;
        }
    }


    private void peekError(TokenType t) {
        String msg = String.format("expected next token to be %s, got %s instead", t, peekToken.type);
        errors.add(msg);
    }

    // - PrefixParser ---------------------------------------------------------

    interface PrefixParser {
        Expression parse();
    }


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


    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;
        };
    }


    private PrefixParser prefixExpressionParser() {
        return () -> {
            Token token = curToken;
            nextToken();
            final Expression right = parseExpression(Precedence.PREFIX);
            return new PrefixExpression(token, token.literal, right);
        };
    }


    private PrefixParser parseBoolean() {
        return () -> new BooleanLiteral(curToken, curTokenIs(TokenType.TRUE));
    }


    private PrefixParser parseGroupedExpression() {
        return () -> {
            nextToken();
            Expression exp = parseExpression(Precedence.LOWEST);
            if (!expectPeek(TokenType.RPAREN)) {
                return null;
            }
            return exp;
        };
    }


    private PrefixParser parseIfExpression() {
        return () -> {
            final Token token = curToken;
            if (!expectPeek(TokenType.LPAREN)) {
                return null;
            }
            nextToken();
            final Expression condition = parseExpression(Precedence.LOWEST);
            if (!expectPeek(TokenType.RPAREN)) {
                return null;
            }
            if (!expectPeek(TokenType.LBRACE)) {
                return null;
            }
            final BlockStatement consequence = parseBlockStatement();

            BlockStatement alternative = null;
            if (peekTokenIs(TokenType.ELSE)) {
                nextToken();
                if (!expectPeek(TokenType.LBRACE)) {
                    return null;
                }
                alternative = parseBlockStatement();
            }
            return new IfExpression(token, condition, consequence, alternative);
        };
    }


    private PrefixParser parseFunctionLiteral() {
        return () -> {
            final Token token = curToken;
            if (!expectPeek(TokenType.LPAREN)) {
                return null;
            }
            List<Identifier> parameters = parseFunctionParameters();
            if (!expectPeek(TokenType.LBRACE)) {
                return null;
            }
            BlockStatement body = parseBlockStatement();
            return new FunctionLiteral(token, parameters, body);
        };
    }


    private BlockStatement parseBlockStatement() {
        final Token token = curToken;
        nextToken();
        List<Statement> statements = new ArrayList<>();
        while (!curTokenIs(TokenType.RBRACE) && !curTokenIs(TokenType.EOF)) {
            Statement stmt = parseStatement();
            if (stmt != null) {
                statements.add(stmt);
            }
            nextToken();
        }
        return new BlockStatement(token, statements);
    }


    private List<Identifier> parseFunctionParameters() {
        List<Identifier> identifiers = new ArrayList<>();
        if (peekTokenIs(TokenType.RPAREN)) {
            nextToken();
            return identifiers;
        }
        nextToken();

        identifiers.add(new Identifier(curToken, curToken.literal));
        while (peekTokenIs(TokenType.COMMA)) {
            nextToken();
            nextToken();
            identifiers.add(new Identifier(curToken, curToken.literal));
        }
        if (!expectPeek(TokenType.RPAREN)) {
            return null;
        }
        return identifiers;
    }

    // - InfixParser ---------------------------------------------------------

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


    private InfixParser parseCallExpression() {
        return function -> {
            Token token = curToken;
            return new CallExpression(token, function, parseCallArguments());
        };
    }


    private List<Expression> parseCallArguments() {
        List<Expression> args = new ArrayList<>();
        if (peekTokenIs(TokenType.RPAREN)) {
            nextToken();
            return Collections.emptyList();
        }
        nextToken();
        args.add(parseExpression(Precedence.LOWEST));
        while (peekTokenIs(TokenType.COMMA)) {
            nextToken();
            nextToken();
            args.add(parseExpression(Precedence.LOWEST));
        }
        if (!expectPeek(TokenType.RPAREN)) {
            return null;
        }
        return args;
    }
}



構文の基本となる Node の型定義です。

package monkey.ast;

public interface Node {
    String tokenLiteral();
}



package monkey.ast;

public interface Statement extends Node {
}



package monkey.ast;

public interface Expression extends Node {
}



package monkey.ast;

import java.util.ArrayList;
import java.util.List;

public class AstNode implements Node {

    private List<Statement> statements;

    AstNode() {
        statements = new ArrayList<>();
    }

    public void add(Statement statement) {
        statements.add(statement);
    }

    @Override
    public String tokenLiteral() {
        if (statements.isEmpty()) {
            return "";
        }
        return statements.get(0).tokenLiteral();
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        for (Statement statement : statements) {
            sb.append(statement.toString());
        }
        return sb.toString();
    }

    public List<Statement> getStatements() {
        return new ArrayList<>(statements);
    }

}



文の表現として、let と returnです。

package monkey.ast;

import monkey.token.Token;
import java.util.Objects;

public class LetStatement implements Statement {

    public final Token token;
    public final Identifier name;
    public final Expression value;

    public LetStatement(Token token, Identifier name, Expression value) {
        this.token = token;
        this.name = name;
        this.value = value;
    }

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

    @Override
    public String toString() {
        return tokenLiteral() + " " +
               name.toString() + " = " +
               (Objects.isNull(value) ? "" : value.toString()) + ";";
    }

}



package monkey.ast;

import monkey.token.Token;
import java.util.Objects;

public class ReturnStatement implements Statement {

    public final Token token;
    public final Expression returnValue;

    public ReturnStatement(Token token, Expression returnValue) {
        this.token = token;
        this.returnValue = returnValue;
    }

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

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

}



式の構成要素です。

package monkey.ast;

import monkey.token.Token;

public class Identifier implements Expression {

    public final Token token;
    public final String value;

    public Identifier(Token token, String value) {
        this.token = token;
        this.value = value;
    }

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

    @Override
    public String toString() {
        return value;
    }
}



package monkey.ast;

import monkey.token.Token;

public class IntegerLiteral implements Expression {

    public final Token token;
    public final Integer value;

    public IntegerLiteral(Token token, Integer value) {
        this.token = token;
        this.value = value;
    }

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

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



package monkey.ast;

import monkey.token.Token;

public class BooleanLiteral implements Expression {

    public final Token token;
    public final Boolean value;

    public BooleanLiteral(Token token, Boolean value) {
        this.token = token;
        this.value = value;
    }

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

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



package monkey.ast;

import monkey.token.Token;
import java.util.Objects;

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

}



package monkey.ast;

import monkey.token.Token;

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() + ')';
    }
}



package monkey.ast;

import monkey.token.Token;

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() + ")";
    }
}



package monkey.ast;

import monkey.token.Token;

import java.util.Collections;
import java.util.List;

public class BlockStatement implements Statement {
    public final Token token;
    public final List<Statement> statements;

    public BlockStatement(Token token, List<Statement> statements) {
        this.token = token;
        this.statements = Collections.unmodifiableList(statements);
    }

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

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        statements.forEach(sb::append);
        return sb.toString();
    }
}



package monkey.ast;

import monkey.token.Token;
import java.util.Optional;

public class IfExpression implements Expression {

    public final Token token;
    public final Expression condition;
    public final BlockStatement consequence;
    public final Optional<BlockStatement> alternative;

    public IfExpression(Token token, Expression condition, BlockStatement consequence, BlockStatement alternative) {
        this.token = token;
        this.condition = condition;
        this.consequence = consequence;
        this.alternative = Optional.ofNullable(alternative);
    }

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

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("if");
        sb.append(condition.toString());
        sb.append(" ");
        sb.append(consequence.toString());
        alternative.ifPresent(bs -> sb.append("else " + bs.toString()));
        return sb.toString();
    }
}



package monkey.ast;

import monkey.token.Token;

import java.util.Collections;
import java.util.List;
import java.util.StringJoiner;

public class FunctionLiteral implements Expression {

    public final Token token;
    public final List<Identifier> parameters;
    public final BlockStatement body;

    public FunctionLiteral(Token token, List<Identifier> parameters, BlockStatement body) {
        this.token = token;
        this.parameters = Collections.unmodifiableList(parameters);
        this.body = body;
    }

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

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append(tokenLiteral());
        sb.append("(");
        StringJoiner sj = new StringJoiner(", ");
        parameters.forEach(p -> sj.add(p.toString()));
        sb.append(sj.toString());
        sb.append(")");
        sb.append(body.toString());
        return sb.toString();
    }
}



package monkey.ast;

import monkey.token.Token;

import java.util.Collections;
import java.util.List;
import java.util.Objects;
import java.util.StringJoiner;

public class CallExpression implements Expression {
    public final Token token;
    public final Expression function;  // Identifier or FunctionLiteral
    public final List<Expression> arguments;

    public CallExpression(Token token, Expression function, List<Expression> arguments) {
        this.token = token;
        this.function = function;
        this.arguments = Objects.isNull(arguments) ? Collections.emptyList() : arguments;
    }

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

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append(function.toString());
        sb.append("(");

        StringJoiner sj = new StringJoiner(", ");
        arguments.forEach(a -> sj.add(a.toString()));
        sb.append(sj.toString());

        sb.append(")");
        return sb.toString();
    }
}



演算子の優先順位定義です。

package monkey.ast;

import monkey.token.TokenType;

import java.util.Arrays;
import java.util.List;

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;
    }
}



最後にテストケースです。

package monkey.ast;

import monkey.lexer.Lexer;
import monkey.token.TokenType;
import org.junit.jupiter.api.Test;
import org.junit.jupiter.params.ParameterizedTest;
import org.junit.jupiter.params.provider.CsvSource;
import static org.assertj.core.api.Assertions.*;

public class ParserTest {


    @Test
    void testLetStatement() {

        String input =
                "let x = 5;"                + "\n" +
                "let foobar = 838383;";

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

        assertThat(astNode.getStatements().get(0)).isInstanceOf(LetStatement.class);
        LetStatement s0 = (LetStatement) astNode.getStatements().get(0);
        assertThat(s0.tokenLiteral()).isEqualTo("let");
        assertThat(s0.name.value).isEqualTo("x");
        assertThat(s0.value.tokenLiteral()).isEqualTo("5");

        assertThat(astNode.getStatements().get(1)).isInstanceOf(LetStatement.class);
        LetStatement s1 = (LetStatement) astNode.getStatements().get(1);
        assertThat(s1.tokenLiteral()).isEqualTo("let");
        assertThat(s1.name.value).isEqualTo("foobar");
        assertThat(s1.value.tokenLiteral()).isEqualTo("838383");

    }


    @Test
    void testReturnStatement() {
        String input =
                "return 5;"                + "\n" +
                "return 9090;";

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

        assertThat(astNode.getStatements().get(0)).isInstanceOf(ReturnStatement.class);
        ReturnStatement s0 = (ReturnStatement) astNode.getStatements().get(0);
        assertThat(s0.tokenLiteral()).isEqualTo("return");
        assertThat(s0.returnValue.tokenLiteral()).isEqualTo("5");

        assertThat(astNode.getStatements().get(1)).isInstanceOf(ReturnStatement.class);
        ReturnStatement s1 = (ReturnStatement) astNode.getStatements().get(1);
        assertThat(s1.tokenLiteral()).isEqualTo("return");
        assertThat(s1.returnValue.tokenLiteral()).isEqualTo("9090");

    }

    @Test
    void testToString() {

        String input = "let x = 99;";

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

        assertThat(astNode.toString()).isEqualTo("let x = 99;");
    }


    @Test
    void testIdentifierExpression() {

        String input = "foobar;";

        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.token.type).isEqualTo(TokenType.IDENT);
        assertThat(s0.expression.tokenLiteral()).isEqualTo("foobar");
    }


    @Test
    void testIntegerLiteralExpression() {

        String input = "5;";

        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.token.type).isEqualTo(TokenType.INT);
        assertThat(s0.expression.tokenLiteral()).isEqualTo("5");
    }

    @Test
    void testParsingPrefixExpressions() {

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

        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(PrefixExpression.class);
        PrefixExpression p0 = (PrefixExpression) s0.expression;
        assertThat(p0.operator).isEqualTo("!");
        assertThat(p0.right.tokenLiteral()).isEqualTo("5");

        assertThat(astNode.getStatements().get(1)).isInstanceOf(ExpressionStatement.class);
        ExpressionStatement s1 = (ExpressionStatement) astNode.getStatements().get(1);
        assertThat(s1.expression).isInstanceOf(PrefixExpression.class);
        PrefixExpression p1 = (PrefixExpression) s1.expression;
        assertThat(p1.operator).isEqualTo("-");
        assertThat(p1.right.tokenLiteral()).isEqualTo("15");

    }

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

    }

    @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);
    }

    @ParameterizedTest
    @CsvSource({
            "true, true",
            "false, false",
            "3 > 5 == false, ((3 > 5) == false)",
            "3 < 5 == true, ((3 < 5) == true)",
    })
    void testBooleanOperatorPrecedenceParsing(String input, String expected) {
        AstNode astNode = new Parser(new Lexer(input)).parse();
        assertThat(astNode.toString()).isEqualTo(expected);
    }

    @ParameterizedTest
    @CsvSource({
            "1 + (2 + 3) + 4, ((1 + (2 + 3)) + 4)",
            "(5 + 5) * 2, ((5 + 5) * 2)",
            "2 / (5 + 5), (2 / (5 + 5))",
            "-(5 + 5), (-(5 + 5))",
            "!(true == true), (!(true == true))",
    })
    void testParenOperatorPrecedenceParsing(String input, String expected) {
        AstNode astNode = new Parser(new Lexer(input)).parse();
        assertThat(astNode.toString()).isEqualTo(expected);
    }


    @Test
    void testIfExpression() {
        String input = "if (x < y) { x } else { y }";
        AstNode astNode = new Parser(new Lexer(input)).parse();

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

        assertThat(es.expression).isInstanceOf(IfExpression.class);
        IfExpression e = (IfExpression) es.expression;

        assertThat(e.condition).isInstanceOf(InfixExpression.class);
        InfixExpression condition = (InfixExpression) e.condition;
        assertThat(condition.toString()).isEqualTo("(x < y)");

        assertThat(e.consequence.toString()).isEqualTo("x");
        assertThat(e.alternative.get().toString()).isEqualTo("y");
    }


    @Test
    void testFunctionLiteralParsing() {
        String input = "fn(x, y) { x + y; }";
        AstNode astNode = new Parser(new Lexer(input)).parse();

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

        assertThat(es.expression).isInstanceOf(FunctionLiteral.class);
        FunctionLiteral fl = (FunctionLiteral) es.expression;

        assertThat(fl.parameters.get(0).value).isEqualTo("x");
        assertThat(fl.parameters.get(1).value).isEqualTo("y");

        assertThat(((ExpressionStatement) fl.body.statements.get(0)).expression)
                .isInstanceOf(InfixExpression.class);
        InfixExpression ie = (InfixExpression) ((ExpressionStatement) fl.body.statements.get(0)).expression;
        assertThat(ie.toString()).isEqualTo("(x + y)");
    }

    @Test
    void testCallExpressionParsing() {
        String input = "add(1, 2 * 3, 4 + 5);";
        AstNode astNode = new Parser(new Lexer(input)).parse();

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

        assertThat(es.expression).isInstanceOf(CallExpression.class);
        CallExpression ce = (CallExpression) es.expression;

        assertThat(ce.function).isInstanceOf(Identifier.class);
        Identifier identifier = (Identifier) ce.function;
        assertThat(identifier.value).isEqualTo("add");

        assertThat(ce.arguments.get(0).toString()).isEqualTo("1");
        assertThat(ce.arguments.get(1).toString()).isEqualTo("(2 * 3)");
        assertThat(ce.arguments.get(2).toString()).isEqualTo("(4 + 5)");

    }

    @ParameterizedTest
    @CsvSource({
            "a + add(b * c) + d, ((a + add((b * c))) + d)",
            "'add(a, b, 1, 2 * 3, 4 + 5, add(6, 7 * 8))', 'add(a, b, 1, (2 * 3), (4 + 5), add(6, (7 * 8)))'",
            "add(a + b + c * d / f + g), add((((a + b) + ((c * d) / f)) + g))",
    })
    void testCallOperatorPrecedenceParsing(String input, String expected) {
        AstNode astNode = new Parser(new Lexer(input)).parse();
        assertThat(astNode.toString()).isEqualTo(expected);
    }
}




次回からは、いよいよ構文解析結果の評価に入っていきます。

と思いましたが、全体を以下でまとめて紹介します。

blog1.mammb.com