In the previous article, Supports while statements. Now I want to correspond to the variable Scope.
Confirm what you want to do with Scope support.
For example, there is the following program.
The variables ʻa, b, c are used inside and outside the f () function. Since the Scope changes inside and outside the function, ʻa and b declared with var inside the function are valid only inside the function.
Println (a) in the function outputs 10, and outside, the value 1 assigned by Global scope is output.
Similarly for b, 20 is output inside and 2 is output outside.
c is not declared inside the function and is a variable of Global scope both inside and outside.
println (c) prints 30 both inside and outside.
The var declaration allows you to assign variables, and separates them with, (comma) so that you can declare multiple variables at the same time.
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)
We will consider how to implement it in the order of parser and interpreter.
Since the concept of Scope itself is expressed inside or outside the function, From the perspective of analysis implementation If the function definition can be parsed, the concept of Scope can be supported.
The variable declaration var is newly introduced.
The keyword var comes at the beginning of the token sequence, so
[Parsing of function definition statements] implemented in the previous article (http://qiita.com/quwahara/items/be71bac4b4359f5e6727#%E6%A7%8B%E6%96%87%E8%A7%A3%E6% Implement in the same way as 9E%90parser%E3%81%AE%E5%AE%9F%E8%A3%85%E3%81%AE%E4%BB%95%E6%96%B9).
Introduces a class that represents the concept of Scope. The Scope class prepares field variables that can express the parent-child relationship so that the hierarchical structure of Scope can be expressed.
Creates a default Global scope when the interpreter starts. When calling a function, create a Scope in the function and make the Scope of the function caller the parent Scope of the Scope in the function. After calling the function, the scope in the function is discarded and the one that was the parent scope is returned to the current scope.
Move on to implementation. About parser and interpreter Let's take a look at the changes and additions in order.
Parser.java
An implementation of Parser.java.
Add a definition of how it works for the meaning of the token.
Since var is a reserved word, I added it to // 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[] { "+", "-", "!" });
// Update
reserved = Arrays.asList(new String[] { "function", "return", "if", "else", "while", "break", "var" });
}
It is a change of the part to be analyzed.
Added a function call to parse var to // Add.
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")) {
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.");
}
}
It is a change of the part to be analyzed.
Added a method var () to parse the var declaration.
The parsing result of the var declaration is summarized in the argument token.
The var () method parses the following patterns:
var → var avar a = 0, (comma) → var a = 0, bThe assignment to token.kind at the beginning of processing determines the meaning of the token to var.
token.block holds the parsed result.
Since multiple declarations can be made with , (comma), the analysis result is stored in token.block, which is a list that can hold multiple.
Performs analysis immediately after var.
Since var should always come with a variable name, request the variable name with ʻident (). If there is an assignment after the variable name, the =token will come. When a=token arrives, it is parsed in the same way as a binary operator, and the parsed result is stored intoken.block. If it is not a = token, the result of ʻident () is kept in token.block as it is.
After that, if there are , tokens, continue to parse them in the same way and keep them in token.block.
Parser.java
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
An implementation of Interpreter.java.
Introduced a class that represents Scope.
I'm porting the field variables functions and variables that were in the ʻInterpreterclass. To represent the hierarchical structure of Scope, we have a field variableparent` that represents the parent hierarchy.
Interpreter.java
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<>();
}
}
This is the initialization part.
The introduced Scope class is used as a field variable.
Prepare Scopes for global and local.
localScope allocates a new instance of the Scope class each time it is executed within a function.
Interpreter.java
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;
}
A change to the method body () that executes expressions sequentially.
Added a method call to handle var declarations at // <-Add.
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")) {
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;
}
The var () method that handles the var declaration.
Since multiple declarations are held in token.block, they are processed in order.
If the element of token.block is a token of the variable name, simply define the variable in Local scope.
If the element is a = token, use the variable name token of ʻitem.leftto define the variable to Local scope. Then execute the= token with ʻexpression (expr).
Interpreter.java
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;
}
This is a change of the ʻident ()method due to the introduction of Scope. Search for functions and variables defined in the while statement. From the Local scope, use theparent` field variable to go back to the higher Scope.
Interpreter.java
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);
}
This is a change of the func () method due to the introduction of Scope.
// Update The following are the changes.
From what was just an assignment of context to ʻinterpreter Changed to clone and assign ʻinterpreter. While statement searches for functions and variables.
From the Local scope, use the parent field variable to go back to the higher Scope.
Interpreter.java
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;
}
This is a change of the DynamicFunc class due to the introduction of Scope.
Before making a function call, create a new Scope with the current Local Scope as the parent Scope.
After the call, the Local scope is restored to the original Scope.
Define the formal argument in the new Scope and execute the processing block of the function.
Interpreter.java
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;
}
}
The program below using the above implementation
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)
Is executed, and the values of the variables ʻa, b, and c` for each Scope are output to the standard output.
Interpreter.java
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
}
That's all for the implementation. Thank you very much.
The full source is available here.
Calc https://github.com/quwahara/Calc/tree/article-13-scope-r3/Calc/src/main/java
There is a continuation article.
** Corresponds to a function expression ** http://qiita.com/quwahara/items/ae33ed944afc34cc5fac
Recommended Posts