¬<><∪∪は任意の曖昧でない文脈自由文法(CFG)を扱うことができますが、文法が曖昧かどうかをチェックできません(ただし、曖昧であることが文法解析時に判明した場合、AssertionError
が発生します)。このため、文法が曖昧でないことは、ユーザによって保証されなければなりません。これを補助する機能として、¬<><∪∪は -v オプションが指定された場合 LALR(1) のコンフリクトを報告します。コンフリクトが存在しない場合、文法が曖昧でないことが保証されます。コンフリクトが存在する場合、文法は曖昧かもしれませんし、曖昧でないかもしれません。
曖昧な文法の例:
$token NUMBER = '0'..'9'+; $parsable Root { expression } expression = Addition | NUMBER ; Addition { expression "+" expression }
この文法は、次のコンフリクトを引き起こします。
¬<><∪∪ Version 0.66 Copyright (c) Koto 2001-2002. Licensed Under GPL. generating parser from 'conflict.notavacc' to 'conflict.java'. conflict.notavacc: generating DFA. conflict.notavacc: generated. 3 states. conflict.notavacc: building the minimal form. conflict.notavacc: built. 3 states. conflict.notavacc: generating extended CFG. conflict.notavacc: generated. 8 states. conflict.notavacc: generating CFG. conflict.notavacc: generated. 9 states. conflict.notavacc: generating LR states. conflict.notavacc: generated. 8 states. conflict.notavacc: tagging. conflict.notavacc: tagged. conflict.notavacc: delivering look-a-head. conflict.notavacc: delivered. conflict.notavacc: generating reductions. conflict.notavacc:4: LALR(1) conflict: 'Addition' (line 4, column 11) with the input: conflict.notavacc:4: expression "+" expression conflict.notavacc:4: with the look-a-head "+", where the reducible nonterminals are: conflict.notavacc:4: 'Addition' (line 4, column 11) from expression "+" expression conflict.notavacc:4: also shiftable. conflict.notavacc: generated. conflict.notavacc: generating LR table. conflict.notavacc: generated. conflict.notavacc: generating types. conflict.notavacc: generated. 2 types. conflict.notavacc: writing to the file 'C:\WORK\02\programs\notavacc\docsrc\_pending\conflict.java'. conflict.notavacc: wrote. 66,738 bytes.
LALR(1) は、入力されたトークンをスタックに積んでいき、可能ならばスタックのトップからいくつかを取り除き、取り除かれたノードを子とする新しいノードに置き換えることを繰り返す、構文解析アルゴリズムです。ノードの置き換えを還元と呼び、還元せずにスタックに積むことをシフトと呼びます。還元を行うかシフトを行うかは、次に入力されるトークン1つを見て決定しなければなりません。決定できないことを、コンフリクトと呼びます。これは、異なる2つ以上の還元が可能な場合(還元還元コンフリクト)か、還元もシフトも可能な場合(シフト還元コンフリクト)、それらが組み合わさったもののいずれかです。上の例では、次のシフト還元コンフリクトが報告されています。
Addition
が期待される状況で、expression
"+"
expression
が入力され(つまりスタックにつまれ)、
"+"
だった場合に、
expression
"+"
expression
を Addition
に還元できるexpression
が続き、スタックが expression
"+"
expression
"+"
expression
になった時点で、トップの3つを Addition
に還元することができる)次の方法があります。
ユーザにとっては最も負担のない理想的な方法ですが、提供者の負担が大きくなります。¬<><∪∪ソースや、¬<><∪∪処理系を変更した場合に、コードの書き換えを再び行わなければなりません。
¬<><∪∪が出力したクラス (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()
のようなキャストをユーザも行う必要があることと、多くのコードを手作業で追加しなければならないことです。
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
等によって代替します。
引き算(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しているので、単項マイナスとして扱われます。Subtraction
と SubtractionRHS
は $private
修飾されており、パーサの外部からアクセスできないため、Addition
や Minus
とは、わざわざ子のノードを調べない限り、区別がつきません。
生成された抽象構文木を書き換えることで、シンタックスシュガーを除去することができます。¬<><∪∪が出力したクラスを extends
し、ノードを作成するファクトリーメソッドである createNode
をオーバーライドします。super.createNode
が返したノードのツリーに対して、Default.Node.replace 等を用いて書き換えを行うことができます。書き換えられるノードは $protected
修飾するのがよいでしょう。
書き換え後のオブジェクトの型が、書き換え前のオブジェクトの型の特定の親の型の場合、RestrictorExpression を用いることで、メソッドの戻り値の型をコントロールできます。A { label:B/C }
は、文法としては A { label:B }
と等価ですが、A のメソッド label の戻り値は、B と C の共通の型になります。
¬<><∪∪の抽象構文木は、コメントやホワイトスペースのトークンも含むため、構文木に含まれるトークンを順に出力することで、構文解析の対象になったテキストを復元することができます。抽象構文木の一部分を書き換えることで特定のコードコンベンションに合うようにプログラムを修正したり、出力時にトークンに応じて処理を変えることで、色やリンクが付加されたHTMLに変換することができます。