Input Specification of ¬<><∪∪ for

このドキュメントでは、(¬<><∪∪コンパイラ・コンパイラが出力するパーザへの入力ではなく)¬<><∪∪コンパイラ・コンパイラへの入力がどのように解釈されるかを説明する。コンパイラ・コンパイラの実行時のエラーを「コンパイル時エラー」、出力されたパーザの実行時のエラーを「実行時エラー」と呼ぶ。

Overall Structure

¬<><∪∪コンパイラ・コンパイラへの入力は、Javaと同じプロセス(JLS 3.2)でトークンの列に変換される。ただし、終端記号は次のようになる。

終端記号 説明
Java の識別子か予約語で、$で始まらないもの
キーワード $で始まる語
セパレータ・オペレータ 以下のEBNFで使われる文字列、および、||&&--!!**++??
Javaの文字リテラル
Javaの文字列リテラル

このドキュメントは、¬<><∪∪への入力の文法を、次の記法を用いたEBNFで示す。

メタ表現 説明
Italic もしくは italic 非終端記号
ITALIC 終端記号(シンボル)
Underlined 終端記号(即値)
expr1 | expr2 選択
expr* Kleene star
expropt 省略可能

トークンの列は、次の文法に従っていなければならない。ゴール記号(開始記号)は、である。

   ::=      opt  *
::= $protectedopt  $parser    ;
::= ( . )*
::= $protected  $constructor  ;
::= | | |

¬<><∪∪はJavaのソースファイルを1つ出力し、それは多数のネストしたタイプを含むトップレベル・クラスを1つ定義する。トップレベル・クラスの完全限定名が、によって決められる。$protectedの場合、出力されるクラスはデフォルトスコープ (パッケージスコープ) になり、そうでない場合publicになる。は、出力されるトップレベル・クラスのコンストラクタを、デフォルトスコープ (パッケージスコープ) にする。は、出力されるクラスの詳細を定義する。

$parser packagename.Parser;

:

この例は、packagename.Parserという名前のトップレベルクラスを出力する。

Lexical Analyzer

   ::=    $whiteopt  $token    ( =   )opt  ;
::= $subtoken    =    ;

出力されるトップレベル・クラスは、字句解析のためのインターフェイスと、デフォルトの実装を含む。デフォルトの実装は、入力された文字列の先頭から、以下で定義される終端記号のどれかが最長一致でマッチする文字列をトークン (その終端記号のインスタンスとも呼ぶ) として切り出すことを繰り返す。

1つのは、1つの終端記号を定義する。終端記号は、マッチする文字の列にマッチする。ただし、が省略されていた場合、そのによって定義される終端記号は、どの列にもマッチしない (ユーザ定義の字句解析器のためだけに使われる)。および、$abstractでないにおける中のも終端記号を定義する。この終端記号は、文字列リテラルが表す文字列にマッチする。同じ文字列を表す複数の文字列リテラルは、合わせて1つの終端記号を定義する。また、文字列リテラルが表す文字列だけにマッチするを持つが1つだけ存在する場合、そのと文字列リテラルは合わせて1つの終端記号を定義する。

2つ以上の終端記号が同じ文字列にマッチする場合、コンパイル時エラーである。終端記号が長さ0の文字列にマッチする場合、コンパイル時エラーである。において、が省略されていないにもかかわらず、どの文字列にもマッチしない場合コンパイル時エラーである。

もし、終端記号が$whiteとして定義されていれば、そのインスタンスをホワイト・トークンと呼ぶ。ホワイト・トークンは、ホワイトスペースやコメントを扱うのに使われる。

は、に対して名前を与える。この名前は、他のの中で使うことができる。

では、に、いま定義しているが出現してはならない。これには、を介した場合も含まれる。

は次の表で定義される(より厳密な文法は、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がマッチする文字列
が表す文字
.. その範囲にある文字
が表す文字列
(サブ)終端記号がマッチする文字列

$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 を定義する。

Syntax Analyzer

   ::=      =    ;
::=     opt  {    }
::= ( $protected | $private )opt  $abstractopt
| $parsable
| $protected-parsable  $protectedopt
::= ->    ( &   )*
::=
::=

出力されるトップレベル・クラスは、字句解析器が出力するトークンの列を構文解析する構文解析器を含む。文法は、拡張されたEBNFで表現される。1つのか1つのが、1つのプロダクションを定義する。は、定義される非終端記号の名前を表し、が、プロダクションの右辺をあらわす。は、の中で、としても現れる。

$abstractな非終端記号から導出される有限個のトークンの列が存在しない場合(死記号の場合)、コンパイル時エラーである。

は次のように定義される(より厳密な文法は、Syntax in EBNFで定義される)。

優先順位 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"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と定義されていれば、その非終端記号と同名のネストしたインターフェイスは、protectedprivateになる。そうでない場合、そのネストしたインターフェイスはpublicになる。

もし非終端記号が$abstractと定義されていれば、その非終端記号はネストしたインターフェイスを生成するが、構文木に現れることはできない。

によって出力されるネストしたインターフェイスは、ラベルと同名で、引数の無いメソッドを持つ。メソッドの戻り値は、そのラベルによってラベル付けされている子(高々1つの子しかラベル付けしない場合)、あるいは子のリスト(複数の子をラベル付けする可能性がある場合)である。戻り値の静的型は、前者の場合ラベル付けされる可能性のある子の型に共通の型(ラベル付けされる可能性のある子すべてを表せる型)で、公平に最も限定的な型(下で定義される)になる。後者の場合、公平に最も限定的な型の配列かjava.util.Listになる(コンパイル時のオプションによる)。

継承関係における子を親より限定的と定義する。型の集合に対して、公平に最も限定的な型を、次のように定義する。もし、型の集合の中で、1つの型がそれ以外の型のどれよりも限定的である場合、その型を公平に最も限定的な型とする。そうでない場合、より限定的な型が集合に含まれるような型を集合から取り除き、残った型すべてを表現できる型の集合を求めて、それらに対する公平に最も限定的な型を再帰的に求め、その結果をここで求める公平に最も限定的な型とする。

例:

A { }
B -> A { }
C -> A { }
X -> B & C { }
Y -> B & C { }
T { label:( X | Y ) }

に対して、メソッドlabelが返しうるオブジェクトはXYであり、その両方を表現できる型(共通の型)は、NodeABCのいずれかである。BCANodeよりも限定的であるが、BCより限定的でも、CBより限定的でもない。従って、1つの型がそれ以外の型のどれよりも限定的ではない。この集合から、より限定的な型BおよびCが存在するAおよびNodeが除かれ、残ったBCの両方を表現できる型の中で、最も限定的な型が求められる。BCの両方を表現できる型はNodeAであり、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の戻り値の静的型は、XYBを表現できる型のなかで公平に最も限定的なものになり、Bになる。

$embedは、expressionをに含まれるエイリアスをコンパイル時に展開する。これは、LALR(1)のコンフリクトの報告に影響する。$embedは将来のバージョンでは単なる式のグループ化として扱われる可能性がある。