Handbook of

  1. このドキュメントについて
  2. ¬<><∪∪ Overview
    1. Features
    2. Core Concept of ¬<><∪∪
    3. プログラム例
  3. 入力
  4. 出力
  5. 字句解析器
    1. 終端記号定義
    2. 部分終端記号定義
    3. トークン式
  6. 構文解析器
    1. 型定義
    2. 別名定義

§1 このドキュメントについて

このドキュメントは、¬<><∪∪の基本的な仕様を簡単に説明したものです。このドキュメントを読むには、Javaやパーサに関する基本的な知識が必要です(下記のCore Concept of ¬<><∪∪を読んで理解できる程度の知識が必要です)。正確さよりも分かりやすさを優先しており、より正確な仕様は仕様書に記述されています。

§2 ¬<><∪∪ Overview

(1) Features

¬<><∪∪ (notavaCC) は、次の特徴を持ったパーサ・ジェネレータ(コンパイラ・コンパイラ)です。

(2) Core Concept of ¬<><∪∪

具象構文木は、非終端記号のインスタンスをノードとし、終端記号のインスタンスを葉とする木だと考えることができます。¬<><∪∪における抽象構文木とは、具象構文木から一部のノードを取り除いたものです。取り除かれたノードの子供は、取り除かれたノードの親のノードの子供になります。¬<><∪∪では、ノードを取り除くかどうかは、インスタンスごとにではなく、非終端記号ごとに選択されます。¬<><∪∪では、BNFのプロダクション LHS ::= RHS に相当する表記は LHS { RHS }LHS = RHS; の2種類があり、後者はノードを構文木から取り除くことを意味します(上の例では、expressiontermexpression = Addition | Subtraction | term ; のように定義されていることを想定しています)。後者の等号を用いた表記は、直感的には、左辺の識別子を右辺の式で置き換えるシンタックスシュガーに近いものです(本ドキュメントでは、そのように説明されます)。抽象構文木のノードは、そのノードをインスタンスとする非終端記号と同名のインターフェイスのオブジェクトで表現され、インターフェイス間に継承関係を設定することができます。ノードの特定の子を、上の operand1 のように、ラベル付けし、インスタンスメソッドによって得ることができます。その戻り値は、ラベル付けされる可能性のあるノードの共通の親の型、あるいは、複数をラベル付けする可能性がある場合 java.util.List になります(例えば label:expression ( "," label:expression )* )。

(3) プログラム例

上のコードから、次のような出力が得られます。


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();
        }
    }
}

§3 入力

¬<><∪∪処理系は、1つのテキストファイル(¬<><∪∪ソース)を入力に取ります。¬<><∪∪ソースは、Javaの処理系が行うのと同様に、コメント等が取り除かれ、トークンの列に変換されます。ただし、¬<><∪∪の識別子や予約語は、Javaとは異なります。

要素説明
識別子 Javaの識別子およびJavaの予約語で、$を含まないもの
予約語 Javaの識別子で、$を含むものからとられます
文字列リテラル、文字リテラル Javaと同様
コメント、ホワイトスペース、改行 Javaと同様

§4 出力

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

§5 字句解析器

字句解析器は、入力されたテキストを、トークンの列に変換します。終端記号定義で指定されるトークン式にマッチする最長の文字列をトークンとして切り出すことを繰り返します。切り出されたトークンを、マッチした終端記号のインスタンスと呼びます。abstractではない型定義、あるいは、別名定義に含まれる文字列リテラルの表す文字列も、トークンとして切り出されます。トークンは、Token型のオブジェクトです。

(1) 終端記号定義

形式:$token 識別子 = トークン式 ;
形式:$white $token 識別子 = トークン式 ;

2つ目の形式は、ホワイトスペースやコメントなどの、文法上無視されるトークンを定義します。

(2) 部分終端記号定義

形式:$subtoken 識別子 = トークン式 ;

トークン式の中で、右辺のトークン式の変わりに識別子を使用できるようにします。右辺のトークン式に、この識別子を間接・直接に含むことはできません。

(3) トークン式

優先順位 形式 マッチする文字列
最低 トークン式1 | トークン式2 どちらかのトークン式がマッチする文字列
5 トークン式1 & トークン式2 両方の式がマッチする文字列
トークン式1 - トークン式2 トークン式1がマッチし、トークン式2がマッチしない文字列
4 トークン式1 トークン式2 トークン式3 ... トークン式1 トークン式2 トークン式3 ... がマッチする文字列を順につなげてできる文字列
3 !トークン式 トークン式がマッチしない文字列
2 トークン式* トークン式がマッチする文字列の0回以上の繰り返し
トークン式+ トークン式がマッチする文字列の1回以上の繰り返し
トークン式? トークン式にマッチする文字列と、空の文字列
[トークン式]
最高 文字リテラル 文字リテラルの表現する文字
文字リテラル1..文字リテラル2 文字リテラル1の文字コード以上で、文字リテラル2の文字コード以下の文字コードを持つ文字
文字列リテラル 文字列リテラルの表現する文字列
識別子 識別子を名前に持つ終端記号定義、部分終端記号定義の右辺のトークン式がマッチする文字列
(トークン式) トークン式がマッチする文字列

§6 構文解析器

構文解析器は、字句解析器の出力するトークン列を入力にとり、抽象構文木を出力します。

(1) 型定義

形式:修飾子 識別子 { 式 }
形式:修飾子 識別子 -> 親型1 & 親型2 & ... { 式 }

識別子が左辺、式が右辺であるような拡張BNFの等式と同様に、構文を構成する非終端記号を定義します。また、この非終端記号のインスタンス(パーズの結果得られる構文木のこの非終端記号に対応する部分)はこの非終端記号と同名のインターフェイスのオブジェクトで表現されます。親型が指定されている場合、インターフェイスはそれらの型をextendsします。そうでない場合、インターフェイスは、Nodeインターフェイスをexntedsします。インターフェイスは、式に含まれるラベルと同名で、引数を取らないメソッドを持ちます。このメソッドは、式の中でラベル付けされている終端記号・非終端記号のインスタンスを返します。もし、ラベル付けされるインスタンスの個数が、2以上になる可能性があれば、戻り値はjava.util.Listになります。そうでない場合、ラベル付けされる可能性のあるインスタンスに共通の型になります。

修飾子意味
$parsableこの非終端記号で定義される文法をパースするメソッドを出力する
$abstractインターフェイスを出力するが、文法を定義するためには使用できない
$protected出力されるインターフェイスがprotectedになる
$private出力されるインターフェイスがprivateになる

(2) 別名定義

形式:識別子 = 式 ;

式の中で、右辺の式の代わりに識別子を使用できるようにします。ただし、右辺の式が$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" と指定されているかのようにラベルを引き継ぎます。

(3) 式

優先順位 形式 意味
最低 式 | 式 いずれか
4 式 式
3 式* 0回以上の繰り返し
式+ 1回以上の繰り返し
式? 省略可能
[式]
式 / 識別子 式に含まれる終端記号・非終端記号が、識別子の型であるかのようにインターフェイスを出力する。これは、メソッドの戻り値の型をコントロールするために使用されます。
2 識別子 : 式 式に含まれる終端記号・非終端記号・別名をラベル付けする
$label : 式 式に含まれる終端記号・非終端記号・別名を$labelでラベル付けする
最高 識別子 その名前をもつ終端記号・非終端記号
文字列リテラル 終端記号
型定義 型定義を別途行い、その識別子を書いたのと同じ
式 # 識別子 (本ドキュメントでは解説しません)
( 式 ) グループ化
$embed ( 式 ) グループ化[*1]

[*1] 現在の実装では、式中に含まれる別名を別名定義における右辺で置換します。$embed しなかった場合、別名は非終端記号として扱われるため、LRの還元が必要になります。$embed した場合、還元が不要になるため、LALR(1) のコンフリクトの警告を抑えることができ、また、パフォーマンスを向上させることができます。この形式は、将来のバージョンでは単なるグループ化として扱われる可能性があります。