レベル: 初級 Benoit Marchal (bmarchal@pineapplesoft.com), Consultant, Pineapplesoft
2001年 11月 01日 Benoît Marchal氏は、今月、2番目の実用的なXML (Working XML) プロジェクトを立ち上げます。HC (Handler Compilerの略) という名前の新しいプロジェクトでは、XPathのリストに対するSAXのContentHandler を自動的に生成することで、イベント・ベースのXMLの構文解析から面倒な作業をなくします。今回のコラムでは、このJavaプロジェクトに対する要件を説明し、ContentHandler から状態遷移図までの全体的な設計を分析します。
実用的なXML の毎月のコラムにおいて、著者は、オープン・ソース・プロジェクトの進ちょくをXML開発者向けに解説します。話題は、設計に関する決定からコーディングの課題にまで及びます。
先月、私は、XSLTベースのWeb公開管理アプリケーションについてのXMプロジェクトの作業を中断し、今後2、3か月はフィードバックを集めることにしました。既に、何人かの読者の方から、XMに関する経験についてのお話しや、バグの報告や、改善の指摘などをいただいています。わざわざ時間を割いて有益な情報をお寄せいただいた方には、心から感謝します。
さて、今回は新しいプロジェクトについてのお話です。実用的なXML コラムでの2番目のプロジェクトとして、SAXのContentHandler の作成を自動化したいと思います。SAXのことをよく知らない方は、「XML by Example, 2nd Edition」からの抜粋である「強力なAPI、SAX」を参照してください。
SAXは、構文指向のAPIとして作られました。アプリケーションでは、SAXのイベントを利用してドキュメントのフローをlistenし、多くの場合、適切な応答を生成します。SAXは、XMLドキュメントの変換およびその他の操作に最適です。SAXは、単純かつ効率の良いインターフェースです。
ただし、SAXはプログラマーの使いやすさではなく機能を優先して作られたので、イベント・ハンドラーを記述する作業は面倒です。SAXではプリプロセスはほとんど行われないので、プログラマーが多くの低レベル処理を作成する必要があります。特に、SAXのイベント・ハンドラーのかなりの部分は、パーサーの処理がドキュメントのどこまで進んだのかを追跡するためのものです。状態追跡処理のコードは、反復が多く、エラーが発生しやすく、一般に、作成するのも保守するのも骨が折れます。
このコラムで紹介するHCつまりHandler Compilerは、コンテンツ追跡用のコードの作成を簡単にしてくれるはずです。特に、HCを使えば、SAXのContentHandler を自動的に作成できるようになります。
上位レベルの仕様
HCの内容をよく理解してもらうために、まずリスト1 を見てください。リスト1で紹介されているContentHandlerは、simpara 要素の中で使われているulink 要素の数を数えるだけの簡単なものです。ドキュメント内の他の場所、たとえばarticleinfo 要素のような場所で使われているulink は無視します。
特別な要素が見つかったらカウンターを増分するだけですから、これ以上簡単な処理はないでしょう。SAXCountHandler の長さは39行ですが、そのうちカウンターに直接関係するのは12行だけです。コードの大部分は、パーサーの状態を追跡するためのものです。
リスト1. SAXCountHandler.java
import java.util.*;
import org.xml.sax.*;
import org.xml.sax.helpers.*;
public class SAXCountHandler
extends DefaultHandler
{
private int count;
private Stack stack;
public void startDocument()
{
count = 0;
stack = new Stack();
}
public void startElement(String uri,
String lName,
String qName,
Attributes atts)
{
if(!uri.equals("http://www.psol.com/2001/docbook"))
return;
if(lName.equals("ulink") &&
"simpara".equals(stack.peek()))
count++;
stack.push(lName);
}
public void endElement(String uri,
String lName,
String qName)
{
if(!uri.equals("http://www.psol.com/2001/docbook"))
return;
stack.pop();
}
public int getCount()
{
return count;
}
}
|
リスト1 を私がお勧めする方法で書いたリスト2 と比べてみてください。HCCountHandler クラスはSAXCounterHandler の半分の大きさで、コードの大部分はカウンターの操作に関係しています。実は、HCCountHandler には状態を追跡するコードはありません。代わりに、特殊な@xpath を使って、どのメソッドをいつ呼び出す必要があるのかを示しています。
HCコンパイラーはリスト2のプリプロセスを行う際に、@xpath コメントを使って、状態の追跡を行うコードを自動的に生成します。ここで重要なのは自動的 という言葉です。つまり、HCを使用しても状態追跡処理のコードが不要になることはありませんが、HCがプログラマーの代わりにコードを作成してくれるということです。
リスト2. HCCountHandler.java
/**
* @xmlns http://www.psol.com/2001/docbook
*/
public class HCCountHandler
implements org.ananas.hc.HCHandler
{
private int count;
/**
* @xpath /
*/
public void init()
{
count = 0;
}
/**
* @xpath simpara/ulink
*/
public void increment()
{
count++;
}
public int getCount()
{
return count;
}
}
|
分析
これで目標が理解できたと思いますので、それを実現する方法を見ていきましょう。
HCはコンパイラーです。つまり、特殊なコメントで修飾されたJavaソース・コード・ファイルを入力として受け取って、クラスをきちんと動作するSAXContentHandler に変換するために必要となるものを生成します。そこで、HCは何を生成する必要があり、どのような方法で生成するか、という2つの側面を分析する必要があります。次のセクションでは、第1の疑問に対する答え、すなわちコードについて検討します。その次のセクションでは、第2の疑問に対する答え、すなわちコンパイラーそのものについて検討します。
わかりやすくするために、少なくとも最初のリリースでは、HCの対象範囲を条件のないXPathに限定します。たとえば、次の記述はリリース1で使用できます。
/
/article/articleinfo/title
simpara/ulink
|
しかし、次の記述はリリース1ではまだ使用できません。
simpara[ulink/@href='index.xml']
|
条件に多くの有効な使い道があることは確かですが、条件を除外して単純化することで、XPathの認識と同時にイベントを発生させることができます。条件が指定されていると、条件が満たされるまでイベントを保存しておかなければなりません。今回は、いつもと同じように、実用的なXML コラムの方針として、コラムを進めながらコードを開発し、プロジェクトが発展する様子をお見せします。したがって、条件に対する制約については、もっと後のバージョンのHCで採り上げることにします。
生成されるコード
図1は、生成されるコードのクラス・モデルを表しています。HCは、ContentHandler インターフェースを実装する標準のXPathHandler クラスを提示します。XPathHandler は、特に、面倒な状態の追跡を行ってくれます。リスト2の例では、XPathHandler はアプリケーション・ハンドラーHCCountHandler を呼び出します。
図1. 生成のクラス・モデル
このアーキテクチャーは、標準のプロキシー・パターンです。XPathHandler クラスは、SAXで定義されている下位レベルの汎用イベントと、プログラマーが定義する上位レベルのアプリケーション固有イベントの間で、プロキシーとして動作します。このようにして、HCは状態を管理する処理からプログラマーを解放してくれます。
最終的には、次のようなコードを記述できるようにしたいと思います。
HCCountHandler counter = new HCCountHandler();
XPathHandler handler = new XPathHandler(counter);
reader.setContentHandler(handler);
reader.parse(uri); |
明らかに、XPathHandler がこのような魔法を実現するためには、アプリケーション・ハンドラーの記述が必要です。コンパイラーは、XPathHandler が必要とする情報を使って、テーブル ・クラスと呼ばれる特別なクラスを生成します。テーブル・クラスには、いくつかのテーブルと、アプリケーション固有の呼び出しを実行するためのいくつかのメソッドが含まれています。
テーブル・クラスの名前は自動的に生成され、基本的にプログラマーからは見えないので、テーブル・クラスの名前は重要ではありません。コンパイラーが、名前の衝突を防ぐのに十分な長くてユニークな接尾辞 (__org_ananas_hc_tables) を付加してくれます。
コンパイラーのフロントエンド
コンパイラーは、テーブル・クラスを自動的に作成します。コンパイラーの標準的な設計では、この処理は、入力ファイルを読み込んでデコードするフロントエンドと、コード (またはこの場合はテーブル・クラス) を生成するバックエンドという2つのモジュールに分かれます。
HCもこの標準に従っていますが、ちょっとしたトリックを使ってフロントエンドの記述を簡略化しています。リスト2をもう一度見てもらうとわかるように、XPathをJavadocのコメントとして記述してあります。この方法は、2つの点で便利です。まず、使い慣れた構文であるということです。さらに、docletメカニズムを通して自由なフロントエンドが提供されることです。
docletは、Javadocを拡張するメカニズムとしてJDK 1.2で採用されました。簡単に言うと、docletとは、JavadocがJavaクラスの解析結果を渡す先のJavaクラスです。docletは、もともと、ドキュメントのプレゼンテーションに対する制御を強化するために設計されたものです。たとえば、標準のHTML出力の代わりにPDFドキュメントを生成するdocletを作成できます。
さらに、Javadocは、非常に多くの情報を提供します。すなわち、クラス名、クラスが含まれるパッケージ、メソッドのリスト、メソッドのパラメーター、そして勿論コメント自体もです。そのため、Javadocをフロントエンドとして使用することは簡単です。足りないのはメソッドの実装だけですが、HCではこれは必要ありません。
docletはcom.sun.javadoc パッケージに導入されています。主要なクラスは、解析ツリーを含むRootDoc です。クラス自体はClassDoc として、またメソッドはMethodDoc として表され、JavadocのコメントはTag クラスのインスタンスです。そのため、@xpath コメントは、最終的に、MethodDoc オブジェクトに付加されたTag オブジェクトとして返されます。
JavadocはXPathを解析しないのでXPathパーサーをフロントエンドに追加する必要がありますが、XPathはJavaクラスより簡単に解析できます。
コンパイラーのバックエンド
バックエンドは、このプロジェクトの中で最も興味深い部分です。バックエンドでは、パス情報を収集してテーブル・クラスを作成します。現時点ではまだこのアルゴリズムを細部までは完成させませんが、図2に示すような状態遷移図 を使用する予定です。状態遷移図とは、本質的に、XPathを認識する方法を制御するフローチャートです。円は状態 を表しています。状態は、有向枝 と呼ばれる矢印で接続されています。有向枝は、ある状態から別の状態への遷移を発生させる入力要素を示しています。
図2. simpara/ulinkに対する状態遷移図
したがって、状態遷移図は特定のXPathを認識する方法を表しています。状態は、ドキュメントの中でパーサーが読み込んでいる場所を追跡するために必要な情報を保持しています。有向枝は、ある状態から次の状態への進行を記録します。
太い線で示された状態は、XPathの終了を示す受理 状態です。普通、処理が受理状態に達すると、特定のXPathに対するアプリケーション・ハンドラーを呼び出す必要があります。明らかに、実際の状態遷移図は、認識しようとするXPathごとに1つずつ、複数の受理状態を持つ複雑なものになります。
状態遷移図は、レクサー（語彙解析プログラム）とパーサー（構文解析プログラム）に対する共通の実装です。また、テキストの検索にも有効です。この図は、テーブルの集合として効率よく表現できる点が特に便利です。
決定性有限オートマトン
状態遷移図を処理するための最も一般的なアルゴリズムは、決定性有限オートマトン (DFA) による変換です。私が初めてDFAと出会ったのは何年か前に正規表現についての仕事をしたときです。そのとき、すでに最後にDFAを使ってから3年以上たっていたので、しばらく勉強する必要がありました。中でも特に、コンパイラーの構成についての代表的な参考書である『ドラゴン・ブック』の第3章と第4章を読み直しました (参考文献を参照)。
数学的には、状態遷移図は状態の集合です。状態の集合の中には1つの初期状態 と1つ以上の受理状態があります。状態遷移図の構成要素としては、ほかに、入力記号 (この場合はXMLのタグ) と、入力記号による状態の変更方法を制御する状態遷移関数 があります。
このモデルは、表1のような状態遷移表 として効率よく表現できます。この表には、状態遷移関数を実現するために必要なすべてのデータが含まれています。たとえば、simpara タグがあったなら状態1から状態2に遷移する、といったことが表現されています。このような表は、非決定性有限オートマトン (NFA) を実現するために使われます。NFAは、状態遷移図を実現する状態機械のを表すためだけの言葉です。
表1. simpara/ulinkの状態遷移表
|
|
入力記号
| |
状態
|
simpara
|
ulink
| | 0 | 1 | - | | 1 | - | 2 | | 2 | - | - |
効率を上げるためにも、決定性有限オートマトンで作業するのが最善です。DFAはNFAの特殊なケースです。空の文字列に対する状態遷移はなく、状態遷移表において特定の状態から出ていく有向枝の数は記号ごとに多くても1つであることが保証されています。つまり、各状態からの遷移は決定論的に計算できます。以下に見るように、NFAをDFAに自動的に変換することが可能です。
状態遷移図の状態は、SAXCountHandler のスタックに相当するものを実現しています。状態遷移表があれば、状態遷移関数を実現するのは簡単なことです。状態遷移関数ができてしまえば、NFAは簡単に実現できます。NFAは状態遷移図を実現する状態機械であることを思い出してください。まとめると、状態遷移表を作ることができれば、XPathは簡単に処理できます。
ありがたいことに、どのような状態遷移図についても状態遷移表を作成する方法が明確に記述されたアルゴリズムがあるので、DFAを使って問題を効率よく解決できます。
状態遷移表の唯一の問題は、実際のアプリケーションでは、状態の数が急速に増加することです。状態遷移表を手書きしていたのでは手間がかかりすぎます。幸い、状態遷移表を手で書く必要はありません。コンパイルするだけで済みます。
パッケージ
コードは3つのパッケージに分かれています。
-
org.ananas.hc はランタイムです。アプリケーションに必ず含まれていなければならないクラスが収められています。このパッケージは、できる限り小さくする必要があります。
-
org.ananas.hc.compiler はコンパイラーです。XPathHandler で必要なテーブル・クラスを作成します。このパッケージには、docletとXPathパーサーも含まれています。
- アプリケーション独自のパッケージは、テーブル・クラスによって作成されます。
次回の予定
今月の実用的なXML では、HCシステムを分析し、アルゴリズムを調べて、主要なクラスとパッケージを設計しました。本当におもしろい部分は、来月、コンパイラーのコーディングに着手してから始まります。いつもと同じように、利用できるようになったコードは、CVSリポジトリーに置いておきます。
参考文献
- いわゆるドラゴン・ブック (「コンパイラ ー 原理・技法・ツール」A. Aho、R. Sethi、J. Ullman共著) は、コンパイラーの設計と構成に関する信頼できる書籍です。
-
強力なAPI、SAX は、XML by Example, 2nd Edition からの抜粋で、SAXの構文解析について紹介されています。
-
JAXP は、XMLの構文解析用の標準Java APIです。SAX、DOM、およびTrAXという3つのコンポーネントで構成されています。
- 読者のRobert Berlinskiが提供してくれたSIA Parser は、もう1つのオートマトン・エンジンです。コンパイラーを使用しない別のアプローチが採用されています。
-
XML Master (ニックネームはXmas) では、XMLドキュメントの特定の要素に対するJavaBeansを生成するというまったく異なるアプローチで、構文解析の簡略化が行われています。
著者について  | 
| | Benoit Marchal氏は、ベルギーのナミュールを拠点にしたコンサルタントおよび著述家です。彼の著作には、 XML by Example(Que社、邦訳: インプレス社「実例で学ぶXML」。間もなく第2版が出版される予定です)、 Applied XML Solutions および XML and the Enterprise があります。また、Gamelanのコラムや、developerWorks XML zoneのコラムWorking XML の著者でもあります。最新プロジェクトの詳細については、www.marchal.com をご覧ください。 |
記事の評価
| 
