Notes for

  1. 曖昧な文法
  2. 抽象構文木のノードに対して、フィールドやメソッドを追加する
    1. フィールドやメソッドを追加したクラスを作成し、そのインスタンスでツリーを置き換える
    2. ノードへメソッドを追加する代わりにノードを引数にとるメソッドを追加する
    3. AspectJを利用する
    4. javamergerを利用する
  3. シンタックスシュガー
    1. 文法による吸収
    2. ツリーの書き換えによる除去
  4. ¬<><∪∪によるソースプログラムの整形
  5. --target
  6. リストと配列
  7. パーザのカスタマイズ
    1. プログラムの流れ
    2. createLexicalAnalyzer
      1. next()
      2. nextChar()
    3. createNode
    4. modifyWholeTree
    5. パーザのアクセス制限
  8. ¬<><∪∪ Syntax by ¬<><∪∪
  9. ¬<><∪∪の名前
  10. 名前の由来

§1 曖昧な文法

¬<><∪∪は任意の曖昧でない文脈自由文法(CFG)を扱うことができますが、文法が曖昧かどうかは、パーザを生成する時点では完全にチェックできません。現在の¬<><∪∪処理系は、¬<><∪∪へ入力されたソースが曖昧である可能性がある場合、以下で説明されるような警告メッセージを出力します。警告メッセージが出力されなかった場合、文法が曖昧でないことが、¬<><∪∪処理系によって(ライセンスに定める「無保証」の範囲で)保証されます。警告メッセージが出力された場合、¬<><∪∪へ入力されたソースは曖昧であるかもしれませんし、そうでないかもしれません。この場合、文法が曖昧でないことは、ユーザによって保証されなければなりません。

現在の¬<><∪∪処理系は、まず LALR(1) のコンフリクトが存在するかどうかを調べます。続いて、簡単な追跡調査を行い、それらのコンフリクトから曖昧性をもたらさないものを除外し、残ったコンフリクトの一覧を警告メッセージとして出力します。以下に警告メッセージの例を示します。

曖昧な文法の例:

警告メッセージ:

LALR(1)は、入力されたトークンをスタックに積んでいき、可能ならばスタックのトップからいくつかをポップし、取り除かれたものを子とするツリー(の根)をプッシュすることを繰り返す構文解析アルゴリズムです。最後にスタックに1つだけ残ったツリーが、構文木になります。¬<><∪∪は、LALR(1)をCFGを扱えるように拡張した構文解析アルゴリズムを使用します。ノードの置き換えを還元と呼び、入力されたトークンをスタックに積むことをシフトと呼びます。LALR(1) では、次に入力されるトークン1つを見て、そのトークンをシフトするか、そのトークンは置いておいて今あるスタックに対して還元操作を行うかを決定しなければなりません。決定できないことを、コンフリクトと呼びます。コンフリクトには、異なる2つ以上の還元が可能な場合(還元/還元コンフリクト)と、還元もシフトも可能な場合(シフト/還元コンフリクト)があります。上の例では、次のシフト/還元コンフリクトが報告されています。

LALR(1) では、リソースの消費を抑えるために、いくつかの状態を同一視します。この影響で、行えないはずの還元やシフトが可能であると報告されたり、一見コンフリクトしていないものがコンフリクトしていると報告されたりする場合があります。

§2 抽象構文木のノードに対して、フィールドやメソッドを追加する

いくつかの方法があります。例として、次の式を表す抽象構文木に、式の値を計算するメソッドを追加する場合を扱います。

$parser OriginalParser;

$abstract Expression { }
expr = Addition -> Expr { operand1:expr "+" operand2:term }
     | Subtraction -> Expr { operand1:expr "-" operand2:term }
     | term
     ;

:

(1) フィールドやメソッドを追加したクラスを作成し、そのインスタンスでツリーを置き換える

¬<><∪∪が出力したクラスを extends した新しいクラスを作成し、そのインスタンスを、ノードを作成するファクトリーメソッドである createNode() で返します。

public class ExtendedParser extends OriginalParser {
    public interface Expression extends OriginalParser.Expression {
        public double evaluate(); // 追加されたメソッド:式の値を計算する
    }
    private class AdditionReplacement extends OriginalParser.Default.Addition implements Expression {
        ...
        public double evaluate() {
            Expression x1 = (Expression) operand1();
                // operand1 は、OriginalParser.Expression なのでキャストが必要
            Expression x2 = (Expression) operand2();
            return x1.evaluate() + x2.evaluate();
        }
    }
    ...
    protected Node createNode(int symbolID, NodeInitializationParameters parameters) {
        // Addition の代わりに AdditionReplacement を返す etc.
        ...
    }
}

このようにして、ツリーのノードを、フィールドやメソッドが追加されたバージョンに差し替えます。この方法の欠点は、(ExtendedParser.Expression) operand1() のようなキャストをユーザも行う必要があることと、多くのコードを手作業で追加しなければならないことです。

(2) ノードへメソッドを追加する代わりにノードを引数にとるメソッドを追加する

double evaluate(Expression expression) {
    if (expression instanceof Addition) {
        Addition addition = (Addition) expression;
        Expression x1 = addition.operand1();
        Expression x2 = addition.operand2();
        return evaluate(x1) + evaluate(x2);
    }
    ...
}

Expressionevaluate メソッドを追加する代わりに、Expression を引数にとる evaluate メソッドを用意します。この方法の欠点は、if文とキャストを書くのが面倒なことと、Expressionextends する新しいクラスを追加したときに、evaluate メソッドの更新を忘れてもコンパイルエラーが発生しないことです。

フィールドを追加したい場合、HashMap等によって代替します。

(3) AspectJを利用する

次のような AspectJ プログラムを用いることで、¬<><∪∪が出力するJavaソースを直接書き換えたかのように、メソッドやフィールドを追加することができます。AspectJは分割コンパイルに対応していないようなので、大規模なプログラムには向かないかもしれません。

public aspect Evaluation {
    public abstract double OriginalParser.Expression.evaluate();
    public double OriginalParser.Addition.evaluate() {
        return operand1().evaluate() + operand2().evaluate()
    }
    :
}

(4) javamergerを利用する

¬<><∪∪には、サンプルプログラムとして、複数のJavaのソースファイルを1つにマージするプログラム(javamerger)が付属しています。これを用いることで、ソースファイルレベルでメソッドやフィールドを追加することができます。追加するメソッドを次のように記述し、¬<><∪∪の出力するファイルとマージします。

public class OriginalParser {
    public static interface Expression {
        public double evaluate();
    }
    public static interface Default {
        public class Addition {
            public double evaluate() {
                return operand1().evaluate() + operand2().evaluate()
            }
        }
        :
    }
}

この方法のデメリットは、javamerger がサンプルプログラムとしての質しかもたないことです。仕様はしっかり決まっていませんし、エラーチェックもしません。また、比較的多量のメモリを消費します(--x-separate-output オプションによって¬<><∪∪が出力するファイルを分割することで若干改善されます)。

§3 シンタックスシュガー

(1) 文法による吸収

引き算(Subtraction)が、足し算(Addition)と単項演算子のマイナス(Minus)を用いて表現できるシンタックスシュガーであることを次のように表現できます。

Minus    { "-" operand:expression }
Addition { operand1:expression "+" operand2:expression}

$private Subtraction -> Addition { operand1:expression "-" operand2:SubtractionRHS }
$private SubtractionRHS -> Minus { operand:expression }

Subtraction は文法上 expression "-" expression ですが、Additionをextendsしているため足し算として扱われます。その2つめのオペランド(SubtractionRHS)は、Minus をextendsしているので、単項マイナスとして扱われます。SubtractionSubtractionRHS$private 修飾されており、パーザの外部からアクセスできません。

(2) ツリーの書き換えによる除去

生成された抽象構文木を書き換えることで、シンタックスシュガーを除去することができます。¬<><∪∪が出力したクラスを extends し、createNode をオーバーライドします。createNode は、NodeInitializationParameters 引数で与えられるノードを子に持つノードを構築するメソッドです。構文木はボトムアップで構築されます。ユーザは super.createNodeが返す部分木にたいして、Default.Node.replaceChild 等を用いて書き換えを行うことができます。根を変更したい場合、Default.Node.replaceChildを呼び出す代わりに、変更後のノードをこのメソッドから返します。戻り値がゴール記号(開始記号)のインスタンスになるのを待って一度に書き換えることもできますし、細かい単位で頻繁に書き換えを行うこともできます。書き換えられてツリーには残らないノードは $protected 修飾することで、パーザ以外からのアクセスを制限することができます。

書き換え後のオブジェクトの型が、書き換え前のオブジェクトの型より非限定的な場合、スラッシュを用いることでメソッドの戻り値の型をコントロールできます。A { label:B/C } は、文法としては A { label:B } と等価ですが、A のメソッド label の戻り値は、B と C の共通の型になります。

§4 ¬<><∪∪によるソースプログラムの整形

¬<><∪∪の抽象構文木は、コメントやホワイトスペースのトークンも含むため、構文木に含まれるトークン(のgetOriginalImage())を順に出力することで、構文解析の対象になったテキストを復元することができます。抽象構文木の一部分を書き換えることで特定のコードコンベンションに合うようにプログラムを修正したり、出力時にトークンに応じて処理を変えることで、色やリンクが付加されたHTMLに変換することができます。

§5 --target

コマンドラインのオプション --target により、特定のバージョンのJavaに最適なプログラムを出力することができます。次の値がサポートされています。デフォルトは、¬<><∪∪を実行しているJavaのVMのバージョンです。

引数 説明
1.2 1.4と、次の点が異なります。
  • java.lang.CharSequenceの代わりにjava.lang.StringBufferが使われます。
  • AmbiguousGrammarErrorは、java.lang.AssertionErrorではなく、java.lang.RuntimeExceptionのサブクラスです。
  • 1.4は、起こってはならない状況になった場合にjava.lang.AssertionErrorを発生させますが、1.3ではjava.lang.RuntimeExceptionが発生します。
1.3 1.2と同じです。
1.4 Java1.4 に最適なプログラムが出力されます。¬<><∪∪は、最初にJava1.4をターゲットとして開発されたため、最も安定しています。ドキュメント通りの出力が行われます。

また、バージョンに続けて :array と記述することで、ラベル付けに対応して出力されるメソッドの戻り値は、List ではなく配列になります。詳細は次のセクションを参照してください。

§6 リストと配列

複数の子をラベル付けする場合、それらの子を返すメソッドが出力されます。その戻り値は、デフォルトではjava.util.Listですが、コンパイル時に --version version:array の形式のオプションを用いることで配列にすることができます。例えば、

$parser Parser;
Root { label:Test* }
Test { }

の出力は次のようになります。

interface Root extends Node {
    public Test[] lable();
}

戻り値を配列にすることには、次のメリットがあります。

一方、次のデメリットもあります。

§7 パーザのカスタマイズ

¬<><∪∪が出力したクラスをextendsし、メソッドをオーバーライドすることで、様々なカスタマイズを加えることができます。

(1) プログラムの流れ

構文解析は、通常次の流れで実行されます。

(2) createLexicalAnalyzer

createLexicalAnalyzerをオーバーライドすることで、ユーザ独自の字句解析器を使用することができます。ユーザは、LexicalAnalyzerインターフェイスを実装した独自のクラスを利用することもできますし、Default.LexicalAnalyzerクラスを元にして、動作をカスタマイズすることもできます。Default.LexicalAnalyzerでは、次のメソッドをオーバーライドすることができます。

(2-1) next()

next()は、字句解析器から次のトークンを取り出すメソッドです。このメソッドをオーバーライドし、super.next()の結果を加工することができます。例えばJavaのassertのような文字列をキーワードとみなすか識別子とみなすかを実行時に変更することができます。また、super.next()を呼び出す代わりに独自にトークンを切り出すこともでき、正規表現では表現できないようなトークンを処理することができます。独自にトークンを切り出した場合、indexなどのフィールドを適切に更新しなければなりません。

(2-2) nextChar()

nextChar()は、入力されたテキストから次の1文字を取り出します。このメソッドをオーバーライドして、JavaのUnicodeエスケープなどの、文字列を文字にマッピングする処理を行うことができます。

Unicodeエスケープを扱いたい場合、このメソッドをオーバーライドして、nextUnicodeEscapedChar()を呼び出すのが簡単です。

(3) createNode

createNodeは、NodeInitializationParametersで与えられるノードを子に持つノードを構築します。createNode が返すのは、部分木であり、ノード単体ではありません。createNode が構築するノードの型は、1つ目の引数で示されます。

createNodeをオーバーライドすることで、次のことが可能になります。

ノードを書き換える場合、ユーザ独自のクラスのインスタンスを用いることができます。ユーザ独自のクラスは通常次のいずれかです。

(4) modifyWholeTree

構文木が構築されたときに呼び出されます。このメソッドをオーバーライドすることで、構築した構文木をユーザに返す直前のタイミングで、構文木を編集することができます。

(5) パーザのアクセス制限

カスタマイズを前提としたパーザを¬<><∪∪で出力させる場合、カスタマイズが加えられていないクラスに対するアクセスを制限したい場合があります。次の方法があります。

§8 ¬<><∪∪ Syntax by ¬<><∪∪

§9 ¬<><∪∪の名前

¬<><∪∪の正式な名前は、論理否定、小なり、大なり、小なり、2項演算子の集合和、2項演算子の集合和、と記述します。Unicodeでは U+00AC U+003C U+003E U+003C U+222A U+222A です(しかし、ローカライズに応じて、適切な文字を選択してもかまいません)。ASCIIで記述する必要があるときは、notavaCC と記述します。機械的な検索の対象になる場合、例えばウェブページ上では、notavaCC を併記したほうが良いでしょう。Javaのプログラム中では、Notavacc のようにキャピタライズします。これは、複数の単語からなる識別子から、機械的に単語を識別できるようにです。

§10 名前の由来