Javaでコンパイラの基礎を理解する （6）

もしも、コンパイラ専門書が読めたなら……

ガリレオ
小山博史
2007/7/11

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

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

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

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

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

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

Parser.java（抜粋）

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)     { /* 略 */ } }

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

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

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

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

createProgramメソッド

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

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

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

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

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

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

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

createExpressionメソッド

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

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

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

createTermメソッド

private AbstractExpression createTerm(ListIterator<Token> tokens) 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; }

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

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

createFactorメソッド

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

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

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

createNumberメソッド

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

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

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

checkメソッド

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

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

3/4

Index
第6回　もしも、コンパイラ専門書が読めたなら……
	Page1 「構文解析」とは、いったい何なのか？ 　　構文木とは？ 　　下向き構文解析法とは？ 　　バックトラッキングとは？
	Page2 構文木を実現するクラス 　　“葉”のクラス 　　“節”のクラス 　　演算の優先度を理解する 　　共通のスーパークラス：AbstractExpressionクラス 　　プログラムを表現するノード：Programクラス 　　演算を表す：Expressionクラス、Termクラス 　　数字を表す：NumberExpressionクラス
	Page3 いよいよ大詰め！ 「構文解析」を行う 　　構文解析を行う：Parserクラス 　　構文解析法の開始：createProgramメソッド 　　加減演算子が出るまで処理：createExpressionメソッド 　　乗除演算子が出るまで処理：createTermメソッド 　　字句によって処理を変える：createFactorメソッド 　　数値のインスタンスを作成：createNumberメソッド 　　どの字句かの判定を行う：checkメソッド
	Page4 最後の仕上げ、 「コード生成」を知る！ 　　子要素が正しいかチェック：Programクラスのcompileメソッド 　　加減演算子命令の生成：Expressionクラスのcompileメソッド 　　乗除演算子命令の生成：Termクラスのcompileメソッド 　　データ操作命令の生成：NumberExpressionクラスのcompileメソッド 　　コンパイルを実際に実行するクラス：Compilerクラス 　　起動を行うクラス：Svm1cクラス そして、Javaでコンパイラを実行する。 もしも、コンパイラ専門書が読めたなら……

Java Solution全記事一覧

＠ITメールマガジン　新着情報やスタッフのコラムがメールで届きます（無料）