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