このドキュメントでは、（￢＜＞＜∪∪コンパイラ・コンパイラが出力するパーザへの入力ではなく）￢＜＞＜∪∪コンパイラ・コンパイラへの入力がどのように解釈されるかを説明する。コンパイラ・コンパイラの実行時のエラーを「コンパイル時エラー」、出力されたパーザの実行時のエラーを「実行時エラー」と呼ぶ。
￢＜＞＜∪∪コンパイラ・コンパイラへの入力は、Javaと同じプロセス(JLS 3.2)でトークンの列に変換される。ただし、終端記号は次のようになる。
| 終端記号 | 説明 |
|---|---|
| IDENTIFIER | Java の識別子か予約語で、$で始まらないもの |
| キーワード | $で始まる語 |
| セパレータ・オペレータ | 以下のEBNFで使われる文字列、および、||、&&、--、!!、**、++、?? |
| CHARACTER | Javaの文字リテラル |
| STRING | Javaの文字列リテラル |
このドキュメントは、￢＜＞＜∪∪への入力の文法を、次の記法を用いたEBNFで示す。
| メタ表現 | 説明 |
|---|---|
| Italic もしくは italic | 非終端記号 |
| ITALIC | 終端記号（シンボル） |
Underlined |
終端記号（即値） |
| expr1 | expr2 | 選択 |
| expr* | Kleene star |
| expropt | 省略可能 |
トークンの列は、次の文法に従っていなければならない。ゴール記号（開始記号）は、Rootである。
| Root | ::= | ParserDeclaration ConstructorScopeopt definition* |
| ParserDeclaration | ::= | $protectedopt $parser JavaName ; |
| JavaName | ::= | IDENTIFIER ( . IDENTIFIER )* |
| ConstructorScope | ::= | $protected $constructor ; |
| definition | ::= | SubtokenDefinition | TokenDefinition | AliasDefinition | TypeDefinition |
￢＜＞＜∪∪はJavaのソースファイルを１つ出力し、それは多数のネストしたタイプを含むトップレベル・クラスを１つ定義する。トップレベル・クラスの完全限定名が、ParserDeclarationによって決められる。ParserDeclarationが$protectedの場合、出力されるクラスはデフォルトスコープ (パッケージスコープ) になり、そうでない場合publicになる。ConstructorScopeは、出力されるトップレベル・クラスのコンストラクタを、デフォルトスコープ (パッケージスコープ) にする。definitionは、出力されるクラスの詳細を定義する。
$parser packagename.Parser; :
この例は、packagename.Parserという名前のトップレベルクラスを出力する。
| TokenDefinition | ::= | $whiteopt $token IDENTIFIER ( = tokenExpression )opt ; |
| SubtokenDefinition | ::= | $subtoken IDENTIFIER = tokenExpression ; |
出力されるトップレベル・クラスは、字句解析のためのインターフェイスと、デフォルトの実装を含む。デフォルトの実装は、入力された文字列の先頭から、以下で定義される終端記号のどれかが最長一致でマッチする文字列をトークン (その終端記号のインスタンスとも呼ぶ) として切り出すことを繰り返す。
１つのTokenDefinitionは、１つの終端記号を定義する。終端記号は、tokenExpressionがマッチする文字の列にマッチする。ただし、tokenExpressionが省略されていた場合、そのTokenDefinitionによって定義される終端記号は、どの列にもマッチしない (ユーザ定義の字句解析器のためだけに使われる)。AliasDefinitionおよび、$abstractでないTypeDefinitionにおけるexpression中のSTRINGも終端記号を定義する。この終端記号は、文字列リテラルが表す文字列にマッチする。同じ文字列を表す複数の文字列リテラルは、合わせて１つの終端記号を定義する。また、文字列リテラルが表す文字列だけにマッチするtokenExpressionを持つTokenDefinitionが１つだけ存在する場合、そのTokenDefinitionと文字列リテラルは合わせて１つの終端記号を定義する。
２つ以上の終端記号が同じ文字列にマッチする場合、コンパイル時エラーである。終端記号が長さ０の文字列にマッチする場合、コンパイル時エラーである。TokenDefinitionにおいて、tokenExpressionが省略されていないにもかかわらず、どの文字列にもマッチしない場合コンパイル時エラーである。
もし、終端記号が$whiteとして定義されていれば、そのインスタンスをホワイト・トークンと呼ぶ。ホワイト・トークンは、ホワイトスペースやコメントを扱うのに使われる。
SubtokenDefinitionは、tokenExpressionに対して名前を与える。この名前は、他のtokenExpressionの中で使うことができる。
TokenDefinitionやSubtokenDefinitionでは、tokenExpressionに、いま定義しているIDENTIFIERが出現してはならない。これには、SubtokenDefinitionを介した場合も含まれる。
tokenExpressionは次の表で定義される（より厳密な文法は、Syntax in EBNFで定義される）。
| 優先順位 | tokenExpression | マッチする文字列 |
|---|---|---|
| 6 | expr1 | expr2 |
どちらかがマッチする文字列 |
| 5 | expr1 & expr2 |
両方がマッチする文字列 |
expr1 - expr2 |
前者がマッチし、後者がしない文字列 | |
| 4 | expr1 expr2 ... | マッチした文字列をつなげた文字列 |
| 3 | ! expr |
マッチしない文字列 |
| 2 | expr * |
0回以上の繰り返し |
expr + |
1回以上の繰り返し | |
expr ? |
0か1回の繰り返し | |
| 1 | [ expr ] |
0か1回の繰り返し |
( expr ) |
exprがマッチする文字列 | |
| CHARACTER | CHARACTERが表す文字 | |
CHARACTER .. CHARACTER |
その範囲にある文字 | |
| STRING | STRINGが表す文字列 | |
| IDENTIFIER | （サブ）終端記号がマッチする文字列 |
$subtoken ANY_CHARACTER = '\u0000'..'\uFFFF' ; $subtoken LINE_TERMINATOR = "\n" | "\r" | "\r\n" ; $subtoken OCTAL_DIGIT = '0'..'7' ; $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 ) ;
この例は、Java の文字リテラル・文字列リテラルを表す終端記号 CHARACTER および STRING を定義する。
| AliasDefinition | ::= | IDENTIFIER = expression ; |
| TypeDefinition | ::= | modifiers IDENTIFIER supertypesopt { expression } |
| modifiers | ::= | ( $protected | $private )opt $abstractopt |
| | | $parsable |
|
| | | $protected-parsable $protectedopt |
|
| supertypes | ::= | -> TypeName ( & TypeName )* |
| TypeName | ::= | IDENTIFIER |
| InlineExpression | ::= | TypeDefinition |
出力されるトップレベル・クラスは、字句解析器が出力するトークンの列を構文解析する構文解析器を含む。文法は、拡張されたEBNFで表現される。１つのAliasDefinitionか１つのTypeDefinitionが、１つのプロダクションを定義する。IDENTIFIERは、定義される非終端記号の名前を表し、expressionが、プロダクションの右辺をあらわす。TypeDefinitionは、expressionの中で、InlineExpressionとしても現れる。
非$abstractな非終端記号から導出される有限個のトークンの列が存在しない場合（死記号の場合）、コンパイル時エラーである。
expressionは次のように定義される（より厳密な文法は、Syntax in EBNFで定義される）。
| 優先順位 | expression | マッチするトークン列 |
|---|---|---|
| 5 | expr1 | expr2 |
いずれかがマッチする列 |
| 4 | expr1 expr2 ... | マッチする列をつなげたもの |
| 3 | expr * |
0回以上の繰り返し |
expr + |
1回以上の繰り返し | |
expr ? |
0か1回の繰り返し | |
expr / TypeName |
exprがマッチする列 （ラベルの型を制御するのに使われる） |
|
| 2 | IDENTIFIER : expr |
exprがマッチする列 (labeled expression) |
$label : expr |
exprがマッチする列 (labeled expression) |
|
| 1 | [ expr ] |
0か1回の繰り返し |
( expr ) |
exprがマッチする列 | |
$embed ( expr ) |
exprがマッチする列 (エイリアスをその式で置き換える) |
|
| IDENTIFIER | 終端・非終端記号がマッチする列 | |
| STRING | その終端記号 | |
| InlineExpression | その非終端記号がマッチする文字列 |
構文解析器は、最初に具象構文木 (CST; concrete syntax tree) を構築する。トークン（終端記号のインスタンス）が構文木の葉になり、非終端記号のインスタンスが構文木のノードを作る。子には順番があり、子は０個以上のラベルでラベル付けされる。label:expressionの形式のlabeled expressionは、expressionに含まれる終端・非終端記号のインスタンスが、labelによってラベル付けされることを表す。１つのラベルが複数のインスタンスをラベル付けしても良い。expressionの中に、同じラベルが字句的に複数回存在しても良い。
同じ入力に対して異なる具象構文木を構築可能なとき、その文法は曖昧な文法である。文法が曖昧である場合、コンパイル時エラーになる場合がある。コンパイル時エラーにならなかった場合、出力される構文解析器は、次のように動作する。入力に対して、異なる具象構文木を構築可能なとき、実行時エラー（AmbiguousGrammarError）である。１種類の具象構文木だけが構築可能なとき、実行時エラー（AmbiguousGrammarError）になるか、その構文木を構文解析の結果として構文解析を終了する。具象構文木が構築不能なとき、文法が曖昧だったとして実行時エラー（AmbiguousGrammarError）になるか、入力に誤りがあるとして実行時エラー（ParseException）になる。コンパイル時エラーになるかどうか、AmbiguousGrammarError になるかどうかは処理系に依存する。
プロダクションの右辺にホワイト・トークンをインスタンスとする終端記号を記述することはできないが、ホワイト・トークンは構文解析の対象となるテキスト中に自由に出現してよい。具象構文木をトラバースしたときにトークンを順に見ることで構文解析の対象となったトークン列を復元できる範囲で、ホワイト・トークンをなるべく根に近いノードが保持するように、また兄弟の間でなるべく順番が若くなるように具象構文木が作られる。
例：
$white $token SPACE = " " ;
$parsable A { "x" B "z" }
B { "y"? }
この例では、x y zが入力された場合、Aのインスタンスの子は、"x"、スペース、B、スペース、"z"になり、例えば "x"、B、"z"にはならない。x zが入力された場合、Aのインスタンスの子は、"x"、スペース、B、"z"になり、"x"、B、スペース、"z"にはならない。
具象構文木を構築した後、構文解析器は、具象構文木からノードを取り除くことで、抽象構文木 (AST; abstract syntax tree) を構築する。AliasDefinitionで定義される非終端記号（エイリアス）のインスタンスであるノードが、全て取り除かれる。取り除かれたノードの子は、取り除かれたノードの親の子になる。取り除かれたノードに$labelによってラベル付けされた子が存在した場合、取り除かれたノードをラベル付けしているラベルで、$labelを置き換える。取り除かれたノードのどの子も$labelによってラベル付けされていない場合、取り除かれたノードをラベル付けしているラベルによって、全ての子がラベル付けされる。
抽象構文木はJavaのオブジェクトによる木構造で表される。トークンは、ネストしたインターフェイスTokenのインスタンスで表される。葉以外のノードは、そのノードが具象構文木においてインスタンスであった非終端記号と同じ名前を持つネストしたインターフェイス のインスタンスで表される。
supertypesは、TypeDefinitionによって出力されるネストしたインターフェイスの継承関係を設定する。TypeNameは、TypeDefinitionによって定義された非終端記号の名前で無ければならない。もし、supertypesが無ければ、そのネストしたインターフェイスは、Nodeのサブインターフェイスになる。Tokenもまた、Nodeのサブインターフェイスである。
もし、非終端記号が$parsableと定義されていれば、出力されるトップレベル・クラスは、その非終端記号をゴール記号とする文法を構文解析する、様々な引数を伴ったpublicなメソッドを持つ。非終端記号が$protected-parsableと定義されていれば、同様だがprotectedなメソッドが出力される。
もし、非終端記号が$protectedか$privateと定義されていれば、その非終端記号と同名のネストしたインターフェイスは、protectedかprivateになる。そうでない場合、そのネストしたインターフェイスはpublicになる。
もし非終端記号が$abstractと定義されていれば、その非終端記号はネストしたインターフェイスを生成するが、構文木に現れることはできない。
TypeDefinitionによって出力されるネストしたインターフェイスは、ラベルと同名で、引数の無いメソッドを持つ。メソッドの戻り値は、そのラベルによってラベル付けされている子（高々１つの子しかラベル付けしない場合）、あるいは子のリスト（複数の子をラベル付けする可能性がある場合）である。戻り値の静的型は、前者の場合ラベル付けされる可能性のある子の型に共通の型（ラベル付けされる可能性のある子すべてを表せる型）で、公平に最も限定的な型（下で定義される）になる。後者の場合、公平に最も限定的な型の配列かjava.util.Listになる（コンパイル時のオプションによる）。
継承関係における子を親より限定的と定義する。型の集合に対して、公平に最も限定的な型を、次のように定義する。もし、型の集合の中で、１つの型がそれ以外の型のどれよりも限定的である場合、その型を公平に最も限定的な型とする。そうでない場合、より限定的な型が集合に含まれるような型を集合から取り除き、残った型すべてを表現できる型の集合を求めて、それらに対する公平に最も限定的な型を再帰的に求め、その結果をここで求める公平に最も限定的な型とする。
例：
A { }
B -> A { }
C -> A { }
X -> B & C { }
Y -> B & C { }
T { label:( X | Y ) }
に対して、メソッドlabelが返しうるオブジェクトはXかYであり、その両方を表現できる型（共通の型）は、Node、A、B、Cのいずれかである。BとCはAやNodeよりも限定的であるが、BはCより限定的でも、CはBより限定的でもない。従って、１つの型がそれ以外の型のどれよりも限定的ではない。この集合から、より限定的な型BおよびCが存在するAおよびNodeが除かれ、残ったB、Cの両方を表現できる型の中で、最も限定的な型が求められる。B、Cの両方を表現できる型はNodeかAであり、Aがより限定的である。これによって、メソッドlabelの戻り値の静的な型は、Aになる。
expr / TypeNameの形式は、文法上はexprを書いたのと同じだが、このexprに基づいて出力されるメソッドの戻り値は、TypeNameに示される型をも表現できるものになる。
例：
A { }
B -> A { }
C -> A { }
X -> B & C { }
Y -> B & C { }
T { label:( X | Y )/B }
上の例では、labelの戻り値の静的型は、X、Y、Bを表現できる型のなかで公平に最も限定的なものになり、Bになる。
$embedは、expressionをに含まれるエイリアスをコンパイル時に展開する。これは、LALR(1)のコンフリクトの報告に影響する。$embedは将来のバージョンでは単なる式のグループ化として扱われる可能性がある。