「Go 言語でつくるインタプリタ」では、Monkey という小さな言語のインタプリタを 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); } }
次回からは、いよいよ構文解析結果の評価に入っていきます。
と思いましたが、全体を以下でまとめて紹介します。