Experimental Features for

このリリースでは、試験的に次の機能が実装されています。

Java 1.5 への対応

--target オプションで 1.5 を指定した場合、Java 1.5 向けの出力を行います。

ambiguity absorber の追加

曖昧な文法についても構文木を扱うことを可能にする機能が追加されています。例えば次の文法は曖昧です。

$parsable
Root        { statement* }

statement   = SingleLineStatement { "statement" ";" }
            | LongIf
            | ShortIf
            ;

$abstract IfThenElseStatement
            { "if" "(" "expr" ")" thenPart:statement "else" elsePart:statement }
LongIf -> IfThenElseStatement
            { "if" "(" "expr" ")" thenPart:statement "else" elsePart:statement }
ShortIf -> IfThenElseStatement
            { "if" "(" "expr" ")" thenPart:statement }

この文法に対して次の入力を与えた場合、次の2種類の構文木を作ることができます(一部の枝を省略しています)。

入力:

statement;
if (expr) if (expr) statement; else statement;
statement;

構文木1:

Root
  SingleLineStatement
  LongIf
    ShortIf
      SingleLineStatement
    `else' (line 2, column 32)
    SingleLineStatement
  SingleLineStatement

構文木2:

Root
  SingleLineStatement
  ShortIf
    LongIf
      SingleLineStatement
      `else' (line 2, column 32)
      SingleLineStatement
  SingleLineStatement

ここで、2つの構文木で異なっている部分に ambiguity absorber と呼ぶノードを挿入し、異なっている部分を ambiguity absorber の子とすることで、1つの木にまとめます。

Root
  SingleLineStatement
  ambiguity absorber
    LongIf
      ShortIf
        SingleLineStatement
      `else' (line 2, column 32)
      SingleLineStatement
    ShortIf
      LongIf
        SingleLineStatement
        `else' (line 2, column 32)
        SingleLineStatement
  SingleLineStatement

この構文木をトラバースして、ambiguity absorber ごとに子のいずれかを選択することで、実用的なパフォーマンスで、複数の構文木のなかから1つを選択することができます。

¬<><∪∪で曖昧な文法を扱うには、例えば次のように ambiguity absorber の作成を宣言しなければなりません。

$absorber DanglingElseAbsorber -> IfThenElseStatement
            { shortIf:ShortIf | longIf:LongIf }

$parsable
Root        { statement* }

statement   = SingleLineStatement { "statement" ";" }
            | LongIf
            | ShortIf
            ;

$abstract IfThenElseStatement
            { "if" "(" "expr" ")" thenPart:statement "else" elsePart:statement }
LongIf -> IfThenElseStatement
            { "if" "(" "expr" ")" thenPart:statement "else" elsePart:statement }
ShortIf -> IfThenElseStatement
            { "if" "(" "expr" ")" thenPart:statement }

DanglingElseAbsorber は、LongIf と ShortIf を子に持つ ambiguity absorber を、DanglingElseAbsorber クラスのインスタンスで表現することを表します。

else をなるべく近い if に対応させるには、木を根からたどって、DanglingElseAbsorber に遭遇するたびに ShortIf を選択します。構文木を書き換えて、DanglingElseAbsorber を除去するプログラムは次のようになります。

    protected void fix(Node node) {
        Iterator it0 = node.getChildNodes().iterator();
        while (it0.hasNext()) {
            Node child = (Node) it0.next();
            
            if (child instanceof DanglingElseAbsorber) {
                DanglingElseAbsorber a = (DanglingElseAbsorber) child;
                ((Default.Node) node).replaceChild(child, a.shortIf());
                child = a.shortIf();
            }
            
            fix(child);
        }
    }

完全なプログラムは examples/dangling_else にあります。

曖昧な文法を扱う場合に、$absorber の導入にはあまり自由度はありません。構文解析の対象のテキストに対して、次で説明するように ambiguity absorber が挿入される場所が自動的に決定され、その absorber を表現できる $absorber 宣言が後述のように検索されます。そのときに、該当する $absorber が存在しない場合、AmbiguousGrammerError が発生します。特に $absorber が一つも無い場合、構文木が2つ以上得られる場合必ず AmbiguousGrammerError が発生するので、旧バージョンの¬<><∪∪と互換性を持っています。

ambiguity absorber が挿入される場所は次のように決まります。解析木のノードで、TypeDefinition で定義される非終端記号と、AliasDefinition で定義される非終端記号で子孫ノードを含めたエイリアス除去の結果単独のTypeDefinitionで定義されるノードに置き換わるもの(これは、与えられたテキストに対してであって、任意のテキストに対して単独のノードに置き換わるものではありません)のある箇所が、ambiguity absorber を挿入する候補になります。そのような候補の中で、最も根から遠い(葉に近い)位置に ambiguity absorber を挿入しようとします。ただし、ambiguity absorber でどのように子を選択したとしても、選択の結果得られる構文木がテキストを正しく表現していなければなりません。

$absorber の検索は、¬<><∪∪のソースファイル中の記述順に行われます。最も上にある $absorber から順番に、今扱っている ambiguity absorber をその $absorber で表現できるかが判定され、最初に表現可能と判定されたものが採用されます。$absorber で表現できるかが判定は次のように行われます。$absorber の { } 内に出現するラベルを順に見ていき、ambiguity absorber の子でそのラベルで表現できるものを割り当てます(label:Type+ の形式の場合、全ての Type を label に割り当てます)。全ての子をラベルに割り当てることができれば、その ambiguity absorber はその $absorber で表現できます。このとき、割り当てのないラベルがあってもかまいません。1つの子が、異なるラベルに同時に割り当てられることはありません。最初に割り当て可能と判断されたラベルに割り当てられます。

構文木を作ったときに、ambiguity absorber を表現している $absorber の型が、その親クラスのラベルの型に一致しない場合があります。この場合、親クラスの子はラベルの型に合うダミーのオブジェクトになり、getWrappedAmbiguityAbsorber() によって ambiguity absorber を取得できます。

曖昧な文法を扱う場合、次のことに注意してください。statement* のような記述で、片方の構文木で1つのstatementと扱われている部分が、他の構文木では2つのstatementを構成していたりしてはいけません。このような曖昧性があると、この statement* は一部分だけが異なったとしても、statement* 全体の複製が必要です。statement* に曖昧な箇所が複数あると、複製の数は、曖昧な箇所の数の指数関数になり、リソースの消費量が極端に増加します。そのような文法を扱う場合、StatementList { statement StatementList? } のような記述を用いることで、構文木のノードの子の数に上限を設けます。

ディスカッション

ambiguity absorber を¬<><∪∪のソース上で表現する方法にはいくつかの選択肢が考えられます。いかにこのリリースとは異なる手法と、そのメリット・デメリットなどを述べます。将来のリリースでは、以下で述べるような手法が採用されるかもしれません。

より根に近い位置での ambiguity absorber を許す方法。
このリリースでは、曖昧性は可能な限り局所的な ambiguity absorber で表現されますが、表現できる $absorber がない場合に、より根に近い位置への ambiguity absorber の挿入を試みる方法が考えられます。この手法では、曖昧性を広域的な ambiguity absorber で表現できるので、ユーザプログラムでは広域的に曖昧性を判断できるようになる可能性があります。一方で、$absorber の記述にバグがあった場合、構文解析対象のテキストの長さ応じて指数関数的にメモリを消費します。このようなバグがあった場合に、何が問題であるのかを特定するのは不可能ではないもののマンパワーが必要です。¬<><∪∪のソースにヒントを加えることで問題の特定を容易にする手法も考えられますが、¬<><∪∪の仕様を複雑にするよりは、ユーザプログラムで解決するほうが、学習コストなどの点から望ましいでしょう。
非終端記号ごとに $absorber を指定する方法。
このリリースでは、全ての $absorber でその適用範囲は文法全体ですが、ambiguity absorber の挿入候補である非終端記号ごとに $absorber を指定する方法が考えられます。例えば、上の例では、ifThenElse = ShortIf | LongIf ; のようなエイリアスを導入し、DanglingElseAbsorber はこのエイリアスの箇所で ambiguity absorber を挿入したいときだけ候補になるというものです。この方法は、想定していない箇所で $absorber のインスタンスを作ってしまうことを避けられ、バグを表面化させる助けになります。また、どの $absorber を選択するかのチェックが、全ての $absorber を対象としなくなるのでパフォーマンスが良くなります。ただし、多くの非終端記号で ambiguity absorber が挿入候補になる場合、それらを個別に $absorber に結びつけるのは、記述量が増え大変です。このため、複数の非終端記号に対して一度に $absorber を割り当てるような記法が必要です。
$absorber の優先順
出現順ではなく、より限定的なものを優先的に採用する方法があるかもしれませんが、適切な仕様やアルゴリズムは自明ではありません。現状の出現順の判定では、$absorber が増えたときに効率が悪くなる問題とあわせて考える必要があります。

弱いトークンの追加

$token IDENTIFIER = $weak tokenExpression ;

上の形式でトークンを定義した場合、このトークンは他の $weak ではないトークンがマッチする文字列にはマッチしなくなります。例えば識別子をこの形式で定義すれば、予約語は自動的に除かれます。

tokenExpression への演算子の追加

次の演算子が追加されています。

tokenExpression 意味
expr1 ++ expr2 expr2 で区切られた1個以上の expr1。つまり、expr1 ( expr2 expr1 )*
expr1 ** expr2 expr2 で区切られた0個以上の expr1。つまり、[ expr1 ( expr2 expr1 )* ]

expression への演算子の追加

tokenExpression と同じく次の演算子が追加されています。

expression 意味
expr1 ++ expr2 expr2 で区切られた1個以上の expr1。つまり、expr1 ( expr2 expr1 )*
expr1 ** expr2 expr2 で区切られた0個以上の expr1。つまり、[ expr1 ( expr2 expr1 )* ]

文法の詳細

Syntax in EBNF を参照してください。