Java でシンプルなインタプリタを実装する



はじめに

Writing An Interpreter In Go を元に、Java を使って 1,000行 以下でインタプリタを作ります。

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

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

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

レコードクラス(JEP 359) や instanceof のパターンマッチ(JEP 305)などを使うため、プレビュー段階ではありますが、JDK 14 を使うことにします。

また、ソースファイルはシングルファイルにして Launch Single-File Source-Code Programs(JEP 330) で直接実行できるようにすることとします。


ソースは以下となります。

github.com


プログラミング言語

ここで扱う言語はシンプルな言語です。

キーワードは、関数を定義する fn、変数を束縛する let、フロー制御を行う if else return があるだけです。

整数と論理値、文字列があり、配列とハッシュ(マップ)があります。

fn は第一級関数で、クロージャがあり高階関数があります。


以下のような変数を扱うことができます。

let name = "monkey";
let result = 10 * (20 / 2);

let array = [1, 2, 3, 4, 5];
myArray[0]; // 1

let hash = {"name": "thorsten", "age": 28};
thorsten["name"]; // thorsten

let add = fn(a, b) { return a + b; };
add(2, 3); // 5

フィボナッチ数を返す関数は以下のように定義できます。

let fibonacci = fn(x) {
  if (x == 0) {
    0
  } else {
    if (x == 1) { 1
  } else {
    fibonacci(x - 1) + fibonacci(x - 2); }
  }
};

以下のような高階関数も扱うこともできます。

let twice = fn(f, x) {
  return f(f(x));
};

let addTwo = fn(x) {
  return x + 2;
};

twice(addTwo, 2); // 6


インタプリタ

インタプリタではソースコードを逐次実行して計算処理を行います。

これは、大きく以下の流れになります。

  1. ソースコードを字句解析器(Lexical Analyzer)にてトークン列に変換する
  2. トークン列を、言語の意味に合わせた抽象構文木(Abstract Syntax Tree)と呼ばれる木構造のデータ表現に変換する
  3. 抽象構文木を辿り評価する(計算処理を実行する)

ここでは、それぞれの処理を Lexer、Parser、Evaluator というクラスで段階的に行います。

ソースは Interpreter.javaというシングルソースだけなので、このファイルを元に大きな流れを説明していきます。


字句解析器 Lexer

Lexer がそれです。

Lexer では、入力となるソースコードを1文字づつ読み込み、演算子や識別子、文字列リテラルといった単位で Token オブジェクトを生成しています。

具体的にはnextToken() の中で以下のように文字を判別して Token を生成しています。

public Token nextToken() {
    skipWhitespace();
    Token token = switch (ch) {
        case '+' -> new Token(TokenType.PLUS);
        case '-' -> new Token(TokenType.MINUS);
        // ...
    };
    readChar();
    return token;
}

例えば foo という変数名であったり、256 などの整数値などの文字列は nextToken() の中で以下のように処理しています。

    default -> {
        if (isLetter(ch)) {
            final String id = readIdentifier();
            yield new Token(TokenType.lookupIdent(id), id);
        } else if (isDigit(ch)) {
            yield new Token(TokenType.INT, readNumber());
        } else {
            yield new Token(TokenType.ILLEGAL, Character.toString(ch));
        }
    }


ここで作成する Token は以下のような enum 値と文字リテラルで構成する(Java14 でプレビュー機能である)レコードクラスの形としています。

public record Token(TokenType type, String literal) {
    public Token(TokenType type) { this(type, type.str); }
}


Lexer で行っていることはこれが全てです。すなわち、ソースを読み込みつつ、意味のある区切りで Token として切り出し、nextToken() で順番に取り出せるようにしています。

ここで行った字句解析の結果を続くParser で利用します。


抽象構文木を生成する Parser

ソースコードを Token として切り出せるようになったので、次は Token から抽象構文木(AST)を生成する処理です。 Parser がこの処理を行います。

Parser は、先程作成した Lexer をフィールドとして持ち、nextToken() で Lexer から Token を取り出します。

public static class Parser {

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

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


抽象構文木(AST)への変換はparseStatement() が入り口となり、以下のようになっています。

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

文(Statement)か、値を返す式(Expression) で処理を分けています。

ここで扱う言語では、「文」は let、return で、それ以外は全て「式」となります。文と式も同じように扱いたいため、式は 式文(ExpressionStatement) として扱っています。


parseStatement() によって、Token は文法上の意味を成す Statement として木構造に変換されます。

木構造となった構文要素は Node インターフェース を最上位に、以下のようなインターフェース階層で構成されます。

public interface Node { }
public interface Statement extends Node { }
public interface Expression extends Node { }

例えば let hoo = 10; といった文は、以下のようなレコードクラスで表現します。

static record LetStatement(
        Token token,
        Identifier name,
        Expression value) implements Statement {
    @Override public String toString() {
        return token.literal + " " +
                name.toString() + " = " +
                (Objects.isNull(value) ? "" : value.toString()) + ";";
    }
}

LetStatement は Statement インターフェースを実装した 文 の一種となります。

let 文は、識別子である Identifier(Expressionの実装レコードクラス) と、右辺の式(Expression) で構成されます。

式(Expression) の中には、式を構成するそれぞれの要素(Node)が含まれるといった形で木構造となります。

同じように return 文を現る ReturnStatement であったり、if 式 を表す IfExpression といった Node インターフェースの実装クラスを生成していくことになります。


一例として LetStatement を生成する parseLetStatement() は以下のような処理になります。

private LetStatement parseLetStatement()  {

    final Token token = curToken;
    if (!expectPeek(TokenType.IDENT)) {
        return null;
    }
    Identifier identifier = parseIdentifier();

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

    nextToken();
    Expression expression = parseExpression(Precedence.LOWEST);
    while (!curTokenIs(TokenType.SEMIC)) {
        nextToken();
    }

    return new LetStatement(token, identifier, expression);
}

識別子となる Identifier、右辺を構成する Expression をそれぞれパースして new LetStatement(token, identifier, expression) のようにインスタンスを生成しています。


パース処理の中で最も興味深い箇所は parseExpression() の処理です。

10 + 5 * 5 といった計算には、演算子の優先順位があり (10 + (5 * 5)) のような形に構成する必要があります。

また、演算には -5 といった前置(prefix)、2 * 3 といった中置(infix) があり「再帰下降構文解析器」としての実装を行っています。前置 を処理する PrefixParser、中置を処理する InfixParser を使い解析を行っていますが、文章で説明してもよくわからなくなるので、実装をデバック実行していただければと思います。


評価機 Evaluator

ここでの評価機は、前処理やコンパイルなどは行わず、Parser にて生成した AST をオンザフライで解釈する tree-walking インタプリタとなります。

Evaluator がこの処理を担当します。

以下のような感じになります。

var parser = Parser.of(Lexer.of(input));
Parser.Statements statements = parser.parse();

var evaluated = Evaluator.of().eval(statements);

statements が AST のリストになるので、これを Evaluator で eval() する流れになります。


中心になるのは eval() 関数です。

private Any eval(Parser.Node node, Environment env) {

    if (node instanceof Parser.Statements n) {
        return evalStatements(n, env);
    } else if (node instanceof Parser.ExpressionStatement n) {
        return eval(n.expression(), env);
    // ...
    }
    return null;
}

パースした AST のインスタンスに応じて評価を繰り返していく流れです。


eval() の戻り値には Any となっており、実際には以下のインターフェースとなります。

interface Any {
    String inspect();
}

評価機の実行過程で評価された値を保持する器を Any というオブジェクトとして表現します(Object は Java では既に存在して使えないので)。

結果値に応じて Any インターフェースを実装するそれぞれのクラスで扱います。

例えば整数型の場合は以下のようなレコードクラスで扱います。

private static record Int(Integer val) implements Any {
    @Override public String inspect() {
        return val.toString();
    }
}

例えば return 文による戻り値を以下のようなレコードクラスで扱います。

private static record ReturnValue(Any value) implements Any {
    @Override public String inspect() {
        return value.inspect();
    }
}

ごく単純な例をあげるならば、AST から得た Node が整数リテラルであれば、以下のように単に Int オブジェクトを生成します。

    } else if (node instanceof Parser.IntegerLiteral n) {
        return new Int(n.value());
    }


さて、先に示した eval() をもう一度確認しましょう。

private Any eval(Parser.Node node, Environment env) {

    if (node instanceof Parser.Statements n) {
        return evalStatements(n, env);
    // ...
    }
    return null;
}

Statements つまり文の集まりであれば、evalStatements(n, env) としており、このメソッドは以下のようになります。

private Any evalStatements(Parser.Statements statements, Environment env) {
    Any result = null;
    for (Parser.Statement statement : statements.statements()) {
        result = eval(statement, env);
        if (result instanceof ReturnValue rv) {
            return rv.value();
        } else if (result instanceof Error) {
            return result;
        }
    }
    return result;
}

文を繰り返し取り出して、eval() により再帰的に評価を実施するようになっています。

それぞれの Node によって処理は様々ですが、一例として中置の演算があった場合は以下のように処理されます。

private Any evalIntegerInfixExpression(String operator, Int left, Int right) {
    int leftVal = left.val();
    int rightVal = right.val();
    return switch (operator) {
        case "+"  -> new Int(leftVal + rightVal);
        case "-"  -> new Int(leftVal - rightVal);
        // ...
    };
}

演算子に応じて、+ であれば leftVal + rightVal で合計した新しい Int オブジェクトを生成しています。

このような演算を AST を巡って行うことで評価を実施する流れになります。

evalStatements() から辿ることで、流れが把握できるかと思います。


まとめ

Java を使ったインタプリタの実装について大枠の流れを説明しました。

以下のように動作します。

f:id:Naotsugu:20200901225038p:plain

1,000 行に満たない実装なので、詳細は以下でソースを参照いただければと思います。

github.com


より詳しくは以下で読むことができます。

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

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

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