Input Specification of ¬<><∪∪ for 0.75

Overall Structure

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

終端記号 説明
IDENTIFIER $で始まる
予約語 $で始まらない
セパレータ・オペレータ 以下のEBNFで使われる文字列、および、!!**++??
CHARACTER Javaの文字リテラル
STRING Javaの文字列リテラル

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

Lexical Analyzer

TokenDefinition    ::=    $whiteopt  $tokenopt  IDENTIFIER  ( =  tokenExpression )opt  ;
SubtokenDefinition ::= $subtoken  IDENTIFIER  =  tokenExpression  ;

出力されるトップレベル・クラスは、字句解析のためのインターフェイスと、デフォルトの実装を含む。1つのTokenDefinitionは、1つの終端記号を定義する。終端記号は、tokenExpressionマッチする文字の列にマッチする。ただし、tokenExpressionが省略されていた場合、そのTokenDefinitionによって定義される終端記号は、どの列にもマッチしない (ユーザ定義の字句解析器のためだけに使われる)。デフォルトの実装は、入力された列から、終端記号のどれかが最長一致でマッチする文字列をトークン (その終端記号のインスタンスと呼ぶ) として切り出すことを繰り返す。AliasDefinitionおよび、$abstractでないTypeDefinitionにおけるexpression中のSTRINGも終端記号を定義する。この終端記号は、文字列リテラルが表す文字列にマッチする。同じ文字列を表す複数の文字列リテラルは、合わせて1つの終端記号を定義する。また、文字列リテラルが表す文字列だけにマッチするtokenExpressionを持つTokenDefinitionが1つだけ存在する場合、そのTokenDefinitionと文字列リテラルは合わせて1つの終端記号を定義する。

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

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

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

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

tokenExpressionは次の表で定義される。

優先順位 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 (サブ)終端記号がマッチする文字列

Syntax Analyzer

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で表現される。1つのAliasDefinitionか1つのTypeDefinitionが、1つのプロダクションを定義する。IDENTIFIERは、定義される非終端記号の名前を表し、expressionが、プロダクションの右辺をあらわす。TypeDefinitionは、expressionの中で、InlineExpressionとしても現れる。

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

expressionは次のように定義される。

優先順位 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) を構築する。トークン(終端記号のインスタンス)が構文木の葉になり、非終端記号のインスタンスが構文木のノードを作る。子には順番があり、子は0個以上のラベルでラベル付けされるlabel:expressionの形式のlabeled expressionは、expressionに含まれる終端・非終端記号のインスタンスが、labelによってラベル付けされることを表す。1つのラベルが複数のインスタンスをラベル付けしても良い。expressionの中に、同じラベルが字句的に複数回存在しても良い。

同じ入力に対して異なる具象構文木を構築可能なとき、その文法は曖昧な文法である。文法が曖昧である場合、コンパイル時エラーになる場合がある。そうでない場合でも、曖昧な入力に対して実行時エラーになる。ある入力がコンパイル時エラーになるかどうかは処理系に依存する。

プロダクションの右辺にホワイト・トークンをインスタンスとする終端記号を記述することはできないが、ホワイト・トークンは構文解析の対象となるテキスト中に自由に出現してよい。具象構文木をトラバースしたときにトークンを順に見ることで構文解析の対象となったトークン列を復元できる範囲で、ホワイト・トークンをなるべく根に近いノードが保持するように、また兄弟の間でなるべく順番が若くなるように具象構文木が作られる。

$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) を構築する。AliasDefinitionで定義される非終端記号(エイリアス)のインスタンスであるノードが、全て取り除かれる。取り除かれたノードの子は、取り除かれたノードの親の子になる。取り除かれたノードに$labelによってラベル付けされた子が存在した場合、取り除かれたノードをラベル付けしているラベルで、$labelを置き換える。取り除かれたノードのどの子も$labelによってラベル付けされていない場合、取り除かれたノードをラベル付けしているラベルによって、全ての子がラベル付けされる。

抽象構文木はJavaのオブジェクトによる木構造で表される。トークンは、ネストしたインターフェイスTokenのインスタンスで表される。葉以外のノードは、そのノードが具象構文木においてインスタンスであった非終端記号と同じ名前を持つネストしたインターフェイス のインスタンスで表される。

supertypesは、TypeDefinitionによって出力されるネストしたインターフェイスの継承関係を設定する。TypeNameは、TypeDefinitionによって定義された非終端記号の名前で無ければならない。もし、supertypesが無ければ、そのネストしたインターフェイスは、Nodeのサブインターフェイスになる。Tokenもまた、Nodeのサブインターフェイスである。

もし、非終端記号が$parsableと定義されていれば、出力されるトップレベル・クラスは、その非終端記号をゴール記号とする文法を構文解析する、様々な引数を伴ったpublicなメソッドを持つ。非終端記号が$protected-parsableと定義されていれば、同様だがprotectedなメソッドが出力される。

もし、非終端記号が$protected$privateと定義されていれば、その非終端記号と同名のネストしたインターフェイスは、protectedprivateになる。そうでない場合、そのネストしたインターフェイスは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が返しうるオブジェクトはXYであり、それらを表現できる静的な型は、NodeABCのいずれかである。BCより限定的でも、CBより限定的でもないので、最も限定的な型は存在しない。この集合から、より限定的な型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は将来のバージョンでは単なる式のグループ化として扱われる可能性がある。