レベル: 初級 Benoit Marchal (bmarchal@pineapplesoft.com), Consultant, Pineapplesoft
2002年 1月 01日 SAX構文解析のためのJavaベースのHandler Compiler (HC) プロジェクトが、アルファ 版のリリースを間近にしています。今月は、DFA構築アルゴリズムのインプリメント方法を説明し、XPathを認識するためのコンパイラーの最初の具体的な使用例を示します。
実用的なXMLの毎月のコラムにおいて、Benoit Marchalは、彼が行っているXML開発者向けのオープン・ソース・プロジェクトの進行を解説しています。話は、設計に関する決定からコーディングの課題にまで及びます。現在のプロジェクトHC (Handler Compilerの頭文字) は、XPathのリストに関するSAX ContentHandlerの生成を自動化することにより、イベント・ベースのXML構文解析に付き物の辛い単調作業を軽減してくれます。
2つ前のコラムで私は、このコラムのための新規プロジェクトとしてHC (Handler Compiler) を立ち上げました。HCの目標は、SAX構文解析でXPathを特定のメソッド (アプリケーション・ハンドラー) と突き合わせるプロキシー・コンテンツ・ハンドラー をコンパイルすることです。
私は、自分でSAXプログラミングを行っていて、状態追跡などの低レベルな反復作業に費やす時間が多すぎることに気付きました。HCは、こうした専門的な問題から免れるための試みです。
今月は、前の2回のコラムで紹介したアルゴリズムをインプリメントしますので、それらのコラムをお読みになっていない読者には、まずそれらに目を通すことをお勧めします (右側にある「関連dWコンテンツ」からリンクされています)。
特に、前回のコラムで私は、いわゆる決定性有限オートマトン (DFA) をコンパイルするアルゴリズムについて検討しました。DFAは、パターンを認識する状態機械を構築するために一般的に使用されているアルゴリズムです。HCの場合、パターンはXPathです。
メッセージおよび表示
このコラムのためのほとんどの開発作業は、先月紹介したDFA構築アルゴリズムのインプリメントに関するものでした。ただし、実際のアルゴリズムの前に、メッセージ表示のためのいくつかのユーティリティー・クラスをインプリメントする必要がありました。それらのほとんどは、このコラムを毎回読んでいる読者にとっては、すでにおなじみのことと思います。
- 私は、Javaが誕生したころから、標準Javaライブラリーに
NotImplementedException のようなものがあればよいのに、と思っていました。これは、予期しない条件を知らせるための例外です。私は、(一般的な例外だけを報告したり、さらに極端な場合には、まったくエラーを報告しなかったりというやり方ではなく) 特定のエラー・コードとともにこれらの例外を報告できるようにすると、バグの追跡に要する時間が節約できることに気付きました。XM用として、類似のクラスをorg.ananas.util パッケージに導入したことがあります。このバージョンは、HCランタイムの一部であることを示すために、org.ananas.hc パッケージに入れられています。
-
Messenger は、XMのメッセンジャー・クラスに非常によく似ています。コンパイラーは、Messenger インターフェースをインプリメントすることによってユーザーと対話します。このインターフェースは、エラーの報告と通知メッセージの表示を行うメソッドを備えています。コンパイラーはバッチ・モードで作動しますので、ユーザーにデータの入力を促す方法を備えていません。このクラスはコンパイラーに特定のものであること (したがって、org.ananas.hc.compiler パッケージに含まれていること) に注意してください。HCランタイム (プロキシーを含みます) は、エラーを報告するためにSAXException またはSAXException の子孫をスローします。
-
DefaultMessenger は、メッセージをコンソールに出力するMessenger のデフォルト・インプリメンテーションです。コンパイラーでGUIフロントエンドを提供するには、メッセージをウィンドウに表示するための、Messenger の代替インプリメンテーションを用意するだけで済みます。
-
MessageStore は国際化対応機能を備えています。これは基本的には、ResourceBundle をMessageFormat 内の最も便利なメソッドに結び付けるものです。
これらのクラスはHCのオペレーション全体としては重要ですが (エラーの報告ができないようなコンパイラーでは困ります)、XPathのコンパイルには直接関係していませんので、特に説明しなくても分かると思います。したがって、このコラムでは、それらについて詳しい説明はしないことにします。その代わりに、ご自分でダウンロードしてコードを検討することをお勧めします (参考文献を参照してください)。
XPathの構文解析
DFAを構築するときには、2つの関連するエレメントが働きます。読者は前回のコラムの議論から、DFAを構築するためのアルゴリズムが入力として解析ツリーを予期していることを思い出されるかもしれません。HCの場合、解析ツリーはXPathを表します。
XPathNode
私は前回のコラムで、解析ツリー内のノード用にHCNode クラスを定義しました。アルゴリズムをインプリメントするときになって、2つの重要なものを忘れていたことに気付きました。
- 前回のコラムで紹介した
HCNode 内に、XPathが正常に認識された場合に行うべき処理を保管するフィールドがありませんでした。こうした情報を保管するために、汎用オブジェクトdata を追加しました。また、XPathの相対的な優先順位を表す整数priority を紹介しました。
- 前回のコラムで説明した
followpos() 関数がインプリメントされていませんでした。これも追加しました。
パーサーを特定のアプリケーションに結び付けたくなかったので、XPathを突き合わせるとき、情報の保管用に汎用オブジェクトを使用するようにしました。XPathの突き合わせ時に何を行うのか、また優先順位をどのように割り当てるのかは、DFAコンパイラーが決定することではありません。
followpos() については、クラス・コンストラクターにアクセス機能と新規コードを追加しました。
case PARENT_OF:
// compute lastpos() and firstpos()
Iterator iterator = left.lastpos().iterator();
while(iterator.hasNext())
{
XPathNode n = (XPathNode)iterator.next();
n.followpos.addAll(right.firstpos());
}
break;
|
前回のコラムで述べたとおり、HCNode はQName をカプセル化します。後者はXMLエレメントを表しますが、HCNode はXPath内のエレメントを表します (したがって、XMLエレメントであっても、child-of関係であってもかまいません)。
実際に作業をしてみると、QName とHCNode の違いがさほど明確なものではないことに気付きました。論理的には、XPath内のXMLエレメントは、別クラスではなくQName によって表されるべきです。
読みやすさを考慮して、HCNode を、QName から継承されるクラスによって置き換えることにしました。用途を反映させて、名前をXPathNode に変更しました。その他の点では、XPathNode は、すでに紹介したHCNode と同じです。より具体的に言うと、これにはfirstpos()、lastpos()、およびfollowpos() メソッドが含まれています。
残念なことに、この方法は1つの問題を引き起こします。XPathNode はQName からequals() とhashCode() を継承します。その結果、followpos() 内のバグを追跡するのが困難になります。
問題は、QName が入力ボキャブラリー中の記号を表していることです。2つの記号のネームスペースURIとローカル名が同じである場合、それらの記号は同一になります。つまり、simpara はsimpara と同じということになります。
ただし、XPathNode には、これが当てはまりません。これらはXPath内の特定のエレメントを表すため、simpara/ulink におけるsimpara はsimpara/emphasis におけるsimpara とは異なります。
より具体的に言うと、両者のfollowpos() は別のものになるべきです。最初の場合はulink で、2番目の場合はemphasis です。
XPathNode のequals() を書き直して、2つの異なるノードが異なるXPathにある場合には、それらが別のものとして扱われるようにする必要があります。デバッグのために、追加の比較メソッドisSynonymousWith() をインプリメントしました。この新規メソッドは2つのXPathNode を比較します。
このメソッドは、現行ノードの下のツリーを反復的に比較する、深い比較を行うことも、現行ノードで停止する、迅速な比較を行うこともできます。このメソッドは、構文解析の結果を予想された結果と比較するためのもので、デバッグだけを目的としています。
また私は、XPathパーサーを使用していて、XPathの終わりを示す特殊なタイプのXPathNode/HCNode であるEND_MARK を、QName で表したほうがよいと考え、この定数をXPathNode からQName に移動しました。
XPathNode/HCNode についてお話ししたときに、私が書いたmerge() と同一のaddAll() が、java.util.Set に含まれていることに気が付きました。私は現在、merge() の代わりにaddAll() を使用しています。
最後に、忘れてはならないことですが、私はこれらのクラスにJUnitテストを適用しました。XPathNode とそのテストは、CVSリポジトリーからダウンロードすることができます (参考文献を参照してください)。
XPathParser
実際のXPath構文解析は、リスト1 に示すXPathParser によって行われます。以前のコラムで述べたように、このクラスはXPathのサブセットだけを認識します。これは、前に決めた、XPath内の条件をサポートしないという方針と一致しています。
クラス・コンストラクターでは、3つまでパラメーターを指定することができます。
-
NamespaceSupport は、ネームスペースを処理するためのSAX定義クラスです。これは、XML修飾名 (db:simpara) をネームスペースURIとローカル名に分解することができます。
-
MessageStore は、基本的には、構文解析エラーを報告するために使用されるメッセージを含むリソース・バンドルです。
-
Messenger は、エンド・ユーザーにエラーを報告するためにパーサーによって使用されます。
構文解析のほとんどはxpath() メソッドで行われます。このメソッドは、普通の構文解析です。標準のStringTokenizer を使用してストリングを基本的なトークンに分解します。次に、それらのトークンをループしてXMLエレメント、属性、およびparent-of区切り文字 (/) を探します。
このメソッドは、トークンを認識すると、適切なタイプのXPathNode (ELEMENT、ATTRIBUTE、およびPARENT-OF) を作成します。絶対XPath標識については、注意が必要です。
実際には、XPathParser のユーザーはxpath() メソッドよりもaxpath() メソッドを頻繁に使用します。axpath() メソッドは、いわゆる拡大解析ツリー (END_MARK のための追加ノードを含む解析ツリー) を戻します。この追加ノードには、XPathとの突き合わせ時に行う処置に関する情報が入ります。上に述べたように、そのためにdata フィールドとpriority フィールドが使用されます。
私は、パーサーのためのJUnitテストも作りました。
DFA構築
DFAFactory クラスは解析ツリーからDFAをコンパイルします。このクラスは、先月説明したアルゴリズムをcreateDFA() メソッドにインプリメントします。このメソッドは、(XPathNode オブジェクトとしての) 解析ツリーをパラメーターとして受け入れ、現在のところ、DFATable のインスタンスを戻すようになっています。
DFATable
DFATable は、主としてテスト用に導入した一時クラスです。最初のHCコラムで説明したように、最終的には、これはtable クラスによって置き換えられる予定です。このクラスは、次の3つの便利なメソッドを提供します。
-
move() は、特定のXMLエレメントにヒットしたときにDFAが移行すべき状態を戻します。このメソッドのパラメーターは、XMLエレメントのQName と現行状態です。
-
isAcceptingState() は、現行状態が受理状態である場合にtrueを戻します。受理状態とは、XPathが認識された状態です。解析ツリーでは、END_MARK のヒットに対応します。
-
getAssociatedData() は、XPathに関連付けられたデータ (あるいは、現行状態が受理状態でない場合にはヌル) を戻します。通常、このデータは、特定のXPathが認識されたときに呼び出すべきメソッドを知らせてくれるものです。
リスト2 はDFATable です。これを見てお分かりになるように、このテスト・クラスは難解ではありません。DFAが認識するQName のリストを収めるために、3つのデータ・フィールド(symbols、遷移表dtran、および受理状態astate) があります。
DFAFactory
リスト3 に示すDFAFactory は、遷移表のコンパイルを行うので、HCコンパイラーのコア・クラスと言えます。createDFA() は、前回のコラムで述べたDFA構築アルゴリズムをそのままインプリメントしたものです。実際、このアルゴリズムはコードのコメント内に現れています。
このコードの解読で最も難しい部分は、状態がXPathNode の集合で表されていることを理解することです。最初のHCコラムで状態およびスタックについて述べたことを思い出してください。つまり、状態とは特定のスタック構成 (すなわち、スタックにあるXMLのエレメントと属性のリスト) を表すものです。
このアルゴリズムでは、XPathNode の集合がスタック構成を表します。実際、このアルゴリズムをトレースすると、可能なすべてのスタック構成と、それらの間の遷移のリストを作成していることにお気付きになるはずです。
このアルゴリズムの最初のループは、XMLドキュメントに現れる可能性のあるXMLエレメントおよび属性のリストを反復処理します。リストを計算するために、DFAFactory は解析ツリーをたどり、uniqueSymbols() メソッドを使用して固有のQName のリストをコンパイルします。
createDFA() は、状態がEND_MARK ノードに対応するかどうかを検査して、受理状態のリストも作成します。
e_closure() は、followpos() 内のノードのリストを計算するヘルパー・メソッドです。
コンパイラーのテスト
HCはまだ完全なものではありませんが、そのバックエンドはこれでほぼ出来上がりです。足りないのはプロキシーとフロントエンドだけです。
DFA構築をテストするために、私はプロキシーとフロントエンドをシミュレートする必要がありました。リスト4 は、このプロキシーをシミュレートするDFAHandler というクラスです。ただしこれは、アプリケーション・ハンドラーを呼び出さず、認識されたXPathを印刷するだけです。
ハンドラーはDFATable のインスタンスを受け入れ、XMLエレメントが与えられると、move() 関数を使用して新規状態に遷移します。
さらに、読者がdb:sect1/db:simpara/db:ulink およびdb:sect1/db:simpara というXPathに関心があるものとします。次に示すコードの抜粋は、それらを認識するDFAの作成方法を表しています。
NamespaceSupport namespace =
new NamespaceSupport();
namespace.declarePrefix("db",
"http://www.ananas.org/2001/docbook");
MessageStore message =
MessageStore.getMessageStore(
"org.ananas.hc.compiler.Message");
XPathParser parser =
new XPathParser(namespace,message);
String xpath1 = "db:sect1/db:simpara/db:ulink",
xpath2 = "db:sect1/db:simpara";
XPathNode first = parser.axpath(xpath1,1,xpath1),
second = parser.axpath(xpath2,2,xpath2),
root = new XPathNode(XPathNode.OR_XPATH,
first,second);
DFAFactory factory = new DFAFactory();
DFATable table = factory.createDFA(root);
XMLReader xparser =
XMLReaderFactory.createXMLReader(
"org.apache.xerces.parsers.SAXParser");
xparser.setContentHandler(new DFAHandler(table));
xparser.parse("file:doc.xml");
|
次回のHCの予定
DFAHandler は、HCが今後どのように動作するのかを示しています。明らかに、前の例は2つのXPathに合わせてハードコーディングされていますが、これは、HCにまだフロントエンドがないためにすぎません (次回のコラムではフロントエンドが登場します)。
しかし、コンパイラーを使用することの威力は、現状でも認めていただけるはずです。DFA構築アルゴリズムがすべての状態管理を行ってくれるからです。
XMに関する興味深いフィードバック
XMの最新情報をここで手短にお伝えします。読者は、XM (XSLT Makeの略称) が「実用的なXML」コラムで紹介された最初のプロジェクトであったことを覚えておいでかもしれません。XMは、XMLとXSLTを使用してWebサイトを公開するための、手ごろなソリューションです。私は、ユーザーからのフィードバックを集めるために、XM開発を一時的に休止しました。
これまで、ananas-discussionメーリング・リストでいくつかのフィードバックをいただいていますが、さらに多くの方のご意見を聞きたいと思いますので、お気軽にアイデアをお寄せください。また、私は先月XMで2つの新規Webサイトを作成しました。最初のものは、XMLで書かれたPineapplesoft社 (私のコンサルティング会社です) のWebサイトを部分的に書き直したものです。2つ目は、ある組織がXMLとXSLTをインプリメントするのを支援する、短期的なコンサルティングの仕事の関係で作ったものです。
メーリング・リストや他の経験によって、いくつかのバグが明らかになり、その大部分を修正しました。こうしたことにより、サード・パーティーがXMを展開する方法について、より深く考えることができました。また、この経験がきっかけとなり、次の2つの新規機能を追加することができました。
- XMには、ドキュメントの外部DTDを無視するオプションが追加されました。これにより、SoftQuad XMetaLが使いやすくなりました (おそらく、他のXMLエディターも使いやすくなると思います)。私は、XMetaLがそのディレクトリーのうちの1つを基準として、パスを挿入していることを発見しました。これは、他のXMLアプリケーション (修正するまではXMも含まれていました) を分断してしまうという、ありがたくない副次作用を持っています。
- XMが
xsl:output エレメントを完全にサポートするようになりました。したがって、大量のXML変換を行う場合などに、XMを使用してXMLドキュメントをプリプロセスすることができます。
これらの変更内容については、今後のコラムで詳しく説明する予定です。ところで、私はCVSリポジトリーに新規コードを収めました。ぜひこのコードをダウンロードしてテストし、お気付きの点をananas-discussionメーリング・リスト (参考文献を参照) にお知らせください。
参考文献
- このプロジェクトに関連するコードは、ananas.org からダウンロードすることができます。そこからdeveloperWorksのCVSリポジトリー、さらにananas-discussionメーリング・リストにリンクをたどってください。このリストに参加し、皆様の知恵をプロジェクトに貸してくださることをお願いします。
-
ZIPファイルを使用したい場合には、それもご利用いただけます。
- いわゆるドラゴン・ブック (コンパイラ ー 原理・技法・ツールA. Aho、R. Sethi、J. Ullman共著) は、コンパイラーの設計と構築に関する信頼できる書籍です。
-
JUnit は、自動化されたテストのためのオープン・ソースのフレームワークです。
-
Extreme programming (XP) は、より高品質なソフトウェアを実現するための推奨事項を集めたものです。
-
Pragmatic Programmers でも、方法論の分野における最新の議論が行われています。
著者について  | 
| | Benoit Marchal氏は、ベルギーのナミュールを拠点にしたコンサルタントおよび著述家です。彼の著作には、 XML by Example(Que社、邦訳: インプレス社「実例で学ぶXML」。間もなく第2版が出版される予定です)、 Applied XML Solutions および XML and the Enterprise があります。また、Gamelanのコラムや、developerWorks XML zoneのコラムWorking XML の著者でもあります。最新プロジェクトの詳細については、www.marchal.com をご覧ください。 |
記事の評価
| 
