本ドキュメントでは、下の表記法を使用します。
コードは、<code>タグによってマークアップされます。スタイルシートをサポートした環境では背景が灰色になります。
¬<><∪∪ソースの文法は、<pre>タグによってマークアップされます。スタイルシートをサポートした環境では緑色になります。
¬<><∪∪ソースの文法は次の拡張BNFで記述されます。
表記 | 意味 |
---|---|
式 | 式 | いずれか |
式 * | 0回以上の繰り返し |
式 + | 1回以上の繰り返し |
式 ? | 省略可能 |
[ 式 ] | 省略可能 |
( 式 ) | グループ化 |
"文字列" | 終端記号 |
¬<><∪∪処理系は、1つのテキストファイル(¬<><∪∪ソース)を入力に取ります。¬<><∪∪ソースは、Javaの処理系が行うのと同様に、コメント等が取り除かれ、トークンの列に変換されます。ただし、¬<><∪∪の識別子や予約語は、Javaとは異なります。
要素 | 説明 |
---|---|
識別子 | Javaの識別子およびJavaの予約語で、$を含まないもの |
予約語 | $package , $token , $subtoken , $WHITE_TOKEN , $protected , $abstract , $parsable , $embed , および $label |
文字列リテラル、文字リテラル | Javaと同様 |
オペレータ、セパレータ | ; , . , = , -> , & , | , - , ! , * , + , ? , [ , ] , .. , ( , ) , / , : , および # |
コメント、ホワイトスペース、改行 | Javaと同様 |
得られたトークン列は、次のRootにより定義される文法に従ってパースされます。
パッケージオプションは、出力されるJavaのクラスが属すパッケージ名を指定します。
¬<><∪∪ソースによって表現されるいくつかのオブジェクトは、名前をもちます。同じ名前をもつオブジェクトが複数存在することはありません。
型名は型の名前でなければなりません。部分終端記号名は、部分終端記号あるいは終端記号の名前でなければなりません。シンボル名は、非終端記号、あるいは、ホワイト・トークンをインスタンスとしない終端記号の名前でなければなりません。
¬<><∪∪処理系は、入力されたファイルの拡張子を .java に変更したファイルへ、public なトップ・レベル・クラスを1つ出力します。このJavaのクラスは、多数のネステッド・クラスを含みます。また、概念的には、字句解析器と構文解析器の2つのモジュールによって構成されます。
出力されるファイルには、ここで記述されるクラス・インターフェイス・メソッド・フィールドが含まれます。
字句解析器はLexicalAnalyzer
ネステッド・インターフェイス型のオブジェクトであり、トークンの列を出力します。トークンは、Token
ネステッド・インターフェイス型のオブジェクトで表現され、終端記号のいずれかのインスタンスです。終端記号は、¬<><∪∪ソース上の終端記号定義、文字列式、トークン予約によって、定義されます。トークンがどの終端記号のインスタンスであるかは、字句解析器によって決定されます。
¬<><∪∪処理系は、LexicalAnalyzer
を実装したDefault.LexicalAnalyzer
ネステッド・クラスを出力します。Default.LexicalAnalyzer
は、Unicodeのテキストをトークンの列に変換します。Default.LexicalAnalyzer
は、入力されたテキストの先頭から、終端記号がマッチする文字列の中で、最長の文字列をトークンとして切り出すことを繰り返します。異なる複数の終端記号が同じ文字列にマッチする場合、その¬<><∪∪ソースはエラーです。切り出されたトークンは、マッチした終端記号のインスタンスです。
識別子で表現される名前をもつ終端記号を定義します(3つめの形式では、$WHITE_TOKENという名前をもちます)。この終端記号は、トークン式がマッチする文字列にマッチします。2つめと3つめの形式で定義される終端記号のインスタンスは、ホワイト・トークンと呼ばれます。
別名定義、もしくは、abstractではない型定義における式に含まれる文字列式は、文字列式が表す文字列にのみマッチする終端記号を、もしそのような終端記号が他の方法によって定義されなければ、定義します。同じ文字列を表す文字列式が複数ある場合であっても、定義される終端記号は1つだけです。文字列式によって定義される終端記号は名前をもちません。
識別子を名前にもつ終端記号を定義します。この終端記号はどの文字列にもマッチしません。
トークン式は次のように、文字列にマッチします。
優先順位 | 形式 | マッチする文字列 |
---|---|---|
最低 | トークン式1 | トークン式2 |
どちらかのトークン式がマッチする文字列 |
5 | トークン式1 & トークン式2 |
両方の式がマッチする文字列 |
トークン式1 - トークン式2 |
トークン式1がマッチし、トークン式2がマッチしない文字列 | |
4 | トークン式1 トークン式2 トークン式3 ... |
トークン式1 トークン式2 トークン式3 ... がマッチする文字列を順につなげてできる文字列 |
3 | !トークン式 |
トークン式がマッチしない文字列 |
2 | トークン式* |
トークン式がマッチする文字列の0回以上の繰り返し |
トークン式+ |
トークン式がマッチする文字列の1回以上の繰り返し | |
トークン式? |
トークン式にマッチする文字列と、空の文字列 | |
[トークン式] |
||
最高 | 文字リテラル |
文字リテラルの表現する文字 |
文字リテラル1..文字リテラル2 |
文字リテラル1の文字コード以上で、文字リテラル2の文字コード以下の文字コードを持つ文字 | |
文字列リテラル |
文字列リテラルの表現する文字列 | |
識別子 (終端記号の名前) |
識別子を名前に持つ終端記号がマッチする文字列 | |
識別子 (部分終端記号の名前) |
識別子を名前に持つ部分終端記号がマッチする文字列 | |
(トークン式) |
トークン式がマッチする文字列 |
IdentifierTokenExpressionを、再帰的に用いることはできません。★もっと正確に書く
SubtokenDefinition ::= "$subtoken" IDENTIFIER "=" tokenExpression ";"
部分終端記号を定義します。この部分終端記号は、識別子を名前にもち、トークン式がマッチする文字列にマッチします。
構文解析器は、字句解析器の出力するトークン列を入力にとり、抽象構文木を出力します。この処理を構文解析と呼びます。構文解析器は、parsableな型定義毎に1つずつ用意されます。構文解析器は、型定義の定義する非終端記号がマッチする具象構文木を考え、その具象構文木の拡大具象構文木が入力されたトークン列にマッチするかを判断します(この拡大具象構文木を、その非終端記号の拡大具象構文木と呼びます)。もしマッチする拡大具象構文木が存在しない場合ParseException
が発生します。もし、マッチする拡大具象構文木が複数存在する場合、その¬<><∪∪ソースは曖昧であるといい、その¬<><∪∪ソースはエラーです。マッチする拡大具象構文木がただ1つ存在する場合、マッチした拡大具象構文木から生成される抽象構文木を返します。
具象構文木は、直感的にはラベル付・順序付の木で、形式的には次のいずれかです。
ただし、n は1以上の整数、N は任意の非終端記号で、C1, C2, C3, ..., Cn-1 は、ラベルの集合、型制限の集合、および具象構文木の3つ組みです。
以下、N(n) = <N, C(n-1)> = <N, C1, C2, ..., Cn-1> = <N, <L1, R1, T1>, <L2, R2, T2>, ..., <Ln-1, Rn-1, Tn-1>> とします。
ある非終端記号に対して、その非終端記号がマッチするn組みN(n)を、その非終端記号のインスタンスと呼びます。
具象構文木は、次のようにトークン列にマッチします。
ある具象構文木の拡大具象構文木は次のいずれかです。
ただし、m, l は0以上の整数、Wk は <φ, φ, ホワイト・トークン> をk個並べたもの、φは空集合です。
抽象構文木とは、具象構文木におけるn組みの最初の要素が、型定義による非終端記号であるような具象構文木で、形式的には次のいずれかです。
ただし、Nは任意の型定義による非終端記号で、C1, C2, C3, ..., Cn-1 は、ラベルの集合、型制限の集合、および抽象構文木の3つ組みです。
N が型定義による非終端記号のとき、具象構文木 N(n) から生成される抽象構文木は、<N, F(C1), F(C2), ..., F(Cn-1))> です。ここで、F は次のように定義されます。
$label
を含まない場合、F(<L, R, N(n)>) = <N, F(<L1∪L, R1∪R, T1>), F(<L2∪L, R2∪R, T2>), ..., F(<Ln-1∪L, Rn-1∪R, Tn-1>)>$label
を含む場合、F(<L, R, N(n)>) = <N, F(<L1←L, R1∪R, T1>), F(<L2←L, R2∪R, T2>), ..., F(<Ln-1←L, Rn-1∪R, Tn-1>)>
ただし、L←M は、L が$label
を含まないときLで、含むときL-{$label
}∪Mです。
型定義による非終端記号Nに対して、Nがマッチする具象構文木から生成される抽象構文木を、Nの広義のインスタンスと呼びます。
構文解析の結果である抽象構文木は、Javaのオブジェクトによるデータ構造によって表現されます。抽象構文木がn組みN(n)のとき、その構文木は、Nと同じ名前をもつネステッド・インターフェイスのオブジェクトによって表現されます。このネステッド・インターフェイスは、Node
ネステッド・インターフェイスを継承しており、getChildList
メソッドは、列 T1, T2, ..., Tn-1 を返します(ただし、Li が空集合でないような Tiのみからなる列を返す選択肢も用意されています)。また、このインターフェイスのラベルLを名前にもつメソッドが、集合 { Tk | L ∈ Lk } を返します。このメソッドの戻り値は、この集合の要素数が2個以上になるような、Nの広義のインスタンスが存在する場合java.util.List
型になります。そうでない場合、Nの広義のインスタンスN(n)の中で、L ∈ Lk を満たす Ck の集合 { <L1, R1, T1>, <L2, R2, T2>, ..., <Ln-1, Rn-1, Tn-1> } における、R1, R2, ..., Rn-1 に含まれる型、および、T1, T2, ..., T3 を広義のインスタンスとする型の共通の親の型になります。★ここ書き直し
privateではない型定義によって、同名のネステッド・インターフェイスが出力されます。$abstract
を伴う型定義は、abstractな型定義と呼ばれ、出力されるインターフェイスはアブストラクトです。$protected
を伴う型定義は、protectedな型定義と呼ばれ、出力されるインターフェイスはプロテクテッドです。$private
を伴う型定義は、privateな型定義と呼ばれ、出力されるインターフェイスはプライベートです(このインターフェイスは、実際には出力されない場合があります。このインターフェイスにリフレクションを用いてアクセスしてはなりません)。protected でも private でもない型定義はpublicな型定義であり、出力されるインターフェイスはパブリックです。$parsable
を伴う型定義は、parsableな型定義と呼ばれます。
->
の右側の&
によって区切られた識別子は、直接の親の型の名前です。出力されるネステッド・インターフェイスは、直接の親の型と同名のネステッド・インターフェイスをextends
します。
型定義は、識別子を名前にもつ非終端記号を定義します。この非終端記号は、具象構文木N(n)にマッチします。ただし、Nはこの非終端記号であり、C1, C2, ..., Cn-1 は式がマッチする3つ組みの列です。型定義が定義する非終端記号を、型定義による非終端記号、あるいは型と呼びます。
abstractではない型定義において、式は、abstractな型定義によって定義された非終端記号の名前を表すIdentifierExpressionを含むことはできません。
別名定義は、識別子を名前にもつ非終端記号を定義します。この非終端記号は、具象構文木N(n)にマッチします。ただし、Nはこの非終端記号であり、C1, C2, ..., Cn-1 は式がマッチする3つ組みの列です。別名定義が定義する非終端記号を、別名定義による非終端記号、あるいは別名と呼びます。
式は次のように、3つ組みの列にマッチします。φは空集合です。
優先順位 | 形式 | マッチする3つ組みの列★ここ書き直し |
---|---|---|
最低 | 式 | 式 |
いずれかの式がマッチする3つ組みの列 |
4 | 式1 式2 |
式1 式2がマッチする3つ組みを S1, S2 とするとき、列 S1 W* S2。ただし、W*は0個以上の<φ, φ, ホワイト・トークン> |
3 | 式* |
長さ0の列、および、SequentialExpression 式 式* が(再帰的に)マッチする列 |
式+ |
SequentialExpression 式 式* がマッチする列 |
|
式? |
式がマッチする3つ組みの列、および、長さ0の列 | |
[式] |
||
式 / 識別子 |
<L1, R1∪T, T1>, <L2, R2∪T, T2>, ..., <Ln-1, Rn-1∪T, Tn-1>、ただし、C(n-1)は式がマッチする列、Tは識別子を名前に持つ型 | |
2 | 識別子 : 式 |
<L1∪{L}, R1, T1>, <L2∪{L}, R2, T2>, ..., <Ln-1∪{L}, Rn-1, Tn-1>、ただし、C(n-1)は式がマッチする列、Lは識別子 |
$label : 式 |
<L1∪{$label }, R1, T1>, <L2∪{$label }, R2, T2>, ..., <Ln-1∪{$label }, Rn-1, Tn-1>、ただし、C(n-1)は、式がマッチする列 |
|
最高 | 識別子 (終端記号の名前) |
<φ, φ, T>、ただし、Tは、その名前をもつ終端記号のインスタンス |
識別子 (非終端記号の名前) |
<φ, φ, N>、ただし、Nは、その名前をもつ非端記号のインスタンス | |
文字列リテラル |
<φ, φ, T>、ただし、Tは、文字列リテラルが表す文字列のみにマッチする終端記号のインスタンス | |
型定義 |
<φ, φ, T>、ただし、Tは、型定義が定義する非終端記号のインスタンス | |
式 # 識別子 |
式がマッチする3つ組みの列★ | |
( 式 ) |
式がマッチする3つ組みの列 | |
$embed ( 式 ) |
式がマッチする3つ組みの列★ |
¬<><∪∪の正式な名前は、論理否定、小なり、大なり、小なり、2項演算子の集合和、2項演算子の集合和、と記述します。Unicodeでは U+00AC U+003C U+003E U+003C U+222A U+222A です。英数字のみで記述する必要があるときは、notavaCC と記述します。機械的な検索の対象になる場合、例えばウェブページ上では、notavaCC を併記したほうが良いでしょう。Javaのプログラム中では、Notavacc のようにキャピタライズします。これは、複数の単語からなる識別子から、機械的に単語を識別できるようにです。