Make a language! (Making a simple calculator ②)

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.

Complete image

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

Contents to be described in the JJT file

  1. Option --Set the characteristics of the source code generated by the build and the output file.
  2. Parser definition-Define the class name of the parser or add your own methods.
  3. Tokenization Definition-Defines what kind of lexical you have. You can also define words to ignore.
  4. Syntax definition--Combine lexical terms to define the syntax. You can write simple processes at the same time.

I will describe the above four points. How to write JavaCC in detail https://javacc.org/javaccgrm ↑ It is written on the site (English).

BNF to JavaCC JJT file

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.

Lexical definition

First, let's define the . The definition in JavaCC is

< 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" ] >
}

Definition of special lexical

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.)

Syntax definition

<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.

Show abstract syntax tree

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.

Semantic analysis and execution

What is the Visitor pattern?

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.

Let Node hold the value

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.

Visitor implementation

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());
	}

}

Start the calculator!

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.

Related article

Make a language! I tried using bison and flex Make a language! (JavaCC environment construction) Make a language! (Making a simple calculator ①)

Recommended Posts

Make a language! (Making a simple calculator ②)
Make a language! (Making a simple calculator ①)
Try to make a simple callback
Make a language! (JavaCC environment construction)
[docker] [nginx] Make a simple ALB with nginx
Try making a calculator app in Java
Making Frontale a microservice
Practice making a simple chat app with Docker + Sinatra
[Personal memo] Make a simple deep copy in Java
Let's make a robot! "A simple demo of Java AWT Robot"
Make a reflection utility ②
Make a reflection utility ③
Make a reflection utility ①
Let's make a calculator application in Java ~ Display the application window
[Beginner] Try to make a simple RPG game with Java ①
Make a simple CRUD with SpringBoot + JPA + Thymeleaf ① ~ Hello World ~
Let's make a simple API with EC2 + RDS + Spring boot ①
Make a simple CRUD with SpringBoot + JPA + Thymeleaf ⑤ ~ Template standardization ~
Ruby Learning # 11 Building a Calculator
[Java] Make it a constant
[Java] Draw a simple pattern
[Rails] Make a breadcrumb trail
Making a minute repeater part.2
Making a minute repeater part.1
Make a rhombus using Java
A story about making a calculator to calculate the shell mound rate