このドキュメントは、¬<><∪∪の基本的な仕様を簡単に説明したものです。このドキュメントを読むには、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 )*
)。
// Simple Expression Syntax
$package parser; // 出力されるクラスが含まれるパッケージの名前(省略可能)
// Token Definitions
$subtoken ANY_CHARACTER = '\u0000'..'\uFFFF' ;
$subtoken LINE_TERMINATOR = "\n" | "\r" | "\r\n" ;
$subtoken WHITE_SPACE = ' ' | '\t' | '\f' | LINE_TERMINATOR ;
$subtoken DIGIT = '0'..'9' ;
$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 INTEGER = '0' | ( ( DIGIT - '0' ) DIGIT* ) ;
// Syntax Definitions
$parsable
Root { expression:expression }
$abstract Expression { }
expression = Addition
| Subtraction
| term
;
Addition -> 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 ")"
;
上のコードから、次のような出力が得られます。
package parser;
public class ExpressionParser {
public Root parseRoot(File file) throws IOException, ParseException { ... }
public Root parseRoot(String sourceName, File file, String charsetName, int tabStop) throws IOException, ParseException { ... }
public Root parseRoot(String sourceName, Reader reader, int tabStop) throws IOException, ParseException { ... }
public Root parseRoot(String sourceName, CharSequence seq, int tabStop) throws ParseException { ... }
public Root parseRoot(LexicalAnalyzer analyzer) throws ParseException { ... }
public static class ParseException extends Exception { ... }
public static class LexicalAnalyzer {
public abstract Token next() throws ParseException;
}
public static class Visitor { ... }
public static interface Node {
public List getChildNodes();
public void accept(Visitor visitor);
public Node getParentNode();
public void setParentNode(Node parentNode);
}
public static interface Token extends Node {
public int getSymbolID();
public String getImage();
public String getSourceName() throws UnsupportedOperationException;
public int getIndex() throws UnsupportedOperationException;
public int getLine() throws UnsupportedOperationException;
public int getColumn() throws UnsupportedOperationException;
}
public static final int EOF_TOKEN = 0;
public static final int TOKEN_WHITE_SPACES = 1;
public static final int TOKEN_TRADITIONAL_COMMENT = 2;
public static final int TOKEN_END_OF_LINE_COMMENT = 3;
public static final int TOKEN_INTEGER = 4;
public static interface Root extends Node {
public Expression expression();
}
public static interface Expression extends Node {
}
public static interface Addition extends Expression {
public Expression operand1();
public Expression operand2();
}
public static interface Subtraction extends Expression {
public Expression operand1();
public Expression operand2();
}
public static interface Multiplication extends Expression {
public Expression operand1();
public Expression operand2();
}
public static interface Division extends Expression {
public Expression operand1();
public Expression operand2();
}
public static interface Number extends Expression {
public Token value();
}
protected static class NodeInitializationParameters { ... }
protected Node createNode(int symbolID, NodeInitializationParameters parameters) throws ParseException { ... }
protected LexicalAnalyzer createLexicalAnalyzer(String sourceName, CharSequence text, int tabStop) throws ParseException { ... }
public static void main(java.lang.String[] args) {
try {
ExpressionParser p = new ExpressionParser();
for (int i = 0; i < args.length; i++) {
java.io.File file = new java.io.File(args[i]);
System.out.println(file);
System.out.println(p.parseRoot(file));
break;
}
} catch(java.lang.Exception x) {
x.printStackTrace();
}
}
}
¬<><∪∪処理系は、1つのテキストファイル(¬<><∪∪ソース)を入力に取ります。¬<><∪∪ソースは、Javaの処理系が行うのと同様に、コメント等が取り除かれ、トークンの列に変換されます。ただし、¬<><∪∪の識別子や予約語は、Javaとは異なります。
要素 | 説明 |
---|---|
識別子 | Javaの識別子およびJavaの予約語で、$を含まないもの |
予約語 | Javaの識別子で、$を含むものからとられます |
文字列リテラル、文字リテラル | Javaと同様 |
コメント、ホワイトスペース、改行 | Javaと同様 |
¬<><∪∪処理系は、入力されたファイルの拡張子を .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 | この非終端記号で定義される文法をパースするメソッドを出力する |
$abstract | インターフェイスを出力するが、文法を定義するためには使用できない |
$protected | 出力されるインターフェイスがprotected になる |
$private | 出力されるインターフェイスがprivate になる |
形式:識別子 = 式 ;
式の中で、右辺の式の代わりに識別子を使用できるようにします。ただし、右辺の式が$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) のコンフリクトの警告を抑えることができ、また、パフォーマンスを向上させることができます。この形式は、将来のバージョンでは単なるグループ化として扱われる可能性があります。