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

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

いよいよ大詰め！ 「構文解析」を行う

　構文木を表現するクラスについても準備が整ったので、ようやく字句のリストから構文木を生成する構文解析クラスの作成ができます。

構文解析を行う：Parserクラス

　クラス名はParserとしましょう。最初の解説を思い出してもらいたいのですが、生成規則ごとに処理を用意する必要があるので、ここではcreateProgram、createExpression、createTerm、createFactor、createNumberといったメソッドを用意することにします。

　また、字句のタイプをチェックするために、checkメソッドを作ります。これらはParserクラスでしか使いませんから、privateメソッドとして用意しておきます。構文木を表現するインスタンスを生成するpublicメソッドとしては、executeメソッドを用意します。

　ちなみに、executeメソッド、各メソッドのパラメータにはjava.util.ListIteratorインターフェイスを実装したイテレータを使っています。これは、バックトラッキングの処理をしやすいようにするためです。

public class Parser {
    public AbstractExpression execute(List<Token> list)
    throws Exception {
        ListIterator<Token> tokens = list.listIterator();
        AbstractExpression programTree = createProgram(tokens);
        return programTree;
    }
    private AbstractExpression createProgram(
        ListIterator<Token> tokens)
    throws Exception { /* 略 */ }
    private AbstractExpression createExpression(
         ListIterator<Token> tokens)
    throws Exception { /* 略 */ }
    private AbstractExpression createTerm(
         ListIterator<Token> tokens)
    throws Exception { /* 略 */ }
    private AbstractExpression createFactor(
         ListIterator<Token> tokens)
    throws Exception { /* 略 */ }
    private AbstractExpression createNumber(
         ListIterator<Token> tokens)
    throws Exception { /* 略 */ }
    private boolean check(ListIterator<Token> tokens, int type)
    { /* 略 */ }
}

Parser.java（抜粋）

構文解析法の開始：createProgramメソッド

　createProgramメソッドでは、前に図5で解説したとおり、字句を取り出し「main」というキーワードかチェック、字句を取り出し「{」かチェック、残りの字句リストが<expression>から生成できる記号列かチェック、最後の字句を取り出し「}」かチェック、という順番で処理をしています。

　字句タイプによってチェックをするcheckメソッドを呼び出しても、字句リストの状態は変わりません。このため、チェックしたら空読みをする必要があります。

　チェック時に問題が発生したら例外を発生させています。このときに、字句の情報をコンソール画面へ出力することにより、どの字句を読み込んだときに問題が出たのかを判断できるようにすることも可能です。

private AbstractExpression createProgram(ListIterator<Token> tokens)
throws Exception {
    Token t = tokens.next();
    if (t.getType() != TokenUtil.KEYWORD) {
        throw new Exception();
    }
    if (!"main".equals(t.getS())) {
        throw new Exception();
    }
    if (!check(tokens, TokenUtil.L_BRACE)) throw new Exception();
    tokens.next(); // L_BRACE
    AbstractExpression e = createExpression(tokens);
    if (!check(tokens, TokenUtil.R_BRACE)) throw new Exception();
    tokens.next(); // R_BRACE
    Program p = new Program();
    p.setValue(t);
    p.add(e);
    return p;
}

createProgramメソッド

　文法のチェックが終わって問題がなければ、ルートとなるProgramクラスのインスタンスを生成して、子要素にはcreateExpressionメソッドで作成された構文木を登録します。こうやって完成した構文木を呼び出し元のexecuteメソッドへ返しています。

加減演算子が出るまで処理：createExpressionメソッド

　次に、createExpressionメソッドです。createProgramメソッドと同様に処理を書いていきます。

　最初の字句は「<term>」に対応するものが来ているはずなので、createTermメソッドで取得します。その後に字句が続く際に、加減演算子が来ていれば、「<expression>」から生成されるものになりますし、そうでない場合は、ここでは判定できないので、繰り返し処理を抜けます。

　加減演算子が次の字句であれば、演算子分については「Token op = tokens.next();」でopへ読み込み、その次の字句には「<term>」が来ていると仮定して、createTermメソッドで次の要素を生成します。

　各要素を入手したら、Expressionクラスのインスタンスを生成してvalueにはopを設定し、子要素には左右の被演算子であるtとt2を順に追加します。

private AbstractExpression createExpression
(ListIterator<Token> tokens) throws Exception {
    AbstractExpression t = createTerm(tokens);
    while (tokens.hasNext()) {
        if (!check(tokens, TokenUtil.OPE_AS)) {
            break;
        }
        Token op = tokens.next();
        AbstractExpression t2 = createTerm(tokens);
        AbstractExpression e = new Expression();
        e.setValue(op);
        e.add(t);
        e.add(t2);
        t = e;
    }
    return t;
}

createExpressionメソッド

乗除演算子が出るまで処理：createTermメソッド

　createTermメソッドについては、ソースコードを見てもらえば分かるように、createExpressionの加減演算子の部分が乗除演算子のものに置き換わり、子要素が「<term>」から「<factor>」になっただけになります。

throws Exception {
    AbstractExpression f = createFactor(tokens);
    while (tokens.hasNext()) {
        if (!check(tokens, TokenUtil.OPE_MD)) {
            break;
        }
        Token op = tokens.next();
        AbstractExpression f2 = createFactor(tokens);
        AbstractExpression e = new Term();
        e.setValue(op);
        e.add(f);
        e.add(f2);
        f = e;
    }
    return f;
}

createTermメソッド

字句によって処理を変える：createFactorメソッド

　createFactorメソッドについては、次に数値の字句が来るか「(」の字句が来るかのどちらかなので、checkメソッドを使って確認をしてから処理を振り分けています。数値の字句であれば、そのままcreateNumberメソッドを呼び出しますし、丸括弧が使われているのであれば、createProgramメソッドと同様にして「(」で始まり、「<expression>」が続き、最後が「)」で終わる構成になっていることを確認しています。

private AbstractExpression createFactor(ListIterator<Token> tokens)
throws Exception {
    if (check(tokens, TokenUtil.NUMBER)) {
        AbstractExpression n = createNumber(tokens);
        return n;
    } else {
        if (!check(tokens, TokenUtil.L_PAREN))
            throw new Exception();
        tokens.next(); // L_PAREN
        AbstractExpression e = createExpression(tokens);
        if (!check(tokens, TokenUtil.R_PAREN))
            throw new Exception();
        tokens.next(); // R_PAREN
        return e;
    }
}

createFactorメソッド

数値のインスタンスを作成：createNumberメソッド

　createNumberメソッドでは、単純に字句と対応するNumberExpressionクラスのインスタンスを作成して返しています。

private AbstractExpression createNumber(ListIterator<Token> tokens)
throws Exception {
    Token t = tokens.next();
    AbstractExpression e = new NumberExpression();
    e.setValue(t);
    return e;
}

createNumberメソッド

どの字句かの判定を行う：checkメソッド

　checkメソッドでは字句のチェックをしています。typeにはTokenUtilで宣言されている字句タイプが渡されることが前提となっています。今回の構文解析プログラムでは、先読みをしてチェックしているので、このメソッドが呼ばれる前と後で字句リストの状態が変わらないようにする必要があります。このため、いったん字句を読み込んで、その値を字句リストへ戻しています。

private boolean check(ListIterator<Token> tokens, int type) {
    Token t = tokens.next();
    tokens.previous();
    return (t.getType() == type);
}

checkメソッド

　以上で構文解析のプログラムについては説明が終わりですが、どうでしょうか。初めてコンパイラについて学習する人にとっては、S1sは結構複雑な文法に見えていたと思いますが、これをチェックするプログラムは意外とパターン化されていて、簡単に作れそうだな、と思いませんか？