The Specification of ¬<><∪∪(書きかけ) for 0.63

  1. 本ドキュメントで使用される表記
  2. 入力
    1. 名前
  3. 出力
  4. 字句解析器
    1. 終端記号定義
    2. 文字列式
    3. トークン予約
    4. トークン式
    5. 部分終端記号定義
  5. 構文解析器
    1. 具象構文木
    2. 拡張具象構文木
    3. 抽象構文木
    4. 抽象構文木の表現
    5. 型定義
    6. 別名定義
  6. Appendix I. ¬<><∪∪ Syntax by ¬<><∪∪

§1 本ドキュメントで使用される表記

本ドキュメントでは、下の表記法を使用します。

¬<><∪∪ソースの文法は、<pre>タグによってマークアップされます。スタイルシートをサポートした環境では緑色になります。

¬<><∪∪ソースの文法は次の拡張BNFで記述されます。

表記意味
式 | 式いずれか
式 *0回以上の繰り返し
式 +1回以上の繰り返し
式 ?省略可能
[ 式 ]省略可能
( 式 )グループ化
"文字列"終端記号

§2 入力

¬<><∪∪処理系は、1つのテキストファイル(¬<><∪∪ソース)を入力に取ります。¬<><∪∪ソースは、Javaの処理系が行うのと同様に、コメント等が取り除かれ、トークンの列に変換されます[現在の実装では、バグにより、Unicodeエスケープは文字・文字列リテラル中でのみ有効です]。ただし、¬<><∪∪の識別子予約語は、Javaとは異なります。

要素説明
識別子 Javaの識別子およびJavaの予約語で、$を含まないもの
予約語 $package, $token, $subtoken, $WHITE_TOKEN, $protected, $abstract, $parsable, $embed, および $label
文字列リテラル文字リテラル Javaと同様
オペレータ、セパレータ ;, ., =, ->, &, |, -, !, *, +, ?, [, ], .., (, ), /, :, および #
コメント、ホワイトスペース、改行 Javaと同様

得られたトークン列は、次のRootにより定義される文法に従ってパースされます。

Root ::= PackageOption? definition* ["\u001A"]

PackageOption ::= "$package" JavaName ";"
JavaName ::= IDENTIFIER ( "." IDENTIFIER )*

definition ::= SubtokenDefinition | TokenDefinition | WhiteTokenDefinition | DeprecatedWhiteTokenDefinition | TokenReservation | TypeDefinition | AliasDefinition

パッケージオプションは、出力されるJavaのクラスが属すパッケージ名を指定します。

(1) 名前

TypeName ::= IDENTIFIER
SubtokenName ::= IDENTIFIER | "$WHITE_TOKEN"
SymbolName ::= IDENTIFIER

¬<><∪∪ソースによって表現されるいくつかのオブジェクトは、名前をもちます。同じ名前をもつオブジェクトが複数存在することはありません。

型名の名前でなければなりません。部分終端記号名は、部分終端記号あるいは終端記号の名前でなければなりません。シンボル名は、非終端記号、あるいは、ホワイト・トークンインスタンスとしない終端記号の名前でなければなりません。

§3 出力

¬<><∪∪処理系は、入力されたファイルの拡張子を .java に変更したファイルへ、public なトップ・レベル・クラスを1つ出力します。このJavaのクラスは、多数のネステッド・クラスを含みます。また、概念的には、字句解析器構文解析器の2つのモジュールによって構成されます。

§4 字句解析器

字句解析器LexicalAnalizerネステッド・インターフェイス型のオブジェクトであり、トークンの列を出力します。トークンは、Tokenネステッド・インターフェイス型のオブジェクトで表現され、終端記号のいずれかのインスタンスです。終端記号は、¬<><∪∪ソース上の終端記号定義文字列式トークン予約によって、定義されます。トークンがどの終端記号のインスタンスであるかは、字句解析器によって決定されます。

¬<><∪∪処理系は、LexicalAnalizerを実装したDefault.LexicalAnalizerネステッド・クラスを出力します。Default.LexicalAnalizerは、Unicodeのテキストをトークンの列に変換します。Default.LexicalAnalizerは、入力されたテキストの先頭から、終端記号がマッチする文字列の中で、最長の文字列をトークンとして切り出すことを繰り返します。異なる複数の終端記号が同じ文字列にマッチする場合、その¬<><∪∪ソースはエラーです。切り出されたトークンは、マッチした終端記号のインスタンスです。

(1) 終端記号定義

TokenDefinition ::= "$token" IDENTIFIER "=" tokenExpression ";"
WhiteTokenDefinition ::= "$white" "$token" IDENTIFIER "=" tokenExpression ";"
DeprecatedWhiteTokenDefinition ::= "$WHITE_TOKEN" "=" tokenExpression ";"

識別子で表現される名前をもつ終端記号を定義します(3つめの形式では、$WHITE_TOKENという名前をもちます)。この終端記号は、トークン式マッチする文字列にマッチします。2つめと3つめの形式で定義される終端記号のインスタンスは、ホワイト・トークンと呼ばれます。

(2) 文字列式

別名定義、もしくは、abstractではない型定義におけるに含まれる文字列式は、文字列式が表す文字列にのみマッチする終端記号を、もしそのような終端記号が他の方法によって定義されなければ、定義します。同じ文字列を表す文字列式が複数ある場合であっても、定義される終端記号は1つだけです。文字列式によって定義される終端記号は名前をもちません。

(3) トークン予約

TokenReservation ::= "$token" IDENTIFIER ";"

識別子を名前にもつ終端記号を定義します。この終端記号はどの文字列にもマッチしません。

(4) トークン式

tokenExpression ::= SelectiveTokenExpression
SelectiveTokenExpression ::= termTokenExpression ( "|" termTokenExpression )*

termTokenExpression ::= SequentialTokenExpression | IntersectionTokenExpression | DifferenceTokenExpression
IntersectionTokenExpression ::= termTokenExpression "&" SequentialTokenExpression
DifferenceTokenExpression ::= termTokenExpression "-" DifferenceTokenExpressionRHS
DifferenceTokenExpressionRHS ::= SequentialTokenExpression

SequentialTokenExpression ::= prefixTokenExpression*

prefixTokenExpression ::= postfixTokenExpression | ComplementaryTokenExpression
ComplementaryTokenExpression ::= "!" prefixTokenExpression

postfixTokenExpression ::= StarTokenExpression | PlusTokenExpression | OptionalTokenExpression | primaryTokenExpression
StarTokenExpression ::= StarTokenExpressionConcrete EmptyTokenExpression
StarTokenExpressionConcrete ::= postfixTokenExpression "*"
PlusTokenExpression ::= postfixTokenExpression "+"
OptionalTokenExpression ::= ( postfixTokenExpression "?" | "[" tokenExpression "]" ) EmptyTokenExpression
EmptyTokenExpression ::= 

primaryTokenExpression ::= CharacterTokenExpression | CharacterRangeTokenExpression | StringTokenExpression | IdentifierTokenExpression | parenthesizedTokenExpression
CharacterTokenExpression ::= CharacterLiteral
CharacterRangeTokenExpression ::= CharacterLiteral ".." CharacterLiteral
StringTokenExpression ::= StringLiteral
IdentifierTokenExpression ::= SubtokenName
parenthesizedTokenExpression ::= "(" tokenExpression ")"

トークン式は次のように、文字列にマッチします。

優先順位 形式 マッチする文字列
最低 トークン式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を、再帰的に用いることはできません。★もっと正確に書く

(5) 部分終端記号定義

SubtokenDefinition ::= "$subtoken" IDENTIFIER "=" tokenExpression ";"

部分終端記号を定義します。この部分終端記号は、識別子を名前にもち、トークン式マッチする文字列にマッチします。

§5 構文解析器

構文解析器は、字句解析器の出力するトークン列を入力にとり、抽象構文木を出力します。この処理を構文解析と呼びます。構文解析器は、parsable型定義毎に1つずつ用意されます。構文解析器は、型定義の定義する非終端記号マッチする具象構文木を考え、その具象構文木の拡張具象構文木が入力されたトークン列にマッチするかを判断します。もしマッチする拡張具象構文木が存在しない場合ParseExceptionが発生します。もし、マッチする拡張具象構文木が複数存在する場合、その¬<><∪∪ソースは曖昧であるといい、その¬<><∪∪ソースはエラーです。マッチする拡張具象構文木がただ1つ存在する場合、マッチした拡張具象構文木から生成される抽象構文木を返します。

(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)を、その非終端記号のインスタンスと呼びます。

具象構文木は、次のようにトークン列にマッチします。

(2) 拡張具象構文木

ある具象構文木拡張具象構文木は次のいずれかです。

ただし、m, l は0以上の整数、Wk は <φ, φ, ホワイト・トークン> をk個並べたもの、φは空集合です。

(3) 抽象構文木

抽象構文木とは、具象構文木におけるn組みの最初の要素が、型定義による非終端記号であるような具象構文木で、形式的には次のいずれかです。

ただし、Nは任意の型定義による非終端記号で、C1, C2, C3, ..., Cn-1 は、ラベルの集合、型制限の集合、および抽象構文木の3つ組みです。

N が型定義による非終端記号のとき、具象構文木 N(n) から生成される抽象構文木は、<N, F(C1), F(C2), ..., F(Cn-1))> です。ここで、F は次のように定義されます。

ただし、L←M は、L が$labelを含まないときLで、含むときL-{$label}∪Mです。

型定義による非終端記号Nに対して、Nがマッチする具象構文木から生成される抽象構文木を、Nの広義のインスタンスと呼びます。

(4) 抽象構文木の表現

構文解析の結果である抽象構文木は、Javaのオブジェクトによるデータ構造によって表現されます。抽象構文木がn組みN(n)のとき、その構文木は、Nと同じ名前をもつネステッド・インターフェイスのオブジェクトによって表現されます。このネステッド・インターフェイスは、Nodeネステッド・インターフェイスを継承しており、getChildListメソッドは、列 T1, T2, ..., Tn-1 を返します。また、このインターフェイスのラベル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 を広義のインスタンスとする型の共通の親の型になります。★ここ書き直し

(5) 型定義

TypeDefinition ::= modifiers IDENTIFIER superTypes "{" expression "}"
modifiers ::= ["$protected" | "$private"] "$abstract"? | "$parsable"
superTypes ::= ["->" TypeName ( "&" TypeName )*]

InlineExpression ::= TypeDefinition

privateではない型定義によって、同名のネステッド・インターフェイスが出力されます。$abstractを伴う型定義は、abstractな型定義と呼ばれ、出力されるインターフェイスはアブストラクトです。$protectedを伴う型定義は、protectedな型定義と呼ばれ、出力されるインターフェイスはプロテクテッドです。$privateを伴う型定義は、privateな型定義と呼ばれ、出力されるインターフェイスはプライベートです(このインターフェイスは、実際には出力されない場合があります。このインターフェイスにリフレクションを用いてアクセスしてはなりません)。$parsableを伴う型定義は、parsableな型定義と呼ばれます。

->の右側の&によって区切られた識別子は、直接の親の型の名前です。出力されるネステッド・インターフェイスは、直接の親の型と同名のネステッド・インターフェイスをextendsします。

型定義は、識別子を名前にもつ非終端記号を定義します。この非終端記号は、具象構文木N(n)にマッチします。ただし、Nはこの非終端記号であり、C1, C2, ..., Cn-1マッチする3つ組みの列です。型定義が定義する非終端記号を、型定義による非終端記号、あるいはと呼びます。

abstractではない型定義において、式は、abstractな型定義によって定義された非終端記号の名前を表すIdentifierExpressionを含むことはできません。

[現在の実装では、バグにより、右辺の式を終端記号および非終端記号上の正規表現と考えて最簡形を求めたときに、異なるラベルが統合されてしまうような型定義をコンパイルできません]

(6) 別名定義

AliasDefinition ::= IDENTIFIER "=" expression ";"

別名定義は、識別子を名前にもつ非終端記号を定義します。この非終端記号は、具象構文木N(n)にマッチします。ただし、Nはこの非終端記号であり、C1, C2, ..., Cn-1マッチする3つ組みの列です。別名定義が定義する非終端記号を、別名定義による非終端記号、あるいは別名と呼びます。

[現在の実装では、バグにより、右辺の式を終端記号および非終端記号上の正規表現と考えて最簡形を求めたときに、異なるラベルが統合されてしまうような別名定義をコンパイルできません]

(7) 式

expression ::= SelectiveExpression
SelectiveExpression ::= SequentialExpression ( "|" SequentialExpression )*

SequentialExpression ::= postfixExpression*

postfixExpression ::= StarExpression | PlusExpression | OptionalExpression | RestrictorExpression | prefixExpression
StarExpression ::= StarExpressionConcrete EmptyExpression
StarExpressionConcrete ::= postfixExpression "*"
PlusExpression ::= postfixExpression "+"
OptionalExpression ::= ( postfixExpression "?" | "[" expression "]" ) EmptyExpression
EmptyExpression ::= 
RestrictorExpression ::= postfixExpression "/" TypeName

prefixExpression ::= LabeledExpression | primaryExpression
LabeledExpression ::= ( IDENTIFIER | "$label" ) ":" prefixExpression

primaryExpression ::= parenthesizedExpression | EmbedExpression | TagExpression | StringExpression | InlineExpression | IdentifierExpression
parenthesizedExpression ::= "(" expression ")"
EmbedExpression ::= "$embed" "(" expression ")"
TagExpression ::= ( StringExpression | IdentifierExpression ) "#" IDENTIFIER
StringExpression ::= StringLiteral
IdentifierExpression ::= SymbolName

式は次のように、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つ組みの列★

§6 Appendix I. ¬<><∪∪ Syntax by ¬<><∪∪

$package jp.gr.java_conf.koto.notavacc.parser;


// Token Definitions

$subtoken ANY_CHARACTER         = '\u0000'..'\uFFFF' ;
$subtoken LINE_TERMINATOR       = "\n" | "\r" | "\r\n" ;
$subtoken WHITE_SPACE           = ' ' | '\t' | '\f' | LINE_TERMINATOR ;
$subtoken ALPHABET              = 'A'..'Z' | 'a'..'z' ;
$subtoken DIGIT                 = '0'..'9' ;
$subtoken HEX_DIGIT             = '0'..'9' | 'A'..'F' | 'a'..'f' ;
$subtoken OCTAL_DIGIT           = '0'..'7' ;

$white $token WHITE_SPACES      = WHITE_SPACE+ ;
$white $token TRADITIONAL_COMMENT
                                = "/*" ( ANY_CHARACTER* - ( ANY_CHARACTER* "*/" ANY_CHARACTER* ) ) "*/" ;
$white $token END_OF_LINE_COMMENT
                                = "//" ( ANY_CHARACTER* - ( ANY_CHARACTER* LINE_TERMINATOR ANY_CHARACTER* ) ) LINE_TERMINATOR ;

$token IDENTIFIER               = IDENTIFIER_LETTER ( IDENTIFIER_LETTER | IDENTIFIER_DIGIT )* ;
$subtoken IDENTIFIER_LETTER     = /*'$' |*/ 'A'..'Z' | '_' | 'a'..'z'
                                | '\u00c0'..'\u00d6' | '\u00d8'..'\u00f6' | '\u00f8'..'\u00ff'
                                | '\u0100'..'\u1fff' | '\u3040'..'\u318f' | '\u3300'..'\u337f'
                                | '\u3400'..'\u3d2d' | '\u4e00'..'\u9fff' | '\uf900'..'\ufaff'
                                ;
$subtoken IDENTIFIER_DIGIT      = '0'..'9'
                                | '\u0660'..'\u0669' | '\u06f0'..'\u06f9' | '\u0966'..'\u096f'
                                | '\u09e6'..'\u09ef' | '\u0a66'..'\u0a6f' | '\u0ae6'..'\u0aef'
                                | '\u0b66'..'\u0b6f' | '\u0be7'..'\u0bef' | '\u0c66'..'\u0c6f'
                                | '\u0ce6'..'\u0cef' | '\u0d66'..'\u0d6f' | '\u0e50'..'\u0e59'
                                | '\u0ed0'..'\u0ed9' | '\u1040'..'\u1049'
                                ;

$token RESERVED_WORD            = ( ( "$" | IDENTIFIER_LETTER ) ( "$" | IDENTIFIER_LETTER | IDENTIFIER_DIGIT )* )
                                - IDENTIFIER
                                - "$package"
                                - "$token" - "$white" - "$subtoken" - "$WHITE_TOKEN"
                                - "$parsable" - "$abstract" - "$protected" - "$private"
                                - "$embed" - "$label"
                                ;

/*
$token BOOLEAN                  = "true" | "false" ;

$token INTEGER                  = ( DECIMAL_INTEGER | HEX_INTEGER | OCTAL_INTEGER ) [ 'l' | 'L' ] ;
$subtoken DECIMAL_INTEGER       = '0' | ( ( DIGIT - '0' ) DIGIT* ) ;
$subtoken HEX_INTEGER           = '0' ( 'x' | 'X' ) HEX_DIGIT+ ;
$subtoken OCTAL_INTEGER         = '0' OCTAL_DIGIT+ ;

$token FLOATING_POINT           = ( FLOATING_POINT_HEAD EXPONENT_PART? FLOAT_TYPE_SUFFIX? ) - INTEGER ;
$subtoken FLOATING_POINT_HEAD   = ( DIGIT* '.'? DIGIT* ) & ( ANY_CHARACTER* DIGIT ANY_CHARACTER* ) ;
$subtoken EXPONENT_PART         = ( 'e' | 'E' ) [ '+' | '-' ] DIGIT+ ;
$subtoken FLOAT_TYPE_SUFFIX     = 'f' | 'F' | 'd' | 'D' ;
*/

$token CHARACTER                = '\'' ( CHARACTER_ELEMENT | '\"' ) '\'' ;
$token STRING                   = '\"' ( CHARACTER_ELEMENT | '\'' )* '\"' ;
$subtoken CHARACTER_ELEMENT     = ( ANY_CHARACTER - LINE_TERMINATOR - '\\' - '\'' - '\"' ) | ESCAPE_SEQUENCE ;
$subtoken ESCAPE_SEQUENCE       = ESCAPE_SEQUENCE1 | ESCAPE_SEQUENCE2 | ESCAPE_SEQUENCE3 ;
$subtoken ESCAPE_SEQUENCE1      = '\\' ( 'n' | 't' | 'b' | 'r' | 'f' | '\\' | '\'' | '\"' ) ;
$subtoken ESCAPE_SEQUENCE2      = '\\' ( [ ['0'..'3'] OCTAL_DIGIT ] OCTAL_DIGIT ) ;
$subtoken ESCAPE_SEQUENCE3      = '\\' 'u'+ HEX_DIGIT HEX_DIGIT HEX_DIGIT HEX_DIGIT ;

// Literals

StringLiteral           { token:STRING }
CharacterLiteral        { token:CHARACTER }

// Name

$abstract Name { identifier:IDENTIFIER }
TypeName -> Name        { identifier:IDENTIFIER }                       // name of TypeDefinition
SubtokenName -> Name    { identifier:( IDENTIFIER | "$WHITE_TOKEN" ) }  // name of SubtokenDefinition
SymbolName -> Name      { identifier:IDENTIFIER }                       // name of TokenReservation, TypeDefinition, or AliasDefinition, but not WhiteTokenDefinition.

// Header

$parsable
Root                    { packageOption:PackageOption? definition* ["\u001A"] }

PackageOption           { name:"$package" value:JavaName ";" }
JavaName                { identifiers:IDENTIFIER ( "." identifiers:IDENTIFIER )* }


// Definitions

$abstract Definition { identifier:IDENTIFIER }
definition              = subtokenDefinitions:SubtokenDefinition
                        | tokenDefinitions:subtokenDefinitions:tokenReservations:TokenDefinition
                        | whiteTokenDefinitions:tokenDefinitions:subtokenDefinitions:tokenReservations:WhiteTokenDefinition
                        | whiteTokenDefinitions:tokenDefinitions:subtokenDefinitions:tokenReservations:DeprecatedWhiteTokenDefinition
                        | tokenReservations:TokenReservation
                        | typeDefinitions:TypeDefinition
                        | aliasDefinitions:AliasDefinition
                        ;
SubtokenDefinition -> Definition
                        { "$subtoken" identifier:IDENTIFIER "=" expression:tokenExpression ";" }
TokenDefinition -> SubtokenDefinition & TokenReservation
                        { "$token" identifier:IDENTIFIER "=" expression:tokenExpression ";" }
WhiteTokenDefinition -> TokenDefinition
                        { "$white" "$token" identifier:IDENTIFIER "=" expression:tokenExpression ";" }
DeprecatedWhiteTokenDefinition -> WhiteTokenDefinition
                        { identifier:"$WHITE_TOKEN"#OBSOLETE_WHITE_TOKEN "=" expression:tokenExpression ";" }
TokenReservation -> Definition
                        { "$token" identifier:IDENTIFIER ";" }
TypeDefinition -> Definition
                        { modifiers identifier:IDENTIFIER superTypes:superTypes "{" expression:expression "}" }
modifiers               = [ protectedKeyword:"$protected" | privateKeyword:"$private" ] abstractKeyword:"$abstract"?
                        | parsableKeyword:"$parsable"
                        ;
superTypes              = [ "->" $label:TypeName ( "&" $label:TypeName )* ] ;
AliasDefinition -> Definition
                        { identifier:IDENTIFIER "=" expression:expression ";" }


// Token Expressions

$abstract TokenExpression { }
tokenExpression         = SelectiveTokenExpression/TokenExpression ;

SelectiveTokenExpression -> TokenExpression
                        { operands:termTokenExpression ( "|" operands:termTokenExpression )* }

termTokenExpression     = SequentialTokenExpression
                        | IntersectionTokenExpression
                        | DifferenceTokenExpression
                        ;
IntersectionTokenExpression -> TokenExpression
                        { lhs:termTokenExpression "&" rhs:SequentialTokenExpression/TokenExpression }
$private DifferenceTokenExpression -> IntersectionTokenExpression
                        { lhs:termTokenExpression "-" rhs:DifferenceTokenExpressionRHS }
$private DifferenceTokenExpressionRHS -> ComplementaryTokenExpression
                        { operand:SequentialTokenExpression }

SequentialTokenExpression -> TokenExpression
                        { operands:prefixTokenExpression* }

prefixTokenExpression   = postfixTokenExpression
                        | ComplementaryTokenExpression -> TokenExpression { "!" operand:prefixTokenExpression }
                        ;

postfixTokenExpression  = StarTokenExpression
                        | PlusTokenExpression -> TokenExpression { operand:postfixTokenExpression "+" }
                        | OptionalTokenExpression
                        | primaryTokenExpression
                        ;
$private StarTokenExpression -> SelectiveTokenExpression
                        { operands:StarTokenExpressionConcrete operands:EmptyTokenExpression }
$private StarTokenExpressionConcrete -> PlusTokenExpression
                        { operand:postfixTokenExpression "*" }
$private OptionalTokenExpression -> SelectiveTokenExpression
                        { ( operands:postfixTokenExpression "?" | "[" operands:tokenExpression "]" ) operands:EmptyTokenExpression }
$private EmptyTokenExpression -> SequentialTokenExpression
                        { }

primaryTokenExpression  = $private CharacterTokenExpression -> CharacterRangeTokenExpression { lower:upper:CharacterLiteral }
                        | CharacterRangeTokenExpression -> TokenExpression { lower:CharacterLiteral ".." upper:CharacterLiteral }
                        | StringTokenExpression -> TokenExpression { string:StringLiteral }
                        | IdentifierTokenExpression -> TokenExpression { name:SubtokenName }
                        | parenthesizedTokenExpression
                        ;
parenthesizedTokenExpression
                        = "(" $label:tokenExpression ")" ;


// Expressions

$abstract Expression { }
expression              = SelectiveExpression/Expression ;

SelectiveExpression -> Expression
                        { operands:SequentialExpression/Expression ( "|" operands:SequentialExpression/Expression )* }

SequentialExpression -> Expression
                        { operands:postfixExpression* }

postfixExpression       = StarExpression
                        | PlusExpression -> Expression { operand:postfixExpression mark:"+" }
                        | OptionalExpression
                        | RestrictorExpression -> Expression { operand:postfixExpression "/" typeRestrictor:TypeName }
                        | prefixExpression
                        ;
$private StarExpression -> SelectiveExpression
                        { operands:StarExpressionConcrete operands:EmptyExpression }
$private StarExpressionConcrete -> PlusExpression
                        { operand:postfixExpression mark:"*" }
$private OptionalExpression -> SelectiveExpression
                        { ( operands:postfixExpression "?" | "[" operands:expression "]" ) operands:EmptyExpression }
$private EmptyExpression -> SequentialExpression
                        { }

prefixExpression        = LabeledExpression -> Expression { label:( IDENTIFIER | "$label" ) ":" operand:prefixExpression }
                        | primaryExpression
                        ;

primaryExpression       = parenthesizedExpression
                        | EmbedExpression -> Expression { "$embed" "(" operand:expression ")" }
                        | TagExpression -> Expression { operand:( StringExpression | IdentifierExpression ) "#" tag:IDENTIFIER }
                        | StringExpression -> Expression { string:StringLiteral }
                        | $protected InlineExpression -> IdentifierExpression { typeDefinition:TypeDefinition }
                        | IdentifierExpression -> Expression { name:SymbolName }
                        ;
parenthesizedExpression = "(" $label:expression ")" ;