Overview for 1.0.3

￢＜＞＜∪∪は次の特徴を持ったコンパイラ・コンパイラです。

拡張BNFベースの記述法により、任意の曖昧でないCFGを扱えます（LALR(∞)に相当する能力を持っています）。
Javaソースを出力します
Javaで書かれており、ソースが公開されています
差集合をサポートするように拡張された（離散数学で言うところの）正規表現によって語彙を定義できます。例えば、C言語のコメントを
"/*" ( ANY_CHARACTER* - ( ANY_CHARACTER* "*/" ANY_CHARACTER* ) ) "*/"
のように記述できます。
オブジェクト指向に基づいた抽象構文木（abstract syntax tree）を出力するパーサを生成します。￢＜＞＜∪∪のコード
Addition -> Expression { operand1:expression "+" operand2:term }
は、BNFのAddition ::= expression "+" termを意味すると同時に、パースの結果を
interface Addition extends Expression { Expression operand1(); Expression operand2(); }
のような型のオブジェクトで表現することを表します。メソッド operand1 や operand2 は、expression や term に対応する式オブジェクトを返します。1 * (2 + 3)は次のように表現されます。

このドキュメントでは、￢＜＞＜∪∪ではどのように文法を記述し、それによって何が得られるかを簡単に説明します。読むには、構文解析に関する基礎的な知識が必要です。

￢＜＞＜∪∪では、字句解析（テキストをトークンの列に変換する処理）と、構文解析（トークンの列を構文木に変換する処理）の両方を１つのファイルに記述します。￢＜＞＜∪∪は、このファイルから、１つのJavaソースファイルを出力します。

ファイルの先頭に、出力されるJavaのクラスの名前を記述します。

$parser packageName.Parser;

:
:

字句解析

`$token`

$token INTEGER = ('0'..'9')+ ;

$token に続けてトークンを定義します。この例では、'0'～'9'が１文字以上つながったものは、INTEGERという種類のトークンに変換されます。+、*、| のような正規表現の記号を使うことができます。「ある範囲の文字のどれか１つ」をあらわすには、'0'..'9' のように、引用符でくくった文字を、二つのピリオドでつなげてあらわします。

`$subtoken`

$token IDENTIFIER          = IDENTIFIER_START IDENTIFIER_PART* ;
$subtoken IDENTIFIER_START = 'a'..'z' | 'A'..'Z' ;
$subtoken IDENTIFIER_PART  = '0'..'9' | IDENTIFIER_START ;

$subtoken は、等号の右辺の式に名前を付けて、$token や $subtoken の中で参照できるようにします。この例では、アルファベット１文字で始まり、アルファベットか数字が０文字以上続いたものが、IDENTIFIERという種類のトークンに変換されます。

再帰的には使用できません。

`$white`

$white $token WHITE_SPACES = WHITE_SPACE+ ;
$subtoken WHITE_SPACE      = ' ' | '\t' | '\f' | LINE_TERMINATOR ;
$subtoken LINE_TERMINATOR  = "\n" | "\r" | "\r\n" ;

$white は、空白やコメントなどの、無視されるトークンを定義します。単一の文字は、' ' のように引用符でくくって表します。"\r\n" は、「'\r' に '\n' が続いたもの」を意味し、'\r' '\n' と同じです。"\n" は '\n' と同じ意味になります。

最長一致/最短一致

$subtoken ANY_CHARACTER         = '\u0000'..'\uFFFF' ;
$subtoken COMMENT_LONGEST_MATCH = "/*" ANY_CHARACTER* "*/" ;
$token COMMENT                  = COMMENT_LONGEST_MATCH - ( COMMENT_LONGEST_MATCH ANY_CHARACTER+ ) ;

トークンへの変換は常に最長一致で行われます。CやJavaのコメントのように最短一致でマッチさせたい場合、上のように記述します。ここで - は、左の正規表現にマッチして、右の正規表現にマッチしない文字列を表します。これによって、COMMENT は途中に "*/" を含むようなものにはマッチしなくなります。

構文解析

Substitution { identifier:IDENTIFIER "=" number:Number ";" }
Number { integer:INTEGER ";" }

BNFの「Substitution ::= IDENTIFIER "=" Number ";"」「Number ::= INTEGER」と同様にプロダクションを定義します。また、同時に次のようなインターフェイスを出力し、構文木のノードをこのインターフェイスのインスタンスで表します。: は、右側の記号を左側の識別子でラベル付けします。identifier() は IDENTIFIER に対応するトークンを返し、number() は Number を返します。

interface Substitution { Token identifier(); Number number(); }
interface Number { Token integer(); }

開始記号

$parsable A { ... }

$parsableと指定することで、A が表す構文を解析するメソッド（parseA）が生成されます。

正規表現の利用

A { integers:INTEGER+ }
B { integers:INTEGER ( "," integers:INTEGER )* }

interface A { List integers(); }
interface B { List integers(); }

正規表現を利用できます（ただし、トークンの定義とは異なり、-は使用できません）。ラベル付けされる記号が複数になりうる場合、戻り値はリストになります。integers() は INTEGER に対応するトークンのリストを返します。

継承関係の設定

A { ... }
B { ... }
C -> A & B { ... }

出力されるクラスに継承関係を設定できます。

interface A { ... }
interface B { ... }
interface C extends A, B { ... }

エイリアス

Foo { bar }
bar = A B label:C ;

トークンの定義における$subtokenと同様に、右辺の式に名前を付けて、参照できるようにします。上の例は、次と同じです。

Foo { A B label:C }

エイリアスとラベル付け

Foo { label2:bar }
bar = A B label:C ;

エイリアスに含まれるすべての記号をラベル付けします。

Foo { label2:A label2:B label2:label:C }

C は、labelとlabel2の両方でラベル付けされます。

エイリアスの仮引数

ただし、$label が使用されている場合、$label がラベル付けしている記号だけをラベル付けします。

Foo { label2:bar }
bar = A $label:B label:C ;

次と同じです。

Foo { A label2:B label:C }

再帰的なエイリアスと算術式

エイリアスは再帰的に使用できます。これを利用すると、算術式を次のように記述できます。

Expression { }
expression      = Addition
                | term
                ;
Addition -> Expression
                { operand1:expression "+" operand2:term }

term            = Multiplication
                | factor
                ;
Multiplication -> Expression
                { operand1:term "*" operand2:factor }

factor          = parenthesizedExpression
                | Number
                ;
Number -> Expression { value:INTEGER }

parenthesizedExpression
                = "(" $label:expression ")"
                ;

エイリアスを展開すると、Multiplicationは次のようになります。

Multiplication -> Expression
                { operand1:Multiplication "*" operand2:Number
                | operand1:Multiplication "*" "(" operand2:Addition ")"
                | operand1:Multiplication "*" "(" operand2:Multiplication ")"
                | operand1:Multiplication "*" "(" operand2:Number ")"
                | operand1:Multiplication "*" "(" "(" operand2:Addition ")" ")"
                | operand1:Multiplication "*" "(" "(" operand2:Multiplication ")" ")"
                | operand1:Multiplication "*" "(" "(" operand2:Number ")" ")"
                | operand1:Multiplication "*" "(" "(" "(" operand2:Addition ")" ")" ")"
                | :
                | :
                | operand1:Number "*" operand2:Number
                | operand1:Number "*" "(" operand2:Addition ")"
                | operand1:Number "*" "(" operand2:Multiplication ")"
                | operand1:Number "*" "(" operand2:Number ")"
                | operand1:Number "*" "(" "(" operand2:Addition ")" ")"
                | operand1:Number "*" "(" "(" operand2:Multiplication ")" ")"
                | operand1:Number "*" "(" "(" operand2:Number ")" ")"
                | operand1:Number "*" "(" "(" "(" operand2:Addition ")" ")" ")"
                | :
                | :
                | "(" operand1:Addition ")" "*" operand2:Number
                | "(" operand1:Addition ")" "*" "(" operand2:Addition ")"
                | "(" operand1:Addition ")" "*" "(" operand2:Multiplication ")"
                | "(" operand1:Addition ")" "*" "(" operand2:Number ")"
                | "(" operand1:Addition ")" "*" "(" "(" operand2:Addition ")" ")"
                | "(" operand1:Addition ")" "*" "(" "(" operand2:Multiplication ")" ")"
                | "(" operand1:Addition ")" "*" "(" "(" operand2:Number ")" ")"
                | "(" operand1:Addition ")" "*" "(" "(" "(" operand2:Addition ")" ")" ")"
                | :
                | :
                | "(" operand1:Multiplication ")" "*" operand2:Number
                | "(" operand1:Multiplication ")" "*" "(" operand2:Addition ")"
                | "(" operand1:Multiplication ")" "*" "(" operand2:Multiplication ")"
                | "(" operand1:Multiplication ")" "*" "(" operand2:Number ")"
                | "(" operand1:Multiplication ")" "*" "(" "(" operand2:Addition ")" ")"
                | "(" operand1:Multiplication ")" "*" "(" "(" operand2:Multiplication ")" ")"
                | "(" operand1:Multiplication ")" "*" "(" "(" operand2:Number ")" ")"
                | "(" operand1:Multiplication ")" "*" "(" "(" "(" operand2:Addition ")" ")" ")"
                | :
                | :
                | "(" operand1:Number ")" "*" operand2:Number
                | "(" operand1:Number ")" "*" "(" operand2:Addition ")"
                | "(" operand1:Number ")" "*" "(" operand2:Multiplication ")"
                | "(" operand1:Number ")" "*" "(" operand2:Number ")"
                | "(" operand1:Number ")" "*" "(" "(" operand2:Addition ")" ")"
                | "(" operand1:Number ")" "*" "(" "(" operand2:Multiplication ")" ")"
                | "(" operand1:Number ")" "*" "(" "(" operand2:Number ")" ")"
                | "(" operand1:Number ")" "*" "(" "(" "(" operand2:Addition ")" ")" ")"
                | :
                | :
                | "(" "(" operand1:Addition ")" ")" "*" operand2:Number
                | "(" "(" operand1:Addition ")" ")" "*" "(" operand2:Addition ")"
                | "(" "(" operand1:Addition ")" ")" "*" "(" operand2:Multiplication ")"
                | "(" "(" operand1:Addition ")" ")" "*" "(" operand2:Number ")"
                | "(" "(" operand1:Addition ")" ")" "*" "(" "(" operand2:Addition ")" ")"
                | "(" "(" operand1:Addition ")" ")" "*" "(" "(" operand2:Multiplication ")" ")"
                | "(" "(" operand1:Addition ")" ")" "*" "(" "(" operand2:Number ")" ")"
                | "(" "(" operand1:Addition ")" ")" "*" "(" "(" "(" operand2:Addition ")" ")" ")"
                | :
                | :
                :
                :
                }

これによって、1*(2+3) は次の構文木で表されます。

抽象構文木

注意

￢＜＞＜∪∪は、いったんエイリアスもプロダクションとみなして解析木を作成した後、エイリアスに対応するノードを削除することによって構文木を得ます。￢＜＞＜∪∪は、１つの入力から複数の解析木を構築可能な文法を扱うことはできません。例えば次の文法を扱うことはできません。

Foo { bar | "A" }
bar = "A" ;

しかし、次の文法であれば扱えます。

Baz { "A" | "A" }

これは、次と同じです。

Baz { "A" }