この記事は Java Advent Calendar 2011 の22日の記事です。
昨日は zinbe さんでjsoupとMicrosoft Translator APIを使ってJSRの日本語リストを作るでした。明日は yamadamn さんでencodeURLとencodeRedirectURLAdd Starです。
JavaCC って何するもの？
Java Compiler Compiler の略で、設定ファイルから Lexer （字句解析器）と Parser （構文解析器）の Java コードを生成してくれるソフトです。と、そんなこと言葉でつらつら書いてても読んでてもおもしろくないので手を動かしましょう。
入手先
JavaCC Home が公式サイトですね。インストールはダウンロードして展開してパスを通せば終わりのようです。ようです、って書いてるのは、僕の場合 Ubuntu で sudo apt-get install javacc で終いなので。パッケージ管理楽でいいですね。
最終的に四則演算ができる電卓を作ります。
初めの一歩
プログラミング言語の入門なら Hello World. を表示、といくところですが、今回は Hello World. のみを受け入れるプログラムを作りましょう。下2つのコードを Parser.jj, Main.java として保存します。
そして、保存したディレクトリで下のコマンドを実行。
$ javacc Parser.jj $ javac Main.java $ java Main
Hello World. と打って改行を押すと何も言わずに終わります。何も言わなければ成功です。では、違う文字を打ってみましょう。字句解析エラーが出ましたね。これで Hello World. のみを受け入れるプログラムができました！わーい。
……もしかしたら Windows だと改行コードの問題で動かないかも。もしそうならそのまま次を読んでください。
解説をしましょう。Parser.jj を見ると、PARSER_BEGIN (Parser) ... PARSER_END (Parser) があります。ここで JavaCC に作ってもらうパーサーの名前を指定します。そして、次の
void List(): {
} {
"Hello World.\n"
}で、受け入れるものを指定します。1つめの {} はまだおまじないということで。BNF だとこんな感じ。
List ::= "Hello World.\n"
トークン
先のプログラムはさすがにしょぼいので、もう少し発展させましょう。"Hello World" のような固定の文字列はトークンにしちゃいましょう。ついでに改行コードも複数に対応しましょう。あと、空白の読み飛ばしもしましょうか。
トークンの定義部分は見ての通り、<トークン名: 規則> の形ですね。規則は | で、「または」指定できます。トークン定義自体も | で繋ぎます。読み飛ばしは SKIP に書きます。こうすると トークンとトークンの間、この場合は <HELLO> と <NL> の間にいくら空白があっても無視されます。
これをコンパイル・実行し、Good-bye World.<改行> と打つと先と同じように字句解析エラーが出ますね。Hello World. Hello World.<改行> なら構文解析エラーが出ます。字句解析エラーは「そんなトークンないよ」というエラーで、構文解析エラーは「トークンは合うけどその順番は受け入れられないよ」というエラーです。
正規表現で受け入れる
トークン規則には正規表現が書けます。今度は整数値を受け入れるパーサーを作りましょう。
気をつけなければいけないところは、メタ文字でなくても必ず " で括ること、また繰り返しの + は必ず ( ... )+ と書き括弧を省略できないことで、他はほぼ解説は要らないでしょう。
受け入れた整数値を取り出そう
さっそくコードを。
おまじないと言っていた List() 後の1つめの {} が出てきました。ここには、この規則で使う変数を宣言します。そして、その変数に <INTEGER> を代入します。それは JavaCC が javacc コマンドで生成した Token クラスのインスタンスとなります。<INTEGER> <NL> の後ろコードは、入力がその構文として受け入れられたときに実行されます。Token#image に入ってある受け入れた文字列を出力します。
次に、新たに Expression() を作り、それに整数値を返させましょう。
Expression() が int を返すようにしています。その他はたいして難しいところはないですかね。
電卓っぽくしていきましょう
先の Expression の名前を PrimaryExpression に変えました。Expression() の規則がややこしくなりますよ。
Expression を JavaCC 拡張の BNF に書き直してみましょう。
Expression ::= PrimaryExpression (PLUS PrimaryExpression | MINUS PrimaryExpression)*
PrimaryExpression の後に、（プラス記号と PrimaryExpression の列、もしくはマイナス記号と PrimaryExpression の列）の0回以上の繰り返し、となりますね。返す値は、val1 に val2 の値を足して、もしくは引いていき、最後に val1 を返します。仮に 1+2-3 を入力した場合、次の図ように解釈されますね。
この木を構文木といいます。
あとはかけ算・わり算
かけ算・わり算を実装して終わりにしましょうか。1+2*3 を入力した場合、次の図のように解釈されたいわけです。
BNF だと次のようになりますね。
List ::= Expression NL Expression ::= MultiplyExpression (PLUS MultiplyExpression | MINUS MultiplyExpression)* MultiplyExpression ::= PrimaryExpression (MULTIPLY PrimaryExpression | DIVIDE PrimaryExpression)* PrimaryExpression ::= INTEGER
というわけで、コードです。
Expression() の PrimaryExpression() が MultipryExpression() に置き代わりました。Expression と PrimaryExpression の間に MultiplyExpression が1段加わっただけで JavaCC の新しい機能はありません。
これで整数の四則演算がきるようになりました。パチパチパチ。
練習として、括弧を処理できるようにするのもいいかもしれません。BNF で次の文法を追加するだけでいいですね。
PrimaryExpression ::= INTEGER | "(" Expression ")"
終わりに
いかがでしたか？後半は少し急ぎ足だったので分かりにくかったかもしれません。使う機会はあまりないかもしれませんが、凝った設定ファイルなどを処理しないといけないときなどに使ってみてください。今回は構文木自体は生成せず解析途中に計算していきましたが、構文木を生成する必要があるときは JJTree とともに使うことになると思います。
後記
日付過ぎてしまいました。すみません。
JavaCC はこの記事を書くために勉強しました。ちょうど Yacc (Bison)・Lex (Flex) で遊んでいたので題材に選びました。解説を読んでる内は yacc + lex とかなり勝手が違うのでとまどいましたが、書いてみるとなるほどこれはいいな、という感じですね。yacc + lex よりも断然高機能ですね。
題材の他の候補としては、アノテーションや Java Web Start がありました。どちらも、自分でコード書いたことないなということで。アノテーション使うことはちょくちょくあるんですけれどね。
Java は中3のころに触りだしたのでもう7年目になるのですが、実はサーバーサイドは触ったことないのでそれも少しは気にはなるんですけど、あんまり興味がないんですよね。Google App Engine をほんの少し触ったぐらいです。
Java Fx もやらないといけないですねー。
関西 Java エンジニアの会にもちょくちょく顔を出しているのでそのときはよろしくお願いします。
それでは。
