In a previous article, I implemented parsing (http://qiita.com/quwahara/items/9bf468ff4286b28d2a24). By the way, I would like to use it to implement a simple interpreter.
Confirm what you want to do in implementation.
What we want to do with the interpreter is to calculate the programmed strings.
Considering the following formula as an example, we aim to finally have 23 assigned to ʻa`.
a = 3 + 4 * 5
Now let's think about how to calculate.
I parsed the expression in previous article.
The parsed expression was parsed so that the operator tokens left and right have values calculated by that operator.
For example, in the expression 6-7, the operator token is -, left has 6, right has 7, and so on.
Also, left and right may have not only values but also formulas that come first in the calculation order.
For example, the expression 3 + 4 * 5 has the operator token+, left has 3, and right has 4 * 5.
Since it has such a data structure, in order to calculate, go down the operator tokens left and right in order.
When you reach the terminal operator, calculate it.
Based on the calculation result, the operator one level higher is calculated.
Calculation can be performed by repeating this operation up to the top.
In the formula 3 + 4 * 5 in the previous example, the terminal operator is*of 4 * 5, so it is calculated to be 20.
The calculation result is used to calculate the operator + one level above.
Since left is 3 and right is the calculation result 20, it is added to 23 and the calculation is completed.
Move on to implementation. Let's take a look at the implementation of the interpreter.
First is the initialization part. Receives a list of tokens parsed by parsing. Calculate this token list. Also, since the interpreter corresponds to a variable, prepare a Map that holds the variable name and its value.
Interpreter.java
public class Interpreter {
public Map<String, Integer> variables;
List<Token> body;
public Interpreter init(List<Token> body) {
variables = new HashMap<>();
this.body = body;
return this;
}
This is a description of the part that starts the calculation.
run () calculates the token list body passed earlier and returns a variable Map that holds the calculation result.
Interpreter.java
public Map<String, Integer> run() throws Exception {
body(body);
return variables;
}
It is the explanation of the part to be calculated.
body () takes the token for one expression from the token list body passed earlier and passes it to ʻexpression ()` that processes the expression.
Interpreter.java
public void body(List<Token> body) throws Exception {
for (Token exprs : body) {
expression(exprs);
}
}
ʻExpression ()` calls the methods that process each token, depending on the meaning of the token, and returns the result as is.
Interpreter.java
public Object expression(Token expr) throws Exception {
if (expr.kind.equals("digit")) {
return digit(expr);
} else if (expr.kind.equals("variable")) {
return var(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");
}
}
digit () takes a numeric token and makes it ʻInteger`.
Interpreter.java
public Integer digit(Token token) {
return Integer.decode(token.value);
}
var () takes the token of the variable and makes it the variable name.
If the variable name is not registered in the variable Map, register the value with 0.
Interpreter.java
public Object var(Token token) {
String name = token.value;
if (!variables.containsKey(name)) {
variables.put(name, 0);
}
return name;
}
ʻAssign ()` assigns a value to a variable.
Interpreter.java
public String assign(Token expr) throws Exception {
String name = variable(expression(expr.left));
Integer value = value(expression(expr.right));
variables.put(name, value);
return name;
}
variable () is the process of ʻassign () and makes sure that the result of ʻexpr.left is the variable name.
Interpreter.java
public String variable(Object value) throws Exception {
if (value instanceof String) {
return (String) value;
} else {
throw new Exception("left value error");
}
}
value () is tailored to a numerical value that can be calculated by ʻexpr.right in the processing of ʻassign () and the processing of the four arithmetic operations described later.
If the argument value is ʻInteger, it is returned as is. If it is String`, the value is fetched from the variable Map and returned.
Interpreter.java
public Integer value(Object value) throws Exception {
if (value instanceof Integer) {
return (Integer) value;
} else if (value instanceof String) {
return variables.get((String) value);
} else {
throw new Exception("right value error");
}
}
calc () performs four arithmetic operations.
Interpreter.java
public Object calc(Token expr) throws Exception {
Integer left = value(expression(expr.left));
Integer right = value(expression(expr.right));
if (expr.value.equals("+")) {
return left + right;
} else if (expr.value.equals("-")) {
return left - right;
} else if (expr.value.equals("*")) {
return left * right;
} else if (expr.value.equals("/")) {
return left / right;
} else {
throw new Exception("Unknown sign for Calc");
}
}
Using the above implementation, the string that is the example program
a = 3 + 4 * 5
And print the variable and its value to standard output.
Interpreter.java
public static void main(String[] args) throws Exception {
String text = "a = 3 + 4 * 5";
List<Token> tokens = new Lexer().init(text).tokenize();
List<Token> blk = new Parser().init(tokens).block();
Map<String, Integer> variables = new Interpreter().init(blk).run();
for (Map.Entry<String, Integer> variable : variables.entrySet()) {
System.out.println(variable.getKey() + " " + variable.getValue());
}
// --> a 23
}
}
That's all for the implementation. Thank you very much.
The source is available here.
Calc https://github.com/quwahara/Calc/tree/article-3-interpreter/Calc/src/main/java
There is a continuation article.
** Add println to the interpreter ** http://qiita.com/quwahara/items/82067b00cbe1cb974e4a
Finally, I will give you a summary of the Interpreter classes.
Interpreter.java
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class Interpreter {
public Map<String, Integer> variables;
List<Token> body;
public Interpreter init(List<Token> body) {
variables = new HashMap<>();
this.body = body;
return this;
}
public Map<String, Integer> run() throws Exception {
body(body);
return variables;
}
public void body(List<Token> body) throws Exception {
for (Token exprs : body) {
expression(exprs);
}
}
public Object expression(Token expr) throws Exception {
if (expr.kind.equals("digit")) {
return digit(expr);
} else if (expr.kind.equals("variable")) {
return var(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");
}
}
public Integer digit(Token token) {
return Integer.decode(token.value);
}
public Object var(Token token) {
String name = token.value;
if (!variables.containsKey(name)) {
variables.put(name, 0);
}
return name;
}
public String assign(Token expr) throws Exception {
String name = variable(expression(expr.left));
Integer value = value(expression(expr.right));
variables.put(name, value);
return name;
}
public String variable(Object value) throws Exception {
if (value instanceof String) {
return (String) 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 String) {
return variables.get((String) value);
} else {
throw new Exception("right value error");
}
}
public Object calc(Token expr) throws Exception {
Integer left = value(expression(expr.left));
Integer right = value(expression(expr.right));
if (expr.value.equals("+")) {
return left + right;
} else if (expr.value.equals("-")) {
return left - right;
} else if (expr.value.equals("*")) {
return left * right;
} else if (expr.value.equals("/")) {
return left / right;
} else {
throw new Exception("Unknown sign for Calc");
}
}
public static void main(String[] args) throws Exception {
String text = "a = 3 + 4 * 5";
List<Token> tokens = new Lexer().init(text).tokenize();
List<Token> blk = new Parser().init(tokens).block();
Map<String, Integer> variables = new Interpreter().init(blk).run();
for (Map.Entry<String, Integer> variable : variables.entrySet()) {
System.out.println(variable.getKey() + " " + variable.getValue());
}
// --> a 23
}
}
Recommended Posts