![閉じる [x]](http://dw1.s81c.com/i/c.gif){kind=small}
このシリーズの第 2 回では、CDT エディターはキーが押される毎にどのようにしてテキスト表現を更新するのかについて説明しました。しかし、CDT エディターは単純にキーワードを特定の色やフォントで表示するだけではなく、それをはるかに上回ることをしています。つまりコードの構造を分析し、すべての関数やステートメント、変数などを追跡するのです。
この分析は、構文解析と呼ばれる巨大なテーマであり、コンピューター科学者達に新たな研究の道を与え続けています。ここでは構文解析の背景にある理論の一部を簡単に説明しますが、焦点を当てるのは CDT での動作機構です。私の目標は、皆さんが CDT パーサーを改善、あるいは修正しようとする場合のために、どのクラスやメソッドを変更すればよいのか、どう変更するのかを理解できるだけの十分な情報を提供することです。
私はこうしたクラスを、BBCDT (Bare Bones C/C++ Development Tool) に追加しました。ですから皆さんは、構文解析がどのように行われるかを、例を通して見ることができます。こうした新しいクラスの大部分は CDT の構文解析プロセスに関係するため、org.bbcdt.dworks.core プラグインの中に入っています (具体的には、org.bbcdt.dworks.core.parser パッケージと、そのサブパッケージの中です)。
CDT は、実際には 2 つのパーサーを持っていることに注意することが重要です。つまり PDOM (Persisted Document Object Model ) を使うものと、使わないものの 2 つです。どちらも現在 (V3.1) の CDT には重要ですが、Doug Schaefer によると、PDOM パーサーが徐々に 2 番目のパーサーの役割も負うようになるだろうとのことです。PDOM パーサーは第 4 回で説明する予定ですが、2 番目のパーサーの方が理解しやすいため、ここではそれを取り上げます。具体的には、Document が更新を受け取った時から新しい AST (Abstract Syntax Tree) が作成されるまでの間に、CDT の中で何が起こるのかについて説明します。このプロセスは、4 つの部分に分けると理解しやすくなります。
- Reconciler と ReconcilingStrategy
- パーサーはどのようにして Document からイベントを受け取るか
- パーサーの作成
- パーサーはどのように作成され、初期化されるか
- 構文解析プロセス
- パーサーはどのように WorkingCopy テキストの構造を分析するのか
- AST
- パーサーのソースコード・モデルと、それにアクセスする方法
Reconciler とその ReconcilingStrategy
第 2 回では、編集される文書の変化に対応して PresentationReconciler がテキストのスタイリング・プロセスを開始する様子を説明しました。これと同様に、CDT の構文解析は、同じタイプのイベントをリッスンする、Reconciler オブジェクトによって開始されます。この 2 つのクラスを間違えないことが重要です。PresentationReconciler クラスは、キーが押される度にテキストの表示を更新します。またReconciler クラスはデーモン・スレッドで実行され、ユーザー・インターフェースを占有することなく文書を構文解析します。Eclipse を使う際に、構文の色分けがエラー検出よりもずっと高速に行われるのは、このためです。
Reconciler のスレッドは、Reconciler のリスナーが新しい Document を検出すると開始します。ユーザーがその Document を更新すると、そのスレッドは CReconcilingStrategy に対してリコンサイルを開始するように命令します。CDT の Reconciler は MonoReconciler です。つまり 1 つの戦略しか持てません。また、この Reconciler はインクリメンタルではありません。これは、Document に変更が発生すると、この Reconciler の戦略は Document 全体に対して行われることを意味します。
CReconcilingStrategy は WorkingCopy にアクセスし、WorkingCopyInfo オブジェクトの中にある WorkingCopy の子を整理するように命令します (WorkingCopyInfo オブジェクトは CDT モデル の他の info オブジェクトと同じように機能します)。しかし WorkingCopy には、まだ子がありません。つまり WorkingCopy は、保存されていない、構造を持たないテキストのバッファーにすぎません。この混乱に秩序をもたらすために、WorkingCopy は自分の parse() メソッドをコールします。これでもまだ構文解析は始まりませんが、これによってパーサーの作成と初期化のプロセスが開始されるのです。
WorkingCopy は、構文解析プロセスを管理する CModelBuilder オブジェクトを構築することによってパーサーの作成を開始します。このオブジェクトは、構文解析される言語をプロジェクトの性質から判断し、WorkingCopy のテキストから文字バッファーを作ります。また、Scanner2 オブジェクトを作るために使用する一連のオブジェクト (IProblemRequestor と IScannerInfoProvider、CodeReader、SourceElementRequestor そして ParserLogService) を、ParserFactory.createScanner() メソッドをコールすることで作成します。このメソッドはバッファーの中の文字群を分析し、パーサーにトークンを提供します。
スキャナーが作られると、CModelBuilder は ParserFactory.createParser() メソッドをコールすることで Parser を作ります。このメソッドは ProblemRequestor に対して、エラーが発生したらエディターのアノテーションの更新を開始するように命令します。そして、Parser の parse() メソッドをコールします。
ここから、楽しいことが始まります。その前に、少し寄り道して構文解析の理論を簡単に説明しましょう。
ここで、「Matt likes pizza」という入力文を考えてみてください。皆さんは個々の単語は知っているかもしれませんが、もし主語 - 動詞 - 目的語という構文がわからないと、文としての意味は理解できません。この文は、入力の要素を抽象構造 (「Matt」= 主語、「likes」= 動詞、「pizza」= 目的語) と一致比較した時に初めて意味をなすのです。もちろん、構文は他にも数多くあり、言語も他に数多くあります。ある言語において、適切な文をどのように構成するかを規定した規則全体を、その言語の文法と呼びます。
プログラミング言語の場合、文法の中には、形式の整ったコード単位 (つまりソースファイル) のすべてが一致すべき抽象モデルが含まれています。この一致比較チェックの最初のステップは、スキャニングまたは字句解析と呼ばれます。スキャナーは、バッファーの中の個々の文字を読み取り、パーサーに理解できるシンボル (キーワードや演算子、言語特有の区切りなどであり、トークンと呼ばれます) を返します。例えば、C のスキャナーは c、o、n、s、t という文字群を読み込むと、const というキーワードを表す 1 つのトークン・オブジェクトを返します。パーサーには空白やコメントは無関係なので、スキャナーはそれらを無視します。
一致比較プロセスの 2 番目のステップは、構文解析です。ここでパーサーは、トークンの組み合わせをテストし、パーサーの文法の抽象要素と比較してどのようであるかを見ます。これは一般的に、上記の主語 - 動詞 - 目的語のような例よりもずっと複雑です。例えば、あるステートメントが「enum」(列挙の宣言) に対応するトークンで始まったとすると、CDT パーサーは、そのステートメントを、自分が持っている enum ステートメントの抽象モデルと一致比較しようとします。つまり CDT パーサーは、ENUM トークンの後にオプションの name がないかを探し、次に L_BRACE トークンと R_BRACE トークンの間に enumerated_list がないかを探し、そして最後の enumerated_list を探します。斜字体にした各用語は、文法の中にある他の抽象要素を指しています。
CDT パーサーを含め、多くのパーサーでは、単純な整形式性チェック以上のことをします。パーサーは入力の構文解析が済むと、その構文情報を、分析や索引付け、検索などに適した形式で保存します。通常、この形式は、AST と呼ばれるツリー形式です。例えば、developerWorks の記事をトークン化し、それを英語という言語のパーサーに送ると、図 1 のようなツリー構造が作られるでしょう。
図 1. AST の例
これを見るとわかるように、ツリーの中の要素は、最上部 (developerWorks Article) では一般的なものですが、下のノードになるほど、より具体的になります。もっとスペースに余裕があれば、一番下のノードが、文や、最終的には特定の単語を含んでいる様子も見せられたでしょう。プログラミング言語の場合、こうした端末ノードには、個々のキーワードや演算子、変数などが含まれます。AST を検索して関数や変数名を見つける方が、文書全体を構文解析し直すよりもずっと容易です。では次に、CDT パーサーがどのように AST を生成するのか、また独自のコードを使って AST をトラバースするための方法について説明します。
CDT の文法ファイルは見たことはありませんが、その抽象モデル要素は、Parser クラスのメソッドから、そしてこれらのメソッドの前にあるコメントから判断することができます。このクラスは org.dworks.bbcdt.internal.core.parser パッケージの中にあります。先ほど触れたように、最初の構文解析メソッドは、translationUnit() です。これは、ソースファイル全体を表現するのは TranslationUnit 要素だからです (先ほどの例の中で、Article 要素が記事全体を表現するのと同じです)。
translationUnit() メソッドの前のコメントの中に、不可解なステートメントがあります。
translationUnit : (declaration)* |
EBNF (Extended Backus Naur Form) に慣れている人であれば、このルールが、TranslationUnit 要素は任意の数の Declaration 要素から構成される、と言っていることがわかるでしょう。こうしたコメントだけでは CDT の文法は完全にわかりませんが、Parser クラスを使おうとする場合や修正しようとする場合には便利です。
Declaration 要素は TranslationUnit の直下にあるため、translationUnit() メソッドは declaration() メソッドをコールします。EBNF ルールでは、宣言の形式は次の 6 つのうちの 1 つです。
- アセンブリー・ステートメント
- asm トークンの後に ASMDefinition 要素が続く
- 名前空間ステートメント
- namespace トークンの後に NamespaceDefinition 要素が続く
- Using ステートメント
- using トークンの後に UsingDeclaration 要素が続く
- Template ステートメント
- template トークンまたは export トークンの後に TemplateDeclaration 要素が続く
- リンクステートメント
- extern トークンの後に LinkageSpecification 要素が続く
- 単純ステートメント
- SimpleDeclaration 要素
declaration() メソッドは、ある宣言の型を判断するために switch ステートメントを使います (switch ステートメントの実行は、スキャナーの、次のトークンの型で決まります)。各トークンは IToken を実装し、その型 (1 から 141 までの間の int) や、スキャンされるファイル、スキャンされる Document の中でのオフセットと長さなどを保存します。
もし宣言が最初の 5 つのカテゴリーのどれにも当てはまらない場合には、その宣言の性質に関する推測と共に simpleDeclaration() メソッドがコールされます。最初の推測では、この宣言をコンストラクターと見なしますが、もしこのメソッドが BackTrackException をスローすると、次の推測では関数宣言と見なします。これも失敗すると、このメソッドはもう 1 度コールされ、今度は変数宣言と推測します。もしこれでも、また別の例外がスローされると、このメソッドは null を返します。
パーサーは、モデル要素と一致比較するためにメソッドをコールし続けますが、その分析の深さは、分析のモードに依存します。構文解析には 5 つのモードがあります。
- QUICK_PARSE
- 関数、またはインクルード・ファイルの内部は構文解析しません。
- STRUCTURAL_PARSE
- 関数の内部は構文解析しませんが、インクルード・ファイルの内部は構文解析します。
- COMPLETE_PARSE
- 関数とインクルード・ファイルの内部を構文解析します。
- COMPLETION_PARSE
- 関数とインクルード・ファイルの内部を構文解析し、オフセットで停止し、シンボル・クエリー参照を最適化します。
- SELECTION_PARSE
- 関数とインクルード・ファイルの内部を構文解析し、オフセットで停止し、選択された範囲のセマンティック (意味) 情報を提供します。
また、構文解析中に Parser がどんなコールバック・オブジェクトを使って情報を保存するのかも、モードによって決まります。QUICK_PARSE モードでは、QuickParseCallback がマクロや関数、宣言、発生するエラーなどを追跡します。それ以外のすべてのモードでは、StructuralParseCallback が、Parser の現在のスコープや変数、namespace ステートメント、enum 宣言といった追加情報を保存します。しかし追加の分析には時間も余計にかかるため、Parser のデフォルト・モードは QUICK_PARSE になっています。
どのコールバック・オブジェクトを使う場合であっても、このオブジェクトによって運ばれる最も重要な情報は、ASTCompilationUnit です。この重要性について、次に説明します。
最初の構文解析メソッド、translationUnit() は、ASTCompilationUnit オブジェクトを作ることで動作を開始します。このオブジェクトは AST の最上位ノードであるばかりではなく、その下にあるすべてのノードのコンテナーでもあります。Parser はソースの中に宣言があることを認識すると、ASTDeclaration のサブクラスを、ASTCompilationUnit の宣言の List に追加します。もしソースファイルの中で最初の宣言が typedef の場合は、ASTCompilationUnit の List の最初の要素は ASTTypedefDeclaration になります。
同様に、各 ASTDeclaration オブジェクトは、その宣言を構成する AST オブジェクトを保存します。例えば ASTFunction で表現される関数宣言は、その宣言の戻り型やパラメーター、その宣言に含まれるすべての関数、などを表現する AST オブジェクトを含んでいます。Parser が構文解析を終えると、ASTCompilationUnit は、そのファイルの構造を表現する完全な AST を含んでいることになります。こうなると、ファイル中の特定の要素を見つけるためには、単純にツリーをトラバースしさえすればよくなります。
Eclipse の中で BBCDT プロジェクトを開くと、(特に org.dworks.bbcdt.core プラグイン・プロジェクトの中には) さらに大量のコードが見えるはずです。こうした新しいクラスの多くは構文解析の設定や実行に必要なものですが、大部分は C/C++ ソースファイルまたは C/C++ の AST の要素を表現しています。
org.dworks.bbcdt.ui プラグインにも、新しいクラスがあります。その大部分はリコンサイル・プロセスのためのものですが、org.dworks.bbcdt.ui.action パッケージの ASTAction クラスは IEditorActionDelegate インターフェースを実装しています。BBCDT エディターが表示されていると、このインターフェースも表示されます。このインターフェースのツールバーをクリックすると、IASTCompilationUnit にアクセスして、宣言オブジェクト群に対する繰り返しが行われます。宣言オブジェクトのどれかが関数または変数を宣言する場合、あるいは namespace や using、extern などで始まる場合には、ASTAction は (各宣言の型と、その宣言型に関する特定の情報とをリストした) ウィンドウを表示します。リスト 1 は、これを実現するコードを示しています。
リスト 1. CDT AST の中の宣言にアクセスする
IASTCompilationUnit unit = CCorePlugin.getCompilationUnit();
Iterator iter = unit.getDeclarations();
while(iter.hasNext()) {
IASTDeclaration decl = (IASTDeclaration)iter.next();
if (decl instanceof IASTFunction)
output += "Function declaration: " +
((IASTFunction)decl).getName();
else if (decl instanceof IASTLinkageSpecification)
output += "Linkage declaration: " +
((IASTLinkageSpecification)decl).getLinkageString();
else if (decl instanceof IASTNamespaceDefinition)
output += "Namespace definition: " +
((IASTNamespaceDefinition)decl).getName();
else if (decl instanceof IASTUsingDeclaration)
output += "Using declaration: " +
((IASTUsingDeclaration)decl).getName();
else if (decl instanceof IASTVariable)
output += "Variable declaration: " +
((IASTVariable)decl).getName();
|
CDT のどこを探しても、このコードは見つかりません。IASTCompilationUnit にアクセスし、トラバースしやすいように、私が適当に作ったのです。ASTAction を変更すると、ノード群を検索することができ、完全なツリーを作ることができます。図 2 は、ASTAction ボタンをクリックした後の BBCDT の出力を示しています。
図 2. BBCDT の AST を分析した出力
この記事では、CDT のParser がエディターの中のテキストの変更にどう反応し、また C/C++ 要素を持つ AST をどのように作成するのかについて説明しました。そして構文解析についての一般的な理論も簡単に説明しました。しかし構文解析には、ここで説明したよりもはるかに多くの内容があります。構文解析に関する素晴らしいオンライン・テキストを「参考文献」にあげましたので、詳しくはそちらを参照してください。
ここで説明した Parser は目的にかなうものですが、欠点も持っています。動作は遅く、1 度に 1 つのソースファイルしか構文解析できないという制限があります。第 4 回で説明するように、CDT は、より強力で複雑な別のパーサーを既に組み込んでいます。
| 内容 | ファイル名 | サイズ | ダウンロード形式 |
|---|---|---|---|
| Sample plug-in files | os-ecl-cdt3-BBCDT_Plugins.zip | 955KB | HTTP |
| Sample plug-in files | os-ecl-cdt3-BBCDT_Projects.zip | 2MB | HTTP |
学ぶために
- アムステルダム大学 (University of Amsterdam) による、構文解析に関するオンライン・テキスト、「Parsing Techniques -- A Practical Guide」を読んでください。
- Eclipse.org で Eclipse CDT について調べてみてください。
- CDT 開発チームのリーダー、Doug Schaefer による素晴らしいブログを読んでください。
-
Eclipse Foundation について、そしてその数多くのプロジェクトについて学んでください。
- Eclipse プラットフォームへの素晴らしい入門記事として、「Eclipse Platform入門」を読んでください。
- IBM developerWorks の Eclipse project resources を利用して、皆さんの Eclipse スキルを磨いてください。
- developerWorks には他にも Eclipse に関連する資料が豊富に用意されています。
- developerWorks の Open source ゾーンを訪れてください。オープンソース技術を使った開発や、IBM 製品でオープンソース技術を使用するためのハウ・ツー情報やツール、プロジェクトの更新情報など、豊富な情報が用意されています。
-
developerWorks technical events and webcasts で最新情報を入手してください。
製品や技術を入手するために
- Eclipse.org から Eclipse CDT をダウンロードしてください。
- IBM alphaWorks に用意された、最新の Eclipse technology downloads を調べてみてください。
- 皆さんの次期オープンソース開発プロジェクトを、IBM trial software を使って革新してください。ダウンロード、あるいは DVD で入手することができます。
議論するために
-
Eclipse newsgroups は、Eclipse を利用し、拡張することに関心を持つ人達のために、豊富なリソースを提供しています。
-
developerWorks blogs から developerWorks のコミュニティーに加わってください。
