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

コンパイラの入り口、「字句解析」のための文字列操作

ガリレオ
小山博史
2007/5/15

　取りあえずの単純な字句解析プログラム

　それでは、実際に字句解析プログラムを作成してみましょう。実は、プログラミング言語S1sを定義するに当たって、字句解析がしやすいように定義をしています。字句の区切り文字として空白を使用することにしてあるので、ソースコードを各語へ分解するプログラムは簡単に作成できます。

■ StringTokenizerクラスで分割する方法

　Javaでは、java.utilパッケージにStringTokenizerという便利なクラスがあるので、これを使うと簡単にS1sのソースコードを字句へ分解できます。ただ単に、文字列の終わりに到達するまで、nextTokenメソッドを呼び出し続ければよいのです。字句の区切り文字として使用する空白の定義を厳密にはしていませんでしたが、タブコード、改行コードも空白とすることにして、StringTokenizerをそのまま使用することにします。

SimpleScanner.java（readLinesメソッド抜粋）

List<Token> tokenList = new LinkedList<Token>(); （略）     // トークンリストの作成     StringTokenizer tokenizer = new StringTokenizer(s);     while (tokenizer.hasMoreTokens()) {         String st = tokenizer.nextToken();         Token token =createToken(st);         token.setLineNumber(current);         tokenList.add(token);     } （略）     return tokenList; }

　createTokenメソッドは次のようになります。基本的に字句単位で文字列sが渡ってくるため、それに応じたtypeの値を判定しています。数値か識別子かは最初の1文字だけで判定しているため、完全な判定とはなっていません。

　数値については、DoubleクラスのparseDoubleメソッドを使って数値へ変換できなかった場合はエラー文字列としています。"@value"などは識別子ではないと判定しますが、"value#"などは識別子と認識されるようになっています。

　そもそも識別子については定義していないため、S1sでは基本的にエラーとして問題はありません。実際に識別子の判定が必要な場合は、言語上で定義をして実装することになる点については留意しておいてください。

SimpleScanner.java（createTokenメソッド抜粋）

private Token createToken(String s) {     Token token = null;     if (TokenUtil.isKeyword(s)) {         token = new Token(TokenUtil.KEYWORD, s);     } else if ("{".equals(s)) {         token = new Token(TokenUtil.L_BRACE, s); （略）     } else if ("*".equals(s) || "/".equals(s)) {         token = new Token(TokenUtil.OPE_MD, s);     } else {             char ch = s.charAt(0);         if (Character.isDigit(ch)) {             try {                 double n = Double.parseDouble(s);                 token = new Token(TokenUtil.NUMBER, n);             } catch(NumberFormatException e) {                 token = new Token(TokenUtil.ERROR, s);             }         } else if (Character.isLetter(ch)) {             token = new Token(TokenUtil.IDENTIFIER, s);         } else {             token = new Token(TokenUtil.ERROR, s);         }     }     return token; }

■ Stringクラスのsplitメソッドで分割する方法

　StringTokenizerクラスを使った実装例を紹介しましたが、Java2 SE 1.4以降では、正規表現が使えるようになり、Stringクラスにsplitメソッドが追加されました。実は、StringTokenizerを使うよりは、こちらのsplitメソッドの方がAPIリファレンスでは推奨されていますから、こちらを使うという選択肢もあります。その場合は、トークンリストの作成部分だけを次のように変更します。

SplitScanner.java（readLinesメソッド抜粋）

List<Token> tokenList = new LinkedList<Token>(); （略）     // トークンリストの作成     for (String st: s.split("\\s")) {         if (st.length() == 0) continue;             Token token =createToken(st);             token.setLineNumber(current);             tokenList.add(token);         } （略）     return tokenList; }

　s.split("\\s")によって、字句に分解されたStringの配列が取得できます。このようにして取得した配列の各要素について処理をするためにfor文を使っています。

　ただし、この正規表現で取得できる配列については、行頭に空白があると、字句として空文字列が表れます。そのため、ここでは「if (st.length() == 0) continue;」で、空文字列の場合は無視をするようにしています。

■ このままでは、字句の開始位置をトークンに保持できない

　StringTokenizerクラスを使う方法にしても、Stringクラスのsplitメソッドを使う方法にしても、単純にプログラムができるというメリットがありますが、字句が出現する位置について算出するのが若干面倒であるため、ここでは実装をしていません。

　また、字句の区切りを必ず付けることを強制するため、例えば「main{1+2}」といった記述はできないということになります。

　StringTokenizerで字句解析プログラムを実装したSimpleScannerTestクラス（別途掲載）を使うと、「main { 0 }」というS1sプログラムが記述されたソースファイル01.s1sからは、下記のようなトークンリストが生成できます。「--------」でトークンを区切って表示しています。どのトークンも開始位置を示すindexが0となっています。

> java SimpleScannerTest 01.s1s -------- line :1 index:0 type :8 value:main -------- line :1 index:0 type :6 value:{ -------- line :1 index:0 type :1 value:0.0 -------- line :1 index:0 type :7 value:}

図4　SimpleScannerで作成されるトークンリスト

　汎用的な字句解析プログラムを作成

　StringTokenizerクラスを使ったり、Stringクラスのsplitメソッドを使ったりすれば、S1sのソースコードを字句解析するプログラムを簡単に作成できることは分かりました。

　しかし、字句の開始位置をトークンに保持できるようにするために、もう少し汎用的に字句解析プログラムを作成してみることを考えてみましょう。これができると、プログラミング言語の文法定義時に、区切り文字として空白を意識して挿入する必要がなくなりますし、ソースコードを記述するときにも、もっと自由に書けるようになります。

■ Iteratorインターフェイスを活用する

　Scannerクラスでトークンリストの作成をするためにS1sTokenizerクラスを用意します。このクラスはjava.utilパッケージのIteratorインターフェイスを実装しています。トークンがある間はhasNextメソッドがtrueを返すので、nextメソッドを使ってトークンを取得し、それをtokenListへ追加していきます。なお、removeメソッドは使わないので、何もしない実装としてあります。

SplitScanner.java（readLinesメソッド抜粋）

List<Token> tokenList = new LinkedList<Token>(); （略）     // トークンリストの作成     Iterator<Token> tokenizer = new S1sTokenizer(s);     while (tokenizer.hasNext()) {         Token token = tokenizer.next();         token.setLineNumber(current);         tokenList.add(token);     } （略）     return tokenList; }

2/3

Index
第5回　コンパイラの入り口、「字句解析」のための文字列操作
	Page1 「字句解析」とは何ぞや？ 　　ソースコードからトークンのリストを作成 　　トークンの種類 　　Javaで1行ずつ読み込むには？ 　　Tokenクラスを定義する 　　TokenUtilクラスを定義する
	Page2 取りあえずの単純な字句解析プログラム 　　StringTokenizerクラスで分割する方法 　　Stringクラスのsplitメソッドで分割する方法 　　このままでは、字句の開始位置をトークンに保持できない 汎用的な字句解析プログラムを作成 　　Iteratorインターフェイスを活用する
	Page3 　　文字判定処理の詳細 　　数字から数値へのトークン化 　　予約語と識別子のトークン化 字句解析プログラムを実行しよう！ 次回は「構文解析」を行って、バイナリコードを生成

Java Solution全記事一覧

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