In the previous article, I added println to interpreter. Let's extend it a bit to allow function definitions and calls.
When implementing, make sure that you do what you want to do and what you do not do.
For example, if you have a program like the one below, the ʻaddV ()function will be defined and we aim to output3` to the standard output.
v = 0
function addV(num) {
v = v + num
}
addV(3)
println(v)
And I decide not to do it for the sake of simplicity. Only one function argument is supported. It does not support no arguments or more than one argument. It does not correspond to the return value of the function. Does not correspond to the scope of the variable. The variable name of the formal argument is also defined globally.
We will consider how to implement it in the order of lexical analysis (Lexer), parser (Parser), and interpreter (Interpreter).
The implemented lexical analysis does not have the ability to parse curly braces, { and }, so implement it.
First, consider an implementation that parses the function definition statement.
Observe the sequence of tokens in the function definition function addV (num) {} to think about how to implement it.
Observing it, you can see that the keyword function always comes at the beginning of the token sequence.
Considering if there is another pattern of similar sequence, where the token sequence comes first,
Consider whether it can be implemented in a form close to that.
With that in mind, the unary operators -1 and + 1 are close together.
This is because if the - or+of the token that comes first is determined, it will be determined as a unary operator.
It seems that parsing of function definitions can be implemented in a similar way.
Next, consider the implementation of parsing the statement of a function call.
The call has the same syntax structure as the previously implemented println (v).
Therefore, it is already implemented.
First, how to implement the function definition.
Introduced a class that represents a function when implementing println ().
The implementation of the println () function inherits from the Func class.
It seems that the implementation of the function definition in the interpreter should also inherit the Func class in the same way.
And if you come across the function definition part while the interpreter is running,
I will dynamically instantiate the inherited class.
Next is how to implement a function call.
As for the call, the implementation of println () can be used as it is, as in the case of parsing.
It is ready to be implemented.
Move on to implementation. About lexical analysis (Lexer), parser (Parser), interpreter (Interpreter) Let's take a look at the changes and additions in order.
Lexer.java
An implementation of Lexer.java.
First, add the function to parse parentheses, { and }.
The end of the curly braces } is treated specially as the end of the block, so
The meaning is ʻeob` (End of Block).
Lexer.java
private boolean isCurlyStart(char c) {
return c == '{' || c == '}';
}
private Token curly() throws Exception {
Token t = new Token();
if (c() == '{') {
t.kind = "curly";
} else {
t.kind = "eob";
}
t.value = Character.toString(next());
return t;
}
I will add the call part of the curly braces analysis. The implementation of Lexer.java is complete.
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 if (isCurlyStart(c())) {
return curly();
} else {
throw new Exception("Not a character for tokens");
}
}
Parser.java
An implementation of Parser.java.
First, add a definition of how it works for the meaning of the token.
Add a reserved that defines a reserved word at <-Add, and add a function to it.
Parser.java
private Map<String, Integer> degrees;
private List<String> factorKinds;
private List<String> binaryKinds;
private List<String> rightAssocs;
private List<String> unaryOperators;
private List<String> reserved; // <-- Add
public Parser() {
degrees = new HashMap<>();
degrees.put("(", 80);
degrees.put("*", 60);
degrees.put("/", 60);
degrees.put("+", 50);
degrees.put("-", 50);
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" }); // <-- Add
}
It is a change of the part to be analyzed.
Added a call to the method func () to parse the function definition to the if statement with <-Add.
Similar to the unary operation, the first token type determines the parsing method.
Parser.java
private Token lead(Token token) throws Exception {
if (token.kind.equals("ident") && token.value.equals("function")) { // <-- Add
return func(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.");
}
}
Added the method func () to parse the function definition.
The analysis result of the function definition is summarized in the argument token.
To summarize, we are adding a field variable to the Token class.
The added field variables are ʻident, param, block. ʻIdent holds a token that represents the function name.
param holds a token that represents a formal argument.
block holds the processing block of the function and its type isList <Token>.
The processing in the func () method traces the tokens in the function definition in order.
First, determine the meaning of the token with func.
Then get the function name by calling the ʻident () method. The ʻident () method verifies that the token means ʻidentand returns that token. Then it consumes the( at the beginning of the argument. Get the formal arguments again with the ʻident () method call.
It then consumes the ) at the end of the argument and the { at the beginning of the block.
For the contents of the block, the return value of the existing block () is assigned as it is.
Finally, consuming the } at the end of the block completes the parsing of the function definition.
The implementation of Parser.java is also complete.
Parser.java
private Token func(Token token) throws Exception {
token.kind = "func";
token.ident = ident();
consume("(");
token.param = ident();
consume(")");
consume("{");
token.block = block();
consume("}");
return token;
}
private Token ident() throws Exception {
Token id = next();
if (!id.kind.equals("ident")) {
throw new Exception("Not an identical token.");
}
if (reserved.contains(id.value)) {
throw new Exception("The token was reserved.");
}
return id;
}
Interpreter.java
An implementation of Interpreter.java.
Introduce a class DynamicFunc that represents a function.
It inherits from the Func class.
Field variables
Context to drive the interpreterparam which represents a formal argumentblockthere is.
The implementation of the ʻinvoke ()method resolves the argument as a value and keeps it in the value of the formal argument. In that state, let the interpretercontext execute block`.
Interpreter.java
public static class DynamicFunc extends Func {
public Interpreter context;
public Token param;
public List<Token> block;
@Override
public Object invoke(Object arg) throws Exception {
Variable v = context.variable(context.ident(param));
v.value = context.value(arg);
context.body(block);
return null;
}
}
It is a change of the part that calls the method that processes each token according to the meaning of the token.
Added function definition where <-Add is.
Interpreter.java
public Object expression(Token expr) throws Exception {
if (expr.kind.equals("digit")) {
return digit(expr);
} else if (expr.kind.equals("ident")) {
return ident(expr);
} else if (expr.kind.equals("func")) { // <-- Add
return func(expr);
} else if (expr.kind.equals("paren")) {
return invoke(expr);
} else if (expr.kind.equals("sign") && expr.value.equals("=")) {
return assign(expr);
} else if (expr.kind.equals("unary")) {
return unaryCalc(expr);
} else if (expr.kind.equals("sign")) {
return calc(expr);
} else {
throw new Exception("Expression error");
}
}
Implementation of the function definition part.
First, make sure that the function name and formal parameter name are not already used.
Generate a class DynamicFunc that represents a function and assign a value to a field variable.
The formal argument param is defined as a variable in advance,
Allocate the instance that represents the variable to the field variable.
Finally, add it to the Map that holds the function name and its value, and the function definition is completed.
Interpreter.java
public Object func(Token token) throws Exception {
String name = token.ident.value;
if (functions.containsKey(name)) {
throw new Exception("Name was used");
}
if (variables.containsKey(name)) {
throw new Exception("Name was used");
}
DynamicFunc func = new DynamicFunc();
func.context = this;
func.name = name;
func.param = token.param;
func.block = token.block;
functions.put(name, func);
return null;
}
The string in the program below using the above implementation
v = 0
function addV(num) {
v = v + num
}
addV(3)
println(v)
To print the value 3 assigned to the variable v to the standard output.
Interpreter.java
public static void main(String[] args) throws Exception {
String text = "";
text += "v = 0";
text += "function addV(num) {";
text += " v = v + num";
text += "}";
text += "addV(3)";
text += "println(v)";
List<Token> tokens = new Lexer().init(text).tokenize();
List<Token> blk = new Parser().init(tokens).block();
new Interpreter().init(blk).run();
// --> 3
}
}
That's all for the implementation. Thank you very much.
The full source is available here.
Calc https://github.com/quwahara/Calc/tree/article-7-function-r2/Calc/src/main/java
There is a continuation article.
** Corresponds to multiple arguments ** http://qiita.com/quwahara/items/0bea3bad4eedd2d803cf