Last time, make a language! I even thought about the grammar of a simple calculator in Making a simple calculator ①. This time, let's make it a program that actually works.
When you enter the formula in the console, it will be calculated and the numerical value will be displayed.
> 2 + 3 * 5
17
> 100 * 1.08
108.00
I will describe the above four points. How to write JavaCC in detail https://javacc.org/javaccgrm ↑ It is written on the site (English).
The following BNF that was defined last time was defined as follows.
BNF with a simple formula
<formula> ::= <加算formula>
<Addition formula> ::= <Multiplication formula> ( <Addition operator> <Multiplication formula> )*
<Multiplication formula> ::= <Monomial> ( <Multiplication operator> <Monomial> )*
<Monomial> ::= <Open brackets> <formula> <Closing brackets> | <Decimal representation>
<Addition operator> ::= "+" | "-"
<Multiplication operator> ::= "*" | "/" | "%"
<Open brackets> ::= "("
<Closing brackets> ::= ")"
<Decimal representation> ::= (<Numbers>)+ ("." (<Numbers>)+)?
<Numbers> ::= "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" | "0"
I will put this in the JJT file in order.
First, let's define the
< ADD_OP : "+"|"-" >
It is described as. The meaning of the symbols is almost the same as the explanation of the symbols used in BNF. http://qiita.com/toru0408/items/9d7263bce7f9a4bdce13#bnf Please refer to. If you replace everything with the javacc description in this way
< ADD_OP : "+" | "-" >
< MUL_OP : "*" | "/" | "%" >
< OPEN_BRACKET : "(" >
< CLOSE_BRACKET : ")" >
< DECIMAL : (< DIGIT >)+ ("." (< DIGIT >)+)? >
< DIGIT : [ "0"-"9" ] >
It will be. [" 0 "-" 9 "] refers to all characters from "0" to "9" in the character code table.
You can also write [" 0 "," 1 "," 2 "," 3 "," 4 "," 5 "," 6 "," 7 "," 8 "," 9 "] ,
Here, "0", "1", ... "9" are lined up in succession on the character code, so you can write [" 0 "-" 9 "]. Similarly, uppercase and lowercase letters can be written as ["a "-" z "," A "-" Z "].
Finally, it is completed by enclosing it in TOKEN {}.
TOKEN :
{
< ADD_OP : "+" | "-" >
| < MUL_OP : "*" | "/" | "%" >
| < OPEN_BRACKET : "(" >
| < CLOSE_BRACKET : ")" >
| < DECIMAL : (< DIGIT >)+ ("." (< DIGIT >)+)? >
| < DIGIT : [ "0"-"9" ] >
}
Actually, I haven't defined the hidden words. For example, spaces and tabs. It is also necessary to write the processing when the lexical analyzer encounters these characters. This time, these characters are ignored (behavior does not change with or without them), so write the following.
SKIP :
{
" "
| "\t"
| "\r"
}
(The line feed character will be used later as a delimiter, so it will not be ignored.)
<formula> ::= <加算formula>
This BNF can be written as:
void Expr() :
{}
{
AddExpr()
}
It should be noted that before and after :, the front corresponds to the left side of BNF and the back corresponds to the right side.
You can write it in Java-like notation as above. Where <expression> corresponds to ʻExpr ()and corresponds to ʻAddExpr ().
Next, define ʻAddExpr ()`.
<Addition formula> ::= <Multiplication formula> ( <Addition operator> <Multiplication formula> )*
Is as follows.
void AddExpr() :
{}
{
MulExpr()
(
< ADD_OP >
MulExpr()
)*
}
The <addition operator> has already defined the lexical, so use <ADD_OP>.
I will define it to the end with this condition.
SimpleNode Root() :
{}
{
Expr() "\n"
{
return jjtThis;
}
}
void Expr() :
{}
{
AddExpr()
}
void AddExpr() :
{}
{
MulExpr()
(
< ADD_OP >
MulExpr()
)*
}
void MulExpr() :
{}
{
UnaryExpr()
(
< MUL_OP >
UnaryExpr()
)*
}
void UnaryExpr() :
{}
{
< OPEN_BRACKET > Expr() < CLOSE_BRACKET >
| Decimal()
}
void Decimal() :
{}
{
< DECIMAL >
}
Root is trying to return a node. This completes the parsing part.
Define the following execution method in the SimpleCalculatorParser class.
PARSER_BEGIN(SimpleCalculatorParser)
package simple_calculator;
import java.util.List;
import java.util.ArrayList;
public class SimpleCalculatorParser
{
public static void main(String [] args)
{
SimpleCalculatorParser.eval(System.in);
}
public static void eval(java.io.InputStream in)
{
//Creating a Parser
SimpleCalculatorParser parser = new SimpleCalculatorParser(in);
try
{
//The dump method of the SimpleNode class displays an abstract syntax tree under its own node
parser.Root().dump(" ");
}
catch (Exception e)
{
e.printStackTrace();
}
}
}
PARSER_END(SimpleCalculatorParser)
As a result, the jjt file created for creating the abstract syntax tree looks like this:
SimpleCalculatorGrammar.jjt
/**
* Simple calculator JJTree file
*/
options
{
STATIC = false; //Do not make parser class methods static
MULTI = true; //Generate ASTXXX class
VISITOR = true; //Generate a Visitor class
UNICODE_INPUT = false; //Do not analyze with Unicode (do not use Japanese etc.)
}
PARSER_BEGIN(SimpleCalculatorParser)
package simple_calculator;
import java.util.List;
import java.util.ArrayList;
public class SimpleCalculatorParser
{
public static void main(String [] args)
{
SimpleCalculatorParser.eval(System.in);
}
public static void eval(java.io.InputStream in)
{
SimpleCalculatorParser parser = new SimpleCalculatorParser(in);
try
{
parser.Root().dump(" ");
}
catch (Exception e)
{
e.printStackTrace();
}
}
}
PARSER_END(SimpleCalculatorParser)
SKIP :
{
" "
| "\t"
| "\r"
}
TOKEN :
{
< ADD_OP :
"+"
| "-" >
| < MUL_OP :
"*"
| "/"
| "%" >
| < OPEN_BRACKET : "(" >
| < CLOSE_BRACKET : ")" >
| < DECIMAL :
(< DIGIT >)+
(
"." (< DIGIT >)+
)? >
| < DIGIT : [ "0"-"9" ] >
}
SimpleNode Root() :
{}
{
Expr() "\n"
{
return jjtThis;
}
}
void Expr() :
{}
{
AddExpr()
}
void AddExpr() :
{}
{
MulExpr()
(
< ADD_OP >
MulExpr()
)*
}
void MulExpr() :
{}
{
UnaryExpr()
(
< MUL_OP >
UnaryExpr()
)*
}
void UnaryExpr() :
{}
{
< OPEN_BRACKET > Expr() < CLOSE_BRACKET >
| Decimal()
}
void Decimal() :
{}
{
< DECIMAL >
}
When you run the SimpleCalculatorParser class
Since it is waiting for input, enter 1 * 2 + 3 to display the abstract syntax tree.
1*2+3
Root
Expr
AddExpr
MulExpr
UnaryExpr
Decimal
UnaryExpr
Decimal
MulExpr
UnaryExpr
Decimal
You can see that the syntax tree was generated correctly.
It is a design pattern for tracing the tree structure. This pattern is used when exploring and manipulating trees. It is so named because it looks like a visitor visits a node in the tree.
Therefore, the node accepts the visiting visitor, and the visitor must visit the node as needed.
Have the AddExpr and MulExpr nodes hold a List of operators. Decimal holds the Token.
For example, when entering 1 * 2 * 3 + 4
Root
Expr
AddExpr [+] List<Token>
MulExpr [*, *] List<Token>
UnaryExpr
Decimal 1 Token
UnaryExpr
Decimal 2 Token
UnaryExpr
Decimal 3 Token
MulExpr
UnaryExpr [] List<Token>
Decimal 4 Token
To each node.
Node is an Object type and can have a value. Specifically, jjtThis.jjtSetValue (Object) is used to hold the value.
Also, the lexical can be assigned as t = <ADD_OP>.
void AddExpr() :
{
/* 1.Preprocessing*/
List tokens = new ArrayList();
Token t = null;
}
{
MulExpr()
(
t = < ADD_OP >
MulExpr() { /* 2. < ADD_OP > MulExpr()Processing for*/ tokens.add(t); }
)*
{
/* 3. MulExpr() ( < ADD_OP > MulExpr() )*Processing for*/
jjtThis.jjtSetValue(tokens);
}
}
If you add processing in this way
SimpleNode Root() :
{}
{
Expr() "\n"
{
return jjtThis;
}
}
void Expr() :
{}
{
AddExpr()
}
void AddExpr() :
{
List tokens = new ArrayList();
Token t = null;
}
{
MulExpr()
(
t = < ADD_OP >
MulExpr() { tokens.add(t); }
)*
{
jjtThis.jjtSetValue(tokens);
}
}
void MulExpr() :
{
List tokens = new ArrayList();
Token t = null;
}
{
UnaryExpr()
(
t = < MUL_OP >
UnaryExpr() { tokens.add(t); }
)*
{
jjtThis.jjtSetValue(tokens);
}
}
void UnaryExpr() :
{}
{
< OPEN_BRACKET > Expr() < CLOSE_BRACKET >
| Decimal()
}
void Decimal() :
{
Token t = null;
}
{
t = < DECIMAL >
{
jjtThis.jjtSetValue(t);
}
}
It will be.
SimpleCalculatorParserVisitor.java
/* Generated By:JavaCC: Do not edit this line. SimpleCalculatorParserVisitor.java Version 5.0 */
package simple_calculator;
public interface SimpleCalculatorParserVisitor
{
public Object visit(SimpleNode node, Object data);
public Object visit(ASTRoot node, Object data);
public Object visit(ASTExpr node, Object data);
public Object visit(ASTAddExpr node, Object data);
public Object visit(ASTMulExpr node, Object data);
public Object visit(ASTUnaryExpr node, Object data);
public Object visit(ASTDecimal node, Object data);
}
/* JavaCC - OriginalChecksum=afb311a7bd4476d0ee434db749efc016 (do not edit this line) */
Above is the automatically generated Visitor interface. Implement this.
Each method describes the process when each node is visited.
In particular,
public Object visit (ASTRoot node, Object data); is when you visit Root
public Object visit (ASTExpr node, Object data); is when you visit Expr
public Object visit (ASTAddExpr node, Object data); is when you visit AddExpr
・ ・ ・
Corresponds to.
The argument node at this time corresponds to jjtThis when jjtThis.jjtSetValue (tokens) is done, and this set value can be node.jjtGetValue (). node holds a child and can be obtained with node.jjtGetChild (index).
It is usually used when visiting a child node like node.jjtGetChild (index) .jjtAccept (this, data).
An example implementation is shown below.
SimpleCalculatorParserVisitorImpl.java
package simple_calculator;
import java.util.List;
public class SimpleCalculatorParserVisitorImpl implements
SimpleCalculatorParserVisitor {
@Override
public Object visit(SimpleNode node, Object data) {
//I don't usually use it.
return null;
}
@Override
public Object visit(ASTRoot node, Object data) {
//Visit your child's node. It can be seen from the syntax definition that there is only one child.
return node.jjtGetChild(0).jjtAccept(this, null);
}
@Override
public Object visit(ASTExpr node, Object data) {
//Visit your child's node. It can be seen from the syntax definition that there is only one child.
return node.jjtGetChild(0).jjtAccept(this, null);
}
@Override
public Object visit(ASTAddExpr node, Object data) {
List<Token> ops = (List<Token>) node.jjtGetValue();
//Get the number of children
int size = node.jjtGetNumChildren();
Double x = (Double) node.jjtGetChild(0).jjtAccept(this, null);
//Perform operations while turning operators and values. Proceed with the calculation while making a set. Example) x0 (+ x1) (+ x2)・ ・ ・
for (int i = 1; i < size; i++) {
switch (ops.get(i - 1).toString()) {
case "+":
x = x + (Double) node.jjtGetChild(i).jjtAccept(this, null);
break;
case "-":
x = x - (Double) node.jjtGetChild(i).jjtAccept(this, null);
break;
}
}
return x;
}
@Override
public Object visit(ASTMulExpr node, Object data) {
// jjtGetValue()With jjtSetValue(Object)You can get the value.
List<Token> ops = (List<Token>) node.jjtGetValue();
int size = node.jjtGetNumChildren();
Double x = (Double) node.jjtGetChild(0).jjtAccept(this, null);
//Perform operations while turning operators and values. Proceed with the calculation while making a set. Example) x0 (* x1) (* x2)・ ・ ・
for (int i = 1; i < size; i++) {
switch (ops.get(i - 1).toString()) {
case "*":
x = x * (Double) node.jjtGetChild(i).jjtAccept(this, null);
break;
case "/":
x = x / (Double) node.jjtGetChild(i).jjtAccept(this, null);
break;
case "%":
x = x % (Double) node.jjtGetChild(i).jjtAccept(this, null);
break;
}
}
return x;
}
@Override
public Object visit(ASTUnaryExpr node, Object data) {
//One child will return the Double, so return it as it is.
return node.jjtGetChild(0).jjtAccept(this, null);
}
@Override
public Object visit(ASTDecimal node, Object data) {
//Convert the word to Double type and return it.
return Double.valueOf(((Token) node.jjtGetValue()).toString());
}
}
Build SimpleCalculatorGrammar.jjt below, prepare SimpleCalculatorParserVisitorImpl.java, and start SimpleCalculatorParser.
SimpleCalculatorGrammar.jjt
/**
* Simple calculator JJTree file
*/
options
{
STATIC = false; //Do not make parser class methods static
MULTI = true; //Generate ASTXXX class
VISITOR = true; //Generate a Visitor class
UNICODE_INPUT = false; //Do not analyze with Unicode (do not use Japanese etc.)
}
PARSER_BEGIN(SimpleCalculatorParser)
package simple_calculator;
import java.util.List;
import java.util.ArrayList;
public class SimpleCalculatorParser
{
public static void main(String [] args)
{
System.out.println(SimpleCalculatorParser.eval(System.in));
}
public static double eval(java.io.InputStream in)
{
SimpleCalculatorParser parser = new SimpleCalculatorParser(in);
double x = 0.0;
SimpleCalculatorParserVisitor visitor = new SimpleCalculatorParserVisitorImpl();
try {
x = (double) parser.Root().jjtAccept(visitor, null);
} catch (ParseException e) {
e.printStackTrace();
}
return x;
}
}
PARSER_END(SimpleCalculatorParser)
SKIP :
{
" "
| "\t"
| "\r"
}
TOKEN :
{
< ADD_OP :
"+"
| "-" >
| < MUL_OP :
"*"
| "/"
| "%" >
| < OPEN_BRACKET : "(" >
| < CLOSE_BRACKET : ")" >
| < DECIMAL :
(< DIGIT >)+
(
"." (< DIGIT >)+
)? >
| < DIGIT : [ "0"-"9" ] >
}
SimpleNode Root() :
{}
{
Expr() "\n"
{
return jjtThis;
}
}
void Expr() :
{}
{
AddExpr()
}
void AddExpr() :
{
List tokens = new ArrayList();
Token t = null;
}
{
MulExpr()
(
t = < ADD_OP >
MulExpr() { tokens.add(t); }
)*
{
jjtThis.jjtSetValue(tokens);
}
}
void MulExpr() :
{
List tokens = new ArrayList();
Token t = null;
}
{
UnaryExpr()
(
t = < MUL_OP >
UnaryExpr() { tokens.add(t); }
)*
{
jjtThis.jjtSetValue(tokens);
}
}
void UnaryExpr() :
{}
{
< OPEN_BRACKET > Expr() < CLOSE_BRACKET >
| Decimal()
}
void Decimal() :
{
Token t = null;
}
{
t = < DECIMAL >
{
jjtThis.jjtSetValue(t);
}
}
Execution result
1+2*3*4
25.0
It went well! !! !! Next time, I would like to make something like a programming language.
Make a language! I tried using bison and flex Make a language! (JavaCC environment construction) Make a language! (Making a simple calculator ①)
Recommended Posts