もしも、コンパイラ専門書が読めたなら……：Javaでコンパイラの基礎を理解する（6）（2/4 ページ）

[小山博史，株式会社ガリレオ]

構文木を実現するクラス

　それでは、実際の構文解析プログラムについて説明をしますが、その前に、最終的に生成する必要がある構文木について表現するクラスを用意しておきます。木構造のようなデータ構造を表現する方法はいくつかありますが、ここではノード（節）とリーフ（葉）を表すクラスと、それらの共通のスーパークラスを1つ用意することにします。

“葉”のクラス

　今回、生成する構文木では、リーフとなるのは「<number>」の字句になります。BNFからチェックの処理を単純に作成するようなことを考えると、「<number> ::= <digit>{<digit>}」と「<digit> ::= 0|1|2|3|4|5|6|7|8|9」の生成規則についてもチェックする処理が必要となるのですが、これらについては、字句解析のときに解析をしてしまっていて、「<digit>」の字句というものは用意していません。ですから、ここでは「<number>」と対応するNumberExpressionクラスを用意すればよいのです。

“節”のクラス

　「<program>」「<expression>」「<term>」については対応するノードのクラスを用意します。「<factor>」と対応するノードのクラスについては必要ありません。「<factor>」の生成規則により、演算の優先度を高める式を表現できるようになっているのですが、この優先度は構文木の構造から分かるため必要ありません。

演算の優先度を理解する

　例えば、「main { 1+2*3 }」と「main { (1+2)*3 }」の構文木を比較してみましょう。ここでは、ノードにもリーフにも「(」や「)」がありませんが、演算の優先度が分かります。

図6　main { 1+2*3 }の構文木

図7　main { (1+2)*3 }の構文木

　ということで、「<program>」にはProgramクラス、「<expression>」にはExpressionクラス、「<term>」にはTermクラスを用意します。なお、NumberExpressionクラスとこれらのスーパークラスとしてはAbstractExpressionクラスを用意します。

共通のスーパークラス：AbstractExpressionクラス

　まず、AbstractExpressionクラスですが、次のように子をArrayList型のchildrenフィールドで保持し、対応する字句の情報をvalueフィールドに保持します。子要素の追加操作を提供するaddメソッドについては何もしないことにしています。コンパイルについては各要素のクラスが機能を提供することにするので、抽象メソッドとしてcompileメソッドを定義しています。

public abstract class AbstractExpression {
    private Token value;
    private ArrayList<AbstractExpression> children
        = new ArrayList<AbstractExpression>();
    public void setValue(Token v) { value = v; }
    public Token getValue() { return value; }
    public ArrayList<AbstractExpression> getChildren() {
        return children;
    }
    public void add(AbstractExpression node) { }
    public Iterator<AbstractExpression> iterator() {
        return children.iterator();
    }
    public abstract void compile(List<Byte> objectCodeList)
    throws Exception;
}

AbstractExpression.java（抜粋）

プログラムを表現するノード：Programクラス

　Programクラスは次のようになります。プログラムを表現するノードですから必ず子要素を1つ持ちます。子要素としてExpressionクラス、NumberExpressionクラス、Termクラスのインスタンスを持つことがあります。このため、addメソッドではchildrenへ要素を追加するために、スーパークラスであるAbstractExpressionクラスのgetChildrenメソッドを呼び出しています。

　compileメソッドについては、後でコーディングしますが、このソースコードをコンパイルするためには実装しておく必要があります。この時点では、何もしないメソッドとして実装しておきます。

public class Program extends AbstractExpression {
    public void add(AbstractExpression node) {
        getChildren().add(node);
    }
    public void compile(List<Byte> objectCodeList)
    throws Exception {
        // TODO
    }
}

ソース Program.java（抜粋）

演算を表す：Expressionクラス、Termクラス

　Expressionクラスは加算と減算を表すので、子要素としてNumberExpressionクラスやTermクラスのインスタンスを持つことがあります。このため、Programクラスと同様にaddメソッドを記述します。Termクラスは、乗算、除算を表す点を除けば、Expressionクラスと同様ですから、addメソッドをExpressionクラスと同じようにします。

public class Expression extends AbstractExpression {
    public void add(AbstractExpression node) {
        getChildren().add(node);
    }
    public void compile(List<Byte> objectCodeList)
    throws Exception {
        // TODO
    }
}

Expression.java（抜粋）

数字を表す：NumberExpressionクラス

　NumberExpressionクラスについては、リーフとなるため子要素を持ちません。このため、AbstractExpressionのaddメソッドをオーバーライドする必要はありません。compileメソッドの実装は必要なので、この時点では取りあえず空のメソッドとしておきます。

public class NumberExpression extends AbstractExpression {
    public void compile(List<Byte> objectCodeList)
    throws Exception {
        // TODO
    }
}

NumberExpression.java（抜粋）

　以上で構文木を表現するクラスについて、最低限の実装が終了しました。