はじめに
以前の記事でインタプリタを実装しました。
インタプリタで四則演算はできるようになりましたが、計算結果は表示できません。
それではさびしいので計算結果を表示するprintlnを追加してみます。
printlnの追加でやりたいこと
実装にあたり、具体的にやりたいことを確認します。
例えば下のようなプログラムがあったら、標準出力に1と改行が出力できることを目指します。
println(1)
また2を代入した変数をprintln()の引数に指定されたら、その内容2が標準出力に改行と出力できることを目指します。
a = 2
println(a)
実装の仕方
これまでで字句解析(Lexer)、構文解析(Parser)、インタプリタ(Interpreter)を実装しました。
それぞれについて順に実装の仕方を考えていきます。
字句解析(Lexer)への実装の仕方
実装した字句解析には括弧、(と)を解析する機能がありません。
まずはそれを追加します。
また字句解析の仕様でアルファベットの並びは変数名(variable)だと意味付けしていました。
しかしアルファベットの並びの１つであるprintlnは変数名ではなく関数名です。
アルファベットの並びという事実だけでは、変数名か関数名かは決まらなくなりました。
そのためアルファベット並びの意味付けを、識別子(ident)へ変更します。
構文解析(Parser)の実装の仕方
実装の仕方を考えるために、まずprintln(1)呼び出しのトークンの並びをよく観察します。
次の4つのトークンへ分解されます。
-
printlnと(と1と)
この並びはa + 1の並びと似たものになっています。
それを見ていきます。
a + 1も同じようにトークンの並びにしてみます。
-
aと+と1
それらを対比させてみます。
-
println→a→ どちらも識別子 -
(→+→ どちらも記号 -
1→１→ どちらも数字 -
)→ 対応なし
a + 1の構文解析は+を真ん中にして、左右にくるトークンを割り付けました。
対比を観察するとprintln(1)も(を真ん中にして、左右にくるトークンがくる構図になっています。
その観察結果から、println(1)を構文解析するには、a + 1を解析刷るように処理して、最後に)トークンがくることを確認すれば構文解析できそうです。
つまり演算子トークンへの構文解析を少し変形してあげれば実装できそうです。
また、先の字句解析の実装の仕方であげた、変数名(variable)から識別子(ident)への変更にも対応します。
インタプリタ(Interpreter)の実装の仕方
println(1)呼び出しを実装するにあたり問題点として、インタプリタでは暗黙的に変数名(variable)をStringで表していました。
いままでは関数名がある可能性がなかったのでそれでよかったのですが、今度は変数名と関数名を区別しなければなりません。
そのため変数名と関数名を表すクラスを、それぞれに導入してあげます。
また構文解析の実装の仕方で観察したように、(がprintln(1)呼び出しのキーになるトークンです。
(トークンに出会ったら、それを処理するメソッドを呼び出すように仕向けます。
最後にこちらでも、先の字句解析の実装の仕方であげた、変数名(variable)から識別子(ident)への変更にも対応します。
Javaで実装してみる
実装にうつります。
こちらもでも字句解析(Lexer)、構文解析(Parser)、インタプリタ(Interpreter)の、
それぞれについて、変更と追加をしたところを順にみていきます。
Lexer.java
Lexer.javaの実装です。
まずは括弧、(と)を解析する機能の追加です。
private boolean isParenStart(char c) {
return c == '(' || c == ')';
}
private Token paren() throws Exception {
Token t = new Token();
t.kind = "paren";
t.value = Character.toString(next());
return t;
}
続いて、変数名(variable)から識別子(ident)への変更への対応です。
private boolean isIdentStart(char c) throws Exception {
return Character.isAlphabetic(c);
}
private Token ident() throws Exception {
StringBuilder b = new StringBuilder();
b.append(next());
while (!isEOT() && (Character.isAlphabetic(c()) || Character.isDigit(c()))) {
b.append(next());
}
Token t = new Token();
t.kind = "ident";
t.value = b.toString();
return t;
}
最後に、括弧の解析の呼び出し部分の追加と、identへの変更の呼び出し部分を修正してあげれば、
Lexer.javaの実装は終了です。
public Token nextToken() throws Exception {
skipSpace();
if (isEOT()) {
return null;
} else if (isSignStart(c())) {
return sign();
} else if (isDigitStart(c())) {
return digit();
} else if (isIdentStart(c())) {
return ident();
} else if (isParenStart(c())) {
return paren();
} else {
throw new Exception("Not a character for tokens");
}
}
Parser.java
Parser.javaの実装です。
まずトークンの意味に対して、どう動作するかの定義を変更します。
<-- Addの箇所で演算子順序の度合いを定義するdegreesへ(を追加します。
(も演算子のように扱うための対応です。
println()は、他の演算子よりも優先的に結合させたいので、その度合を80にします。
<-- Updateの箇所でidentへの変更に対応します。
public Parser() {
degrees = new HashMap<>();
degrees.put("(", 80); // <-- Add
degrees.put("*", 60);
degrees.put("/", 60);
degrees.put("+", 50);
degrees.put("-", 50);
degrees.put("=", 10);
factorKinds = Arrays.asList(new String[] { "digit", "ident" }); // <-- Update
binaryKinds = Arrays.asList(new String[] { "sign" });
rightAssocs = Arrays.asList(new String[] { "=" });
}
解析を行う部分の変更です。
解析を行う処理を<-- Addがあるif文の箇所へ加えました。
operator.leftとoperator.rightへトークンを割り付けるところは、元々あった上にあるif文の演算子の解析とほとんど同じです。
operator.right = expression(0);のexpression()の引数が上のif文と違って0なのは、
関数の引数として、式を１つ独立してとるためで、先行や後続の演算子と優先順位を比較する必然性がないからです。
consume()は次にくるトークンが閉じ括弧であることを確認して、解析で注目するトークンを次へ進めます。
Parser.javaの実装は終了です。
private Token bind(Token left, Token operator) throws Exception {
if (binaryKinds.contains(operator.kind)) {
operator.left = left;
int leftDegree = degree(operator);
if (rightAssocs.contains(operator.value)) {
leftDegree -= 1;
}
operator.right = expression(leftDegree);
return operator;
} else if(operator.kind.equals("paren") && operator.value.equals("(")) { // <-- Add
operator.left = left;
operator.right = expression(0);
consume(")");
return operator;
} else {
throw new Exception("The token cannot place there.");
}
}
private Token consume(String expectedValue) throws Exception {
if (!expectedValue.equals(token().value)) {
throw new Exception("Not expected value");
}
return next();
}
Interpreter.java
Interpreter.javaの実装です。
まずは変数名と関数名を区別するために、それぞれを表すクラスを導入します。
関数の方は今後の拡張を考えて、抽象クラスにしておきます。
invoke()メソッドで実際に関数が行う処理を実装します。
public static class Variable {
public String name;
public Integer value;
@Override
public String toString() {
return name + " " + value;
}
}
public static abstract class Func {
public String name;
abstract public Object invoke(Object arg) throws Exception;
}
public static class Println extends Func {
public Println() {
name = "println";
}
@Override
public Object invoke(Object arg) throws Exception {
System.out.println(arg);
return null;
}
}
初期化部分の変更です。
関数に対応するのに、関数名とその値を保持するMapを追加しました。
そこへprintln()の実体を追加します。
public class Interpreter {
public Map<String, Func> functions;
public Map<String, Variable> variables;
List<Token> body;
public Interpreter init(List<Token> body) {
functions = new HashMap<>();
Func f = new Println();
functions.put(f.name, f);
variables = new HashMap<>();
this.body = body;
return this;
}
トークンの意味によって、それぞれを処理するメソッドを呼び分ける部分の変更です。
関数呼び出しを<-- Addがある箇所へ加えました。
identへの変更を<-- Updateがある箇所にしています。
public Object expression(Token expr) throws Exception {
if (expr.kind.equals("digit")) {
return digit(expr);
} else if (expr.kind.equals("ident")) { // <-- Update
return ident(expr);
} else if (expr.kind.equals("paren")) { // <-- Add
return invoke(expr);
} else if (expr.kind.equals("sign") && expr.value.equals("=")) {
return assign(expr);
} else if (expr.kind.equals("sign")) {
return calc(expr);
} else {
throw new Exception("Expression error");
}
}
var()をident()へ変更しました。
識別子が関数名なら関数へ解決します。
そうでなければ変数へ解決します。
public Object ident(Token token) {
String name = token.value;
if (functions.containsKey(name)) {
return functions.get(name);
}
if (variables.containsKey(name)) {
return variables.get(name);
} else {
Variable v = new Variable();
v.name = name;
v.value = 0;
variables.put(name, v);
return v;
}
}
次のメッドでは変数名を表すために導入したVariableクラスへ対応しています。
public Variable assign(Token expr) throws Exception {
Variable variable = variable(expression(expr.left));
Integer value = value(expression(expr.right));
variable.value = value;
return variable;
}
public Variable variable(Object value) throws Exception {
if (value instanceof Variable) {
return (Variable) value;
} else {
throw new Exception("left value error");
}
}
public Integer value(Object value) throws Exception {
if (value instanceof Integer) {
return (Integer) value;
} else if (value instanceof Variable) {
Variable v = (Variable) value;
return v.value;
}
throw new Exception("right value error");
}
invoke()は関数呼び出しを実行します。
この記事でやりたかったことです。
func()はinvoke()の処理で、expr.leftの結果が関数名であることを確かめます。
private Object invoke(Token expr) throws Exception {
Func f = func(expression(expr.left));
Integer value = value(expression(expr.right));
return f.invoke(value);
}
public Func func(Object value) throws Exception {
if (value instanceof Func) {
return (Func) value;
} else {
throw new Exception("Not a function");
}
}
以上の実装を使って下のプログラムになっている文字列
a = 3 + 4 * 5
println(a)
を計算し、変数へ代入された値を標準出力へプリントします。
public static void main(String[] args) throws Exception {
String text = "a = 3 + 4 * 5";
text += "println(a)";
List<Token> tokens = new Lexer().init(text).tokenize();
List<Token> blk = new Parser().init(tokens).block();
new Interpreter().init(blk).run();
// --> 23
}
}
実装は以上です。
ありがとうございました。
おわりに
ソースの全文はこちらで公開しています。
Calc
https://github.com/quwahara/Calc/tree/article-4-interpreter/Calc/src/main/java
続きの記事があります。
優先順位付けの括弧に対応する
http://qiita.com/quwahara/items/b76c6e438aeb32450391