Edited at

12 while文に対応する

More than 1 year has passed since last update.


はじめに

以前の記事で比較演算子と論理演算子や、if文に対応しました。

その延長でwhile文に対応したいと思います。


while文対応でやりたいこと

簡単にやりたいことを確認します。

例えば下のようなプログラムがあったら、

while文で繰り返し、vになったところで繰り返しをぬけて、println()が出力されことを目指します。

v = 0

while (v < 4) {
v = v + 1
if (v == 2) {
break
}
}
println(v)


実装の仕方

実装の仕方ですが、

while文の実装はif文の対応とほとんど同じで、

break文の実装は関数の戻り値対応とほとんど同じとなっています。

なので詳しい説明はそちらを参照して頂いて、早速実装してみましょう。


Javaで実装してみる

実装にうつります。

構文解析(Parser)、インタプリタ(Interpreter)について、

変更と追加をしたところを順にみていきます。


Parser.java

Parser.javaの実装です。

トークンの意味に対して、どう動作するかの定義を追加します。

whilebreakが予約語となるので、<-- Updateのところへ加えました。


Parser.java

    public Parser() {

degrees = new HashMap<>();
degrees.put("(", 80);
degrees.put("*", 60);
degrees.put("/", 60);
degrees.put("+", 50);
degrees.put("-", 50);
degrees.put("==", 40);
degrees.put("!=", 40);
degrees.put("<", 40);
degrees.put("<=", 40);
degrees.put(">", 40);
degrees.put(">=", 40);
degrees.put("&&", 30);
degrees.put("||", 30);
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", "while", "break"}); // <-- Update
}

解析を行う部分の変更です。

whileの解析を行う関数の呼び出しをはじめの<-- Addのところへ加えました。

breakの解析を2つめの<-- Addのところへ加えました。

breakの解析はtoken.kindへの代入で、トークンの意味をbrkに決定して終わりです。


Parser.java

    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")) {
return if_(token);
} else if (token.kind.equals("ident") && token.value.equals("while")) { // <-- Add
return while_(token);
} else if (token.kind.equals("ident") && token.value.equals("break")) { // <-- Add
token.kind = "brk";
return 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.");
}
}

解析を行う部分の変更です。

while文の解析を行うメソッドwhile_()を追加しました。

前述したようにif文の解析を、単純にした説明になります。

while文の解析結果は引数のtokenにまとめられます。

while_()メソッドでの処理は、while文定義のトークンを順になぞるようになっています。

最初にtoken.kindへの代入で、トークンの意味をwhileに決定します。

次に条件文の始まりの(を消費します。

expression()メソッドはwhile文の条件文を解析して、token.leftへ保持します。

次いで条件文の終わり)を消費します。

処理ブロックの解析です。

ブロックの始まりの{があれば、{トークンと}トークンで囲まれた

処理ブロックを解析するbody()メソッドを呼び出して、token.blockへ保持します。

ブロックの始まりの{がなければ、処理ブロックは1文だけだとみなして、token.blockへ保持します。


Parser.java

    private Token while_(Token token) throws Exception {

token.kind = "while";
consume("(");
token.left = expression(0);
consume(")");
if (token().value.equals("{")) {
token.block = body();
} else {
token.block = new ArrayList<Token>();
token.block.add(expression(0));
}
return token;
}


Interpreter.java

Interpreter.javaの実装です。

式を逐次実行するメソッドbody()への変更です。

body()のシグニチャーにboolean[] brkを加えました。

brkの役割りは2つです。

1つめはbrknullでないなら、breakが可能な状況であることを表します。

2つめはbreakにであったら、呼び出し元にもbreakにであったことを伝播します。

brkbooleanの配列型にしたのは、呼び出し元に値を返すためです。

// <-- Add 2のところで逐次実行するトークンがbreakかを判定します。

トークンがbreakならbreak可能な状況か判定します。

brkbreakにであったことを呼び出し元に伝えるためにtrueを代入します。

// <-- Add 1のところへwhile文を処理するメソッドの呼び出しを追加しました。

while文の処理ブロックの中でreturnが呼ばれた場合に上位へ戻れるように、

ret[0]trueかを判定して、body()メソッドを中断します。


Interpreter.java

    public Object body(List<Token> body, boolean[] ret, boolean[] brk) throws Exception {

for (Token exprs : body) {
if (exprs.kind.equals("if")) {
Object val = if_(exprs, ret, brk);
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 if (exprs.kind.equals("while")) { // <-- Add 1
Object val = while_(exprs, ret);
if (ret != null && ret[0]) {
return val;
}
} else if (exprs.kind.equals("brk")) { // <-- Add 2
if (brk == null) {
throw new Exception("Can not break");
}
brk[0] = true;
return null;
} else {
expression(exprs);
}
}
return null;
}

while文を実行するwhile_()メソッドです。

token.leftが条件式を保持しています。

isTrue()メソッドで、条件式が真かを判定します。

条件式が真のあいだはtoken.blockを繰り返します。

ただし条件式が真であっても、body()メソッド呼び出し内で、

returnbreakトークンにであったら繰り返しは中断します。


Interpreter.java

    public Object while_(Token token, boolean[] ret) throws Exception {

boolean[] brk = new boolean[1];
Object val;
while (isTrue(token.left)) {
val = body(token.block, ret, brk);
if (ret != null && ret[0]) {
return val;
}
if (brk[0]) {
return null;
}
}
return null;
}

続いてbody()メソッドのシグニチャーを変更したことへの対応です。

if文内でもbreakが呼ばれることがあります。

そのためif_()メソッドのシグニチャーにもbrk仮引数を追加して、

body()メソッドの呼び出しではそれを渡します。


Interpreter.java

    public Object if_(Token token, boolean[] ret, boolean[] brk) throws Exception {

List<Token> block;
if (isTrue(token.left)) {
block = token.block;
} else {
block = token.blockOfElse;
}
if (block != null) {
return body(block, ret, brk);
} else {
return null;
}
}

引き続きbody()メソッドのシグニチャーを変更したことへの対応です。

<-- Updateにあるbody()メソッドの呼び出しでは、

break呼び出しが行えない文脈での処理なので

body()メソッドの引数brknullで呼び出します。


Interpreter.java

    public Map<String, Variable> run() throws Exception {

body(body, null, null); // <-- Update
return variables;
}

public static class DynamicFunc extends Func {

public Interpreter context;
public List<Token> params;
public List<Token> block;

@Override
public Object invoke(List<Object> args) throws Exception {
for (int i = 0; i < params.size(); ++i) {
Token param = params.get(i);
Variable v = context.variable(context.ident(param));
if (i < args.size()) {
v.value = context.value(args.get(i));
} else {
v.value = null;
}
}
boolean[] ret = new boolean[1];
return context.body(block, ret, null); // <-- Update
}
}


以上の実装を使って下のプログラム

v = 0

while (v < 4) {
v = v + 1
if (v == 2) {
break
}
}
println(v)

を実行し、標準出力へ2を順にプリントします。


Interpreter.java

    public static void main(String[] args) throws Exception {

String text = "";
text += "v = 0";
text += "while (v < 4) {";
text += " v = v + 1";
text += " if (v == 2) {";
text += " break";
text += " }";
text += "}";
text += "println(v)";
List<Token> tokens = new Lexer().init(text).tokenize();
List<Token> blk = new Parser().init(tokens).block();
new Interpreter().init(blk).run();
// --> 2
}

実装は以上です。

ありがとうございました。


おわりに

ソースの全文はこちらで公開しています。

Calc

https://github.com/quwahara/Calc/tree/article-12-while-r2/Calc/src/main/java

続きの記事があります。

Scopeに対応する

http://qiita.com/quwahara/items/d9f932195da1b655b617