Go to Qiita Advent Calendar 2024 Top
LoginSignup
6
4

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

@toru0408(Toru Ikeda)

言語を作る！(シンプルな電卓を作る編②)

Posted at

前回、言語を作る！シンプルな電卓を作る編①でシンプルな電卓の文法まで考えました。
今回は実際に動くプログラムにします。

完成イメージ

コンソールに計算式を入力すると計算されて数値を表示します。

> 2 + 3 * 5
17
> 100 * 1.08
108.00

JJTファイルに記述する内容

  1. オプション - ビルドで生成するソースコードの特性や出力するファイルを設定します。
  2. パーサ定義 - パーサのクラス名を定義したり独自のメソッドを追加します。
  3. 字句定義 - どのような種類の字句があるかを定義します。無視する字句等も定義できます。
  4. 構文定義 - 字句を組み合わせて構文を定義します。同時に簡単な処理を記述できます。

以上4点を記述していきます。JavaCCの詳細な書き方は
https://javacc.org/javaccgrm
↑サイト（英語）に書いてあります。

BNFをJavaCCのJJTファイルへ

前回、定義した以下のBNFを次のように定義しました。

単純な計算式のBNF
<式> ::= <加算式>
<加算式> ::= <乗算式> ( <加算演算子> <乗算式> )*
<乗算式> ::= <単項式> ( <乗算演算子> <単項式> )*
<単項式> ::= <開括弧> <式> <閉括弧> | <10進数表現>

<加算演算子> ::= "+" | "-"
<乗算演算子> ::= "*" | "/" | "%"
<開括弧> ::= "("
<閉括弧> ::= ")"
<10進数表現> ::= (<数字>)+ ("." (<数字>)+)?
<数字> ::= "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" | "0"

これを順番にJJTファイルに落とし込んでいきます。

字句の定義

まず、<加算演算子>を定義してみましょう。
JavaCCでの定義は

< ADD_OP : "+"|"-" >

のように記述します。記号の意味はBNFで用いる記号の説明とほぼ同じです。
http://qiita.com/toru0408/items/9d7263bce7f9a4bdce13#bnf
を参照してください。
このようにしてすべてをjavaccの記述に置き換えると

< ADD_OP : "+" | "-" >
< MUL_OP : "*" | "/" | "%" >
< OPEN_BRACKET : "(" >
< CLOSE_BRACKET : ")" >
< DECIMAL : (< DIGIT >)+ ("." (< DIGIT >)+)? >
< DIGIT : [ "0"-"9" ] >

となります。[ "0"-"9" ]は文字コード表上の"0"から"9"までのすべての文字を指します。
["0", "1", "2", "3", "4", "5", "6", "7", "8", "9"]と書くこともできますが、
ここで文字コード上で"0","1",・・・"9"は連続で並んでいますので[ "0"-"9" ]と書くことができます。同様に大文字小文字英字を["a"-"z", "A"-"Z"]と書くことができます。

最終的にTOKEN{}で囲んで完成です。

TOKEN :
{
  < ADD_OP : "+" | "-" >
| < MUL_OP : "*" | "/" | "%" >
| < OPEN_BRACKET : "(" >
| < CLOSE_BRACKET : ")" >
| < DECIMAL : (< DIGIT >)+ ("." (< DIGIT >)+)? >
| < DIGIT : [ "0"-"9" ] >
}

特殊な字句の定義

実は隠れた字句の定義ができていません。例えば、空白やタブ等のことです。これらの文字に字句解析器がエンカウントしたときの処理も書いておく必要があります。今回はこれらの文字は無視する（あってもなくとも挙動が変わらない）ので以下の記述をします。

SKIP :
{
  " "
| "\t"
| "\r"
}

（改行文字は後々で区切りの目印として使うので無視しません。）

構文の定義

<式> ::= <加算式>

このBNFは次のように書けます。

void Expr() :
{}
{
  AddExpr()
}

注目するべきは:の前後で前がBNFの左辺に対応し、後が右辺に対応しています。
上のようにJavaに似た記法で書くことができます。ここで<式>はExpr()に、<加算式>はAddExpr()に対応します。
次にAddExpr()を定義します。

<加算式> ::= <乗算式> ( <加算演算子> <乗算式> )*

は次のようになります。

void AddExpr() :
{}
{
  MulExpr()
  (
    < ADD_OP > 
    MulExpr()
  )*
}

<加算演算子>はすでに字句の定義を行ったので< ADD_OP >を使います。
この調子で最後まで定義していきます。

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はノードを返すようにしています。
これで構文解析の部分は完成です。

抽象構文木を表示

SimpleCalculatorParserクラスに以下の実行用のメソッドを定義します。

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)
  {
    // Parserの作成
    SimpleCalculatorParser parser = new SimpleCalculatorParser(in);
    try
    {
      // SimpleNodeクラスのdumpメソッドは自身のノード以下の抽象構文木を表示する
      parser.Root().dump(" ");
    }
    catch (Exception e)
    {
      e.printStackTrace();
    }
  }
}

PARSER_END(SimpleCalculatorParser)

その結果、抽象構文木の作成用に作られるjjtファイルは以下のようになります。

SimpleCalculatorGrammar.jjt
/**
 * Simple calculator JJTree file
 */
options
{
  STATIC = false; // parserクラスのメソッドをstaticにしない
  MULTI = true; // ASTXXXクラスを生成する
  VISITOR = true; // Visitorクラスを生成する
  UNICODE_INPUT = false; // ユニコードで解析を行わない（日本語等を使わない）
}

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

SimpleCalculatorParserクラスを実行すると
入力待ちになるので1*2+3と入力して抽象構文木が表示されます。

1*2+3
 Root
  Expr
   AddExpr
    MulExpr
     UnaryExpr
      Decimal
     UnaryExpr
      Decimal
    MulExpr
     UnaryExpr
      Decimal

構文木が正しく生成されたことが分かります。

意味解析と実行

Visitorパターンとは

木構造をたどるためのデザインパターンです。木を探索したり、操作したりする場合に用いられるパターンです。木のノードを訪問者(visitor)が訪れる(visit)ように見えることからそのような名前がついています。

そのため、ノードは訪れてきたVisitorを受け入れて(accept)、Visitorはノードを必要に応じて訪れる必要があります。

Nodeに値を保持させる

AddExprとMulExprノードに演算子のListを保持させます。
DecimalはTokenを保持させます。

例えば、123+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

を各ノードに保持させます。
※(ノード名 データ 型)の順で書いています。

NodeはObject型でvalueを持たせることができます。具体的にはjjtThis.jjtSetValue(Object)で値を保持させます。
また、字句はt = < ADD_OP >のように代入させることができます。

void AddExpr() :
{
  /* 1. 前処理 */
  List tokens = new ArrayList();
  Token t = null;
}
{
  MulExpr()
  (
    t = < ADD_OP > 
    MulExpr() { /* 2. < ADD_OP > MulExpr() に対する処理 */ tokens.add(t); }
  )*
  {
    /* 3. MulExpr() ( < ADD_OP > MulExpr() )* に対する処理 */
    jjtThis.jjtSetValue(tokens);
  }
}

このようにして処理を追加すると

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

となります。

Visitorの実装

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) */

上は自動生成されたVisitorのインターフェイスです。これを実装します。
それぞれのメソッドはそれぞれのnodeを訪れたときの処理を記述します。
具体的には、
public Object visit(ASTRoot node, Object data);はRootを訪れたとき、
public Object visit(ASTExpr node, Object data);はExprを訪れたとき、
public Object visit(ASTAddExpr node, Object data);はAddExprを訪れたとき、
・・・
に対応します。
このときの引数nodeはjjtThis.jjtSetValue(tokens)したときのjjtThisに対応していて、このsetした値をnode.jjtGetValue()できます。nodeは子どもを保持していて、node.jjtGetChild(index)で取得できます。
普通はnode.jjtGetChild(index).jjtAccept(this, data)のようにして子ノードを訪れるときに使います。

以下に実装の1例を示します。

SimpleCalculatorParserVisitorImpl.java
package simple_calculator;

import java.util.List;

public class SimpleCalculatorParserVisitorImpl implements
		SimpleCalculatorParserVisitor {

	@Override
	public Object visit(SimpleNode node, Object data) {
		// 普通は使わない。
		return null;
	}

	@Override
	public Object visit(ASTRoot node, Object data) {
		// 自分の子どものノードを訪れる。子どもが1つのみ存在することは構文定義からわかる。
		return node.jjtGetChild(0).jjtAccept(this, null);
	}

	@Override
	public Object visit(ASTExpr node, Object data) {
		// 自分の子どものノードを訪れる。子どもが1つのみ存在することは構文定義からわかる。
		return node.jjtGetChild(0).jjtAccept(this, null);
	}

	@Override
	public Object visit(ASTAddExpr node, Object data) {
		List<Token> ops = (List<Token>) node.jjtGetValue();
		// 子どもの数を取得
		int size = node.jjtGetNumChildren();
		Double x = (Double) node.jjtGetChild(0).jjtAccept(this, null);
		// 演算子と値を回しながら演算を行う。セットにしながら演算を進める。例) 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()でjjtSetValue(Object)した値を取得できる。
		List<Token> ops = (List<Token>) node.jjtGetValue();
		int size = node.jjtGetNumChildren();
		Double x = (Double) node.jjtGetChild(0).jjtAccept(this, null);
		// 演算子と値を回しながら演算を行う。セットにしながら演算を進める。例) 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) {
		// 子どもが1つでDoubleを返却してくるのでそのまま返却。
		return node.jjtGetChild(0).jjtAccept(this, null);
	}

	@Override
	public Object visit(ASTDecimal node, Object data) {
		// 字句をDouble型に変換して返却。
		return Double.valueOf(((Token) node.jjtGetValue()).toString());
	}

}

電卓を起動!

下のSimpleCalculatorGrammar.jjtをビルドして、SimpleCalculatorParserVisitorImpl.javaを用意して、SimpleCalculatorParserを起動してみます。

SimpleCalculatorGrammar.jjt
/**
 * Simple calculator JJTree file
 */
options
{
  STATIC = false; // parserクラスのメソッドをstaticにしない
  MULTI = true; // ASTXXXクラスを生成する
  VISITOR = true; // Visitorクラスを生成する
  UNICODE_INPUT = false; // ユニコードで解析を行わない（日本語等を使わない）
}

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);
  }
}
実行結果
1+2*3*4
25.0

うまくいきました！！！
今度はプログラミング言語的ものを作ってみたいと思います。

関連記事

言語を作る！bisonとflexを使ってみた
言語を作る！(JavaCCの環境構築編)
言語を作る！(シンプルな電卓を作る編①)

6
4
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
6
4

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?