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

- 作者:Thorsten Ball
- 発売日: 2018/06/16
- メディア: 単行本(ソフトカバー)
レコードクラス(JEP 359) や instanceof のパターンマッチ(JEP 305)などを使うため、プレビュー段階ではありますが、JDK 14 を使うことにします。
また、ソースファイルはシングルファイルにして Launch Single-File Source-Code Programs(JEP 330) で直接実行できるようにすることとします。
ソースは以下となります。
プログラミング言語
ここで扱う言語はシンプルな言語です。
キーワードは、関数を定義する 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
インタプリタ
インタプリタではソースコードを逐次実行して計算処理を行います。
これは、大きく以下の流れになります。
- ソースコードを字句解析器(Lexical Analyzer)にてトークン列に変換する
- トークン列を、言語の意味に合わせた抽象構文木(Abstract Syntax Tree)と呼ばれる木構造のデータ表現に変換する
- 抽象構文木を辿り評価する(計算処理を実行する)
ここでは、それぞれの処理を 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 を使ったインタプリタの実装について大枠の流れを説明しました。
以下のように動作します。
1,000 行に満たない実装なので、詳細は以下でソースを参照いただければと思います。
より詳しくは以下で読むことができます。

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