Java 言語でつくるインタプリタ
「Go 言語でつくるインタプリタ」では、Monkey という小さな言語のインタプリタを Go で実装する過程が書かれています。
あくまで教育目的として、字句解析〜構文解析〜評価 までをシンプルな実装で丁寧に解説しています。
- 作者:Thorsten Ball
- 出版社/メーカー: オライリージャパン
- 発売日: 2018/06/16
- メディア: 単行本(ソフトカバー)
ここでは、Go で写経するだけなのも面白みが無いので、「Go 言語でつくるインタプリタ」の流れを Java に変換しつつ紹介してみます。
前回
までで作成した字句解析の結果を、構文解析器に通し、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;")); } }
次回は演算子の構文解析となります。