(57)【要約】【課題】XML文書などテキスト形式に変換可能な木構造データの字句、構文解析を低コストかつ高速に処理する文書処理装置を提供する。【解決手段】XML文書を入力し一定の意味を持つ文字列単位に、入力文字列の位置や長さの情報を内部に含むトークンを生成し、特別な要素文字列から生成されたトークンを判定しソフトウェアに通知する字句解析手段と、字句解析手段からの出力トークンから木構造データを構成ためのノードを生成する構文解析手段と、任意の出力先アドレスが記載されたディスクリプタを許可し、直前に実行されたディスクリプタの出力結果を利用して、直前に実行されたディスクリプタの実行結果の直後に次のディスクリプタの実行結果を格納すべく、先に許可されたディスクリプタの出力先アドレスを更新するディスクリプタ管理手段を具備することを特徴とする文書処理装置。【選択図】図１
2011100234.tif 000002
【特許請求の範囲】
【請求項１】
文書処理手段と、文書処理制御手段と、を含む文書処理装置であって、
前記文書処理手段は、
テキスト形式で表現された文書の文字列データを入力し、
前記入力文字列から一定の意味を持つトークン単位に、当該トークンの種類と、当該トークンを構成する文字列に関する情報を示すトークン構成文字列情報と、を含むトークンデータを生成し、
生成した前記トークンデータの内容が、予め定めた種類のトークンである際に、前記予め定めた種類のトークンを生成したことを通知する特別トークン生成通知信号を出力し、
生成した前記トークンデータを出力する字句解析手段と、
前記字句解析手段から出力される前記トークンデータを入力とし、
ノードの種類と、ノードを構成する文字列に関する情報を示すノード構成文字列情報と、他のノードとの接続に関する情報であるノード間接続情報と、を含む、木構造データを構成するためのノードを生成して出力し、
最後のノードが出力された際に、処理終了を示す処理終了通知信号と、構文解析手段から出力された複数のノード総数もしくは総サイズに関する情報を出力する構文解析手段を含む
ことを特徴とする文書処理装置。
【請求項２】
請求項1の文書処理装置において、
前記文書処理手段が出力するトークンもしくはノードにおいて、
文書の文字列データに含まれ、実体は別に定義されて別の文字もしくは文字列に置換されている参照文字を独立したトークンもしくはノードとして生成し出力する
ことを特徴とする文書処理装置。
【請求項３】
請求項2の文書処理装置において、
前記文書処理手段は、文書の文字列データに含まれ、実体は別に定義されて別の文字もしくは文字列に置換されている参照文字が文字参照や実体参照を指す
ことを特徴とする文書処理装置。
【請求項４】
請求項1ないし3いずれか一に記載の文書処理装置において、
前記文書処理制御手段は、
前記文書処理手段に処理を依頼する制御情報と、前記文書処理手段が処理すべき文書に関連する情報と、前記文書処理手段が文書の文字列データから生成するトークンもしくはノードの出力先を示す出力先情報と、を含む記述子を複数管理し、
前記文書処理手段から出力される処理終了通知信号と、文書処理手段から出力される複数のノード総数もしくは総サイズに関する情報を入力し、
前記文書処理手段が前記処理終了通知信号を出力した依頼に該当する記述子の次に処理すべき記述子の出力先情報を、文書処理手段が前記処理終了通知信号を出力した依頼において出力したトークンもしくはノードにおける最終トークンもしくはノードに連続して、前記文書処理手段が前記処理終了通知信号を出力した依頼に該当する記述子の次に処理すべき記述子により、前記文書処理手段が出力するトークンもしくはノードにおける最初のトークンもしくはノードを配置可能な情報に更新する
ことを特徴とする文書処理装置。
【請求項５】
請求項4の文書処理装置において、
前記文書処理制御手段は、前記文書処理手段が特別トークン生成信号を出力すべきトークンに関する情報を文書処理手段に通知する特別トークン通知手段を備える
ことを特徴とする文書処理装置。
【請求項６】
請求項1ないし5いずれか一に記載の文書処理装置において、
前記文書処理手段は、
テキスト形式で表現された文書の文字列データを入力し、前記入力文字列データから一定の意味を持つトークン単位に、当該トークンの種類と、当該トークンを構成する文字列の開始位置を示すトークン構成文字列開始アドレスと、トークンを構成する文字列の長さを示すトークン文字列長と、を含むトークンデータを生成し出力する字句解析手段と、
前記字句解析手段から出力されるトークンデータを入力とし、ノードの種類と、ノードを構成する文字列の開始位置を示すノード構成文字列開始アドレスと、ノードを構成する文字列の長さを示すノード文字列長と、他のノードとの接続に関する情報であるノード間接続情報を含む、木構造データを構成ためのノードを生成し出力する構文解析手段と、を備える
ことを特徴とする文書処理装置。
【請求項７】
請求項1ないし5いずれか一に記載の文書処理装置において、
前記文書処理手段は、
テキスト形式で表現された文書の文字列データを入力し、前記入力文字列データから一定の意味を持つ単位に、トークンの種類と、入力した文書内におけるトークン構成文字列の開始位置を示すトークン構成文字列開始アドレスと、入力した文書内におけるトークン構成文字列の長さを示すトークン文字列長を含むトークンデータを生成し出力する字句解析手段と、
字句解析手段から出力されるトークンデータを入力とし、ノードの種類と、入力した文書内におけるノード構成文字列の開始位置を示すノード構成文字列開始アドレスと、入力した文書内におけるノード構成文字列の長さを示すノード文字列長と、他のノードとの接続に関する情報であるノード間接続情報を含む、木構造データを構成ためのノードを生成し出力する構文解析手段と、を備える
ことを特徴とする文書処理装置。
【請求項８】
請求項1ないし5いずれか一に記載の文書処理装置において、
前記文書処理手段は、
テキスト形式で表現された文書の文字列データを入力し、入力文字列データから一定の意味を持つ単位に、トークンの種類と、トークンを構成する文字列の入力された文書の先頭からの位置を示すトークン構成文字列開始アドレスと、トークンを構成する文字列の長さを示すトークン文字列長を含むトークンデータを生成し出力する字句解析手段と、
字句解析手段から出力されるトークンデータを入力とし、ノードの種類と、ノードを構成する文字列の入力された文書の先頭からの位置を示すノード構成文字列開始アドレスと、ノードを構成する文字列の長さを示すノード文字列長と、他のノードとの接続に関する情報であるノード間接続情報を含む、木構造データを構成ためのノードを生成し出力する構文解析手段と、を備える
ことを特徴とする文書処理装置。
【請求項９】
請求項4または5に記載の文書処理装置において、
前記文書処理制御手段は、
前記文書処理装置に処理を依頼する制御情報と、
文書処理手段が処理すべき文字列の先頭位置を意味する文字列開始アドレスと、
文書処理手段が処理すべき文字列の長さを示す文字列長と、
文書処理手段が文書の文字列データから生成するトークンもしくはノードの出力先を示す出力先アドレスを含む記述子と、を管理し、
文書処理手段から出力される処理終了通知信号と、
文書処理手段から出力される複数のノード総数もしくは総サイズに関する情報と、を入力し、
前記文書処理手段が前記処理終了通知信号を出力した依頼に該当する記述子の出力先アドレスに、文書処理手段から出力される複数のノード総数もしくは総サイズに関する情報を加算し、
前記文書処理手段が前記処理終了通知信号を出力した依頼に該当する記述子の次に処理すべき記述子の出力先アドレスを、前記加算した結果の情報に更新する
ことを特徴とする文書処理装置。
【請求項１０】
請求項4または5に記載の文書処理装置において、
前記文書処理制御手段は、
文書処理手段に処理を依頼する制御情報と、
文書処理手段が処理すべき文字列の先頭位置を意味する文字列開始アドレスと、
文書処理手段が処理すべき文字列の長さを示す文字列長と、
文書処理手段が文書の文字列データから生成するトークンもしくはノードの出力先を示す出力先アドレスを含む記述子を複数管理し、文書処理手段から出力される処理終了通知信号と、
文書処理手段から出力される複数のノード総数もしくは総サイズに関する情報と、
を入力し、
前記文書処理手段が過去に処理した各記述子の文書処理手段から出力される複数のノード総数もしくは総サイズに関する情報に、入力した、前記文書処理手段から出力される複数のノード総数もしくは総サイズに関する情報を加算し保持し、
前記文書処理手段が前記処理終了通知信号を出力した依頼に該当する記述子の次に処理すべき記述子の出力先アドレスを、文書処理手段が最初に処理した依頼に該当する記述子の出力先アドレスに前記加算結果を加算した情報に更新する
ことを特徴とする文書処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、XML文書に代表されるテキスト文書の構造化データへの変換、およびその逆変換を低コストかつ高速に処理するデータ処理技術に関する。
【背景技術】
【０００２】
インターネットの高速化はインターネットを介した複数のコンピュータシステム間の電子文書の交換を活性化した。近年では、企業の基幹サーバ間の電子文書交換のみならず、企業サーバと一般消費者の持つPC間、PCどうしで電子文書を交換する機会も増えてきている。例えば、HTTP (HyperText Transfer Protocol)やSOAP (Simple Object Access Protocol)といったプロトコルを用いて、既存の静的なWebページをPCに提供するだけでなく、インターネットを経由してデスクトップと同等のソフトウェア機能を提供することができる。一般に、RIA (Rich Internet Application)と呼ばれるWebサービスは、サービス提供側である企業サーバとサービス利用側であるPC間で電子文書を交換しインターネットを経由したアプリケーションを実現する。
【０００３】
そのWebサービスにおいては、インターネット上の電子文書の交換を柔軟かつ容易に実現することを目的に、XML (Extensible Markup Language)が電子文書の共通フォーマットとなりつつある。XMLは非特許文献1にて規定される標準規格であり、従来のバイナリ形式でなくテキスト形式で表現できる文書フォーマットを定義する言語である。XML文書の例を図26に示す。XMLでは"<"や">"のタグなどの区切り文字を用いて文書を構成する。区切り文字によって区別される語彙は、要素や属性、テキストなどである。図26においてはbookやtitleなどタグにより囲まれた語彙が要素であり、countryが属性名、japanが属性値、Tarou Yamadaなどがテキストである。なお、図26はXML文書の基本となる構造を示しているにすぎず、例えば当該XML文書が準拠する規格といった情報が格納されるXML宣言やXML文書に意味を付加するDTD (Document Type Definition)を省略している。
【０００４】
コンピュータシステム(以下コンピュータ)がXML文書をデータとして利用する場合、テキスト形式で表現されるXML文書をコンピュータが解析可能なフォーマットであるバイナリ形式に変換する必要がある。ここで、非特許文献1に準拠するXML文書は当該文書に含まれる要素やテキストなどが入れ子構造となるよう設計されなければならない。つまり、ある要素やテキストは必ず一つの親要素を持つ。このことから、XML文書はn進木の木構造データとして扱うことを許可されている。
【０００５】
具体的に、頂点となる要素をルートノードとし、そのルートノードに続く要素や属性、テキストをルートノードの子ノード、もしくはその子ノードの子ノードとして連結する。図27は図26のXML文書を木構造データ化した一例である。図27では属性およびテキストを一ノードとしているが、これに限定しない。つまり、図26のXML文書において、Author要素を構成するノードはその内部に属性名であるcountryや属性値japan、およびテキストTarou Yamadaを持つノードとして構成することも可能である。これは、XML文書を解析するXML文書処理装置が、当該XML文書処理装置を利用するアプリケーションに提供すべきAPIが非特許文献2で定義されている一方、当該XML文書処理装置のXML文書の内部の表現方法が定義されていないためである。
【０００６】
続けて、XML文書処理装置のXML文書解析方法、つまりXML文書から木構造データへの変換方法の概要を説明する。XML文書処理装置の処理は大きくXML文書の字句解析、および構文解析の2つから構成される。XML文書の字句解析とはXML文書を1文字ずつ読み込みトークンと呼ばれる一定の意味を持つ集合体を生成することである。具体的に"<"、"a"、">"、"X"、"X"、"X"、"<"、"/"、"a"、">"と入力される文字列を"<a>"、"XXX"、"</a>"といった一定の意味を持つトークンに変換する。なお、上記で示すトークンの単位は一例であり、これに限定しない。
【０００７】
XML文書の構文解析とは字句解析により生成したトークンから木構造データの構成要素であるノードを作成することである。具体的に、トークン間の親子関係を各トークンに付加したものがノードであり、そのノードの集合が木構造データである。先に述べたように、XML文書処理装置内における木構造データの表現方法に標準規定はない。例えば"<a b=c>XXX</a>"というXML文書の一部に関して、開始要素ノード"a"を頂点ノード（ルートノード）とし、その子ノードとして属性名ノード"b"、属性名ノード"b"の子ノードに属性値"c"、開始要素ノード"a"の子ノードであり属性名ノード"b"の兄弟ノードとして文字ノード"XXX"、開始要素ノード"a"の子ノードであり属性名ノード"b"および文字ノード"XXX"の兄弟ノードとして終了要素ノード"a"があるツリーデータを構成しても良く、また、開始要素ノード"a"を頂点ノード（ルートノード）とし、開始要素ノード"a"はそのノード内情報として属性名"b"および属性値"c"を持ち、開始要素ノード"a"の子ノードとして文字ノード"XXX"と終了要素ノード"a"を持つツリーデータを構成しても良い。
【０００８】
さて、XMLをデータフォーマットとして利用する場合、先に述べたようにテキスト形式からバイナリ形式に変換する必要があるため、従来と比較すると、データ処理に時間がかかる欠点がある。近年のコンピュータの性能向上により、企業サーバやPCにおいては無視できる性能劣化である場合もあるが、非力な組込み機器においては無視できない性能劣化である。今後、XMLフォーマットが携帯電話やカーナビゲーションシステムといった組込み機器へ浸透する可能性は十分あり、上記の性能劣化は直近の課題である。
【０００９】
上記問題を解消すべく複数の手法が提案されている。特許文献1はXML文書をバイナリ形式で表現することでテータ処理にかかる時間を削減できる手法である。具体的に、特許文献1ではXML文書にてテキスト形式で表現される要素や属性などをバイナリ形式で表現する。
【００１０】
第二に、XML文書処理をソフトウェアで処理するのでなくハードウェアで処理する手法があげられる。XML文書処理に最適化されたハードウェアでXML文書処理を行うことで、汎用プロセッサに対して処理効率を高めることができ、ひいては周波数比でXML文書処理性能を向上させることができる。なお、一般にある処理装置をハードウェア化する場合、特許文献2に示されるDMA (Direct Memory Access)と呼ばれる手法をとる。DMAに対応したハードウェアは汎用プロセッサを介さずにXML文書が格納されたメモリにアクセスするできるため、XML文書にアクセスするためのデータ転送負荷を軽減することができる。
【００１１】
なお、DMA対応ハードウェア処理装置のソフトウェア制御方法は以下のようなフローとなる。
(1)  処理対象データをメモリ上のDMAバッファに配置する
(2)  ハードウェア処理装置が出力するデータ用のDMAバッファを確保する
(3)  ハードウェア処理装置の制御レジスタを設定する
(4)  ハードウェア処理装置を起動する
(5)  ハードウェア処理装置処理終了を割込みかポーリングにより察知する
またDMA対応ハードウェア処理装置はディスクリプタと呼ばれる処理依頼内容が書かれた記述子を専用のディスクリプタバッファに連続して配置して置くことで、連続してディスクリプタ単位に処理することができる。当然であるが、アクセラレータが連続してディスクリプタ処理を実行するには、予めソフトウェアがディスクリプタを用意する必要がある。なお、ディスクリプタは制御情報、入力データ先頭アドレス、入力データサイズ、出力データ用先頭アドレスなど自動的にメモリアクセスを実行するための情報を含む。
【先行技術文献】
【特許文献】
【００１２】
【特許文献１】特許第3832807号公報
【特許文献２】特許第3824122号公報
【非特許文献】
【００１３】
【非特許文献１】Tim Bray、外4名、"Extensible Markup Language (XML) 1.0 （Fifth Edition"、[online] 、平成20年11月26日、W3C、［平成21年10月26日検索］、インターネット＜URL: http://www.w3.org/TR/2008/REC-xml-20081126/＞
【非特許文献２】Vidur Apparao、外10名、"Document Object Model (DOM) Level 1 Specification"、[online] 、平成10年10月1日、W3C、［平成21年10月26日検索］、インターネット＜URL:http://www.w3.org/TR/1998/REC-DOM-Level-1-19981001/＞
【発明の概要】
【発明が解決しようとする課題】
【００１４】
本発明が解決しようとする問題は以下の4つである。
【００１５】
第一に、特許文献1は標準規格である非特許文献1を拡張する仕様であり、非特許文献1に準拠するものの特許文献1に対応しないXML文書処理装置は、特許文献1を適用したXML文書を解析できない。それゆえ、XML文書の利点の一つである汎用性、および保守運用の容易性を損なうことになる。
【００１６】
第二に、特許文献1はXML文書処理装置におけるXML文書と木構造データの変換方法について言及しておらず、結果、木構造データを構成するノードのデータ構造も定義されていない。しかし、非特許文献2から図28のノード構成が容易に想定される。
【００１７】
図28において、ノードタイプ900は、当該ノードがどのような種類のノードなのか、具体的に要素か属性かその他ノードなのかを示す情報であり、ノード名901は要素名や属性名といった名前を示す。なお、ネームスペース名などを含むこともできる。子ノード数902は当該ノードの子ノードの数を示す。子ノード数902は木構造データから任意のノードを探索する際の助けにはなるものの、当該ノードの親ノードや兄弟ノードを調査することで得られる計算可能な情報であるため必須の情報ではない。リンク情報903は当該ノードに接続される親や子ノード、兄弟ノードへの接続情報が含まれる。但しリンク情報903は木構造の表現形式により持つべき情報が異なる。コンテキスト904は、当該ノードに含まれる文字列を示す。なお、文字列を一ノードとする木構造データでは本情報は省略されるだろう。文書関連情報905は当該ノードを構成する文字情報(例えば当該ノードが要素である場合要素名の文字列が該当する情報である)が位置する文書の行数などを示す。なお、文書関連情報905は木構造データから任意のノードを探索する際の助けにはなるものの必須ではない。
【００１８】
図28のノード構造を持つ木構造データを出力するXML文書処理装置は、当該解析処理を行う時間に対して非効率なデータ入出力時間を要す可能性が高い。これは字句・解析処理は任意のルールによる変換をXML文書に施すだけであり、処理時間を要さないからである。つまり、上記のXML文書処理装置は巨大なXML文書になるほど、XML文書処理装置の処理時間に対するデータ入出力時間の影響が大きくなり、結果、統合的にXML文書処理装置のパフォーマンスが劣化する。特許文献1は上述のデータ入力処理負荷を軽減する効果があるが、データ出力負荷への対応は明記されておらず、性能向上効果が限定的と言える。
【００１９】
第三に、一般にソフトウェア、ハードウェアに限らず、あるデータ列を処理する際、メモリ容量が有限である点、レスポンスが低下する点を考慮して、処理対象データ列の全データをメモリに展開し処理装置に処理を依頼することはしない。一定の大きさのサイズに分割したデータ列（チャンクデータ）を入力に処理装置に処理を依頼し、分割された処理結果を依頼側が結合する。
【００２０】
この時、結果データをメモリ上に非連続に配置すると、メモリ断片化が発生しパフォーマンスの低下が懸念となる。結果データサイズが入力データサイズと同一である処理を行う処理装置においては、入力データと同サイズのメモリ領域を、直前の結果データを格納している領域に連続して確保することでメモリ断片化を発生させなくてすむ。
【００２１】
一方、XML文書の字句解析および構文解析は、XML文書のテキストデータを入力し、トークンもしくはノードを出力するため、処理装置に入力されるデータサイズと結果として出力されるデータサイズが異なる。トークンやノードは一定の文字から構成され、トークンやノードを構成する文字列長は文書に依存するためである。
【００２２】
それゆえ、XML文書を処理する際に特許文献2では先行して連続したディスクリプタを用意することができず、DMAによる効果が得られない問題が考えられる。もしくは、メモリ断片化を覚悟することでディスクリプタの連続配置が可能となるが、同様にパフォーマンスが低下する問題がある。
【００２３】
第四に、特許文献2を適用したXML文書処理装置は、1ディスクリプタの処理終了後に割込みなどの手法を用いて処理完了を通知する。それゆえ、1ディスクリプタ処理が終了するまで、XML文書処理装置に処理を依頼する依頼側は、依頼したXML文書に対する処理を行うことができず、最終的にXML文書処理全体のレスポンスを低下させる可能性がある。
【課題を解決するための手段】
【００２４】
本発明は上述の事情を考慮してなされたものであり、本発明は未知のXML文書を含むあらゆるXML文書の字句・構文解析を低コストにかつ高速に処理できる手段を提供する。なお、上記において、ハードウェアを一例にXML文書処理装置の課題を説明したが、本発明によるXML文書処理装置の実現手段をハードウェアに限定するものではない。
【００２５】
また、上記において、XML文書を例に文書処理装置の課題を説明したが、本発明はXML文書に処理に限定されない。つまり、テキスト形式で表現される文書をバイナリ形式に変換する、もしくはバイナリ形式で表現されるデータをテキスト形式の文書に変換する処理装置、特に、テキスト形式で表現される文書から可変長のバイナリ形式データを生成する、もしくはバイナリ形式データから可変長のテキスト形式文書を生成する文書処理装置に適合できる。本発明が適用できる文書処理装置のXML文書以外の具体例にHTML文書処理装置が挙げられる。
【００２６】
また、本発明は、XML文書に限らずテキスト形式に変換可能な木構造データの字句・構文解析処理に適用することができる。具体的に、HTML、SGMLに適用可能である。
【００２７】
上述の課題を解決するために、本発明の好ましい実施形態によるXML文書処理手段において、
XML文書のテキストデータを入力し、入力文字列から一定の意味を持つ単位に、トークン種類、トークン構成文字列開始アドレス、トークン構成文字列長、文書関連情報などを含むトークン情報を生成し出力する字句解析手段と、
字句解析手段から出力されるトークン情報を入力し、特殊要素から生成されたトークン情報かを判定し、特殊要素から生成されたトークンである場合に割込み依頼を発行する特殊要素判定手段と、
字句解析手段から出力されるトークン情報を入力とし、ノード種類、ノード構成文字列開始アドレス、ノード構成文字列長、ノード間接続情報などを含む、木構造データを構成ためのノードを生成し出力する構文解析手段と、
ディスクリプタを読み込み、字句解析および構文解析の実行指示を発行するなど、ディスクリプタの制御を行うディスクリプタ制御手段と、
特殊要素から出力される割込み依頼を入力し、CPUに対して割込みを通知する割込み管理手段で構成されるXML文書処理手段と、
XML文書処理手段が出力する結果を割込み等の通知手段により把握し、直前に実行されたディスクリプタに含まれる出力先アドレス、および直前に実行されたディスクリプタによりXML文書処理装置が生成した実行結果のデータサイズ情報を、もしくは直前に実行されたディスクリプタに含まれる出力先アドレスに直前に実行されたディスクリプタによりXML文書処理装置が生成した実行結果のデータサイズ情報を加算した結果をバッファする実行結果管理手段と、
XML文書処理手段の制御情報、XML文書テキストデータが格納される場所を示すアドレス情報と、XML文書テキストデータ長と、XML文書処理手段が出力するトークンもしくはノードの出力先アドレス情報を含むディスクリプタを複数配置するためのバッファであるディスクリプタリングを管理し、連続実行されるディスクリプタの2つ目以降のディスクリプタの出力先アドレスを前述した実行結果管理手段がバッファする値を利用して更新するディスクリプタリング管理手段を具備することを特徴とする。
【発明の効果】
【００２８】
本発明を用いたXML文書処理装置は、第一に未知のXML文書を含むあらゆるXML文書の字句・構文解析を高速に処理できる。第二に、メモリ断片化による性能劣化を回避できる。第三に、XML文書を利用するアプリケーションが必要とする情報に低レスポンスにアクセスできる。
【図面の簡単な説明】
【００２９】
【図１】本発明の1実施形態を例示するブロック図である。
【図２】図1構成のメモリマップの詳細を例示する図である。
【図３】図1構成の実体参照、文字参照を解決するテーブルの詳細を例示する図である。
【図４】図1構成の処理制御部の詳細を例示する図である。
【図５】図1構成の処理制御部の処理フローを例示する図である。
【図６】図1構成の入出力制御部の詳細を例示する図である。
【図７】図1構成の入出力制御部の第一の処理フローを例示する図である。
【図８】図1構成の入出力制御部の第二の処理フローを例示する図である。
【図９】図1構成の字句解析部の詳細を例示する図である。
【図１０】図1構成の字句解析部の第一の処理フローを例示する図である。
【図１１】図1構成の字句解析部の第二の処理フローを例示する図である。
【図１２】図1構成の字句解析部の第三の処理フローを例示する図である。
【図１３】図1構成の構文解析部の詳細を例示する図である。
【図１４】図1構成の構文解析部の処理フローを例示する図である。
【図１５】図1構成の割込み管理部の詳細を例示する図である。
【図１６】図1構成のXML文書処理制御部の詳細を例示する図である。
【図１７】図1構成のXML文書処理制御部の第一の処理フローを例示する図である。
【図１８】図1構成のXML文書処理制御部の第二の処理フローを例示する図である。
【図１９】図1構成のXML文書処理制御部の第三の処理フローを例示する図である。
【図２０】本発明の第二の実施形態を例示するブロック図である。
【図２１】図2構成のメモリマップの詳細を例示する図である。
【図２２】図2構成の入出力制御部の詳細を例示する図である。
【図２３】図2構成の割込み管理部の詳細を例示する図である。
【図２４】図2構成のXML文書処理制御部の詳細を例示する図である。
【図２５】図2構成のXML文書処理制御部の処理フローを例示する図である。
【図２６】XML文書の一例を示す図である。
【図２７】図26のXML文書から生成される木構造データの一例を示す図である。
【図２８】XML文書から生成される1ノードの構成例を示す図である。
【発明を実施するための形態】
【００３０】
以下の実施例においてはXML文書の字句・構文解析を行うXML文書処理装置について記述するが、本発明はXML文書の字句解析のみ行うXML文書処理装置にも適用可能である。
【実施例１】
【００３１】
以下、図面を用いて本発明の第一の実施形態を詳細に説明する。なお、全図に示す同一の番号は同一の機能を持つため説明を省略する。
【００３２】
図1は本発明の一実施形態に係るXML文書処理装置10を示す構成図である。図1において、XML文書処理装置10はXML文書処理部100とCPU 101と第一記憶装置102で構成され、XML文書処理部100とCPU 101と第一記憶装置102は、バスなどの内部信号線103で接続されている。
【００３３】
XML文書処理装置100は処理制御部110と入出力制御部111と字句解析部112と構文解析部113と割込み管理部114で構成される。なお、処理制御部110の詳細は以後別図を用いて行う。
【００３４】
CPU 101はXML文書を外部ネットワークや第二記憶装置であるハードディスクドライブなどから取得し第一記憶装置102に格納する処理部、さらにはXML文書処理部100にて生成されるノード情報を使用するXMLアプリケーション120と、XML文書処理部100を制御するXML文書処理制御部121を、第一記憶装置102に格納されたプログラム（図示していない）をCPU101が実行することにより、プロセスとして実現する。
【００３５】
これらのプログラムは、あらかじめ、上記第一記憶装置102に格納されていても良いし、必要なときに、入出力インタフェース(図示していない)とXML文書処理装置10が利用可能な媒体を介して、他の装置から上記第一記憶装置102に導入されてもよい。媒体とは、たとえば、入出力インタフェースに着脱可能な記憶媒体、または通信媒体（すなわち有線、無線、光などのネットワーク、または当該ネットワークを伝搬する搬送波やディジタル信号）を指す。
【００３６】
第一記憶装置102はCPU 101やXML文書処理部100で利用するデータを格納する。本実施例では、複数のディスクリプタを格納するための領域であるディスクリプタリング130とXMLアプリケーション130にて用意されるXML文書テキストデータを格納するための領域であるXML文書140とXML文書内で参照される文字参照および実体参照を格納するテーブルである参照文字テーブル150とXML文書処理部100から出力されるノード情報を格納するための領域である木構造データバッファ160で構成される。
【００３７】
なお、本実施例においては、ディスクリプタリング130はディスクリプタ0 131〜ディスクリプタs-1 132までのs個のディスクリプタを格納できるものとしている。また、木構造データバッファ160は、ディスクリプタリング130のサイズに合わせ、ディスクリプタ0の指示を受けXML文書処理装置10から出力される木構造データを格納する領域であるディスクリプタ0木構造データ161からディスクリプタs-1の指示を受けXML文書処理装置10から出力される木構造データを格納する領域であるディスクリプタs-1木構造データ164のs個のバッファから構成される。
【００３８】
なお、上記の説明において、ディスクリプタリング130に格納できるディスクリプタ数と、木構造データバッファ160に格納できる木構造データ数を同一としたのは説明を明確にするためであり、これに限定しない。
【００３９】
ディスクリプタ0木構造データ161はディスクリプタ0によりXML文書処理装置10が生成する木構造データを構成するノード群ノード0 162〜ノードt-1が格納される。
【００４０】
ディスクリプタリングバッファ140は、複数のディスクリプタを格納するための領域であり、図1では第一のディスクリプタ150から第sのディスクリプタ151が格納されている。本実施例では、ディスクリプタリングバッファ140はs個のディスクリプタを格納することができ、第一のディスクリプタ150をディスクリプタリングバッファ140の先頭に配置し、続くディスクリプタを連続して配置し、最後に第sのディスクリプタ151を配置するリング構造としている。ただし、上記は本実施例のディスクリプタ管理方法を限定するものではない。なお、第sのディスクリプタが格納される位置までディスクリプタリングバッファ140が使用された場合、続くディスクリプタは第一のディスクリプタ150の位置に配置されるディスクリプタが有効でなければ、第一のディスクリプタ150の位置に配置される。
【００４１】
続けて、図2を用いて、131〜132および161〜163の詳細な説明を行う。本実施例において、ディスクリプタ(ディスクリプタ0 131〜ディスクリプタs-1)は、制御情報170と有効フラグ171と文字列先頭アドレス172と文字列長173と出力先アドレス174と生成ノード数175と通知要素情報176を含む。
【００４２】
制御情報170はXML文書処理部100の動作を規定する情報が記述される。具体的に、XML文書処理部100が複数の文字コードに対応する場合、XML文書140に格納されるXML文書の文字コードを指定することが可能である。有効フラグ171は当該ディスクリプタが有効かどうか、換言してXML文書処理部100で処理済みのディスクリプタか未処理のディスクリプタかを判定するフラグである。文字列先頭アドレス172は当該ディスクリプタが指定するXML文書140の一部もしくは全てのテキストデータの先頭のアドレスを示す。
【００４３】
文字列長173は当該ディスクリプタが指定し、XML文書処理装置10が処理すべきXML文書140のデータサイズを示す。つまり、XML文書処理部100が当該ディスクリプタで処理すべきXML文書のデータは文字列先頭アドレス172の指すアドレスから文字列長173だけのデータである。出力先先頭アドレス174はXML文書処理部100が当該ディスクリプタで指定されるXML文書データ、換言して文字列先頭アドレス172から文字列長173の示す長さのXML文書データから生成されるノード情報を格納する領域の先頭アドレスである。本実施例においては、ディスクリプタ0 131で指定される出力先先頭アドレス174は、ディスクリプタ0木構造データ161の先頭アドレスであり、ディスクリプタs-1 132で指定される出力先先頭アドレス174は、ディスクリプタs-1木構造データ164の先頭アドレスである。
【００４４】
生成ノード数175は当該ディスクリプタの指示によりXML文書処理装置10が生成するノードの総数、もしくは全生成ノードのデータサイズである。本領域はXML文書処理装置10が書き込むための領域であり、ディスクリプタ設定時に値を設定する必要はない。通知要素情報176は当該ディスクリプタ処理中にXML文書処理装置10が通知要素情報176に指定する要素を発見した際に、ソフトウェアへの通知を所望する要素に関する情報を含む。
【００４５】
なお、ディスクリプタの構成要素は一例であり、これに限定しない。例えば、生成ノード数175はディスクリプタに属さず、別領域に配置しても良い。
【００４６】
各ディスクリプタの木構造データ(ディスクリプタ0木構造データ161〜ディスクリプタ0木構造データ164)に含まれるノード(ノード0 162〜ノードt-1 163)は、ノード種類180と文字列先頭アドレス181と参照文字列先頭アドレス182と文字列長183と子ノード接続情報184と兄弟ノード接続情報185から構成される。なお、本実施例におけるディスクリプタ0木構造データ161を構成するノード数をtと置いているが、これは説明を容易にするためでありサイズを限定するものではない。但し、tは文書に依存した数であり、当該ディスクリプタで指定されるXML文書テキストデータの文字数をTとし、全て属性を含まない開始タグとすると、0からT/3までで可変となる。
【００４７】
ノード種類180は当該ノードの種類を示す。具体的に、開始タグ、終了タグ、属性名、属性値、処理命令、コメント、テキストなどが種別される。文字列先頭アドレス181は当該ノードを構成する文字列であり、XML文書140に含まれる一部文字列へのポインタを意味する。但し、文字列先頭アドレス181はC言語などのポインタであっても、XML文書140の先頭からのオフセットであっても、XML文書140に含まれる一部文字列の開始場所がわかる情報であれば良い。参照文字先頭アドレス182は、当該ノードが文字参照もしくは実体参照である場合に使用され、参照文字テーブル150に含まれる参照情報文字列へのポインタを意味する。但し、参照文字列先頭アドレス182はC言語などのポインタであっても、参照文字テーブル150の先頭要素からのオフセットであっても、参照文字テーブル150に含まれる各要素の先頭がわかる情報であれば良い。
【００４８】
図3に参照文字テーブル150の一例を示す。参照文字テーブル150の１列目は定義済み実体であり、XML文書で実際に表記される文字列を意味する。参照文字テーブル150の２列目はXML文書処理装置10が出力する文字コードであり、例えば参照文字テーブル150をT[][]とすると、T[0][0]は"&"として表示される。つまり、参照文字先頭アドレス182はその対象とする定義済み実体の文字列が&amp;である場合、&T[0][0]のアドレスとなる。なお、参照文字テーブル150に格納されるデータは必ずしも文字列である必要はない。換言して、参照文字テーブル150の各要素がどの参照文字を示しているかが判断できれば良い。
【００４９】
文字列長183は当該ノードを構成する文字列の長さを示す。つまり、当該ノードを構成する文字列は文字列先頭アドレス181もしくは参照文字先頭アドレス182の指す場所から文字列長183の指す場所までの文字列である。子ノード接続情報184は当該ノードに子ノードとして接続されるノードへのリンク情報が含まれる。同様に、兄弟ノード接続情報185は当該ノードに隣接する兄弟ノードとして接続されるノードへのリンク情報が含まれる。前述の通り、本実施例のノードは接続情報格納場所として、1つの子ノード接続情報184および1つの兄弟ノード接続情報185を持つ。つまり、n進木を二分木として表現している。これは、本実施例において、1ノードサイズを固定長とする方が説明が容易であるためである。但し、ノードのサイズは可変長であっても良く、ノードサイズを限定するものではない。
【００５０】
なお、当該ノードが文字参照もしくは実体参照でない場合は参照文字先頭アドレス182を持つ必要はなく、また、当該ノードが文字参照もしくは実体参照である場合は文字列先頭アドレス181を持つ必要はない。
【００５１】
ここで、本実施例において、参照文字テーブル150を用意し文字参照や実体参照が異なるアドレスを用いるのは、本実施例のXML文書処理装置10の出力するノードの構成要素に文字列そのものを含まないためである。換言して、本実施例のXML文書処理装置が出力するノードは入力されるXML文書140の一文字列を指し、その文字列を識別する構造であるため、XML文書140に含まれない文字列は別途用意するテーブルに格納し、その別途用意するテーブルに格納される一文字列を参照する必要があるためである。
【００５２】
続けて、図4を用いて処理制御部110の詳細な説明を行う。処理制御部110は動作制御部200と制御レジスタ210とディスクリプタレジスタ202で構成される。動作制御部200は入出力制御部111と接続され、入力と出力両方向に制御信号とデータ信号で接続される。また、動作制御部200は割込み管理部114と接続され、動作制御部200の出力方向に割込み要求信号と割込み種別データ信号、入力方向に割込み終了通知信号が接続される。
【００５３】
図5を用いて処理制御部110の詳細な動作フローの説明を行う。処理制御部110の動作制御部200は入力データ信号を経由して入出力制御部111からレジスタ設定データを受信し、制御レジスタ201に書き込む(T101)。なお、本実施例において、レジスタ設定データの受信方法、つまり入出力制御部111と処理制御部110間の通信プロトコルは特に規定しないが、一例として、入力制御信号はイネーブル信号を含み、イネーブル信号がアクティブの時に入力データ信号にて転送されているデータをレジスタ設定データとして取り組む方法が挙げられる。以降、データ信号は、処理依頼の目的に必要なデータそのものを転送するための信号とし、制御信号はイネーブル信号やデータ信号の補助となる情報を転送するための信号として説明を行う。
【００５４】
続けて、動作制御部200は入出力制御部111から起動フラグデータを受信し、XML文書処理の一連の動作を開始する。動作制御部200はまず入出力制御部111に対して、出力データ信号を経由して制御レジスタ201のデータを参照し得られる現在処理すべきディスクリプタの先頭アドレスの情報を送信する(T102)。なお、本実施例おいて、読み込み対象ディスクリプタのアドレスの送信方法は左記の入力方法と同様に特に規定しないが、一例として、出力制御信号はイネーブル信号を含み、イネーブル信号をアクティブにして並行して出力データ信号にディスクリプタアドレスを渡す方法が挙げられる。
【００５５】
以下、入力出力の方向を問わず、また処理制御部110と入出力制御部111間の転送に限らず、転送プロトコルに関して明確に説明しない。上記の説明を今後説明するデータ転送処理に関して適用する方法は容易に想定できるためである。
【００５６】
続けて、動作制御部200は入出力制御部111からディスクリプタデータを受信しディスクリプタレジスタ202に書き込む(T103)。その後、ディスクリプタレジスタ202に格納されたレジスタの有効フラグ171が有効かどうかを確認し(T104)、T104が真であれば動作制御部200は入出力制御部111に処理開始を依頼する(T105)。T105の処理内容は具体的に、XML文書140からディスクリプタレジスタ202の文字列先頭アドレス172で指定されるアドレスからディスクリプタレジスタ202の文字列長173で指定される長さだけデータを読み込み、読み込みデータを字句解析部112に転送することである。それゆえ、T105では処理制御部110は入力制御部111に対して、制御信号にイネーブル信号、データ信号に処理要求を意味するフラグ信号や当該ディスクリプタの文字列先頭アドレス172と文字列長173と出力先先頭アドレス174を転送する。また、当該ディスクリプタの通知要素情報176も並行して転送される。
【００５７】
続けて、入出力制御部111から終了通知が送信されているかを確認し(T106)、T106が偽であれば真になるまでT106を繰り返す。なお、終了通知に関する詳しい説明は別途図7を用いて行う。T106が真であれば、動作制御部200はディスクリプタレジスタ202の値を編集し、具体的に、有効フラグ171を無効化し、入出力制御部111から送信された終了通知とともに転送される生成ノード数情報を生成ノード数175に書き込む。その後、当該ディスクリプタを読み込んだアドレスに入出力制御部111に更新したディスクリプタレジスタ202の値を書き戻すよう依頼する(T107)。続けて、動作制御部200は割込み管理部114に1ディスクリプタの処理が終了したことを通知する割込みの発行を依頼する(T108)。その後、割込み管理部114から割込みの終了通知があれば(T109)、T102に戻り、なければT109を繰り返し確認する。なお、T104が偽であれば処理終了となる(T110)。また、T102に処理を戻る際に、次に読むべきディスクリプタにアクセスするために、制御レジスタ201に含まれるディスクリプタアドレスを更新する。さらに、本実施例では、割込み管理部114からの割込み終了通知を受信するまで処理を進めていないが、これは説明を容易にするためであり、必ず割込み管理部114からの割込み終了通知後に次の処理であるT102を行わなければならないわけではない。
【００５８】
続けて、図6を用いて入出力制御部111の詳細な説明を行う。入出力制御部111は動作制御部210とデータバッファ211と文字列カウンタ212とノードカウンタ213で構成される。動作制御部200は処理制御部110と接続され、同様に、内部信号線103とも入出力の両方向に制御信号とデータ信号が結線されている。
【００５９】
図7を用いて入出力制御部111の詳細な動作フローの説明を行う。図7は内部信号線103を経由してXML文書140からデータを読み込む際のフローチャートである。なお、図7ではディスクリプタ処理に関するフローを省略している。前述した処理制御部110のフローである図５の説明から容易に想定できるためである。まず動作制御部210はXML文書処理装置10の初期化時などに文字列カウンタ212の初期化が必要であれば実行し処理を開始する(T120)。動作制御部210は処理制御部110よりT105で送信される処理依頼を受け、信号線103を経由してXML文書104から所望する文字列データを取得し、データバッファ211に書き込む(T121)。なお、処理制御部110から処理依頼を受信する際、文字列長173に関する情報は文字列カウンタ212に格納されるものとする。
【００６０】
続けて、現在の文字カウンタ212が1より大きければ(T122)、字句解析部112へデータバッファ211の未送信文字1文字を送信する(T123)。なお、本実施例においてT123で送信するデータは1文字としている。これは後で述べる字句解析部112の説明を容易にするためであり、これに限定しない。つまり、一例として入出力制御部111は字句解析部112に複数の文字を転送し、字句解析部112は転送される全てのデータを一度に処理しても良く、また、字句解析部112が内部でバッファしても良い。続けて、文字列カウンタ212を-1しT122に戻る(T124)。
【００６１】
T122が偽であり文字列カウンタ212が0でなければ(T125)、字句解析部112へ最終文字フラグおよびデータバッファ211の未送信文字1文字を送信する(T126)。なお、最終文字フラグはT126にて送信する文字が最終であることを示す情報であれば、特に限定しない。T125が真であれば処理終了となる(T127)。
【００６２】
続けて、図8を用いて入出力制御部111の詳細な動作フローの説明を行う。図8は内部信号線103を経由して構文解析部113が出力するノード情報を木構造データバッファ160に書き込む際のフローチャートである。なお、図8においてもディスクリプタ処理に関するフローを省略している。前述した処理制御部110のフローである図５の説明から容易に想定できるためである。まず動作制御部210はXML文書処理装置10の初期化時などにノードカウンタ213の初期化が必要であれば実行し処理を開始する(T130)。続けて、構文解析部113よりノード情報を受信し、信号線103を経由して木構造データバッファ160に書き込む(T131)。なお、出力場所は、T105にて指定される出力先アドレスにノードカウンタ213の値を直接、もしくはノードカウンタ213の値に何らかの演算を施した値を加算した値である。
【００６３】
続けて、ノードカウンタ213に1を加算し(T133)、T131にて受信したノード情報そのものに、もしくはT131にてノード情報受信時に入力制御信号が最終フラグを含んでいなければ(T133)T131へ戻る。T132が真であれば処理制御部へ処理終了通知およびノードカウンタ213の値を送信し(T134)、終了する(T135)。
【００６４】
続けて、図9を用いて字句解析部112の詳細な説明を行う。字句解析部112は字句解析オートマトン220と認知モデルスタック221とトークンバッファ222と参照文字解決部223と特殊要素判定部224で構成される。字句解析オートマトン220は入出力制御部111と入力方向が接続され、入出力制御部111より入力される文字データおよび認知モデルスタック221に保持される認知モデルを引数にトークンを生成し、トークンバッファ222に生成したトークンを格納し、特殊要素判定部224へ生成トークンを出力する。
【００６５】
認知モデルスタック221はXML文書の解析の状態を保持しておくバッファであり、"<a>XXX</a>"といったXML文書の一部データにおいて先頭から解析する場合、開始タグ内、テキスト内、終了タグ内の順で認知モデルが変化する。なお、説明を明確にするために名称をスタックとしているが、データ構造上のスタック(FILO)でなくても構わない。トークンバッファ222には字句解析オートマトン220が生成するトークン情報を一時格納する。
【００６６】
参照文字解決部223は入出力制御部111と入出力両方向に接続され、字句解析オートマトン220に入力される文字列が実体参照もしくは文字参照である場合に、入力制御部111を経由して参照文字テーブル150の一部もしくは全てを読み込み、字句解析オートマトン220より渡される文字に対して、該当する参照文字を指すアドレスを字句解析オートマトン220に渡す。
【００６７】
特殊要素判定部224は、入出力制御部111と字句解析オートマトン220に入力方向を接続し、字句解析オートマトン220から出力されるトークンが、入出力制御部111から出力される通知要素情報176に該当するトークンかを判定し、判定内容によって割込み管理部114へ割込み要求を発行する。また、字句解析オートマトン220が出力するトークンをそのまま構文解析部113に出力する。
【００６８】
続けて、図10を用いて字句解析部112の処理フローを説明する。なお、図10は本実施例の本質に関係のないことから、エラーケースを考慮していない。まず、XML文書処理装置10の起動時など、初期化が必要であれば(T141)、認知モデルスタック221（以下Sとする）の0番目であるS[0]に認知モデルPCDATAを設定し、Sの1要素を示すポインタpSをSの0番目の要素を指すよう設定する(T142)。また、当該ディスクリプタの処理開始時に、特殊要素判定部224は入力制御部111から入力される通知要素情報176を受信し内部でバッファする。なお、PCDATAを解析可能な文字列であることを意味する認知モデルとしている。
【００６９】
続けて、入力制御部111より入力される文字を受信し(T143)、読み込み文字が開始文字に該当すれば(T144)、トークンバッファが空であるかどうかをチェックし(T145)、空でなければトークンバッファに格納されるトークン情報を特殊要素判定部224に出力する(T146)。なお、T126にて設定され文字と共に入力される最終文字フラグは最終文字フラグと共に入力される文字を含むトークンが出力される時に、並行して出力される。
【００７０】
その後、以前に設定された認知モデルを削除する(T147)。ここでT145の判定が偽であればT146およびT147は実行されない。なお、T145にて判定される開始文字とは認知モデルの開始を指示する区切り子であり、XMLではタグの開始を意味する"<"、処理命令の開始を意味する"<!"、コメントの開始を意味する"<--"などが開始文字に該当する。但し、本実施例においては文字参照・実体参照の開始文字（XMLでは"&"）は含まれない。
【００７１】
続けて、pSに当該開始文字の認知モデルをバッファし(T148)、これから作成する予定のトークンの種別を識別するために使用されるトークン種別をpSが指すSの要素に設定する(T149)。
【００７２】
その後、特殊要素判定部224は、入力されたトークン情報が通知要素情報176に該当するかどうかを判断し(T151)、T151が真であれば割込み管理部114に割込み発行を依頼し、割込み管理部114は割込みを発行(T152)、CPU101からの割込み解除を待つ（T153）。T151が偽であれば、T152〜T153は実行されない。その後、T144にて受信した制御信号に最終文字フラグが含まれているかを判定し(T154)、T154が真であれば終了(T155)、T154が偽であればT143に戻る。なお、本実施例では説明を容易にするため、T153の後にT154を実行するよう記述しているが、字句解析オートマトン220と特殊要素判定部224および割込み管理部114は並列に動作しても良い。
【００７３】
T143にて受信する文字が開始文字でなく終了文字である場合(T150)、A(図11)を、T150が偽であればB(図12)を実施する。ここで終了文字とは、認知モデルの終了を指示する区切り子であり、XMLではタグの終了を意味する">"、マーク宣言の終了を意味する"]]"、コメントの終了を意味する"-->"などが終了文字に該当する。但し、本実施例においては文字参照・実体参照の開始文字（XMLでは";"）は含まれない。Aではトークンバッファに格納されるトークン情報を出力し(T146)、以前に設定された認知モデルを削除する(T147)。
【００７４】
入力文字が開始文字でも終了文字でもない場合、トークンバッファ202に保持されているトークン情報を更新すべく、トークンを構成する文字列情報に入力文字を追加する（T170）。Bでは、T143受信文字が参照文字の開始区切り子かを判定し(T160)、トークンバッファが空であるかどうかをチェックし(T145)、T145〜T147を実施する。その後、pSに参照文字トークンを意味する種別を設置する(T162)。
【００７５】
T160が偽でありT143の入力文字が参照文字の終了文字であれば(T165)、字句解析オートマトン220は参照文字解決部223へ入力文字を引数として該当参照文字の先頭アドレスを要求し(T163)、参照文字解決部223は入力制御部111に参照テーブル150を要求し、字句解析オートマトン220から入力される文字列が参照テーブル150のいずれかの要素に該当すれば、字句解析オートマトン220に該当要素の先頭アドレスを渡す(T164)。字句解析オートマトン220は、T164で受け取った参照実体を指すアドレスをトークンバッファ222に書き込み、特殊要素判定部224へ出力し(T146)、以前に設定された認知モデルを削除し(T147)、Cに戻る。
【００７６】
T165が偽である場合、トークンを構成する文字列を更新すべくトークンバッファ222に入力文字を追記する。
【００７７】
なお、T155の時点でトークンバッファが空でない場合の処理は特に規定しない。トークンバッファに格納したまま、次のディスクリプタの処理を続けても、トークンバッファのデータを一旦T146と同様に不完全なトークンとして出力し、次のディスクリプタの処理へ進んでも良い。
【００７８】
続けて、図13を用いて構文解析部113の説明を行う。構文解析部113は構文解析オートマトン230と親ノードバッファ231と兄弟ノードバッファ232と現在生成中のノードをバッファする生成ノードバッファ233で構成される。構文解析オートマトン230は字句解析と入力方向を接続し、また入出力制御部111と出力方向が接続される。構文解析オートマトン230は字句解析部122より入力されるトークンデータと、ノードバッファ231、232に保持されるノード情報を引数にノードを生成し入出力制御部111に出力する。
【００７９】
親ノードバッファ231は現在解析中のノードの親に当たるノードに関する情報を格納する。親ノードバッファ231に格納すべきデータは特に規定しないが、例えば、木構造データバッファ160内の親ノードが格納されるアドレスが該当し、処理を効率化するために親ノードのコピー情報を格納しても良い。兄弟ノードバッファ232は現在解析中のノードの兄に当たる兄弟ノードに関する情報を格納する。兄弟ノードバッファ232に格納すべきデータは特に規定しないが、例えば、木構造データバッファ160内の兄弟ノードが格納されるアドレスが該当し、処理を効率化するために兄弟ノードのコピー情報を格納しても良い。
【００８０】
生成ノードバッファ233は名の通り、現在生成中のノードを一時格納するためのバッファである。
【００８１】
続けて、図14を用いて構文解析部113の処理フローを説明する。なお、図14は本実施例の本質に関係のないことから、エラーケースを考慮していない。まず、XML文書処理装置10の起動時など、初期化が必要であれば(T171)、親ノードバッファ231(以下Pとする)と兄弟ノードバッファ232(以下Bとする)を初期化する(T172)。
【００８２】
字句解析部112より入力されるトークンを受信し(T173)、受信トークンが開始トークンか(T174)、終了トークンか(T180)を判断する。なお、開始トークンは開始区切り子を契機に生成されたトークンを意味しており、同様に終了トークンは終了区切り子を契機に生成されたトークンを意味している。そして、本実施例では処理が同一であることから、実体参照および文字参照を示すトークンは開始トークンに属す。
【００８３】
T174が真である場合、構文解析部113はT173にて受信したトークンからノードを生成し、入出力制御部111に出力する(T175)。なお、T175で作成可能なノード情報は、ノード種類180と文字列先頭アドレス181と参照文字列先頭アドレス182と文字列長183と空白の子ノード接続情報184と空白の兄弟ノード接続情報185である。ここで、トークンと同様に、文字参照もしくは実体参照でないノードは参照文字列先頭アドレス182を持つ必要がなく、文字参照もしくは実体参照のノードは文字列先頭アドレス181を持つ必要はない。
【００８４】
続けて、PがNULLでなければ(T176)、親ノードバッファ231の情報を参考に、Pの指す親ノードを取得し(T177)、親ノードの子ノード接続情報184にT175にて生成したノードへの接続情報を書き込む(T178)。なお、子ノード接続情報184にはT175にて生成したノードを一意に特定できる情報であれば特に規定しない。その後、PをT175にて生成したノードに更新する(T179)。なおT76が偽であればT177およびT178は処理されない。
【００８５】
その後、T173にて受信したトークンと同タイミングで取得された制御信号が最終文字フラグを含むか判定し(T187)、T187が真であれば終了(T189)、偽であればT173へ戻る。
【００８６】
T174が偽でT180が真であれば、構文解析部113はT173にて受信したトークンからノードを生成し、入出力制御部111に出力する(T181)。なお、T181で作成可能なノード情報は、ノード種類180と文字列先頭アドレス181と参照文字列先頭アドレス182と文字列長183と空白の子ノード接続情報184と空白の兄弟ノード接続情報185である。ここで、トークンと同様に、文字参照もしくは実体参照でないノードは参照文字列先頭アドレス182を持つ必要がなく、文字参照もしくは実体参照のノードは文字列先頭アドレス181を持つ必要はない。
【００８７】
続けて、BがNULLでなければ(T182)、兄弟ノードバッファ232の情報を参考に、Bの指す兄弟ノードを取得し(T183)、兄弟ノードの兄弟ノード接続情報185にT181にて生成したノードへの接続情報を書き込む(T184)。なお、兄弟ノード接続情報185にはT181にて生成したノードを一意に特定できる情報であれば特に規定しない。その後、BをNULLとし、T187に進む。
【００８８】
T180が偽であれば構文解析部113はT173にて受信したトークンからノードを生成し、入出力制御部111に出力する(T186)。なお、T186で作成可能なノード情報は、ノード種類180と文字列先頭アドレス181と参照文字列先頭アドレス182と文字列長183と空白の子ノード接続情報184と空白の兄弟ノード接続情報185である。ここで、トークンと同様に、文字参照もしくは実体参照でないノードは参照文字列先頭アドレス182を持つ必要がなく、文字参照もしくは実体参照のノードは文字列先頭アドレス181を持つ必要はない。
【００８９】
続けて、BがNULLでなければ(T187)、兄弟ノードバッファ232の情報を参考に、Bの指す兄弟ノードを取得し(T188)、兄弟ノードの兄弟ノード接続情報185にT186にて生成したノードへの接続情報を書き込む(T189)。なお、兄弟ノード接続情報185にはT186にて生成したノードを一意に特定できる情報であれば特に規定しない。その後BにT186にて生成したノードを設定し(T190)、T187へ進む。
【００９０】
続けて、図15を用いて割込み管理部114の説明を行う。割込み管理部114は動作制御部240と割込み状態レジスタ241で構成される。動作制御部240は処理制御部110および字句解析部112間で割込み要求および割込み種別を受け、割込み終了を通知する信号で結線される。また、CPU101とも処理終了割込みおよび特殊要素通知割込みに関して、複数本の割込み要求信号と割込み要求信号と対となる複数本の割込み終了通知信号で結線される。
【００９１】
動作制御部240は処理制御部110もしくは字句解析部112からの割込み要求を受け、割込み状態レジスタ241を更新し、つまり、割込み要求に応じて割込み状態レジスタ241の対応する一部をアクティブにし、CPU101へ割込みを発行する。また、CPU101からの割込み終了通知を受け、割込み状態レジスタ241の対応する一部をネガティブにし、対応する終了通知を処理制御部110もしくは字句解析部112に送信する。
【００９２】
続けて、図16を用いてXML文書処理制御部121の説明を行う。XML文書処理制御部121はディスクリプタリング管理部250と割込みハンドラ252で構成される。ディスクリプタリング管理部250はXMLアプリケーション120の処理依頼を受け、ディスクリプタを作成し、ディスクリプタリング130の適切な領域に配置する、もしくはXMLアプリケーション120からディスクリプタを受信しディスクリプタリング130の適切な領域に配置する。具体的に、ディスクリプタ設置時点で有効フラグ171が有効なディスクリプタの次の領域に配置する。なお、ディスクリプタリング130をリング構成とする場合、リングの最終に最後の有効フラグ171が有効なディスクリプタがあればディスクリプタリング130の先頭に配置する。
【００９３】
XMLアプリケーションは、必ずしも含む必要はないがXML文書処理部100が処理を終了した時に処理すべきハンドラであるアプリケーション処理終了割込みハンドラ253と、XMLアプリケーション120が指定する要素をXML文書処理部100が発見した場合に処理すべきハンドラであるアプリケーション特殊要素割込みハンドラ254を含む。
【００９４】
割込みハンドラ252はXML文書処理部100から発行される割込み要求を受け起動し、XMLアプリケーション120への通知やディスクリプタの出力先アドレスの修正を行う。
【００９５】
以降、図17〜図19を用いて、XML文書処理制御部121の処理フローを説明する。第一に、図17を用いてXML文書処理部100から発行される割込み要求の処理フローを説明する。まずXMLアプリケーション120がディスクリプタnをXML文書処理制御部121に送信し(T300)、処理開始要求を発行する(T301)。XML文書処理制御部121はXML文書処理部100に処理開始要求を発行し(T302)、XML文書処理部100は上記で述べた処理を実行する(T303)。XMLアプリケーション120がディスクリプタの通知要素情報176にて指定する特殊要素をXML文書処理部100が発見した場合、特殊要素発見を通知する割込みを発行する(T305)。割込みハンドラ252はXMLアプリケーションがアプリケーション特殊要素割込みハンドラ254を含む場合、さらに、アプリケーション特殊要素割込みハンドラ254を事前にXML文書処理制御部121に通知している場合、アプリケーション特殊要素割込みハンドラ254を実行する(T306)。
【００９６】
XML文書処理部100はT303終了後に、処理終了通知割込みを発行する(T307)。先ほどと同様に、割込みハンドラ252はXMLアプリケーションがアプリケーション処理終了割込みハンドラ253を含む場合、さらに、アプリケーション処理終了割込みハンドラ253を事前にXML文書処理制御部121に通知している場合、アプリケーション処理終了割込みハンドラ253を実行する(T308)。
【００９７】
続けて図18を用いて、ディスクリプタリング管理部250と割込みハンドラ252の連携によるディスクリプタ単位の出力結果連続配置を可能にする処理フローの説明を行う。まず、XMLアプリケーション120は出力先先頭アドレス174に木構造データバッファ161の先頭アドレスを記述したディスクリプタnを送信する(T310)。なお、本実施例では説明を容易にするためにT310にてディスクリプタnの出力先先頭アドレス174を木構造データバッファ161の先頭アドレスに設定したが、これに限定しない。
【００９８】
続けてXMLアプリケーション120は処理開始要求を発行し(T310)、T310を受けXML文書処理制御部121はXML文書処理部100に処理開始要求を発行する(T312)。XML文書処理部100は処理を実行し(T313)、処理終了通知割込みを発行する(T314)。割込みハンドラ252はT314を受け、XMLアプリケーション120がアプリケーション処理終了割込みハンドラ253を含む場合、さらに、アプリケーション処理終了割込みハンドラ253を事前にXML文書処理制御部121に通知している場合、アプリケーション処理終了割込みハンドラ253を実行する(T315)。
【００９９】
その後、割込みハンドラ252はディスクリプタnの出力先アドレス174(以下アドレス)とディスクリプタnの生成ノード数(以下オフセット)をバッファする(T316)。T316の後に、XMLアプリケーション120は出力先先頭アドレス174に任意のアドレスを記述したディスクリプタn+1を送信する(T317)。XML文書処理制御部121のディスクリプタリング管理部250はT316でバッファしたアドレスとオフセットの加算結果をディスクリプタn+1の出力先アドレス174に代入する(T318)。そしてT318にて更新されたディスクリプタn+1の処理をXML文書処理部100が実行することで(T319)、ディスクリプタn+1の出力結果である木構造データは、ディスクリプタnの出力結果である木構造データの次の領域から連続して配置される。
【０１００】
なお、T316で直前のディスクリプタのアドレスとオフセットを別々に保持せずに、アドレスとオフセットの加算結果を保持しても良い。また、直前のディスクリプタのアドレスとオフセットを保持せず、ディスクリプタリング130に格納された実施済みのディスクリプタの情報からアドレスとオフセットを抽出することができるが、推奨しない。ディスクリプタリングはXMLアプリケーション120からの処理依頼を常に受け付ける状態にしておく、つまりディスクリプタリングに空きがある状態としていることが好ましいが、そのような実装形態では割り込みハンドラ252がアドレスとオフセットを抽出する前に、未処理のディスクリプタで上書きされてしまう可能性があるためである。
【０１０１】
また、図18と異なり、XML文書処理部100が処理中にXMLアプリケーション120がディスクリプタを設置する場合も処理の流れは同様である。図19に左記の状況の処理フローを示すが、本明細書での説明は省略する。
【０１０２】
上述の構成により、第一に図28のノード構成に対して、構文解析部113から出力されるノードのデータサイズを削減できるため、信号線103を経由してXML文書処理部100から木構造データバッファ160に構文解析部113が生成したノードを転送する時間が低減する。それゆえ、XML文書処理部100の処理性能を統合的に向上させることができる。また、木構造データバッファ160の容量を削減できる。さらに、本効果はXML文書に依存しないため、未知のXML文書を含むあらゆるXML文書の字句・構文解析が可能である。
【０１０３】
第二に、ディスクリプタ0木構造データ161〜ディスクリプタs-1木構造データ164を連続して配置することができるため、メモリ断片化による性能劣化を回避できる。
【０１０４】
第三に、たとえXML文書処理部100がディスクリプタの処理中であっても、XMLアプリケーション120が指定する特殊要素を字句解析部112が発見次第に、XML文書処理制御部121を経由してXMLアプリケーション120は特殊要素を参照でき、結果、XMLアプリケーション120は低レスポンスに特殊要素に関連した処理を行うことが可能となる。
【実施例２】
【０１０５】
以下、図面を用いて本発明の第二の実施形態を説明する。なお、全図に示す同一の番号は同一の機能を持つため説明を省略する。また、本実施例の説明は実施例1の差分の説明とする。
【０１０６】
図20は、図1の入出力制御部111と異なり、入出力制御部300が割込み管理部301と接続されている点、図1の割込み管理部114と異なり、割込み管理部301からCPU101で動作するXML文書処理制御部302に接続される割込み線が1本に統合されている。
【０１０７】
また、図21に示すメモリマップにおいて、図2の文字列先頭アドレス181を文字列オフセット310としている。つまり、XML文書処理部100の出力する木構造データを構成するノードに関して、ノードを構成する文字列がXML文書140のどこに格納されているかが判断できる情報であれば特に規定しない。
【０１０８】
図22は入出力制御部300の詳細を示している。入出力制御部111と異なるのは、左記に説明したように、割込み管理部301と接続されている点である。また、図23は割込み管理部301の詳細を示しており、割込み管理部114との相違点は処理終了割込みレジスタ321と特殊要素割込みレジスタ322が追加され、さらに、入出力制御部300と接続していることである。
【０１０９】
処理終了割込みレジスタ321は、処理制御部110から発行される割込み要求時に割込み種別を記憶しておくレジスタであり、特殊要素割込みレジスタ322は字句解析部112から発行される割込み要求時にどの特殊要素が発見されたかを記憶しておくレジスタである。321322共に、CPU101からの割込み終了通知信号により、対応する情報をクリアする。
【０１１０】
これは割込み管理部301からXML文書処理制御部302に発行される割込み線の本数が実施例1と異なり、複数種別の割込みが統合されたため、XML文書処理制御部302は割込み検知後、XML文書処理部100にどの割込みなのかを確認する必要がある。そこで、入出力制御部300はXML文書処理制御部302の割込み確認要求を受け、割込み管理部301にどの割込みが発生しているのかを問い合わせ、割込み管理部301は、321および322を参照し、割込みの種別を応答、順次XML文書処理制御部302まで応答する。以上のフローを図25に示す。
【０１１１】
本実施例により、XML文書処理部100に費やすCPUの割込み用ピン数を削減できる。
【符号の説明】
【０１１２】
10：XML文書処理装置
100：XML文書処理部
101：CPU
102：第一外部記憶
103：バスなどの内部信号線
110：処理制御部
111：入出力制御部
112：字句解析部
113：構文解析部
114：割込み管理部
120：XMLアプリケーション
121：XML文書処理制御部
130：ディスクリプタリング
131：ディスクリプタ0
132：ディスクリプタs-1
140：XML文書
150：参照文字テーブル
160：木構造データバッファ
161：ディスクリプタ0木構造データ
162：ノード0
163：ノードt-1
164：ディスクリプタs-1木構造データ
170：制御情報
171：有効フラグ
172：文字列先頭アドレス
173：文字列長
174：出力先先頭アドレス
175：生成ノード数
176：通知要素情報
180：ノード種類
181：文字列先頭アドレス
182：参照文字列先頭アドレス
183：文字列長
184：子ノード接続情報
185：兄弟ノード接続情報
200：処理制御部内動作制御部
201：制御レジスタ
202：ディスクリプタレジスタ
210：入出力制御部内動作制御部
211：データバッファ
212：文字列カウンタレジスタ
213：ノードカウンタレジスタ
220：字句解析オートマトン
221：認知モデルスタック
222：トークンバッファ
223：参照文字解決部
224：特殊要素判定部
230：構文解析オートマトン
231：親ノードバッファ
232：兄弟ノードバッファ
233：生成ノードバッファ
240：割込み管理部内動作制御部
241：割込み状態レジスタ
250：ディスクリプタリング管理部
252：割込みハンドラ
253：アプリケーション処理終了割込みハンドラ
254：アプリケーション特殊要素割込みハンドラ
300：入出力制御部
301：割込み管理部
302：XML文書処理制御部
310：入出力制御部内動作制御部
320：割込み管理部内動作制御部
321：処理終了割込みレジスタ
322：特殊要素割込みレジスタ
330：割込みハンドラ
【図１】
2011100234.tif 000003
【図２】
2011100234.tif 000004
【図３】
2011100234.tif 000005
【図４】
2011100234.tif 000006
【図５】
2011100234.tif 000007
【図６】
2011100234.tif 000008
【図７】
2011100234.tif 000009
【図８】
2011100234.tif 000010
【図９】
2011100234.tif 000011
【図１０】
2011100234.tif 000012
【図１１】
2011100234.tif 000013
【図１２】
2011100234.tif 000014
【図１３】
2011100234.tif 000015
【図１４】
2011100234.tif 000016
【図１５】
2011100234.tif 000017
【図１６】
2011100234.tif 000018
【図１７】
2011100234.tif 000019
【図１８】
2011100234.tif 000020
【図１９】
2011100234.tif 000021
【図２０】
2011100234.tif 000022
【図２１】
2011100234.tif 000023
【図２２】
2011100234.tif 000024
【図２３】
2011100234.tif 000025
【図２４】
2011100234.tif 000026
【図２５】
2011100234.tif 000027
【図２６】
2011100234.tif 000028
【図２７】
2011100234.tif 000029
【図２８】
2011100234.tif 000030