日(?)記

■ 03/09/18 JavaCC との違い

JavaCC との違いを書いたドキュメントがあると良い、とのことなので、少し書きます。

■ JavaCC 自体は、Yacc と同様、文法とプログラムを併記しておくと、構文要素を発見するごとにそのプログラムを起動するタイプのコンパイラ・コンパイラです。JavaCC には構文木を自動生成する機能はないのですが、JavaCC には JJTree というコンパイラ・コンパイラが付属しており、これは JavaCC に構文木を自動生成する機能を追加したものです。一方、￢＜＞＜∪∪は構文木を自動生成する機能はありますが、プログラムを起動する機能はありません（まったくないわけではありませんが、起動されるタイミングが保証されないので、あまり意味がありません）。

XMLで言うと、上が SAX で、下が DOM に似ているかもしれません。

JavaCC と￢＜＞＜∪∪だと共通点の方が少ないので、まず、JJTree と￢＜＞＜∪∪との違いを説明します。

■ 次のBNFであらわされるJavaのfor文を考えてみます（[ ... ] は省略可能を表します）。JJTreeと￢＜＞＜∪∪では、例えば次のように記述されます。

// BNF
ForStatement ::= "for" "(" [ ForInit ] ";" [ Expression ] ";" [ ForUpdate ] ")" Statement

// JJTree
void forStatement() #ForStatement :
{}
{
    "for" "(" [ forInit() ] ";" [ expression() ] ";" [ forUpdate() ] ")" statement()
}

// ￢＜＞＜∪∪
ForStatement -> Statement {
    "for" "(" [ forInit:ForInit ] ";" [ condition:expression ] ";" [ forUpdate:ForUpdate ] ")" statement:statement
}

JJTree では、JavaCC がメソッドを出力することを主眼においている関係で、メソッド宣言に似た形式で文法を記述します。￢＜＞＜∪∪では、クラスを出力することを主眼においているので、クラス宣言を連想させる（？）表記法になっています。JJTreeや￢＜＞＜∪∪はこれから次のようなクラスを出力し、入力されたテキストに対して、これらのクラスのインスタンスで作られたツリー状のデータ構造（構文木）を出力します。

// JJTree の出力
class Node {
    Node[] children;
}
class ForStatement extends Node {
}

// ￢＜＞＜∪∪の出力
class ForStatement extends Statement {
    ForInit forInit();
    Expression condition();
    ForUpdate forUpdate();
    Statement statement();
}

￢＜＞＜∪∪では、親クラスの指定が可能になっている点と、label: の形式でラベルを付けておくとメソッドが出力される点が異なります。JJTree の場合、for (x; y; z) s の x, y, z, s が、children で保持されます。ところが、x, y, z のうち省略されたものがあると、その要素の分だけ children の長さが短くなります。例えば y にアクセスしたい場合、x が省略されていれば children[0] で y にアクセスし、省略されていなければ children[1] でアクセスしなければなりません（もちろん y が省略されていた場合、ForUpdate か Statement が入っています）。というわけで、JJTree では、ユーザはfor文の条件式を得るための、次のようなメソッドを書くことになります。一方、￢＜＞＜∪∪では、ラベルを付けるだけで、このようなメソッドはコンパイラ・コンパイラが出力します。

static Expression conditionOf(ForStatement f) {
    Node result;
    if (f.children[0] instanceof ForInit) {
        result = f.children[1];
    } else {
        result = f.children[0];
    }
    if (result instanceof Expression) {
        return (Expression) result;
    } else {
        return null;
    }
}

JJTree でも、文法を変更することで children を固定長にすれば、(Expression) children[1] のように毎回書くことでメソッドを作らずにすますこともできますが、マジックナンバーを添え字に書いたり、いちいちキャストしなければなりません。また、文法を変更した場合に children[1] を children[2] に変更しなければならない可能性もあり、メソッドを作るほうが安全です。

■ 一方、JavaCC で構文木を作る場合は、記述は次のようになります。

ForStatement forStatement() :
{ ForInit n1 = null;
  Expression n2 = null;
  ForUpdate n3 = null;
  Statement n4 = null; }
{
  "for" "("
  [ n1=forInit() ] ";"
  [ n2=expression() ] ";"
  [ n3=forUpdate() ] ")"
  n4=statement()
  { return new ForStatement(n1, n2, n3, n4); }
}

部分的にJavaのプログラムが埋め込まれています。ここでは、入力されたテキストにfor文が見つかったら、変数 n1～n4 を用意して、forInit などの構文要素を表すオブジェクトを適宜代入し、最後に ForStatement オブジェクトを作成する、といったことが書かれています。こういったコードや、クラス ForStatement は丸ごとユーザが記述するわけで、￢＜＞＜∪∪やJJTreeと比べるとかなり面倒です。

これ以外には、次のような違いがあります。

■ JavaCC/JJTree では、JavaCC が得意な部分はJavaCCにまかせつつ、JavaCC では手に負えない部分は人間がハンドリングするということが比較的簡単にできます。一方￢＜＞＜∪∪でそれを行うのは困難で、基本的に全て￢＜＞＜∪∪に任せる形になります。また JavaCC のハンドリングは強力で、複雑な文法であろうが曖昧な文法であろうが、人間がプログラムを書きさえすれば扱うことができます。

■ しかしその代償として、JavaCC/JJTree では、人間のハンドリングなしに処理できる文法はあまり多くありません。例えば次の文法を扱えません。

// BNF
  expr ::= term
         | expr "+" term

  term ::= factor
         | term "*" factor

factor ::= "(" expr ")"
         | NUMBER

一方￢＜＞＜∪∪は、曖昧でない文法であれば、（拡張）BNFで記述できるものはなんでも扱えます。これは、Yacc が扱える文法よりも広範囲です。例えば、Yacc では Java 1.5 の文法を扱うのは困難ですが、￢＜＞＜∪∪では扱えます。

■ その他に、トークンの定義の書き方が少し違ったり、算術式の構文木を扱うときの考え方が少し違ったりします。

■ まとめ

ForStatement -> Statement {
  "for" "("
  [ forInit:ForInit ] ";"
  [ condition:expression ] ";"
  [ forUpdate:ForUpdate ] ")"
  statement:statement
}

void forStatement() #ForStatement :
{}
{
  "for" "("
  [ forInit() ] ";"
  [ expression() ] ";"
  [ forUpdate() ] ")"
  statement()
}

ForStatement forStatement() :
{ ForInit n1 = null;
  Expression n2 = null;
  ForUpdate n3 = null;
  Statement n4 = null; }
{
  "for" "("
  [ n1=forInit() ] ";"
  [ n2=expression() ] ";"
  [ n3=forUpdate() ] ")"
  n4=statement()
  { return new ForStatement(n1, n2, n3, n4); }
}

class ForStatement extends Statement {
    ForInit forInit();
    Expression condition();
    ForUpdate forUpdate();
    Statement statement();
}

class Node {
    Node[] children;
}
class ForStatement extends Node {
}