このドキュメントは、¬<><∪∪の基本的な仕様を簡単に説明したものです。このドキュメントを読むには、Javaやパーサに関する基本的な知識が必要です(下記のCore Concept of ¬<><∪∪を読んで理解できる程度の知識が必要です)。正確さよりも分かりやすさを優先しており、より正確な仕様は仕様書に記述されています。
¬<><∪∪ (notavaCC) は、次の特徴を持ったパーサ・ジェネレータ(コンパイラ・コンパイラ)です。
"/*" ( ANY_CHARACTER* - ( ANY_CHARACTER* "*/" ANY_CHARACTER* ) ) "*/"
Addition -> Expression { operand1:expression "+" operand2:term }
Addition ::= expression "+" term
を意味すると同時に、パースの結果をinterface Addition extends Expression { Expression operand1(); Expression operand2(); }
operand1
やoperand2
は、ノードの特定の子をラベル付けする働きがあり、1 * (2 + 3)
は次のように表現されます。
具象構文木は、非終端記号のインスタンスをノードとし、終端記号のインスタンスを葉とする木だと考えることができます。¬<><∪∪における抽象構文木とは、具象構文木から一部のノードを取り除いたものです。取り除かれたノードの子供は、取り除かれたノードの親のノードの子供になります。¬<><∪∪では、ノードを取り除くかどうかは、インスタンスごとにではなく、非終端記号ごとに選択されます。¬<><∪∪では、BNFのプロダクション LHS ::= RHS
に相当する表記は LHS { RHS }
と LHS = RHS;
の2種類があり、後者はノードを構文木から取り除くことを意味します(上の例では、expression
や term
は expression = Addition | Subtraction | term ;
のように定義されていることを想定しています)。後者の等号を用いた表記は、直感的には、左辺の識別子を右辺の式で置き換えるシンタックスシュガーに近いものです(正確には異なりますが、本ドキュメントでは簡便のため、そのように説明されます)。抽象構文木のノードは、そのノードをインスタンスとする非終端記号と同名のインターフェイスのオブジェクトで表現され、インターフェイス間に継承関係を設定することができます。ノードの特定の子を、上の operand1
のように、ラベル付けし、インスタンスメソッドによって得ることができます。その戻り値は、ラベル付けされる可能性のあるノードの共通の親の型、あるいは、複数をラベル付けする可能性がある場合 java.util.List
になります(例えば label:expression ( "," label:expression )*
)。
Expression
{ operand1:expression "+" operand2:term }
Subtraction -> Expression
{ operand1:expression "-" operand2:term }
term = Multiplication -> Expression { operand1:term "*" operand2:factor }
| Division -> Expression { operand1:term "/" operand2:factor }
| factor
;
factor = parenthesizedExpression
| Number -> Expression { value:INTEGER }
;
parenthesizedExpression
= "(" $label:expression ")"
;
]]>
上のコードから、次のような出力が得られます。
¬<><∪∪処理系は、1つのテキストファイル(¬<><∪∪ソース)を入力に取ります。¬<><∪∪ソースは、Javaの処理系が行うのと同様に、コメント等が取り除かれ、トークンの列に変換されます。ただし、¬<><∪∪の識別子や予約語は、Javaとは異なります。
要素 | 説明 |
---|---|
識別子 | Javaの識別子およびJavaの予約語で、$を含まないもの |
予約語 | Javaの識別子で、$を含むものからとられます |
文字列リテラル、文字リテラル | Javaと同様 |
コメント、ホワイトスペース、改行 | Javaと同様 |
¬<><∪∪ソースは、次の形式をとります。
$package パッケージ名; // 出力されるJavaのクラスが属すパッケージの名前(オプション)
$protected $constructor; // コンストラクタのスコープ(オプション)
以下で説明されるような終端記号・非終端記号の定義
$protected $constructor;
を指定すると、出力されるパーサのコンストラクタが、(protectedではなく)デフォルトスコープ(パッケージスコープ)になります。指定されていない場合publicになります。
¬<><∪∪処理系は、入力されたファイルの拡張子を .java に変更したファイルへ、public なトップ・レベル・クラスを1つ出力します。このJavaのクラスは、多数のネステッド・クラスを含みます。また、概念的には、字句解析器と構文解析器の2つのモジュールによって構成されます。
出力されるファイルには、ここで記述されるクラス・インターフェイス・メソッド・フィールドが含まれます。
字句解析器は、入力されたテキストを、トークンの列に変換します。終端記号定義で指定されるトークン式にマッチする最長の文字列をトークンとして切り出すことを繰り返します。切り出されたトークンを、マッチした終端記号のインスタンスと呼びます。abstractではない型定義、あるいは、別名定義に含まれる文字列リテラルの表す文字列も、トークンとして切り出されます。トークンは、Token
型のオブジェクトです。
形式:$token 識別子 = トークン式 ;
形式:$white $token 識別子 = トークン式 ;
2つ目の形式は、ホワイトスペースやコメントなどの、文法上無視されるトークンを定義します。
形式:$subtoken 識別子 = トークン式 ;
トークン式の中で、右辺のトークン式の変わりに識別子を使用できるようにします。右辺のトークン式に、この識別子を間接・直接に含むことはできません。
優先順位 | 形式 | マッチする文字列 |
---|---|---|
最低 | トークン式1 | トークン式2 |
どちらかのトークン式がマッチする文字列 |
5 | トークン式1 & トークン式2 |
両方の式がマッチする文字列 |
トークン式1 - トークン式2 |
トークン式1がマッチし、トークン式2がマッチしない文字列 | |
4 | トークン式1 トークン式2 トークン式3 ... |
トークン式1 トークン式2 トークン式3 ... がマッチする文字列を順につなげてできる文字列 |
3 | !トークン式 |
トークン式がマッチしない文字列 |
2 | トークン式* |
トークン式がマッチする文字列の0回以上の繰り返し |
トークン式+ |
トークン式がマッチする文字列の1回以上の繰り返し | |
トークン式? |
トークン式にマッチする文字列と、空の文字列 | |
[トークン式] |
||
最高 | 文字リテラル |
文字リテラルの表現する文字 |
文字リテラル1..文字リテラル2 |
文字リテラル1の文字コード以上で、文字リテラル2の文字コード以下の文字コードを持つ文字 | |
文字列リテラル |
文字列リテラルの表現する文字列 | |
識別子 |
識別子を名前に持つ終端記号定義、部分終端記号定義の右辺のトークン式がマッチする文字列 | |
(トークン式) |
トークン式がマッチする文字列 |
構文解析器は、字句解析器の出力するトークン列を入力にとり、抽象構文木を出力します。
形式:修飾子 識別子 { 式 }
形式:修飾子 識別子 -> 親型1 & 親型2 & ... { 式 }
識別子が左辺、式が右辺であるような拡張BNFの等式と同様に、構文を構成する非終端記号を定義します。また、この非終端記号のインスタンス(パーズの結果得られる構文木のこの非終端記号に対応する部分)はこの非終端記号と同名のインターフェイスのオブジェクトで表現されます。親型が指定されている場合、インターフェイスはそれらの型をextends
します。そうでない場合、インターフェイスは、Node
インターフェイスをexnteds
します。インターフェイスは、式に含まれるラベルと同名で、引数を取らないメソッドを持ちます。このメソッドは、式の中でラベル付けされている終端記号・非終端記号のインスタンスを返します。もし、ラベル付けされるインスタンスの個数が、2以上になる可能性があれば、戻り値はjava.util.List
になります。そうでない場合、ラベル付けされる可能性のあるインスタンスに共通の型になります。
修飾子 | 意味 |
---|---|
$parsable | この非終端記号で定義される文法をパースするpublicなメソッドを出力する |
$protected-parsable | 上と同様だが、メソッドはprotectedになる |
$abstract | インターフェイスを出力するが、文法を定義するためには使用できない |
$protected | 出力されるインターフェイスがprotected になる |
$private | 出力されるインターフェイスがprivate になる |
$protected
も$private
も指定されていない場合、出力されるインターフェイスはpublic
になります。
形式:識別子 = 式 ;
式の中で、右辺の式の代わりに識別子を使用できるようにします。ただし、右辺の式が$label
を含む場合、この別名にかかるラベルは、右辺の式の$label
によってラベル付けされている終端記号・非終端記号・別名にのみ引き継がれます。そうでない場合、右辺に含まれる全ての終端記号・非終端記号・別名に引き継がれます。
例えば、次のコード
x = "a" "b" ;
y = $label:"a" "b" ;
z = $label:"a" $label:"b" ;
に対して、l:x
, l:y
, l:z
は、l:"a" l:"b"
, l:"a" "b"
, l:"a" l:"b"
と記述されているかのように扱われます。
優先順位 | 形式 | 意味 |
---|---|---|
最低 | 式 | 式 |
いずれか |
4 | 式 式 |
列 |
3 | 式* |
0回以上の繰り返し |
式+ |
1回以上の繰り返し | |
式? |
省略可能 | |
[式] |
||
式 / 識別子 |
式に含まれる終端記号・非終端記号が、識別子の型であるかのようにインターフェイスを出力する。これは、メソッドの戻り値の型をコントロールするために使用されます。 | |
2 | 識別子 : 式 |
式に含まれる終端記号・非終端記号・別名をラベル付けする |
$label : 式 |
式に含まれる終端記号・非終端記号・別名を$label でラベル付けする |
|
最高 | 識別子 |
その名前をもつ終端記号・非終端記号 |
文字列リテラル |
終端記号 | |
型定義 |
型定義を別途行い、その識別子を書いたのと同じ | |
式 # 識別子 |
(本ドキュメントでは解説しません) | |
( 式 ) |
グループ化 | |
$embed ( 式 ) |
グループ化[*1] |
[*1] 現在の実装では、式中に含まれる別名を別名定義における右辺で置換します。$embed
しなかった場合、別名は非終端記号として扱われるため、LRの還元が必要になります。$embed
した場合、還元が不要になるため、LALR(1) のコンフリクトの警告を抑えることができ、また、パフォーマンスを向上させることができます。この形式は、将来のバージョンでは単なるグループ化として扱われる可能性があります。