このリリースでは、試験的に次の機能が実装されています。
--target オプションで 1.5 を指定した場合、Java 1.5 向けの出力を行います。
曖昧な文法についても構文木を扱うことを可能にする機能が追加されています。例えば次の文法は曖昧です。
$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 を¬<><∪∪のソース上で表現する方法にはいくつかの選択肢が考えられます。いかにこのリリースとは異なる手法と、そのメリット・デメリットなどを述べます。将来のリリースでは、以下で述べるような手法が採用されるかもしれません。
ifThenElse = ShortIf | LongIf ;
のようなエイリアスを導入し、DanglingElseAbsorber はこのエイリアスの箇所で ambiguity absorber を挿入したいときだけ候補になるというものです。この方法は、想定していない箇所で $absorber のインスタンスを作ってしまうことを避けられ、バグを表面化させる助けになります。また、どの $absorber を選択するかのチェックが、全ての $absorber を対象としなくなるのでパフォーマンスが良くなります。ただし、多くの非終端記号で ambiguity absorber が挿入候補になる場合、それらを個別に $absorber に結びつけるのは、記述量が増え大変です。このため、複数の非終端記号に対して一度に $absorber を割り当てるような記法が必要です。$token
IDENTIFIER =
$weak
tokenExpression ;
上の形式でトークンを定義した場合、このトークンは他の $weak ではないトークンがマッチする文字列にはマッチしなくなります。例えば識別子をこの形式で定義すれば、予約語は自動的に除かれます。
次の演算子が追加されています。
tokenExpression | 意味 |
---|---|
expr1 ++ expr2 |
expr2 で区切られた1個以上の expr1。つまり、expr1 ( expr2 expr1 ) * |
expr1 ** expr2 |
expr2 で区切られた0個以上の expr1。つまり、[ expr1 ( expr2 expr1 ) * ] |
tokenExpression と同じく次の演算子が追加されています。
expression | 意味 |
---|---|
expr1 ++ expr2 |
expr2 で区切られた1個以上の expr1。つまり、expr1 ( expr2 expr1 ) * |
expr1 ** expr2 |
expr2 で区切られた0個以上の expr1。つまり、[ expr1 ( expr2 expr1 ) * ] |
Syntax in EBNF を参照してください。