はじめに
以前の記事でwhile文に対応しました。
今度は変数のScopeに対応したいと思います。
Scope対応でやりたいこと
Scope対応でやりたいことを確認します。
例えば下のようなプログラムがあります。
変数a、b、cがf()関数の内と外で使われています。
関数の内と外ではScopeが変わるので、関数内でvarで宣言されているa、bは、関数内でのみ有効です。
関数内でのprintln(a)は10が出力され、外ではGlobal scopeで代入した値1が出力されます。
bも同じように内では20、外で2が出力されます。
cは関数内で宣言されておらず、内でも外でもGlobal scopeの変数になります。
println(c)は内でも外でも30が出力されます。
var宣言では変数の代入をできることにし、,(カンマ)で区切って複数の変数を同時に宣言できようにします。
a = 1
b = 2
c = 3
function f() {
var a = 10, b
b = 20
c = 30
println(a)
println(b)
println(c)
}
f()
println(a)
println(b)
println(c)
実装の仕方
実装の仕方について、構文解析(Parser)、インタプリタ(Interpreter)と順に考えていきます。
構文解析(Parser)の実装の仕方
Scopeの概念そのものは、関数の内か外かで表現されているので、
解析実装の視点から考えると、
関数定義が解析できていれば、Scopeの概念にも対応できています。
変数宣言のvarは新しく導入されました。
キーワードvarはトークンの並びの始めにくるので、
以前の記事で実装した関数定義文の構文解析と同じように実装します。
インタプリタ(Interpreter)の実装の仕方
Scopeの概念を表すクラスを導入します。
ScopeクラスはScopeの階層構造を表せるように、親子関係を表現できるフィールド変数を用意します。
インタプリタの起動時には既定のGlobal scopeを作ります。
関数呼び出し時には、その関数内のScopeを作り、関数呼び出し元のScopeを関数内Scopeの親Scopeにします。
関数呼び出し後は関数内Scopeを破棄して、親Scopeにしていたものを現状のScopeに戻します。
Javaで実装してみる
実装にうつります。
構文解析(Parser)、インタプリタ(Interpreter)について、
変更と追加をしたところを順にみていきます。
Parser.java
Parser.javaの実装です。
トークンの意味に対して、どう動作するかの定義を追加します。
varが予約語となるので// Updateのところへ加えました。
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[] { "+", "-", "!" });
// Update
reserved = Arrays.asList(new String[] { "function", "return", "if", "else", "while", "break", "var" });
}
解析を行う部分の変更です。
varの解析を行う関数の呼び出しを// 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")) {
return if_(token);
} else if (token.kind.equals("ident") && token.value.equals("while")) {
return while_(token);
} else if (token.kind.equals("ident") && token.value.equals("break")) {
token.kind = "brk";
return token;
// Add
} else if (token.kind.equals("ident") && token.value.equals("var")) {
return var(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.");
}
}
解析を行う部分の変更です。
var宣言の解析を行うメソッドvar()を追加しました。
var宣言の解析結果は引数のtokenにまとめられます。
var()メソッドでは次のパターンの解析を行います。
-
varの後に変数名がある →var a - さらに変数へ代入している →
var a = 0 -
,(カンマ)で複数の変数を宣言している →var a = 0, b
処理始めのtoken.kindへの代入で、トークンの意味をvarに決定します。
token.blockは解析した結果を保持します。
,(カンマ)で複数の宣言ができるので、複数が保持できるリストになっているtoken.blockに解析結果を保持します。
varの直後の解析を行います。
varは必ず変数名がくるはずなのでident()で変数名を要求します。
変数名のあとに代入があるときは=トークンがきます。
=トークンがきたときは、二項演算子と同じように解析して、その解析結果をtoken.blockに保持します。
=トークンでないときは、ident()の結果をそのままtoken.blockに保持します。
その後,トークンがあれば、続けて同じように解析して、token.blockに保持します。
private Token var(Token token) throws Exception {
token.kind = "var";
token.block = new ArrayList<Token>();
Token item;
Token ident = ident();
if (token().value.equals("=")) {
Token operator = next();
item = bind(ident, operator);
} else {
item = ident;
}
token.block.add(item);
while (token().value.equals(",")) {
next();
ident = ident();
if (token().value.equals("=")) {
Token operator = next();
item = bind(ident, operator);
} else {
item = ident;
}
token.block.add(item);
}
return token;
}
Interpreter.java
Interpreter.javaの実装です。
Scopeを表すクラスを導入しました。
Interpreterクラスにあったフィールド変数のfunctionsとvariablesを移植しています。
Scopeの階層構造を表すために、親階層を表すフィールド変数parentを持っています。
public static class Scope {
public Scope parent;
public Map<String, Func> functions;
public Map<String, Variable> variables;
public Scope() {
functions = new HashMap<>();
variables = new HashMap<>();
}
}
初期化の部分です。
導入したScopeクラスをフィールド変数にしています。
globalとlocalのScopeを用意します。
localScopeは関数内へ実行がうつるごとに、新しいScopeクラスのインスタンスを割り付けます。
Scope global;
Scope local;
List<Token> body;
public Interpreter init(List<Token> body) {
global = new Scope();
local = global;
Func f = new Println();
global.functions.put(f.name, f);
this.body = body;
return this;
}
式を逐次実行するメソッドbody()への変更です。
// <-- Addのところへvar宣言を処理するメソッドの呼び出しを追加しました。
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")) {
Object val = while_(exprs, ret);
if (ret != null && ret[0]) {
return val;
}
} else if (exprs.kind.equals("brk")) {
if (brk == null) {
throw new Exception("Can not break");
}
brk[0] = true;
return null;
} else if (exprs.kind.equals("var")) { // <-- Add
var(exprs);
} else {
expression(exprs);
}
}
return null;
}
var宣言を処理するvar()メソッドです。
token.blockに複数の宣言が保持されているので順に処理します。
token.blockの要素が変数名のトークンだったら、単純にLocal scopeへ変数を定義します。
要素が=トークンだったら、item.leftの変数名トークンを使ってLocal scopeへ変数を定義します。
その後、=トークンをexpression(expr)で実行します。
public Object var(Token token) throws Exception {
for (Token item : token.block) {
String name;
Token expr;
if (item.kind.equals("ident")) {
name = item.value;
expr = null;
} else if (item.kind.equals("sign") && item.value.equals("=")) {
name = item.left.value;
expr = item;
} else {
throw new Exception("var error");
}
if (!local.variables.containsKey(name)) {
newVariable(name);
}
if (expr != null) {
expression(expr);
}
}
return null;
}
public Variable newVariable(String name) {
Variable v = new Variable();
v.name = name;
v.value = 0;
local.variables.put(name, v);
return v;
}
Scope導入によるident()メソッドの変更です。
while文で関数や変数が定義されていないか探索します。
Local scopeから、parentフィールド変数を使って、上位のScopeへさかのぼります。
public Object ident(Token token) {
String name = token.value;
Scope scope = local;
while (scope != null) {
if (scope.functions.containsKey(name)) {
return scope.functions.get(name);
}
if (scope.variables.containsKey(name)) {
return scope.variables.get(name);
}
scope = scope.parent;
}
return newVariable(name);
}
Scope導入によるfunc()メソッドの変更です。
// Update以下が変更箇所です。
contextを単なるinterpreterの代入だったものから、
interpreterをクローンして代入するように変更しましたwhile文で関数や変数が定義されていないか探索します。
Local scopeから、parentフィールド変数を使って、上位のScopeへさかのぼります。
public Object func(Token token) throws Exception {
String name = token.ident.value;
if (local.functions.containsKey(name)) {
throw new Exception("Name was used");
}
if (local.variables.containsKey(name)) {
throw new Exception("Name was used");
}
List<String> paramCheckList = new ArrayList<String>();
for (Token p : token.params) {
String param = p.value;
if (paramCheckList.contains(param)) {
throw new Exception("Parameter name was used");
}
paramCheckList.add(param);
}
DynamicFunc func = new DynamicFunc();
// Update
func.context = new Interpreter();
func.context.global = global;
func.context.local = local;
func.context.body = body;
func.name = name;
func.params = token.params;
func.block = token.block;
local.functions.put(name, func);
return null;
}
Scope導入によるDynamicFuncクラスの変更です。
関数呼び出しをする前に、現状のLocal Scopeを親Scopeとする、新しいScopeを生成します。
呼び出し後はLocal scopeを元のScopeに復帰します。
仮引数を新しいScopeに定義して、関数の処理blockを実行します。
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 {
Scope parent = context.local;
context.local = new Scope();
context.local.parent = parent;
for (int i = 0; i < params.size(); ++i) {
Token param = params.get(i);
Variable v = context.newVariable(param.value);
if (i < args.size()) {
v.value = context.value(args.get(i));
} else {
v.value = null;
}
}
Object val;
boolean[] ret = new boolean[1];
val = context.body(block, ret, null);
context.local = parent;
return val;
}
}
以上の実装を使って下のプログラム
a = 1
b = 2
c = 3
function f() {
var a = 10, b
b = 20
c = 30
println(a)
println(b)
println(c)
}
f()
println(a)
println(b)
println(c)
を実行し、Scopeごとの変数a、b、cの値を標準出力へ出力します。
public static void main(String[] args) throws Exception {
String text = "";
text += "a = 1";
text += "b = 2";
text += "c = 3";
text += "function f() {";
text += " var a = 10, b";
text += " b = 20";
text += " c = 30";
text += " println(a)";
text += " println(b)";
text += " println(c)";
text += "}";
text += "f()";
text += "println(a)";
text += "println(b)";
text += "println(c)";
List<Token> tokens = new Lexer().init(text).tokenize();
List<Token> blk = new Parser().init(tokens).block();
new Interpreter().init(blk).run();
// --> 10
// --> 20
// --> 30
// --> 1
// --> 2
// --> 30
}
実装は以上です。
ありがとうございました。
おわりに
ソースの全文はこちらで公開しています。
Calc
https://github.com/quwahara/Calc/tree/article-13-scope-r3/Calc/src/main/java
続きの記事があります。
関数式に対応する
http://qiita.com/quwahara/items/ae33ed944afc34cc5fac