Tips of 0.67

  1. 文法が曖昧でないことを保証する
    1. 警告メッセージの詳細
  2. 抽象構文木のノードに対して、フィールドやメソッドを追加する
    1. 出力されたJavaソースを直接書き換える
    2. ノードを、フィールドやメソッドが追加されたものに差し替える
    3. メソッドの代わりにノードを引数にとるメソッドを利用する
  3. シンタックスシュガー
    1. 文法による吸収
    2. ツリーの書き換えによる除去
  4. ¬<><∪∪によるソースプログラムのフォーマッティング

§1 文法が曖昧でないことを保証する

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

警告メッセージが出力される文法が曖昧でないことを保証するのに、次のようなアプローチがあります。

(1) 警告メッセージの詳細

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

曖昧な文法の例:

$token    NUMBER         = '0'..'9'+;
$parsable Root           { expression }
          expression     = Addition | NUMBER ;
          Addition       { expression "+" expression }

警告メッセージ:

generating a parser from 'conflict.notavacc' into 'conflict.java'.
conflict.notavacc:4: warning: LALR(1) conflicts: One of the input to the conflicted state is
conflict.notavacc:4: warning:         expression "+" expression, to parse 'Addition' (line 4, column 11).
conflict.notavacc:4: warning:     For the look-ahead "+",
conflict.notavacc:4: warning:     the reducible nonterminals are
conflict.notavacc:4: warning:         'Addition' (line 4, column 11) from expression "+" expression
conflict.notavacc:4: warning:         also shiftable.

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

LALR(1) は、異なる状態を同一視することで、消費するリソースを減らします。コンフリクトは、同一視される状態に対して1回だけ報告されるため、上で報告されている入力は、そのコンフリクトの一例であることに注意してください。また、その入力に対しては行えないはずの還元やシフトが可能であると報告されることもあります。詳細は、構文解析に関する文献を参照してください。

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

次の方法があります。

(1) 出力されたJavaソースを直接書き換える

ユーザにとっては最も負担のない理想的な方法ですが、提供者の負担が大きくなります。¬<><∪∪ソースや、¬<><∪∪処理系を変更した場合に、コードの書き換えを再び行わなければなりません。

(2) ノードを、フィールドやメソッドが追加されたものに差し替える

¬<><∪∪が出力したクラス (OriginalParser) を extends します。ノードを作成するファクトリーメソッドである createNode をオーバーライドします。

public class ExtendedParser extends OriginalParser {
    public interface Expression extends OriginalParser.Expression {
        public double evaluate(); // 追加されたメソッド:式の値を計算する
    }
    private class AdditionReplacement extends implements Expression OriginalParser.Default.Addition {
        ...
        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() のようなキャストをユーザも行う必要があることと、多くのコードを手作業で追加しなければならないことです。

(3) メソッドの代わりにノードを引数にとるメソッドを利用する

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);
    }
    ...
}

Expression に evaluate メソッドを追加する代わりに、Expression を引数にとる evaluate メソッドを用意します。この方法の欠点は、Expression を直接 extends する新しいクラスを追加した場合は、必ず evaluate を更新しなければならないこと(そして、更新を忘れてもコンパイルエラーが発生しないこと)と、本来の目標であるノードに対するフィールドやメソッドの追加を達成していないことです。

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

§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 修飾されており、パーサの外部からアクセスできないため、AdditionMinus とは、わざわざ子のノードを調べない限り、区別がつきません。

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

生成された抽象構文木を書き換えることで、シンタックスシュガーを除去することができます。¬<><∪∪が出力したクラスを extends し、ノードを作成するファクトリーメソッドである createNode をオーバーライドします。super.createNode が返したノードのツリーに対して、Default.Node.replace 等を用いて書き換えを行うことができます。書き換えられるノードは $protected 修飾するのがよいでしょう。

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

§4 ¬<><∪∪によるソースプログラムのフォーマッティング

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