はじめに
前回まででJavaCCの基本的な使い方の解説が終わりました。今回からはより実用的なサンプルを作成していこうと思います。今回は、四則演算ができる簡単な式言語を実装します。
必要な環境
前回と同じく、JavaCC 4.0、J2SE 5.0、Antを用意しておいてください。今回は新しくサンプルプログラムを作成するので、前回のサンプルは不要です。
今回利用するファイル
今回は、整数の四則演算ができる簡単な式言語を実装します。まず最初に足し算・引き算だけができるものを作成して、それを元に掛け算・割り算や文字列の扱いができるところまで実装していきます。今回作成するファイルは次のようになります。
| ファイル/フォルダ | 内容 |
| /CodeZine | |
| build.xml | 構築スクリプト |
| build.properties | 環境設定 |
| /src | |
| /codezine | |
| /expr | |
| Expr.java | 処理プログラム |
| ExprParser.jjt | 文法定義ファイル |
| BaseNode.java | ノードの基底クラス |
| /parser | |
| /build | |
| /classes |
サンプルプログラム
ビルド用antスクリプトです。このスクリプトは前回までのものとまったく同じものです。このようにantスクリプトでは環境や作成するプログラムに依存する部分をpropertiesファイルに抜き出しておくと再利用しやすくなります。
<?xml version="1.0" encoding="UTF-8"?> <project name="ParserLexer" default="default" basedir="."> <target name="init"> <property file="build.properties"/> </target> <target name="cc" depends="init"> <delete dir="${build.parser.dir}" includes="*.*"/> <jjtree target="${src.jjt.file}" outputdirectory="${build.parser.dir}" javacchome="${javacc.dir}"/> <javacc target="${build.jj.file}" javacchome="${javacc.dir}"/> </target> <target name="compile" depends="init"> <javac destdir="${build.classes.dir}" srcdir="${src.dir}" debug="true"> <include name="**/*.java"/> </javac> </target> </project>
環境依存の部分を記述したpropertiesファイルです。javacc.dirには、JavaCC4.0を解凍したフォルダを指定してください。
javacc.dir=C:\\java\\tool\\javacc-4.0
src.dir=src
build.classes.dir=build/classes
src.expr.dir=${src.dir}/codezine/expr
src.jjt.file=${src.expr.dir}/ExprParser.jjt
build.parser.dir=${src.expr.dir}/parser
build.jj.file=${build.parser.dir}/ExprParser.jj
式言語のJavaCC文法定義です。前述のantスクリプトのccタスクを実行して構文解析のコードを生成してください。
//オプション定義 options{ STATIC=false; MULTI=true; VISITOR=true; NODE_EXTENDS="codezine.expr.BaseNode"; } //パーサークラスの定義 PARSER_BEGIN(ExprParser) package codezine.expr.parser; public class ExprParser{ } PARSER_END(ExprParser) //トークンの定義 SKIP: { " " | "\r" | "\t" | "\n" } TOKEN: { <PLUS : "+"> | <MINUS: "-"> | <INTEGER: (["0" - "9"])+> } //文法の定義 ASTStart Start(): {} { AddExpr() { return jjtThis;} } void AddExpr() #void: {} { Integer() ( <PLUS> Integer() #Add(2) | <MINUS> Integer() #Sub(2) ) * } void Integer(): { Token t;} { t = <INTEGER> { jjtThis.nodeValue = t.image;} }
ノードの基底クラスです。前回のものとパッケージが違うだけです。
package codezine.expr; public class BaseNode { public String nodeValue; }
今回の式言語の処理の実装は次のように行います。
package codezine.expr; import codezine.expr.parser.*; import java.io.*; public class Expr implements ExprParserVisitor{ public static void main(String[] args) throws ParseException, IOException{ InputStreamReader in = new InputStreamReader(System.in); BufferedReader reader = new BufferedReader(in); String line; while((line = reader.readLine()) != null){ ExprParser parser = new ExprParser(new StringReader(line)); Expr visitor = new Expr(); ASTStart start = parser.Start(); System.out.println(start.jjtAccept(visitor, null)); } } public Object visit(SimpleNode node, Object data) { return null; //ここには来ない } /** 開始記号 */ public Object visit(ASTStart node, Object data) { return node.jjtGetChild(0).jjtAccept(this, null); } /** 足し算 */ public Object visit(ASTAdd node, Object data) { Integer left = (Integer) node.jjtGetChild(0).jjtAccept(this, null); Integer right = (Integer) node.jjtGetChild(1).jjtAccept(this, null); return left + right; } /** 引き算 */ public Object visit(ASTSub node, Object data) { Integer left = (Integer) node.jjtGetChild(0).jjtAccept(this, null); Integer right = (Integer) node.jjtGetChild(1).jjtAccept(this, null); return left - right; } /** 数値リテラル */ public Object visit(ASTInteger node, Object data) { String value = node.nodeValue; return Integer.valueOf(value); } }
実行すると、足し算引き算の演算ができています。
C:\java\product\CodeZine\build\classes>java codezine.expr.Expr 3+5-2+1 7
簡単な式言語でのノード生成の制御
それではこの式言語のプログラムについて見てみましょう。まず構文定義ファイルを見てみます。この構文でのトークンとしては「+」「-」の演算子と数値を定義しています。
//トークンの定義 TOKEN: { <PLUS : "+"> | <MINUS: "-"> | <INTEGER: (["0" - "9"])+> }
生成規則として、つぎのような規則を定義しています。
void AddExpr() #void:
{}
{
Integer() (
<PLUS> Integer() #Add(2)
| <MINUS> Integer() #Sub(2) ) *
}
ここで#voidや#Add(2)という指定がありますが、これはノード生成を制御するためのJJTreeに対する指定です。このノード生成指定を除いた生成規則自体は次のようなものになっています。
void AddExpr():
{}
{
Integer() ( <PLUS> Integer() | <MINUS> Integer())*
}
AddExpr生成規則は、この生成規則に#で始まるノード生成制御が指定してされている形になっています。#voidはノードクラスを抑制する指定です。#voidを生成規則に付けると、その生成規則に対応するノードクラスを生成しません。#Add(2)や#Sub(2)は条件によってノードクラスを生成することを指定します。
ノード生成の指定の形式は
#ノード名(条件)
となっています。
#Add(2)ではそこまでに2つの生成規則が生成されていればノードを生成します。実際に生成されるノードクラスの名前は「ASTノード名」になります。他にも#Hoge(>2)とすると生成される生成規則が2つを越えたときにノードを生成します。慣れるまでは、2項演算子を指定する際の定型として覚えておけばいいと思います。
このようにノード生成の指定を使うと足し算と引き算で別々のノードが生成されるので、処理の実装では次のように足し算と引き算の処理を記述しています。
/** 足し算 */ public Object visit(ASTAdd node, Object data) { Integer left = (Integer) node.jjtGetChild(0).jjtAccept(this, null); Integer right = (Integer) node.jjtGetChild(1).jjtAccept(this, null); return left + right; } /** 引き算 */ public Object visit(ASTSub node, Object data) { Integer left = (Integer) node.jjtGetChild(0).jjtAccept(this, null); Integer right = (Integer) node.jjtGetChild(1).jjtAccept(this, null); return left - right; }
数値は次のようにInteger型として取得しています。
public Object visit(ASTInteger node, Object data) { String value = node.nodeValue; return Integer.valueOf(value); }
演算子の優先順位
それでは次は、掛け算、割り算を実装してみましょう。掛け算、割り算で気をつけなければならないことは、これらの演算子は足し算・引き算よりも優先度が高いことです。「12+4*3」は左から順に計算して48になるのではなくて、掛け算を優先して最初に「4*3」を計算する必要があり、結果は24になります。
ついでに演算子の優先順位でかかせない「(」「)」も実装しましょう。「(12+4)*3」とした場合には48になるようにします。優先順位は次のようになります。
| 優先度 | 演算子 |
| 低い 高い | + 、- |
| * 、/ | |
| 数値 、(～) |
掛け算、割り算と()を追加したときの文法定義は次のようになります。
TOKEN:
{
<PLUS : "+">
| <MINUS: "-">
| <MUL: "*">
| <DIV: "/">
| <LPAREN: "(">
| <RPAREN: ")">
| <INTEGER: (["0" - "9"])+>
}
//文法の定義
ASTStart Start():
{}
{
AddExpr() { return jjtThis;}
}
void AddExpr() #void:
{}
{
MulExpr() (
<PLUS> MulExpr() #Add(2)
| <MINUS> MulExpr() #Sub(2) ) *
}
void MulExpr() #void:
{}
{
Value() (
<MUL> Value() #Multi(2)
| <DIV> Value() #Division(2) )*
}
void Value() #void:
{}
{
Integer()
| <LPAREN> AddExpr() <RPAREN>
}
void Integer():
{ Token t;}
{
t = <INTEGER> { jjtThis.nodeValue = t.image;}
}
処理用のJavaコードには次のように掛け算、割り算のコードを追加します。追加されるノードは掛け算、割り算のASTMultiとASTDivisionなので、それぞれに対応する処理を記述します。
/** 掛け算 */ public Object visit(ASTMulti node, Object data) { Integer left = (Integer) node.jjtGetChild(0).jjtAccept(this, null); Integer right = (Integer) node.jjtGetChild(1).jjtAccept(this, null); return left * right; } /** 割り算 */ public Object visit(ASTDivision node, Object data) { Integer left = (Integer) node.jjtGetChild(0).jjtAccept(this, null); Integer right = (Integer) node.jjtGetChild(1).jjtAccept(this, null); return left / right; }
このように、文法規則を追加しても元からあったJavaのコードの方には変更を加えなくても良いことが分かります。
この変更を加えてant ccタスク、ant compileタスクで構築したあと実行してみると、括弧や演算子の優先順位が処理されていることが分かります。
C:\java\product\CodeZine\build\classes>java codezine.expr.Expr 13+5*3-(2+1) 25
結果が45や47にならないことから、掛け算と括弧の中が先に処理されていることが確認できます。演算子に優先順位があるときには、優先順位の低い演算子の生成規則から優先順位の高い演算子の生成規則を生成するような文法にします。例えば、この例では、足し算・引き算の生成規則AddExprから掛け算・割り算の生成規則MulExprを生成しています。
void AddExpr() #void:
{}
{
MulExpr() (
<PLUS> MulExpr() #Add(2)
| <MINUS> MulExpr() #Sub(2) ) *
}
また、足し算と引き算や掛け算と割り算のように優先順位が同じ演算子は、同じ生成規則にしています。
