￢＜＞＜∪∪は任意の曖昧でない文脈自由文法（CFG）を扱うことができますが、文法が曖昧かどうかは、パーザを生成する時点では完全にチェックできません。現在の￢＜＞＜∪∪処理系は、￢＜＞＜∪∪へ入力されたソースが曖昧である可能性がある場合、以下で説明されるような警告メッセージを出力します。警告メッセージが出力されなかった場合、文法が曖昧でないことが、￢＜＞＜∪∪処理系によって（ライセンスに定める「無保証」の範囲で）保証されます。警告メッセージが出力された場合、￢＜＞＜∪∪へ入力されたソースは曖昧であるかもしれませんし、そうでないかもしれません。この場合、文法が曖昧でないことは、ユーザによって保証されなければなりません。
現在の￢＜＞＜∪∪処理系は、まず LALR(1) のコンフリクトが存在するかどうかを調べます。続いて、簡単な追跡調査を行い、それらのコンフリクトから曖昧性をもたらさないものを除外し、残ったコンフリクトの一覧を警告メッセージとして出力します。以下に警告メッセージの例を示します。
曖昧な文法の例：
$parser Conflict;
$token NUMBER = '0'..'9'+;
$parsable Root { expression }
expression = Addition | NUMBER ;
Addition { expression "+" expression }
警告メッセージ：
generating a parser from `Conflict.notavacc'. Conflict.notavacc:5:11: warning: LALR(1) conflict: `Addition' (line 5, column 11) may be ambiguous. Conflict.notavacc:5:11: warning: One of the input for it to the conflicted state is Conflict.notavacc:5:11: warning: `expression "+" expression' Conflict.notavacc:5:11: warning: For the lookahead `"+"', Conflict.notavacc:5:11: warning: the reducible nonterminal is Conflict.notavacc:5:11: warning: `Addition' (line 5, column 11) from `expression "+" expression' Conflict.notavacc:5:11: warning: also the lookahead is shiftable as follows: Conflict.notavacc:5:39: warning: `"+"' (line 5, column 39)
LALR(1)は、入力されたトークンをスタックに積んでいき、可能ならばスタックのトップからいくつかをポップし、取り除かれたものを子とするツリー（の根）をプッシュすることを繰り返す構文解析アルゴリズムです。最後にスタックに１つだけ残ったツリーが、構文木になります。￢＜＞＜∪∪は、LALR(1)をCFGを扱えるように拡張した構文解析アルゴリズムを使用します。ノードの置き換えを還元と呼び、入力されたトークンをスタックに積むことをシフトと呼びます。LALR(1) では、次に入力されるトークン１つを見て、そのトークンをシフトするか、そのトークンは置いておいて今あるスタックに対して還元操作を行うかを決定しなければなりません。決定できないことを、コンフリクトと呼びます。コンフリクトには、異なる２つ以上の還元が可能な場合（還元/還元コンフリクト）と、還元もシフトも可能な場合（シフト/還元コンフリクト）があります。上の例では、次のシフト/還元コンフリクトが報告されています。
Addition が期待される状況で、expression "+" expression が入力された（つまりスタックにつまれた）状態で、
"+" だった場合に、
expression "+" expression を Addition に還元できるexpression が続き、スタックが expression "+" expression "+" expression になった時点で、トップの３つを Addition に還元することができる）LALR(1) では、リソースの消費を抑えるために、いくつかの状態を同一視します。この影響で、行えないはずの還元やシフトが可能であると報告されたり、一見コンフリクトしていないものがコンフリクトしていると報告されたりする場合があります。
いくつかの方法があります。例として、次の式を表す抽象構文木に、式の値を計算するメソッドを追加する場合を扱います。
$parser OriginalParser;
$abstract Expression { }
expr = Addition -> Expr { operand1:expr "+" operand2:term }
| Subtraction -> Expr { operand1:expr "-" operand2:term }
| term
;
:
￢＜＞＜∪∪が出力したクラスを 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() のようなキャストをユーザも行う必要があることと、多くのコードを手作業で追加しなければならないことです。
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 メソッドを用意します。この方法の欠点は、if文とキャストを書くのが面倒なことと、Expression を extends する新しいクラスを追加したときに、evaluate メソッドの更新を忘れてもコンパイルエラーが発生しないことです。
フィールドを追加したい場合、HashMap等によって代替します。
次のような AspectJ プログラムを用いることで、￢＜＞＜∪∪が出力するJavaソースを直接書き換えたかのように、メソッドやフィールドを追加することができます。AspectJは分割コンパイルに対応していないようなので、大規模なプログラムには向かないかもしれません。
public aspect Evaluation {
public abstract double OriginalParser.Expression.evaluate();
public double OriginalParser.Addition.evaluate() {
return operand1().evaluate() + operand2().evaluate()
}
:
}
￢＜＞＜∪∪には、サンプルプログラムとして、複数のJavaのソースファイルを１つにマージするプログラム（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 オプションによって￢＜＞＜∪∪が出力するファイルを分割することで若干改善されます）。
引き算（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しているため足し算として扱われます。その２つめのオペランド（SubtractionRHS）は、Minus をextendsしているので、単項マイナスとして扱われます。Subtraction と SubtractionRHS は $private 修飾されており、パーザの外部からアクセスできません。
生成された抽象構文木を書き換えることで、シンタックスシュガーを除去することができます。￢＜＞＜∪∪が出力したクラスを extends し、createNode をオーバーライドします。createNode は、NodeInitializationParameters 引数で与えられるノードを子に持つノードを構築するメソッドです。構文木はボトムアップで構築されます。ユーザは super.createNodeが返す部分木にたいして、Default.Node.replaceChild 等を用いて書き換えを行うことができます。根を変更したい場合、Default.Node.replaceChildを呼び出す代わりに、変更後のノードをこのメソッドから返します。戻り値がゴール記号（開始記号）のインスタンスになるのを待って一度に書き換えることもできますし、細かい単位で頻繁に書き換えを行うこともできます。書き換えられてツリーには残らないノードは $protected 修飾することで、パーザ以外からのアクセスを制限することができます。
書き換え後のオブジェクトの型が、書き換え前のオブジェクトの型より非限定的な場合、スラッシュを用いることでメソッドの戻り値の型をコントロールできます。A { label:B/C } は、文法としては A { label:B } と等価ですが、A のメソッド label の戻り値は、B と C の共通の型になります。
￢＜＞＜∪∪の抽象構文木は、コメントやホワイトスペースのトークンも含むため、構文木に含まれるトークン（のgetOriginalImage()）を順に出力することで、構文解析の対象になったテキストを復元することができます。抽象構文木の一部分を書き換えることで特定のコードコンベンションに合うようにプログラムを修正したり、出力時にトークンに応じて処理を変えることで、色やリンクが付加されたHTMLに変換することができます。
￢＜＞＜∪∪が出力したクラスをextendsし、メソッドをオーバーライドすることで、様々なカスタマイズを加えることができます。
構文解析は、通常次の流れで実行されます。
parse メソッドが呼び出されます。parse メソッドの引数を基にして、createLexicalAnalyzer によって字句解析器が作られます。createNode によって、ボトムアップで構文木が作られます。modifyWholeTree が呼び出され、その戻り値が parse メソッドの戻り値として返されます。
createLexicalAnalyzerをオーバーライドすることで、ユーザ独自の字句解析器を使用することができます。ユーザは、LexicalAnalyzerインターフェイスを実装した独自のクラスを利用することもできますし、Default.LexicalAnalyzerクラスを元にして、動作をカスタマイズすることもできます。Default.LexicalAnalyzerでは、次のメソッドをオーバーライドすることができます。
next()は、字句解析器から次のトークンを取り出すメソッドです。このメソッドをオーバーライドし、super.next()の結果を加工することができます。例えばJavaのassertのような文字列をキーワードとみなすか識別子とみなすかを実行時に変更することができます。また、super.next()を呼び出す代わりに独自にトークンを切り出すこともでき、正規表現では表現できないようなトークンを処理することができます。独自にトークンを切り出した場合、indexなどのフィールドを適切に更新しなければなりません。
nextChar()は、入力されたテキストから次の１文字を取り出します。このメソッドをオーバーライドして、JavaのUnicodeエスケープなどの、文字列を文字にマッピングする処理を行うことができます。
Unicodeエスケープを扱いたい場合、このメソッドをオーバーライドして、nextUnicodeEscapedChar()を呼び出すのが簡単です。
createNodeは、NodeInitializationParametersで与えられるノードを子に持つノードを構築します。createNode が返すのは、部分木であり、ノード単体ではありません。createNode が構築するノードの型は、１つ目の引数で示されます。
createNodeをオーバーライドすることで、次のことが可能になります。
createNode(int, TopLevelClass.NodeInitializationParameters, boolean)を利用することで、ラベル付けされていないノードをツリーから除外し、メモリの消費を抑えることができますsuper.createNodeあるいはデフォルトの型実装のコンストラクタによって作られたノードを根とする部分木に対して、Default.Node.replaceChild 等を用いて、根以外のノードの書き換えを行うことができます。super.createNodeあるいはデフォルトの型実装のコンストラクタによって作られたノードを参考にし、オブジェクトを独自にコンストラクトして返すことで、部分木の根を変更することができますノードを書き換える場合、ユーザ独自のクラスのインスタンスを用いることができます。ユーザ独自のクラスは通常次のいずれかです。
NodeInitializationParametersを取るものNodeの派生クラス構文木が構築されたときに呼び出されます。このメソッドをオーバーライドすることで、構築した構文木をユーザに返す直前のタイミングで、構文木を編集することができます。
カスタマイズを前提としたパーザを￢＜＞＜∪∪で出力させる場合、カスタマイズが加えられていないクラスに対するアクセスを制限したい場合があります。次の方法があります。
$packageの宣言の次に、$protected $constructor; と書くことによって、￢＜＞＜∪∪が出力するパーザのコンストラクタを、パッケージスコープにすることができます。これにより、カスタマイズが加えられていないパーザをインスタンス化できるのは、同じパッケージに属すクラスに限られます。$protected-parsable修飾子を用いることで、構文解析を行うメソッドをprotectedにすることができます。
$parser jp.gr.java_conf.koto.notavacc.parser.Original;
$protected $constructor;
// Token Definitions
$subtoken ANY_CHARACTER = '\u0000'..'\uFFFF' ;
$subtoken LINE_TERMINATOR = "\n" | "\r" | "\r\n" ;
$subtoken WHITE_SPACE = ' ' | '\t' | '\f' | LINE_TERMINATOR ;
$subtoken ALPHABET = 'A'..'Z' | 'a'..'z' ;
$subtoken DIGIT = '0'..'9' ;
$subtoken HEX_DIGIT = '0'..'9' | 'A'..'F' | 'a'..'f' ;
$subtoken OCTAL_DIGIT = '0'..'7' ;
$white $token WHITE_SPACES = WHITE_SPACE+ ;
$subtoken TRADITIONAL_COMMENT_WIDE_MATCH = "/*" ANY_CHARACTER* "*/" ;
$white $token TRADITIONAL_COMMENT = TRADITIONAL_COMMENT_WIDE_MATCH - ( TRADITIONAL_COMMENT_WIDE_MATCH ANY_CHARACTER+ ) ;
$white $token END_OF_LINE_COMMENT = "//" (ANY_CHARACTER - LINE_TERMINATOR)* LINE_TERMINATOR ;
$token IDENTIFIER = IDENTIFIER_START IDENTIFIER_PART* ;
$subtoken IDENTIFIER_START = 'A'..'Z' | '_' | 'a'..'z' | '\u0080'..'\uffff' ;
$subtoken IDENTIFIER_PART = '0'..'9' | '$' | IDENTIFIER_START ;
$token RESERVED_WORD = ( "$" IDENTIFIER_PART* )
- "$parser" - "$package" - "$constructor"
- "$token" - "$white" - "$subtoken"
- "$parsable" - "$abstract" - "$protected" - "$private"
- "$embed" - "$label"
;
$token RESERVED_MARK = "||" | "&&" | "--" | "!!" | "**" | "++" | "??" ;
/*
$token BOOLEAN = "true" | "false" ;
$token INTEGER = ( DECIMAL_INTEGER | HEX_INTEGER | OCTAL_INTEGER ) [ 'l' | 'L' ] ;
$subtoken DECIMAL_INTEGER = '0' | ( ( DIGIT - '0' ) DIGIT* ) ;
$subtoken HEX_INTEGER = '0' ( 'x' | 'X' ) HEX_DIGIT+ ;
$subtoken OCTAL_INTEGER = '0' OCTAL_DIGIT+ ;
$token FLOATING_POINT = ( FLOATING_POINT_HEAD EXPONENT_PART? FLOAT_TYPE_SUFFIX? ) - INTEGER ;
$subtoken FLOATING_POINT_HEAD = ( DIGIT* '.'? DIGIT* ) & ( ANY_CHARACTER* DIGIT ANY_CHARACTER* ) ;
$subtoken EXPONENT_PART = ( 'e' | 'E' ) [ '+' | '-' ] DIGIT+ ;
$subtoken FLOAT_TYPE_SUFFIX = 'f' | 'F' | 'd' | 'D' ;
*/
$token CHARACTER = '\'' ( CHARACTER_ELEMENT | '\"' ) '\'' ;
$token STRING = '\"' ( CHARACTER_ELEMENT | '\'' )* '\"' ;
$subtoken CHARACTER_ELEMENT = ( ANY_CHARACTER - LINE_TERMINATOR - '\\' - '\'' - '\"' ) | ESCAPE_SEQUENCE ;
$subtoken ESCAPE_SEQUENCE = ESCAPE_SEQUENCE1 | ESCAPE_SEQUENCE2 ;
$subtoken ESCAPE_SEQUENCE1 = '\\' ( 'n' | 't' | 'b' | 'r' | 'f' | '\\' | '\'' | '\"' ) ;
$subtoken ESCAPE_SEQUENCE2 = '\\' ( [ ['0'..'3'] OCTAL_DIGIT ] OCTAL_DIGIT ) ;
// Literals
StringLiteral { token:STRING }
CharacterLiteral { token:CHARACTER }
// Name
$abstract Name { identifier:IDENTIFIER }
TypeName -> Name { identifier:IDENTIFIER } // name of TypeDefinition
SubtokenName -> Name { identifier:IDENTIFIER } // name of SubtokenDefinition
SymbolName -> Name { identifier:IDENTIFIER } // name of TokenReservation, TypeDefinition, or AliasDefinition, but not WhiteTokenDefinition.
// Header
$parsable
Root { parserDeclaration:ParserDeclaration constructorScope:ConstructorScope? definition* ["\u001A"] }
ParserDeclaration { protectedKeyword:"$protected"? "$parser" name:JavaName ";" }
JavaName { identifiers:IDENTIFIER ( "." identifiers:IDENTIFIER )* }
ConstructorScope { "$protected" "$constructor" ";"}
// Definitions
$abstract Definition { identifier:IDENTIFIER }
definition = subtokenDefinitions: SubtokenDefinition
| tokenDefinitions: tokenReservations: subtokenDefinitions: TokenDefinition
| whiteTokenReservations: tokenDefinitions: tokenReservations: subtokenDefinitions: WhiteTokenDefinition
| tokenReservations: TokenReservation
| whiteTokenReservations: tokenReservations: WhiteTokenReservation
| typeDefinitions:TypeDefinition
| aliasDefinitions:AliasDefinition
;
SubtokenDefinition -> Definition
{ "$subtoken" identifier:IDENTIFIER "=" expression:tokenExpression ";" }
TokenDefinition -> SubtokenDefinition & TokenReservation
{ "$token" identifier:IDENTIFIER "=" expression:tokenExpression ";" }
WhiteTokenDefinition -> TokenDefinition & WhiteTokenReservation
{ "$white" "$token" identifier:IDENTIFIER "=" expression:tokenExpression ";" }
TokenReservation -> Definition
{ "$token" identifier:IDENTIFIER ";" }
WhiteTokenReservation -> TokenReservation
{ "$white" "$token" identifier:IDENTIFIER ";" }
TypeDefinition -> Definition
{ modifiers identifier:IDENTIFIER superTypes:superTypes "{" expression:expression "}" }
modifiers = [ protectedKeyword:"$protected" | privateKeyword:"$private" ] abstractKeyword:"$abstract"?
| parsableKeyword:"$parsable"
| protectedParsableKeyword:parsableKeyword:"$protected-parsable" protectedKeyword:"$protected"?
;
superTypes = [ "->" $label:TypeName ( "&" $label:TypeName )* ] ;
AliasDefinition -> Definition
{ identifier:IDENTIFIER "=" expression:expression ";" }
// Token Expressions
$abstract TokenExpression { }
tokenExpression = SelectiveTokenExpression/TokenExpression ;
SelectiveTokenExpression -> TokenExpression
{ operands:termTokenExpression ( "|" operands:termTokenExpression )* }
termTokenExpression = SequentialTokenExpression
| IntersectionTokenExpression
| DifferenceTokenExpression
;
IntersectionTokenExpression -> TokenExpression
{ lhs:termTokenExpression "&" rhs:SequentialTokenExpression/TokenExpression }
$private DifferenceTokenExpression -> IntersectionTokenExpression
{ lhs:termTokenExpression "-" rhs:DifferenceTokenExpressionRHS }
$private DifferenceTokenExpressionRHS -> ComplementaryTokenExpression
{ operand:SequentialTokenExpression }
SequentialTokenExpression -> TokenExpression
{ operands:prefixTokenExpression* }
prefixTokenExpression = postfixTokenExpression
| ComplementaryTokenExpression -> TokenExpression { "!" operand:prefixTokenExpression }
;
postfixTokenExpression = StarTokenExpression
| PlusTokenExpression -> TokenExpression { operand:postfixTokenExpression "+" }
| OptionalTokenExpression1
| primaryTokenExpression
;
$private StarTokenExpression -> SelectiveTokenExpression
{ operands:StarTokenExpressionConcrete operands:EmptyTokenExpression }
$private StarTokenExpressionConcrete -> PlusTokenExpression
{ operand:postfixTokenExpression "*" }
$private OptionalTokenExpression1 -> SelectiveTokenExpression
{ operands:postfixTokenExpression "?" operands:EmptyTokenExpression }
$private EmptyTokenExpression -> SequentialTokenExpression
{ }
primaryTokenExpression = $private CharacterTokenExpression -> CharacterRangeTokenExpression { lower:upper:CharacterLiteral }
| CharacterRangeTokenExpression -> TokenExpression { lower:CharacterLiteral ".." upper:CharacterLiteral }
| StringTokenExpression -> TokenExpression { string:StringLiteral }
| IdentifierTokenExpression -> TokenExpression { name:SubtokenName }
| OptionalTokenExpression2
| parenthesizedTokenExpression
;
$private OptionalTokenExpression2 -> SelectiveTokenExpression
{ "[" operands:tokenExpression "]" operands:EmptyTokenExpression }
parenthesizedTokenExpression
= "(" $label:tokenExpression ")" ;
// Expressions
$abstract Expression { }
expression = SelectiveExpression/Expression ;
SelectiveExpression -> Expression
{ operands:SequentialExpression/Expression ( "|" operands:SequentialExpression/Expression )* }
SequentialExpression -> Expression
{ operands:postfixExpression* }
postfixExpression = StarExpression
| PlusExpression -> Expression { operand:postfixExpression mark:"+" }
| OptionalExpression1
| RestrictorExpression -> Expression { operand:postfixExpression "/" typeRestrictor:TypeName }
| prefixExpression
;
$private StarExpression -> SelectiveExpression
{ operands:StarExpressionConcrete operands:EmptyExpression }
$private StarExpressionConcrete -> PlusExpression
{ operand:postfixExpression mark:"*" }
$private OptionalExpression1 -> SelectiveExpression
{ operands:postfixExpression "?" operands:EmptyExpression }
$private EmptyExpression -> SequentialExpression
{ }
prefixExpression = LabeledExpression -> Expression { label:( IDENTIFIER | "$label" ) ":" operand:prefixExpression }
| primaryExpression
;
primaryExpression = parenthesizedExpression
| EmbedExpression -> Expression { "$embed" "(" operand:expression ")" }
| StringExpression -> Expression { string:StringLiteral }
| $protected InlineExpression -> IdentifierExpression { typeDefinition:TypeDefinition }
| IdentifierExpression -> Expression { name:SymbolName }
| OptionalExpression2
;
$private OptionalExpression2 -> SelectiveExpression
{ "[" operands:expression "]" operands:EmptyExpression }
parenthesizedExpression = "(" $label:expression ")" ;
IDENTIFIERがJavaの識別子に使用できる文字だけで構成されていることは、別途確認されますInlineExpressionは、nameメソッドがTypeDefinitionで定義される識別子を返すように変更されたクラスのインスタンスに差し替えられます￢＜＞＜∪∪の正式な名前は、論理否定、小なり、大なり、小なり、２項演算子の集合和、２項演算子の集合和、と記述します。Unicodeでは U+00AC U+003C U+003E U+003C U+222A U+222A です（しかし、ローカライズに応じて、適切な文字を選択してもかまいません）。ASCIIで記述する必要があるときは、notavaCC と記述します。機械的な検索の対象になる場合、例えばウェブページ上では、notavaCC を併記したほうが良いでしょう。Javaのプログラム中では、Notavacc のようにキャピタライズします。これは、複数の単語からなる識別子から、機械的に単語を識別できるようにです。
|
← | |
← | |
← | |