JavaCC(Java compiler compiler)は SunTest がフリーで公開しているJava向けの字句解析器/構文解析器生成プログラムです。直接プログラミング言語の解析器(パーサ)を書く代わりに文法を決まった形式で書き、パーサを自動生成させることができます。

本格的なコンパイラの開発から定義ファイルの解析といった一般的なテキスト処理まで威力を発揮するツールで、UNIXで使用されている yacc/lex とほぼ同等の機能を持っています。

JavaCCでは、入力する文字列のフォーマット、つまり文法を定義したものが入力ファイルとなり、これを文法を解釈するプログラムのJavaソースに変換します。 生成したJavaソースのコンパイルは、通常のJavaプログラムと同様にjavacコマンドを使用します。

コンパイルまでの手順

JavaCCの文法ファイルには字句解析と構文解析の文法を記述する。このファイルの拡張子は通常"jj"である。これをJavaCCでコンパイルすると、字句解析器と構文解析器などが作成される。これらはJavaのソース・ファイルである。

> javacc grammer.jj
> ls
Parser.java ParserTokenManeger.java ...

Parserは構文解析器で、この名前は指定できる。ParserTokenManagerは字句解析器で、構文解析器のクラスの名前にTokenManagerを付加したものになる。これらをコンパイルすればパーサのクラスファイルができる。

> javac Parser.java
> ls
Parser.class Parser.java ParserTokenManager.class ParserTokenManager.java ...

JavaCCの文法ファイル

JavaCCの文法ファイルは大きく4つの部分に分けられる。オプションを記述する部分、作成されるパーサのクラスファイルにコピーされる部分、字句解析の規則を記述する部分、文法をBNF記法で記述する部分である。

オプションの記述

オプションはoptions節で記述を行う。オプションの記述例を次に示す。

options {
  STATIC=false;
}

パーサクラスの記述

BEGIN_PARSER(クラス名)とEND_PARSER(クラス名)の間にクラスの宣言部とメンバ(フィールドとメソッド)を記述する。ここで記述したメンバはそのまま出力されるクラスのソースコードにコピーされる。

パーサクラスの例を次に示す。

PARSER_BEGIN (Parser)
import java.io.*;
public class Parser {
  static public void main(String[] args) {
    try {
      InputStream in;
      if (args.length == 0) {
        in = System.in;
      } else {
        in = new BufferedInputStream(new FileInputStream(args[0]));
      }
      new Parser(in).Input();
    } catch (Exception e) {
      e.printStackTrace();
    }
  }
}
PARSER_END (Parser)

字句解析の規則

通常、字句解析は構文解析と分けて行われる。これは人間の理解を助けるという理由もある、字句解析の文法(正規文法)は構文解析の文法よりも小さいため、分割した方が速くて小さい解析器を作成できるからである。

字句解析の規則では入力として無視する文字と、構文解析の単位となるトークンまたは終端記号と呼ばれる記号を定義する。

入力として無視する記号を空白文字、タブ文字、改行文字とすると、次のようになる。

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

トークンの定義の例を次に示す。

TOKEN:
{
  <PLUS: "+"> |
  <MINUS: "-"> |
  <MUL: "*"> |
  <DIV: "/"> |
  <POWER: "^"> |
  <LPAREN: "("> |
  <RPAREN: ")"> |
  <NUM: (<DIGIT>)+ ("." (<DIGIT>)+)?> |
  <#DIGIT: ["0"-"9"]>
}

BNF記法による文法の記述

ここでは構文解析の文法を記述する。 BNF記法による文法の記述方法例を次に示す。

このパーサの入力 ::= 足し算式 <EOF>
足し算式 ::= 掛け算式 ((<PLUS> | <MINUS>) 掛け算式)*
掛け算式 ::= 指数式 ((<MUL> | <DIV>) 指数式)*

"|"(縦棒)は「または」の意味、"*"は「0回以上の繰り返し」の意味である。このような形で文法を定義する。左辺または右辺のホワイトスペースで区切られた各々が文法記号である。そして、このそれぞれの式を生成規則と呼ぶ。入力が最終的には全てトークン(終端記号)になるように生成規則を定義する。トップダウンに考えていくと、入力の文字列は最後にはトークンの列に分解される。トークンを構成する各文字のことは字句解析の範囲なので、ここでは考える必要はない。字句解析が先に行われ、その結果であるトークン列が構文解析の入力になる。

実際のJavaCCの文法ファイルの書き方は、メソッドに似た形式で記述する。その例を次に示す。

void Input():
{}
{
 SumExpression() <EOF>
}
void SumExpression():
{}
{
 MulExpression() ((<PLUS> | <MINUS>) MulExpression())*
}
void MulExpression():
{}
{
 PowerExpression ((<MUL> | <DIV>) PowerExpression())*
}

メソッドの形式に書くのには、実際にパースというのは文法記号ごとに対応するメソッドを呼び出す事に相当するからである。最初は開始記号であるInputが呼ばれ、次にInputからSumExpression()が呼び出され、SumExpression()からMulExpression()が、というように順にメソッド呼び出しが行われ、何事も無く全てのメソッド呼び出しが終了すればパースに成功した、つまり入力がその文法に適合した、ということになる。

スポンサーリンク