( 1 )1

プログラミング言語のスコープ階層を反映した構造化解析器
神谷 年洋 † 石尾 隆 ‡ 井上 克郎 ‡ソフトウェアの開発では，コンパイラやリバースエ

して，リバースエンジニアリングツール，lint などのンジニアリングツールなど，ソースコードを処理する

ソースコード診断ツール，変更波及解析やスライスなための種々のツールが用いられる．これらのツールがどの依存関係解析を求めるツールなど，数多くのツー必要とする字句解析や構文解析をサポートするため

ルが存在する．また，diff や grep，バージョン管理シに，これまでに lex と yacc を初めとする多くのコン

ステムといった，基本的には任意のファイルを処理可

パイラ・コンパイラが開発・利用されてきた．コンパ

能なツールにおいても，ソースコードの意味を考慮す

イラ・コンパイラによって，これらのツールの開発のることでより高度な処理を行うことを目指したもの

生産性や保守性が向上する一方で，処理対象のプロが登場してきている [8] [14] [19]．

グラミング言語の構文がコンパイラ・コンパイラの能これらのツールは，そのツールが必要とするソース

力を超える部分では，複雑なプログラミングが必要

コードの意味情報の程度によって，字句解析，プリプとされる．本稿では，オブジェクト指向プログラミン

ロセッシング，構文解析，意味解析等を行う．これま

グ言語に特徴的なスコープの階層性，構文エラーか

でに，字句解析や構文解析をサポートするため，lex

らの回復処理，繰り返し型開発，回帰テスト等への対と yacc [13]，JavaCC [11]，ANTLR [1]，Boost Spirit

応を取り入れた解析器（字句解析，構文解析，意味解[4] などの字句解析器，構文解析器生成ツール（以降，析を含む）の新しい設計を提案する．設計段階からこ「コンパイラ・コンパイラ」）が開発・利用されてきた．

れらを取り入れることで，複雑なプログラミングを

コンパイラ・コンパイラを用いることで，正規表現

一掃し，ディペンダブルな解析器の開発を可能にするや拡張 BNF で記述された字句規則および構文規則かことを目指す．具体的な適用例として，オブジェクト

ら，字句解析器および構文解析器のプログラムを生成

指向プログラミング言語の一つである Featherweight

することが可能になる．また同時に，それら字句規則

Java を対象とする解析器を実装し，その有効性や適や構文規則を，ソースコード処理ツールの意味解析部

用可能性について評価する．

分と分離して記述することが可能になるなど，ツールを開発する労力が削減され，可読性や保守性が向上す

1 はじめにる．その一方で，プログラミング言語の構文規則は，

ソフトウェアの開発では，ソースコードを入力とす

しばしばこれらのコンパイラ・コンパイラの制限を超る様々なツールが用いられる．コンパイラを筆頭と† Toshihiro

Kamiya, 科 学 技 術 振 興 機 構 さ き が け,
PRESTO, Japan Science and Technology Agency.
‡ Takashi Ishio, Katsuro Inoue, 大阪大学大学院情報科学研究科, Graduate School of Information and Scienceand Technology, Osaka University.

え，そのような場合には適用に困難が伴う．
本稿では，オブジェクト指向プログラミング言語（以降「OOPL」）に特徴的なスコープの階層性を，クラスの継承の階層によって実装する解析器（字句解析，構文解析，意味解析を含む）の新しい設計を提案

2

( 2 )

コンピュータソフトウェア

ソースファイル（文字の並び）トークンの並び

構文解析

コンパイラ・コンパイラ

ソースコード処理ツール

字句解析

字句規則
（正規表現）

字句解析規則
（BNF）

AST等

…

意味解析

出力

図1

ソースコード処理ツールの構成とコンパイラ・コンパイラの適用する．具体的な適用例として，小規模ながらもクラス
やインスタンス変数，メソッドといった概念を備える
プログラミング言語 Featherweight Java [7] を対象とする解析器を，JavaCC [11] を利用して実装する．

2 コンパイラ・コンパイラの利用
図 1 に，構文解析を行うソースコード処理ツールの典型的なシステム構成を示す．字句解析は，ソース
ファイル中の文字の並びを，トークンと呼ばれるプロ
グラミング言語で意味を持つ最小の単位の並びに変換する．その後，構文解析や意味解析によって，トーclass C extends Object {Object value;C() {super();
this.value = new Pair(new A(), new B()).setfst(new B());}}
class Pair extends Object {Object fst;
Object snd;
Pair(Object fst, Object snd) {super();
this.fst = fst;
this.snd = snd;}
Pair setfst(Object newfst) {return new Pair(newfst, this.snd);}}（以下省略）

クンの並びから，式，文，関数定義，クラス定義といった，より大きな構成要素を取り出す．ツールはそ

図2

Fetherweight Java のソースコードの例の後，これらの構成要素に対する実行コードや依存関係を生成したり，型チェックや最適化といった処理を

文解析器は構文エラーからの回復処理を行う必行う．

要がある．このようなエラー回復処理を記述する

従来のコンパイラ・コンパイラは，字句解析器や構ためには，構文解析器の内部処理に関する知識が文解析器の生成を容易にする一方で，現状では以下の必要であり，また，場合によってはエラー回復処

ような制限や問題点がある．

理を見越して構文規則を定義する，などの手法も1. ソースコード中に存在する複数の構文エラーを一度に検出することが必要とされている場合，構併用する必要がある [2]．

2. 構文解析器は何らかの方法で前方参照を解決す( 3 )

Vol. 0 No. 0

1983

3

パッケージ
クラス
ソースファイル

不可視または
アクセス不可メソッド
関数定義

他のメソッド公開されている場合

インスタンス変数

公開されている場合

可視かつアクセス可能

関数定義

関数定義

他のクラス

図3

公開されている場合

レキシカルスコープ
図4

OOPL のスコープおよびアクセス制御る必要がある．図 2 に，Java [10] の文法を簡略化

どの処理を行う必要がある．しかし，これらの解した Featherweight Java [7] で記述されたサンプ

決策はいずれも構文解析器の開発に制約を課す

ルプログラムを示す．下線を引いた部分は，ソーことになる．バックトラックを用いるためには，

スコード中に定義が現れる前に利用されているク

いったん受理された部分のアクションの副作用をラスやメソッドである．オブジェクト指向プログ

どのように取り消すかを考える必要がある．構ラミング言語では，手続き型言語 Pascal や C で

文解析器が字句解析器を制御する方法では，構基本となっているレキシカルスコープ (図 3) に

文解析器と字句解析器の間に相互依存が生じる

代わって，クラスやパッケージによるスコープやために，ソースコード処理ツールのプログラム

アクセス制御 (図 4) を多用する傾向にあり，こが複雑になる．AST を修正する方法では，構文のような前方参照が，インスタンス変数，メソッ

解析が構文解析器（の拡張 BNF による記述）と

ド，クラスなどに対して起こる．

AST 修正ルーチン（のプログラミング言語によ3. C++ [18] や Java といった OOPL の文法には，

る記述）とに分散することになり，やはり複雑に

特定の識別子が型やパッケージの名前であることなる．

を字句解析器が区別できない場合に，構文規則がこの問題の一部は，BNF や構文図（といった自曖昧にな部分がある．

由文脈文法を記述する [16] 記法）によって定義a b(c); c が型ならプロトタイプ，c が変数な
ら変数宣言 (C++)

t<a.b.c.d.e> t が汎用型であれば型，さもなければエラー (C++, Java 1.5 [9])されたプログラミング言語を，より弱い文法ク
ラスを処理する構文解析器を用いて構文解析することに起因する．例えば，代表的なコンパイ
ラ・コンパイラである Yacc（あるいは Bison)(a.b.c.d.e) a.b.c.d.e が型であればキャスト[3] や SableCC [17] の構文解析器は LALR(1)，演算子，e がインスタンス変数の名前であれ

ANTLR [1] や JavaCC [2] の構文解析器は LL(k)ば変数の参照 (C++, Java)で あ る ．ま た ，文 献 [5] で は ，“The grammar

解決策としては，構文解析器はバックトラックを

for Java presented piecemeal in the preceding

行うか（再帰下降構文解析器の場合），処理中にchapters is much better for exposition, but it

シンボルテーブルを生成するなどの手段によってcannot be parsed left-to-right with one token

字句解析器を制御するか，あるいは，構文解析のof lookahead (中略). These problems and the

結果生成された AST(抽象構文木) を修正するな

solutions adopted for the LALR(1) grammar

4コンピュータソフトウェア

are presented below” と述べられている．

( 4 )3.1 漸進的解析器
本稿で提案する構文および意味解析器（以降，構文

3 OOPL に適した構文解析

および意味の解析を合わせたものを単に「解析」，本

上述の制限や問題点は，従来のコンパイラ・コンパ

稿で提案する解析器を「漸進的解析器」と呼ぶ）の設イラによって生成される構文解析器が，ソースコード

計は，OOPL の構文および意味規則を，パッケージ

内の出現順序に従ってトークンを処理する方法を用いやクラス，メソッドといった，入れ子になったスコーていることに起因するところが大きい．この処理方法

プを作り出す言語要素を境界として分割し，それぞれは，Pascal や C 言語で用いられるレキシカルスコーの分割に対応する構文および意味規則の部分（以降プ (図 3)，つまり，そこに至るまでに出現したものが「部分規則」）を継承関係にある別個のクラスに実装可視となるようなスコープを処理するのに都合がよするものである．さらに，「内側」の言語要素（たとえい．一方で，OOPL のクラスやパッケージによるスばメソッド）の解析を担当するクラスは，「外側」のコープとアクセス制御 (図 4) は，入れ子のレベルが言語要素（たとえばクラス）の解析を担当するクラス

同じかより外側のものは可視であり，内側のものは公から導出される．実行時には，基底クラスが「外側」

開されない限り不可視であるという，外側から内側への言語要素を先に解析した後で，導出クラスがメソッの階層性を持っている．

ドオーバーライドにより「内側」の言語要素の解析を

本稿では，（処理対象となっているプログラミング行う．この設計により，基底クラスの意味解析により言語の）クラスやパッケージといったスコープと可視生成したスコープに基づいてトークン列を修正してか性制御の「外側から内側に向かう階層性」を，構文おら導出クラスが構文解析を行うことが可能になり，シ

よび意味解析を実装するクラスの継承階層によって実

ンボルテーブルなどを利用した字句解析器を用いるこ装する手法を提案する．このアプローチにより，上述となく，型や名前を区別した構文規則をそのまま利用の制限や問題点は以下のように解消・解決される．

することができる．また，導出クラスが構文エラーを

1. 構文エラーからの回復処理を構造化例外処理と例外として送出することにより，構文エラーの回復処

して組み込むことが可能になり，単一のソース

理を構造化例外処理によって行うことが可能になる．

コードに含まれる複数個のエラーを検出することが容易である．

2. 前方参照の問題が生じない．

3.2 漸進的解析器の構成
図 5 に，クラス，インスタンス変数，メソッド（お3. 字句解析器が変数名と型とを区別することが可

よびパラメータ），自動変数を持ち，強く型付けさ能になり，曖昧または無限個の先読みが必要な文れた（すなわち，明示的な型の宣言を必要とする）

法を解消するための変形処理を容易に組み込む

OOPL を対象とする漸進的解析器のクラス階層と，ことができる．

処理全体の実行順序を示す．この図で，partialSrc とまた，本手法にはさらに以下のような利点もある．

あるのは，ソースファイルの一部，全体，または複数• プログラミング言語の構文規則を（最初から全のソースファイルの内容を保持するオブジェクトであ部作り込むのではなく）部分的な構文規則から順に作り込んでいくことで，繰り返し型開発に対応

る．構文解析器は，部分規則に対応する 4 つのクラスから構成されている†1 ．解析は，以下の順序で進行

する．

する．

• ツールの開発を通じて，個々の部分的な構文規(1) PackageParser は，ソースコード中でクラス則に対するテストケースを，開発の最後まで回帰†1 漸進的解析器は，構文解析だけではなく意味解析も行うため，クラス名やメソッド名が HogeParser,
parseHoge() などとなっているのは不適切かもしれな
いが，「意味解析をする」を意味するうまい動詞が見つからないため，このままにしておく．

テストのために用いることができる．

( 5 )

Vol. 0 No. 0

1983

5

実行順序
PackageParser#interfaces-code+parse(partialSrc):code#parserInterface(partialSrc):interface#parseClass(partialSrc):code

ClassParser#instanceVars#methods#parseClass(partialSrc):code#parseMethod(partialSrc):code

InterfaceParser
MethodParser#parameters#parseMethod(partialSrc):code#parseInterface(partialSrc):interface

図5

漸進的解析器の典型的なクラス階層

を定 義 し て い る 部 分 す べ て 見 つ け だし ，par-「parse*()」) のパラメータや戻り値 (partialSrc, in-

seInterface() を呼び出すことにより，それらを

terface, code) によるものと，protected インスタン

InterfaceParser に渡す．

ス変数 (interfaces, instanceVars, methods) によるも

(2) InterfaceParser はクラスのインターフェイスのがある．前者はメソッドが呼び出されるたびに違う（公開メソッドのシグネチャや公開インスタン

内容が生成されて渡されること，後者はそのクラスのス変数の型）を調べて PackageParser に返す．

parse*() メソッドによって内容が生成された後，導出

PackageParser はその情報を interfaces に追加しクラスの parse*() メソッドを（複数回）呼び出す間ていく．

は変化しないことを意図している（従って，実装の際(3) PackageParser は，クラスを定義するソースに必ずしもオーバーライドされるメソッドと，そのパ

コードの部分を，parseClass() を呼び出すことにラメータや protected インスタンス変数を用いる必要より，ClassParser に渡す．

はなく，オーバーライドされるメソッドの代わりに委(4) ClassParser はすべてのメソッドのシグネチ
ャと イ ン ス タ ン ス 変 数 の 型 を 調 べ て ，個々のメ ソッド を 定 義 す る ソ ー ス コ ー ド の 部 分 を ，parseMethod() を呼び出すことにより，MethodParser に渡す．

譲を用い，個々のデータに対応する getter/setter を用意しても良い）．
個々の構文解析器クラスの parse*() メソッドの内部処理は，以下の通りである．

(1) 受け取った partialSrc が保持するソースコー(5) MethodParser はそれぞれのメソッドのオブドの部分を，基底クラスの protected インスタン

ジェクトコードを生成し，ClassParser に返す．

ス変数が保持するデータを参照しながら，構文解(6) ClassParser は受け取ったオブジェクトコードと，自らが生成したオブジェクトコードをあわせて，PackageParser に返す．

析を行う．

(2) 途中，そのクラスの導出クラスに渡すべき部分が出現した場合には，直ちにその部分を新た(7) 最後に，PackageParser は受け取ったオブジェ

な partialSrc オブジェクトにして導出クラスのクトコードをまとめて最終的なオブジェクトコー

parse*() を呼び出すか，または，後で導出クラス

ドとする．

を呼ぶためにその部分を記録しておく．

クラス階層間のデータの受け渡しは，オーバーラ
イドされるメソッド (parse(), parseInterface(), par-seClass(), parseMethod()，以降，これらをまとめて(3) 途中，構文エラーが検出された場合には，その構文エラーを例外として送出する．

(4) 導出クラスの parse*() の呼び出しが正常終了

6コンピュータソフトウェア

1: PARSER_BEGIN(FWJParser)
2: public class FWJParser {3: public static void main(String[] args)
throws ParseException {4:
new FWJParser(System.in).Input();
5: }
6: }
7: PARSER_END(FWJParser)
8: SKIP : {9: " " | "¥t" | "¥n" | "¥r" | "¥f"
10: }11: TOKEN : {12: < LP: "(" > | < RP: ")" >13: | < LB: "{" > | < RB: "}" >14: | < COMMA: ","> | < SEMICOLON: ";" >15: | < DOT: "." > | < EQUAL: "=" >16: | < CLASS: "class" > | < EXTENDS: "extends" >17: | < NEW: "new" > | < RETURN: "return" >18: | < SUPER: "super" > | < THIS: "this" >19: | < ID: ( <LETTER> )+ >20: | < #LETTER: ["¥u0041"-"¥u005a", "¥u005f","¥u0061"-"¥u007a" ] >21: }22: void Input() : { } { // 開始シンボル
23: ( CL() )* <EOF>
24: }25: void CL() : { } { // クラス定義
26: <CLASS> <ID> <EXTENDS> <ID>
27: <LB>

図6

( 6 )

28: ( LOOKAHEAD(2) <ID> <ID> <SEMICOLON> )*29: K() ( M() )*30: <RB>
31: }32: void K() : { } { // コンストラクタ
33: <ID> <LP> ( ParamL() )? <RP>
34: <LB>
35: <SUPER> <LP> ( ArgL() )? <RP> <SEMICOLON>
36: ( <THIS> <DOT> <ID> <EQUAL> e() <SEMICOLON> )*37: <RB>
38: }39: void ParamL() : { } { // パラメータの並び
40: <ID> <ID> ( <COMMA> <ID> <ID> )*41: }42: void ArgL() : { } { // 実引数の並び
43: e() ( LOOKAHEAD(2) <COMMA> e() )*44: }45: void M() : { } { // メソッド定義
46: <ID> <ID> <LP> ( ParamL() )? <RP>
47: <LB> <RETURN> e() <SEMICOLON> <RB>
48: }49: void e() : { } { // 式
50: a() ( LOOKAHEAD(2) ( LOOKAHEAD(2) <DOT> <ID> )+51: ( <LP> ( ArgL() )? <RP> )? )?
52: | <LP> <ID> <RP> e()
53: }54: void a() : { } { // 式の一部
55: <THIS> | <ID> | <NEW> <ID> <LP> ( ArgL() )? <RP>
56: }Featherweight Java の構文規則を示すため JavaCC で記述された従来型の構文解析器

せず，構文エラーが送出された場合には，直ちにとが可能になる．

その構文エラーを再送出するか，あるいは，（複

図 5 では，プログラミング言語の構文規則や意味規

数個の構文エラーを検出するためには）その構文

則を 4 つの部分規則に分割することを想定しているが，エラーを記録しておき，後にそれらの構文エラー

扱う文法の複雑さに応じて，さらに，MethodParserをまとめた例外を作って送出する．

を StatementParser や ExpressionParser などに分割

漸進的解析器のクラス階層は，開発者がツールのすることも考えられる．

開発に当たって，基底クラスから順に部分規則やオブ
ジェクトコード生成を実装することも意図したもの

4 例題: Featherweight Javaにもなっている．たとえば，図 5 の場合なら，Pack-

本章では，例題として，Java を簡略化した文法をageParser，InterfaceParser，ClassParser，Method-

持つ Featherweight Java [7]（以降「FWJ」）に漸進

Parser の順に開発される．従来から，プログラミン

的解析器を適用する．FWJ は元々Java の汎用型拡

グ言語の処理系の開発においては，経験的にこのよう張である GJ の形式的検証のために提案された．従っな部分規則への分割が行われることがあるが，漸進て，OOPL の特徴であるクラスやメソッドといった的解析器ではそれに加えて，部分規則のそれぞれに入れ子のスコープを持つ強く型付けされた言語であ対応するテストケースのテスト用ルーチンを，オー

りながら，その文法は少数の構文規則で構成されていバーライドされる parse*() メソッドに閉じこめるこる（FWJ のサンプルプログラムは図 2 を参照）．

とができる（4.1 で具体的な例を示す）．これにより，

図 6 に，JavaCC で記述した FWJ の字句規則およ

いったん作成されたテストケースを，構文解析器の開び構文規則を示す．これは同時に，従来の手法で実装発が進んだ後も引き続き回帰テストとして用いるこ

した構文解析器の例でもある．この構文解析器では，

( 7 )

Vol. 0 No. 0

入れ子になったスコープや前方参照の解決を一切行っていないが，構文規則が単純であるため，特に問題な
く構文解析を行うことができる．クラス名，メソッド
名，変数名は区別されることなく，識別子を意味する
終端シンボル ID（19 行目で定義されている）で受理されており，名前の衝突などの意味解析は一切行っていない（たとえば，28 行目ではインスタンス変数の宣言を「識別子 識別子 セミコロン」というトークンの並びとして受理している）．また，入力となるソー
スコード中に複数の構文エラーが含まれている場合には，最初の構文エラーを検出した時点で終了する．
以降では，FWJ の漸進的解析器を，3.2 で示した
漸進的解析器の構成とその実装順序に従って実装する．具体的には，クラスを境界として構文規則および意味規則を分割し，PackageParser と ClassParser
を作成する．本稿ではソースコードの説明に必要な部分のみを示すが，ソースコード全体は http://

sel.ist.osaka-u.ac.jp/ ~kamiya/ pparser/から入手可能である．

4.1 PackageParser の作成
図 7 の上段に，実際に作成した FWJPackageParserの (JavaCC の拡張 BNF によって記述された) 部分
規則の構文定義を示す．字句規則は図 6 と同じである．BlockLike() は，中括弧の対応を数えることに
より個々のクラスの定義に相当するソースコード部
分を切り出すための規則である．図 7 の下段に，メ
ソッド parse() および parseClass() の処理内容を示す．BlockLike() によって受理されるソースコー
ド部分が，変数 classDefs に格納されていて，それ

1983

7

Input() :( CL() ) * <EOF>
CL() :<CLASS> <ID> <EXTENDS> <ID> BlockLike()
BlockLike() :<LB>( <ID> | <LP> | <RP> | <SUPER> | <THIS>| <DOT> | <EQUAL> | <SEMICOLON> | <COMMA>| <RETURN> | <NEW> | BlockLike() )*<RB>
1: PARSER_BEGIN(FWJPackageParser)（省略）
9: public class FWJPackageParser
10: {
（省略）
21: protected HashMap classDefs;
22:
23: public final void parse() {24: try {25:
classDefs = Input();26:
for (Iterator i = classDefs.entrySet().iterator();i.hasNext(); ) {27:
Map.Entry e = (Map.Entry) i.next();
28:
MyClassCode code = (MyClassCode)e.getValue();29:parseClass(code);
30:
}
31: }
32: catch (Exception e) {33:
e.printStackTrace();
34: }
35: }
36:
37: /* FWJPackageParserのテスト用。継承クラスでオーバーライドすること */38: protected void parseClass(MyClassCode code) {39: try {40:
System.out.println("class: " + code.className);
41:
System.out.println("super: " + code.superName);
42:
MyReader reader = new MyReader(code.body);
43:
int ch;44:
while ((ch = reader.read()) > 0) {45:
System.out.print((char)ch);
46:
}
47:
System.out.println("");
48: }49: catch (Exception e) {50:
e.printStackTrace();
51: }
52: }
53: }
(以下省略)

らを引数として，protected メソッド parseClass()が呼ばれる（27 から 29 行目）．FWJPackageParser

図7

FWJPackageParserの parseClass() は，クラスのテストに用いることを目的として，切り出した個々のクラスの名前と基底4.2 ClassParser の作成

クラスの名前，クラス定義の内部を印字する（37 か

図 8 の左側に FWJClassParser の部分規則の構文

ら 52 行目）．次に作成する ClassParser では，この定義を示す．字句規則に新しい種類の終端シンボル

メソッドがオーバーライドされ，クラス定義の解析を

TYPEID が導入されていることに注意する．TYPEID は行うルーチンに置き換えられる．

クラスの名前を表す識別子であり，FWJClassParser
が構文解析を始める前に FWJPackageParser によって検出されていたすべてのクラス名が TYPEID とし8

コンピュータソフトウェア

Input() :<LB>( LOOKAHEAD(2) V() )*K() ( M() )*
<RB>
V() :
<TYPEID> <ID> <SEMICOLON>
K() :<TYPEID> <LP> ( ParamL() )? <RP>
BlockLike()
ParamL() :<TYPEID> <ID>
( <COMMA> <TYPEID> <ID> )*M() :( <TYPEID> | <VOID> ) <ID>
<LP> ( ParamL() )? <RP>
BlockLike()
BlockLike() :<LB>( <ID> | <TYPEID> | <LP> | <RP>
| <SUPER> | <THIS>| <DOT> | <EQUAL>| <SEMICOLON> | <COMMA>| <RETURN> | <NEW> | BlockLike() )*
<RB>

( 8 )

1: PARSER_BEGIN(FWJClassParser)（省略）
9: public class FWJClassParser
10: {11: public static void main(String[] args) {12: try {13:
FWJPackageParser parser = new FWJPackageParser(System.in) {14:
private FWJClassParser parser;
15:
protected void parseClass(MyClassCode code) {
16:
try {
17:
TypeRecognizeReader reader= new TypeRecognizeReader(code.body);（省略）23:
MyClassData classData = parser.Input();
24:
parser.parseMethod(classData.ctor);25:
for (Iterator i = classData.methods.entrySet().iterator(); i.hasNext(); ) {26:
Map.Entry e = (Map.Entry) i.next();
27:
MyMethodCode methodCode = (MyMethodCode)e.getValue();
28:
parser.parseMethod(methodCode);
29:
}
30:
}
31:
catch (ParseException e) {32:
System.err.println("error: in method " + code.className + ": "+ e.toString());
33:
}
(省略)
37:
}
38:
};
39:
parser.parse();40: }41: catch (Exception e) {42:
e.printStackTrace();
43: }
44: }
(以下省略)

図8

FWJClassParserて受理される．図 8 の右側に，FWJClassParser のある．この例には，型とそれ以外の名前とを区別す

parserClass() メソッドの内容を示す（3.2 の説明

る構文規則を用いた場合には構文エラーとして検出とは異なり，FWJClassParser は FWJPackagePaser

される 2 つのエラーが含まれている．出力例では期の導出クラスになっていない．理由は後述）．17 行

待通り 2 つのエラーが検出されていることがわかる

目の TypeRecognizeReader は，parseClass() の引（図 6 の構文解析器を用いた場合，これらのエラーは数として受け取ったソースコードを変形するフィル

検出されない）．実際には，Java の言語仕様はクラタであり，型を表す識別子を修飾して，字句解析器

ス名とメソッド名前が同じであることを許すため，コに TYPEID として受理させる役目を持つ．24 から 29

ンパイラ javac [10] は後者（12 行目）を構文エラーと行目で，K() および M() によって切り出されたコン

しないが，もう一つの独立に実装された Eclipse のコ

ストラクタやメソッド定義のソースコード部分を，ンパイラ [12] は警告を出力する．

parseMethod() に渡している．31 から 33 行目は構
文エラーを処理する部分であり，parseClass() が構
文エラーを送出したとき，それを標準エラー出力に印字して処理を続行する処理を記述している．

実装を通じて判明した技術的な問題点としては以下のものがある．

• 3.2 の 説 明 と は 異 な り，FWJClassParser を
FWJPackageParser の導出クラスにせず，代わ

図 9 はこの解析器をテストするために作成されたりに，匿名内部クラスを用いて parseClass() を

エラーを含む入力の例，および，この解析器の出力でオーバーライドしている．これは，両クラスを

( 9 )

Vol. 0 No. 0

1983

9

返し型開発，テスト駆動型開発とも親和性がある．
1: class A extends Object {2: C() { super(); }3: }4: class Pair extends Object {5: Object fst;
6: Object snd;
7: Pair(Object fst, Object snd) {8: super();
9: this.fst = fst;
10: this.snd = snd;
11: }12: Pair Pair(Object newfst) {13: return new Pair(newfst, this.snd);
14: }
15: }
error: in method Pair:classparser.ParseException:
Encountered "type:Pair" at line 1,
column 151.
Was expecting:<ID> ...
error: in method A:
classparser.ParseException:
Encountered "C" at line 1, column 3.
Was expecting:<TYPEID> ...

漸進的解析器は再帰下降構文解析器によっても開発可能であるが，従来のコンパイラ・コンパイラを用いても開発できることを示すために，4 章の例題ではJavaCC を用いて Featherweight Java の漸進的解析器を作成した．開発の途中で判明した実装上の問題
は，コンパイラ・コンパイラをその開発者が想定しない方法で用いたため生じた技術的な問題であり，いずれ解決するものと楽観している．
同例題では，本質的に曖昧な名前（例えば，クラスとメソッドが同じ名前を持つ場合など）は，漸進的解析器ではうまく扱えないことも判明した．ただし，このような状況は Java 言語の名前付け規約に従う限り
ほとんど発生しない [6] し，また，構文エラーにはならないまでもコンパイラによっては警告が出力されるものである．なお，C/C++においては，型とメンバが同じ名前を持つ場合等にも，このような曖昧な名前
が生じる．

図9

エラーを含む入力例と FWJClassParser の出力

漸進的解析器の開発では，構文規則と意味規則の全体が用意されておらず，部分規則に対応する構文解析

JavaCC によって生成した場合，両クラスに継承器の開発を通じて段階的に構文規則を生成していく関係があると名前の衝突が起きるためである．

ことを想定している．課題としては，4 章の例題のよ• 図 9 のエラーメッセージの中で不正な行番号がうに構文規則と意味規則の全体が与えられていると表示されている．これは，構文解析器によって切きに，それを部分規則に分割する作業をサポートするり出された部分的なソースコードの特定の行の，手法の開発があげられる．特に，前段の構文解析器で元のソースコードでの行番号を調べる簡便な手は識別子として受理されていたものが，後段の構文解段が見あたらなかったためである．

析器では型名や変数名，メソッド名として受理される部分では，Data Reification [15] 等の技術を応用する

5 まとめと課題

ことが考えられる．

本稿で提案した構文および意味解析器の新しい設計「漸進的解析器」により，OOPL の入れ子になっ6 謝辞たスコープルールをクラス階層によって実現し，構文

本論文の匿名査読者の方々に，心より感謝いたしま

エラーからの回復を構造化例外によって処理することす．ご指摘により，本論文に含まれていた重大な誤りが可能になる．さらに，シンボルテーブルなどの手段や術語の混乱を修正することができました．

を用いることなく特定の識別子が型であるかを字句解析器が判定することが可能になり，識別子が型であ

参考文献

るか否かで異なった構文であると見なす構文規則を利[ 1 ] ANTLR Home Page, http://www.antlr.org/.
[ 2 ] Appel, A. and Palsberg, J., Modern Compiler
Implementation in Java, 2nd Ed., Cambridge University Press (2002).
[ 3 ] Bison 1.35

用することができる．漸進的解析器の設計は，これらの問題を，オブジェクト指向パラダイムの枠組みの中で見通しよく解決するものであり，また同時に，繰り10コンピュータソフトウェア

http://www.gnu.org/software/bison/manual/, Free
Software Foundation.
[ 4 ] Boost.Spirit Home,
http://spirit.sourceforge.net/.
[ 5 ] Gosling, J., Joy, B., Steele, G., Java Language
Specification, First Edition, Chapter 19, LALR(1)Grammar, Taken from http://java.sun.com/docs/
books/jls/first edition/html/19.doc.html[ 6 ] ゴスリン, G., ジョイ, B., スティール, G., ブラーハ,G.(著), 村上雅章 (訳), Java 言語仕様 第 2 版, ピアソン・
エデュケーション (2000), Gosling, J., Joy, B., Steele,G., Java Language Specification, 2nd Ed., Pearson
Education (2000).
[ 7 ] Igarashi, A., Pierce, B., and Wadler, P.: Featherweight Java: A Minimal Core Calculus for Javaand GJ, ACM Transactions on Programming Languages and Systems, 23(3), pp. 396-450 (2001).
[ 8 ] 泉田聡介, 植田泰士, 神谷年洋, 楠本真二, 井上克郎: ソフトウェア保守のための類似コード片検索ツー
ル, 電子情報通信学会論文誌, vol. J86-D-I, no. 12, pp.
906-908 (2003).
[ 9 ] J2SE 1.5, http://java.sun.com/j2se/1.5/.
[10] Java Technology, http://java.sun.com/.
[11] JavaCC Home, https://javacc.dev.java.net/.

( 10 )[12] JDT, Eclipse Project,
http://www.eclipse.org/jdt/.
[13] Levine, J., Mason, T., and Brown, D., Lex &Yacc, 2nd Ed., O’Reilly & Associates (1992).
[14] Ohst, D., and Kelter, U. : A Fine-grained Version and Configuration Model in Analysis and Design, Proceedings of the IEEE 18th International
Conference on Software Maintenance (ICSM2002),
pp. 521-527 (2002).
[15] Ozaki, H., Ban, S., and Gondow, K.: An Environment for Evolutionary Prototyping Java Programs Based on Abstract Interpretation, Proceedings of the IEEE 5th Asia Pacific Structural Engineering & Construction Conference (APSEC2003),
pp. 362-370 (2003).
[16] 都倉信樹, オートマトンと形式言語, 昭晃堂 (1995).
[17] SableCC, http://www.sablecc.org/.
[18] Stroustrup, B. 著, 株式会社ロングテール, 長尾高弘
訳, プログラミング言語 C++ 第３版, アジソン・ウェスレ
イ (1998). Stroustrup, B., The C++ Programming
Language 3rd Ed., Addison-Wesley, (1997).
[19] 吉田敦, 山本一郎, 阿草滋: 意味を考慮した差分抽出
ツール, 情報処理学会論文誌, vol. 38, no. 6, pp.11631171 (1997).