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

Java

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

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

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


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

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

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


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



前回

blog1.mammb.com

までで作成した字句解析の結果を、構文解析器に通し、AST(抽象構文木)を作成します。

パーサージェネレータは使わず、ベタに実装していく流れになります。


構文の型定義

構文には「文」と「式」があり、これらを合わせてノードと呼ぶことにします。

構文 は以下のインターフェースの組み合わせで表現します。

public interface Node {
    String tokenLiteral();
}


「文」を表す Statement は Node を継承します。

public interface Statement extends Node { }


「式」を表す Expression も Node を継承します。

public interface Expression extends Node { }


そして、構文解析器は以下のような AST のルートとなる AstNode を生成するものとします。

public class AstNode implements Node {

    private List<Statement> statements;

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

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

AstNode は List<Statement> statements のように、複数の文で構成されます。


では、これらの基本型を使い、構文解析器(パーサ)を少しづつ実装していきます。


let 文

最初に let x = 10; のような let 文 を扱います。

これは、let <identifier> = <expression>; という形になっています。


<identifier> を表す型を定義しましょう。

public class Identifier implements Expression {

    public final Token token;
    public final String value;

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

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


そして、let 文 は、Identifier と Expression を持つ LetStatement という型で表現します。

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; // TokenType.LET
        this.name  = name;
        this.value = value;
    }

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

この型が、let <identifier> = <expression>; という let文 を表します。


さて、Expression の中身は何になるでしょうか？

let x = 1 + 2; だったり、let x = add(1, 2); だったり、様々な「式」が考えられます。最初は、 let x = 10; のように整数リテラルだけを扱うことにします。


では、整数リテラルを表す型を定義しましょう。

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

これで、最初の目標となる、 let x = 10; といった文を表現する準備が整いました。


では、構文解析器の実装にとりかかりましょう。



初期の構文解析器

構文解析器の原型は以下のようになります。

public class Parser {

    private final Lexer lexer;
    private Token curToken;
    private Token peekToken;

    public Parser(Lexer lexer) {
        this.lexer = lexer;
        this.curToken  = lexer.nextToken();
        this.peekToken = lexer.nextToken();
    }

    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 void nextToken() {
        curToken = peekToken;
        peekToken = lexer.nextToken();
    }
  
    private Statement parseStatement()  {
        switch (curToken.type) {
        case LET:
            return parseLetStatement(); // let 文のパース
        default:
            return null;
        }
    }

    private LetStatement parseLetStatement()  {
        // これから実装
        return null;
    }
}

parse() で字句解析済みの Token を取り出しながら、parseStatement() で構文に変換しながら AstNode に加えていくだけです。

字句解析でもあったように、curToken が現在のトークン、peekToken が(のぞき見用の)その次のトークンとなっています。


では、最初にこの Parser が満たすべきテストを書いていきます。

public class ParserTest {

    @Test
    public void letStatement() {
        String input =
            "let x = 5;"            + "\n" +
            "let foobar = 838383;";
      
        Lexer lexer = new Lexer(input);
        Parser parser = new Parser(lexer);

        AstNode astNode = parser.parse();

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

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


    }
}

作成済みの Lexer をそのまま使い、parse() にて取り出した AstNode の中身が LetStatement となっているかを検証しています。



let 文の解析

では Parser の中身を実装していきます。

public class Parser {

    // ...

    private LetStatement parseLetStatement()  {
        final Token token = curToken;

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

        if (!expectPeek(TokenType.ASSIGN)) { // =
            return null;
        }
        
        nextToken();
        Expression value = new IntegerLiteral(
            curToken, Integer.parseInt(curToken.literal)); // 10

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

        return new LetStatement(token, name, value); // let x = 10;
    }


    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 {
            return false;
        }
    }
}

parseLetStatement() で let に続くトークンを検証しつつ、LetStatement を生成しています。


この内容で、テストはグリーンとなり、まずは let が解析できるようになりました。


続いて、もう一つの文である return 文に取り掛かりましょう。



return 文

Monkey 言語の文には let と return があります。

return 5; のような文となり、return <expression>; のような形式となります。


以下のような型で表現することとします。

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

先程の let と同じような感じですね。


今回も、<expression> には整数リテラルだけを考えます。

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

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

        Lexer lexer = new Lexer(input);
        Parser parser = new Parser(lexer);

        AstNode astNode = parser.parse();

        assertThat(astNode.getStatements().get(0), is(instanceOf(ReturnStatement.class)));
        ReturnStatement s0 = (ReturnStatement) astNode.getStatements().get(0);
        assertThat(s0.tokenLiteral(), is("return"));
        assertThat(s0.returnValue.tokenLiteral(), is("5"));

        assertThat(astNode.getStatements().get(1), is(instanceOf(ReturnStatement.class)));
        ReturnStatement s1 = (ReturnStatement) astNode.getStatements().get(1);
        assertThat(s1.tokenLiteral(), is("return"));
        assertThat(s0.returnValue.tokenLiteral(), is("9090"));

    }



さて、テストを満たすようにパーサの実装に進みましょう。

パース処理に parseReturnStatement() を追加します。

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


let の場合と同様となります。

    private ReturnStatement parseReturnStatement() {

        final Token token = curToken;

        nextToken();
        Expression value = new IntegerLiteral(curToken, Integer.parseInt(curToken.literal));

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

        return new ReturnStatement(token, value);
    }

ちなにみ、Monkey 言語では、末尾の; は省略可能なので、TokenType.SEMIC はスキップするようになっています。


これでテストが通ります。

限定的ではありますが、let と return の解析ができるようになりました。


この先で、パーサを適宜拡張していきますが、ここでエラー情報とデバッグ文字を出力できるようにしておきましょう。


構文エラーの記録

Parser で構文エラーがあった場合、今のままでは何が起こったのか分からなくなるので、エラー処理を追加します。


Parser に以下の変更を加えます。

public class Parser {

    // ...
    private List<String> errors; // ★ 追加

    public Parser(Lexer lexer) {
        // ...
        this.errors = new ArrayList<>(); // ★ 追加
    }


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

}

errors というエラー記録用のフィールドを用意し、expectPeek() で想定しないトークンであった場合にエラーを記録できるようになりました。



toString() の実装

ASTの各ノードに toString を追加してデバッグ時に情報を得やすいようにしておきましょう。


今まで作成した構文の型に toString を追加していきます。


最初に AstNode です。

public class AstNode implements Node {

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


LetStatement です。

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


ReturnStatement です。

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


Identifier です。

public class Identifier implements Expression {
    @Override
    public String toString() {
        return value;
    }
}


IntegerLiteral です。

public class IntegerLiteral implements Expression {
    @Override
    public String toString() {
        return token.literal;
    }
}



まとめ

ここまでのソースは以下のようになりました。


構文のノードを表す Node です。

package monkey.ast;

public interface Node {
    String tokenLiteral();
}


文を表すインターフェースStatement`です。

package monkey.ast;

public interface Statement extends Node {
}


式を表すインターフェースExpressionです。

package monkey.ast;

public interface Expression extends Node {
}


Identifierです。

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

}


IntegerLiteralです。

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


LetStatementです。

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

}


ReturnStatementです。

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.lexer.Lexer;
import monkey.token.Token;
import monkey.token.TokenType;

import java.util.ArrayList;
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;

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


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


    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 = new IntegerLiteral(curToken, Integer.parseInt(curToken.literal));

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

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


    private ReturnStatement parseReturnStatement() {

        final Token token = curToken;

        nextToken();
        Expression value = new IntegerLiteral(curToken, Integer.parseInt(curToken.literal));

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

        return new ReturnStatement(token, value);
    }


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

}


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

package monkey.ast;

import monkey.lexer.Lexer;

import org.junit.Test;
import static org.hamcrest.core.Is.is;
import static org.hamcrest.core.IsInstanceOf.instanceOf;
import static org.junit.Assert.*;

public class ParserTest {

    @Test
    public void letStatement() {

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

        Lexer lexer = new Lexer(input);
        Parser parser = new Parser(lexer);

        AstNode astNode = parser.parse();

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

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

    }


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

        Lexer lexer = new Lexer(input);
        Parser parser = new Parser(lexer);

        AstNode astNode = parser.parse();

        assertThat(astNode.getStatements().get(0), is(instanceOf(ReturnStatement.class)));
        ReturnStatement s0 = (ReturnStatement) astNode.getStatements().get(0);
        assertThat(s0.tokenLiteral(), is("return"));
        assertThat(s0.returnValue.tokenLiteral(), is("5"));

        assertThat(astNode.getStatements().get(1), is(instanceOf(ReturnStatement.class)));
        ReturnStatement s1 = (ReturnStatement) astNode.getStatements().get(1);
        assertThat(s1.tokenLiteral(), is("return"));
        assertThat(s1.returnValue.tokenLiteral(), is("9090"));

    }

    @Test
    public void testToString() {

        String input = "let x = 99;";

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

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




次回は演算子の構文解析となります。

blog1.mammb.com