はじめに
以前の記事で関数の戻り値に対応しました。
次はif文に対応したいと思います。
if文対応でやりたいこと
簡単にやりたいことを確認します。
例えば下のようなプログラムがあったら、初めのprintln()では3が出力され、
次のprintln()では4が出力されることを目指します。
簡単のためにif文の真偽の判定は、0以外が真、0が偽とします。
function f(a) {
if (a) {
return 3
} else {
return 4
}
}
println(f(1))
println(f(0))
実装の仕方
実装の仕方について、構文解析(Parser)、インタプリタ(Interpreter)と順に考えていきます。
字句解析(Lexer)はとくに変更しません。
構文解析(Parser)の実装の仕方
if文の構文解析の実装の仕方は、以前の記事で実装した関数定義文の構文解析と似ています。
はじめにキーワードifがあり、それに続くトークンの出現順序も決まっているので、順にトークンをなぞって解析します。
インタプリタ(Interpreter)の実装の仕方
インタプリタでは式を逐次実行するメソッドbody()で、
if文を処理するように変更します。
if文の中でreturnがあったときに、扱いやすいためです。
Javaで実装してみる
実装にうつります。
構文解析(Parser)、インタプリタ(Interpreter)について、
変更と追加をしたところを順にみていきます。
Parser.java
Parser.javaの実装です。
トークンの意味に対して、どう動作するかの定義を追加します。
ifとelseが予約語となるので、<-- Updateとあるところに追加しました。
public Parser() {
degrees = new HashMap<>();
degrees.put("(", 80);
degrees.put("*", 60);
degrees.put("/", 60);
degrees.put("+", 50);
degrees.put("-", 50);
degrees.put("=", 10);
factorKinds = Arrays.asList(new String[] { "digit", "ident" });
binaryKinds = Arrays.asList(new String[] { "sign" });
rightAssocs = Arrays.asList(new String[] { "=" });
unaryOperators = Arrays.asList(new String[] { "+", "-" });
reserved = Arrays.asList(new String[] { "function", "return", "if", "else" }); // <-- Update
}
解析を行う部分の変更です。
ifの解析を行う関数の呼び出しを<-- Addがある箇所へ加えました。
private Token lead(Token token) throws Exception {
if (token.kind.equals("ident") && token.value.equals("function")) {
return func(token);
} else if (token.kind.equals("ident") && token.value.equals("return")) {
token.kind = "ret";
if (!token().kind.equals("eob")) {
token.left = expression(0);
}
return token;
} else if (token.kind.equals("ident") && token.value.equals("if")) { // <-- Add
return if_(token);
} else if (factorKinds.contains(token.kind)) {
return token;
} else if (unaryOperators.contains(token.value)) {
token.kind = "unary";
token.left = expression(70);
return token;
} else if (token.kind.equals("paren") && token.value.equals("(")) {
Token expr = expression(0);
consume(")");
return expr;
} else {
throw new Exception("The token cannot place there.");
}
}
解析を行う部分の変更です。
if文の解析を行うメソッドif_()を追加しました。
if文の解析結果は引数のtokenにまとめられます。
まとめるにあたり、Tokenクラスへフィールド変数を追加しています。
追加したフィールド変数はblockOfElseです。
if文のelse側の処理ブロックを保持するために追加しました。
型はList<Token>になっています。
if_()メソッドでの処理は、if文定義のトークンを順になぞるようになっています。
最初にtoken.kindへの代入で、トークンの意味をifに決定します。
次に条件文の始まりの(を消費します。
expression()メソッドはif文の条件文を解析して、token.leftへ保持します。
次いで条件文の終わり)を消費します。
処理ブロックの解析です。
ブロックの始まりの{があれば、{トークンと}トークンで囲まれた
処理ブロックを解析するbody()メソッドを呼び出して、token.blockへ保持します。
ブロックの始まりの{がなければ、処理ブロックは1文だけだとみなして、token.blockへ保持します。
else側の処理ブロックの解析もほとんど同じです。
private Token if_(Token token) throws Exception {
token.kind = "if";
consume("(");
token.left = expression(0);
consume(")");
if (token().value.equals("{")) {
token.block = body();
} else {
token.block = new ArrayList<Token>();
token.block.add(expression(0));
}
if (token().value.equals("else")) {
consume("else");
if (token().value.equals("{")) {
token.blockOfElse = body();
} else {
token.blockOfElse = new ArrayList<Token>();
token.blockOfElse.add(expression(0));
}
}
return token;
}
{トークンと}トークンで囲まれた処理ブロックを解析します。
func()メソッドの処理ブロックを解析する箇所でも、
同じことをしていたので、このメソッドを呼ぶように変更しました。
private List<Token> body() throws Exception {
consume("{");
List<Token> block = block();
consume("}");
return block;
}
Interpreter.java
Interpreter.javaの実装です。
式を逐次実行するメソッドbody()への変更です。
// <-- Addの箇所へif文を処理するメソッドの呼び出しを追加しました。
if文の処理ブロックの中でreturnが呼ばれた場合に上位へ戻れるように、
ret[0]がtrueかを判定して、body()メソッドを中断します。
public Object body(List<Token> body, boolean[] ret) throws Exception {
for (Token exprs : body) {
if (exprs.kind.equals("if")) { // <-- Add
Object val = if_(exprs, ret);
if (ret != null && ret[0]) {
return val;
}
} else if (exprs.kind.equals("ret")) {
if (ret == null) {
throw new Exception("Can not return");
}
ret[0] = true;
if (exprs.left == null) {
return null;
} else {
return expression(exprs.left);
}
} else {
expression(exprs);
}
}
return null;
}
if文を実行するif_()メソッドです。
token.leftが条件式を保持しています。
isTrue()メソッドで、条件式が真かを判定します。
条件式が真ならtoken.blockを実行します。
偽ならtoken.blockOfElseを実行します。
public Object if_(Token token, boolean[] ret) throws Exception {
List<Token> block;
if (isTrue(token.left)) {
block = token.block;
} else {
block = token.blockOfElse;
}
if (block != null) {
return body(block, ret);
} else {
return null;
}
}
public boolean isTrue(Token token) throws Exception {
return 0 != value(expression(token));
}
以上の実装を使って下のプログラム
function f(a) {
if (a) {
return 3
} else {
return 4
}
}
println(f(1))
println(f(0))
を実行し、標準出力へ3と4を順にプリントします。
public static void main(String[] args) throws Exception {
String text = "";
text += "function f(a) {";
text += " if (a) {";
text += " return 3";
text += " } else {";
text += " return 4";
text += " }";
text += "}";
text += "println(f(1))";
text += "println(f(0))";
List<Token> tokens = new Lexer().init(text).tokenize();
List<Token> blk = new Parser().init(tokens).block();
new Interpreter().init(blk).run();
// --> 3
// --> 4
}
実装は以上です。
ありがとうございました。
おわりに
ソースの全文はこちらで公開しています。
Calc
https://github.com/quwahara/Calc/tree/article-10-if-r2/Calc/src/main/java
続きの記事があります。
比較演算子と論理演算子に対応する
http://qiita.com/quwahara/items/162d01c5af7c69cfa0ed