JP5338487B2 - 構文解析装置、構文解析方法、及びプログラム - Google Patents

Description

本発明は、マークアップ言語で記述されたテキストを構文解析する技術に関する。

テキストファイルに、文章とともに、その文章の構造やデザイン、レイアウトなどを記述するための言語としてマークアップ言語が知られている。このマークアップ言語では、文章の構造やレイアウトなどがタグと呼ばれる文字列で指定される。

このマークアップ言語の使用例として、コンピュータ間の相互通信時には、ＸＭＬ(Extensible Markup Language)形式で情報をやりとりする場面が増えている。

ＸＭＬの文法は非特許文献１で規定されている。ＸＭＬでは、用途に応じてタグの種類を自在に規定することができるため、さまざまなアプリケーション分野でコンピュータ間通信の記述形式として用いられる。

また、ウェブブラウザで閲覧するウェブページを記述するために広く用いられているＨＴＭＬ(Hyper Text Markup Language)も、ＸＭＬ同様、マークアップ言語である。ＨＴＭＬでは、非特許文献２に記載されているように、タグの種類が予め規定されている。

マークアップ言語で記述されたテキストをコンピュータ内で処理する際は、コンピュータは、そのテキストをコンピュータが扱いやすい内部形式に変換した上で保持してから処理を開始する。この内部形式として、一般にツリー状のデータ構造がよく用いられる。

マークアップ言語で使用されるタグは、＜ＡＡ＞・・・＜／ＡＡ＞のように開始タグと終了タグの対になっており、この対は入れ子にすることができる。タグの対の入れ子関係を親子関係とみれば、テキスト全体のタグ構造はツリー形式で表現できる。コンピュータ内で、内部形式がツリー構造のデータとして保持されることが多いのはそのためである。

マークアップ言語で記述されたテキストをコンピュータが読み込み、コンピュータ内部形式に変換する処理を、パージング（Ｐａｒｓｉｎｇ）と呼ぶ。ＸＭＬ形式で、互いにデータを送受信するコンピュータシステムや、ＨＴＭＬを扱うウェブブラウザでは、このパージングは必要不可欠な処理である。

ところで、近年では、コンピュータ内で演算処理をつかさどるＣＰＵ（Central Processing Unit中央演算処理ユニット）の処理クロックの高速化は頭打ちであり、複数のＣＰＵを使った並列処理によりシステム全体の処理能力を高める方式が注目されている。マークアップ言語のパージングを並列処理により高速化することができれば、今後いっそうの普及が見込まれるマルチＣＰＵやマルチコア（以下単に複数ＣＰＵと記す）を用いたシステムにおいて、その並列処理能力を十分に引き出し、システム全体の高速化に寄与できると考えられる。

パージングは、入力されたテキストを先頭から順に読みながら解析する処理であるため、そのままでは本質的に逐次処理である。複数のＣＰＵを利用してパージングする場合、逐次処理を並列化して処理するための工夫が必要となる。

非特許文献３では、前処理と本処理の二段構成による方式を論じている。まず、コンピュータは、前処理として、テキストを解析してツリー構造だけを求める。後段の本処理では、コンピュータは、このツリー構造に基づいて、テキストをいくつかの部分に分解し、分解した各部を複数ＣＰＵによって並列処理する。コンピュータは、前処理では、詳細な字句解析を省略し、データ構造の解析に限定するので、高速に処理できる。このように、比較的処理時間がかかる本処理部を並列処理することで、全体としてパージング処理性能を高めることができる。

非特許文献４では、非特許文献３の方式を更に改良し、前処理におけるタグ対応関係の解析をも並列処理できる方式を述べている。非特許文献４に記載された発明は、前処理部で字句解析に用いられる状態遷移機械を変形することで、コンピュータがテキスト中の任意部分からの字句解析を開始することを可能にしている。このため、コンピュータは、入力されたテキストを複数の断片に分割し、それらに対して並列に字句解析を行うことができる。その後、コンピュータは、解析結果を突き合わせて、それらを先頭から順につなぐ。このようにして前処理部全体の処理が完了する。

特許文献１には、複数のパージング処理部を用意しておき、ある一つのパージング処理部で入力テキストの構文解析中にパージング不能な入力に遭遇すると、別のパージング処理部に処理を依頼する方式が記載されている。

特開平１１―６５８５３号公報

ワールドワイドウェブコンソーシアム（Ｗ３Ｃ），Ｅｘｔｅｎｓｉｂｌｅ Ｍａｒｋｕｐ Ｌａｎｇｕａｇｅ（ＸＭＬ）１．０，Ｗ３Ｃ Ｒｅｃｏｍｍｅｎｄａｔｉｏｎ ２６ Ｎｏｖｅｍｂｅｒ ２００８ Ｄ．Ｒａｇｇｅｔｔ／Ｗ３Ｃ，"Ｇｅｔｔｉｎｇ ｓｔａｒｔｅｄ ｗｉｔｈ ＨＴＭＬ"，http://www.w3.org/MarkUp/Guide/，２００５ Ｗ．Ｌｕ他， "Ａ Ｐａｒａｌｌｅｌ Ａｐｐｒｏａｃｈ ｔｏ ＸＭＬ Ｐａｒｓｉｎｇ"， ７ｔｈ ＩＥＥＥ／ＡＣＭ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｇｒｉｄ Ｃｏｍｐｕｔｉｎｇ，２００６ Ｙｉｎｆｅｉ Ｐａｎ他， "Ｓｉｍｕｌｔａｎｅｏｕｓ ｔｒａｎｓｄｕｃｅｒｓ ｆｏｒ ｄａｔａ−ｐａｒａｌｌｅｌ ＸＭＬ ｐａｒｓｉｎｇ"， ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｐａｒａｌｌｅｌ ａｎｄ Ｄｉｓｔｒｉｂｕｔｅｄ Ｐｒｏｃｅｓｓｉｎｇ，２００８

しかし、非特許文献３、４や、特許文献１に開示された技術では、パージング処理を並列化しても処理性能が十分 に向上しない場合があった。

非特許文献３に記載されたコンピュータでは、前処理が完了してからでないと、本処理を開始できない。このため、このコンピュータでは、テキストを入力してから、ツリーが出力されるまでのレイテンシが長くなってしまう。

非特許文献４に記載されたコンピュータでは、前処理自体において、並列に行われた解析結果を突き合わせて、テキスト全体に対する正しいデータ構造を得る作業が必要である。このつき合わせ作業が完了するまでは、コンピュータは本処理が開始できず、本処理が開始されないとツリーも生成されない。このため、この方式でもレイテンシが長いという問題が生じる。

特許文献１に開示された方式では、テキスト内で同じ文法しか使用されない場合は、並列処理が全く行われず、スループットが向上しない。

本発明は、マークアップ言語の構文解析において、並列化により、文法に関わらず、スループットおよびレイテンシを向上することを目的とする。

上記目的を達成するために、本発明の構文解析装置は、割り当てられたリソースを使用して、マークアップ言語で記述されたテキストを順次、字句解析していき、該テキストにおけるタグの位置を取得するタグ位置取得手段と、前記タグ位置取得手段による前記字句解析と並行して、割り当てられたリソースを使用して、該字句解析が終わっている部分のうち、前記タグ位置取得手段により取得された前記タグの位置で区切られた前記テキストのそれぞれの部分を並列に構文解析する並列解析手段と、前記タグ位置取得手段による前記字句解析の処理速度をできるだけ速くし、前記テキストにおける、該字句解析が終わり、前記構文解析手段による前記構文解析が終わっていない部分の文字数を所定の範囲内にするように、前記タグ位置取得手段に割り当てるリソース量と前記並列解析手段に割り当てるリソース量とを調整する調整手段と、を有する。

本発明の構文解析方法は、タグ位置取得手段が、割り当てられたリソースを使用して、マークアップ言語で記述されたテキストを順次、字句解析していき、該テキストにおけるタグの位置を取得し、並列解析手段が、前記タグ位置取得手段による前記字句解析と並行して、割り当てられたリソースを使用して、該字句解析が終わっている部分のうち、前記タグ位置取得手段により取得された前記タグの位置で区切られた前記テキストのそれぞれの部分を並列に構文解析し、調整手段が、前記テキストにおける、前記タグ位置取得手段により前記字句解析が行われている位置から、前記並列解析手段により前記構文解析が行われている位置を引いた値が、正の値で所定の範囲内であり、且つ前記構文解析の処理速度ができるだけ速くなるように、該タグ位置取得手段と該並列解析手段とに割り当てるリソースの割合を調整する、構文解析方法である。

本発明のプログラムは、コンピュータに、割り当てられたリソースを使用して、マークアップ言語で記述されたテキストを順次、字句解析していき、該テキストにおけるタグの位置を取得するタグ位置取得手順、前記タグ位置取得手順における前記字句解析と並行して、割り当てられたリソースを使用して、該字句解析が終わっている部分のうち、前記タグ位置取得手順で取得された前記タグの位置で区切られた前記テキストのそれぞれの部分を並列に構文解析する並列解析手順、及び前記タグ位置取得手順における前記字句解析の処理速度をできるだけ速くし、前記テキストにおける、該字句解析が終わり、前記構文解析手順における前記構文解析が終わっていない部分の文字数を所定の範囲内にするように、前記タグ位置取得処理に割り当てるリソース量と前記並列解析処理に割り当てるリソース量とを調整する調整手順、を実行させるためのプログラムである。

本発明によれば、構文解析装置は、テキストを字句解析してタグの位置を取得し、並行して、タグで区切られたそれぞれの部分を並列に構文解析し、字句解析と構文解析とに割り当てるリソース量を調整する。構文解析装置は、タグ位置に基づいて並列解析するので、文法に関わらずに並列解析でき、スループットが向上する。また、構文解析装置は、字句解析、構文解析を並行して行い、字句解析において各部分の解析結果を突き合わせる必要がないので、レイテンシが小さくなる。

本発明の第１の実施形態の構文解析装置の一構成例を示すブロック図である。 本発明の第１の実施形態のＸＭＬテキストの一例である。 本発明の第１の実施形態の字句解析部の状態遷移図である。 本発明の第１の実施形態のタグ一時記憶部の一構成例を示す図である。 本発明の第１の実施形態の先行解析表の一例である。 （ａ）本発明の第１の実施形態の構文解析方法を説明するための図である。（ｂ）本発明の第１の実施形態のＸＭＬツリーの一例を示す図である。 本発明の第１の実施形態の構文解析装置の動作を示すシーケンス図である。 本発明の第１の実施形態の要素構文解析処理を示すフローチャートである。 本発明の第１の実施形態の粒度推定処理を示すフローチャートである。 本発明の第１の実施形態の例外処理を示すフローチャートである。 本発明の第１の実施形態の主パージングの動作を示すシーケンス図である。 （ａ）本発明の第１の実施形態のパージングの進度の一例を示す図である。（ｂ）本発明の第１の実施形態のタグ一時記憶部内の位置情報の一例を示す図である。（ｃ）本発明の第１の実施形態の先行解析表の記載内容の一例を示す図である。（ｄ）本発明の第１の実施形態のＸＭＬツリーの一例を示す図である。 （ａ）本発明の第１の実施形態のパージングの進度の一例を示す図である。（ｂ）本発明の第１の実施形態のタグ一時記憶部内の位置情報の一例を示す図である。（ｃ）本発明の第１の実施形態の先行解析表の記載内容の一例を示す図である。（ｄ）本発明の第１の実施形態のＸＭＬツリーの一例を示す図である。 （ａ）本発明の第１の実施形態のパージングの進度の一例を示す図である。（ｂ）本発明の第１の実施形態のタグ一時記憶部内の位置情報の一例を示す図である。（ｃ）本発明の第１の実施形態の先行解析表の記載内容の一例を示す図である。（ｄ）本発明の第１の実施形態のＸＭＬツリーの一例を示す図である。 （ａ）本発明の第１の実施形態のパージングの進度の一例を示す図である。（ｂ）本発明の第１の実施形態のタグ一時記憶部内の位置情報の一例を示す図である。（ｃ）本発明の第１の実施形態の先行解析表の記載内容の一例を示す図である。 本発明の第１の実施形態のＸＭＬツリーの一例を示す図である。 （ａ）本発明の第１の実施形態のパージングの進度の一例を示す図である。（ｂ）本発明の第１の実施形態のタグ一時記憶部内の位置情報の一例を示す図である。（ｃ）本発明の第１の実施形態の先行解析表の記載内容の一例を示す図である。 本発明の第１の実施形態のＸＭＬツリーの一例を示す図である。 （ａ）本発明の第１の実施形態のパージングの進度の一例を示す図である。（ｂ）本発明の第１の実施形態のタグ一時記憶部内の位置情報の一例を示す図である。（ｃ）本発明の第１の実施形態の先行解析表の記載内容の一例を示す図である。 本発明の第１の実施形態のＸＭＬツリーの一例を示す図である。 本発明の第１の実施形態のパージングの進度の一例を示す図である。 本発明の第１の実施形態のＸＭＬツリーの一例を示す図である。 本発明の第２の実施形態の構文解析装置の一構成例を示すブロック図である。 本発明の第２の実施形態の先行パージング部の一構成例を示すブロック図である。 （ａ）本発明の第２の実施形態の先行パージングの進度の一例を示す図である。（ｂ）本発明の第２の実施形態の主タグ一時記憶部内の位置情報の一例を示す図である。（ｃ）本発明の第２の実施形態の副タグ一時記憶部内の位置情報の一例を示す図である。（ｄ）本発明の第２の実施形態の先行解析表の記載内容の一例を示す図である。 （ａ）本発明の第２の実施形態の先行パージングの進度の一例を示す図である。（ｂ）本発明の第２の実施形態の主タグ一時記憶部内の位置情報の一例を示す図である。（ｃ）本発明の第２の実施形態の副タグ一時記憶部内の位置情報の一例を示す図である。（ｄ）本発明の第２の実施形態の先行解析表の記載内容の一例を示す図である。 （ａ）本発明の第２の実施形態の先行パージングの進度の一例を示す図である。（ｂ）本発明の第２の実施形態の副タグ一時記憶部内の位置情報の一例を示す図である。 （ａ）本発明の第２の実施形態の先行パージングの進度の一例を示す図である。（ｂ）本発明の第２の実施形態の主タグ一時記憶部内の位置情報の一例を示す図である。（ｃ）本発明の第２の実施形態の副タグ一時記憶部内の位置情報の一例を示す図である。（ｄ）本発明の第２の実施形態の先行解析表の記載内容の一例を示す図である。 （ａ）本発明の第２の実施形態の先行パージングの進度の一例を示す図である。（ｂ）本発明の第２の実施形態の主タグ一時記憶部内の位置情報の一例を示す図である。（ｃ）本発明の第２の実施形態の先行解析表の記載内容の一例を示す図である。 （ａ）本発明の第２の実施形態の先行パージングの進度の一例を示す図である。（ｂ）本発明の第２の実施形態の主タグ一時記憶部内の位置情報の一例を示す図である。（ｃ）本発明の第２の実施形態の先行解析表の記載内容の一例を示す図である。 本発明の第３の実施形態の構文解析装置の一構成例を示すブロック図である。 本発明の第４の実施形態の構文解析装置の一構成例を示すブロック図である。

（第１の実施形態）
本発明を実施するための第１の実施形態について図面を参照して詳細に説明する。

図１は、本実施形態の構文解析装置１の一構成例を示すブロック図である。構文解析装置１は、入力されたＸＭＬテキストのデータ構造を解析する装置である。同図を参照すると、構文解析装置１は、入力部１０、先行パージング部１１、主パージング部１２、先行パージング実行論理ＣＰＵ１３、主パージング実行論理ＣＰＵ群１４、進度調整部１５、および出力部１６を有する。

入力部１０は、入力一時記憶部１０２を有する。入力部１０は、ＸＭＬで記述されたＸＭＬテキスト１０１を、入力一時記憶部１０２に読み込み、先行パージング部１１および主パージング部１２に入力する。入力部１０は、例えば、例えばＯＳ（Operating System）のファイルオープンシステムコールやネットワーク通信システムコールを用い、ＸＭＬテキスト１０１を入力一時記憶部１０２に読み込む。入力部１０は、ＸＭＬテキスト１０１の全部を読み込んでもよいし、パージングに必要な部分を含む範囲で、ＸＭＬテキスト１０１の一部だけを読み込んでもよい。

先行パージング部１１は、字句解析部１１１、タグ一時記憶部１１２、およびタグ対応登録部１１３、および先行パージング進捗情報１１４を有する。

先行パージング部１１は、新たにＸＭＬテキスト１０１の処理を始める際に、字句解析部１１１、タグ一時記憶部１１２、および先行パージング進捗情報１１４を初期化する。初期化により、字句解析部１１１は初期状態、すなわち、入力されたテキストの先頭位置から字句解析を開始する状態となる。

字句解析部１１１は、入力一時記憶部１０２に記憶されたＸＭＬテキスト１０１の先頭から順に文字を取得し、ＸＭＬ文法に沿った字句解析を行う。字句解析部１１１で使用されるＸＭＬ文法は、ＸＭＬ規格で規定されている開始タグと終了タグとを認識できる範囲に絞った、ＸＭＬ本来の文法の簡略版の文法である。この簡略版の文法については後述する。

また、字句解析部１１１は、ＸＭＬテキスト１０１中で、現在字句解析を行っている位置、すなわち字句解析の進度を示す情報を先行パージング進捗情報１１４として保持し、その値を適宜更新する。ここで、適宜更新の頻度は、字句解析手段１１１が入力一時記憶部１０２から文字を１つ取得するたびに更新するという頻度でもよいし、開始タグないし終了タグを発見するたびに更新する等の、やや低頻度の更新であってもよい。

字句解析部１１１は、字句解析において、開始タグを発見すると、その開始タグの位置を示す位置情報をタグ一時記憶部１１２に格納する。

ここで、開始タグの位置とは、ＸＭＬテキスト１０１において開始タグの出現位置を一意に特定するに足りる情報であって、例えば、テキストの先頭から文字単位に数えた、開始タグの先頭文字のオフセット（変位）値を位置として用いることができる。

字句解析部１１１は、字句解析において、終了タグを発見したとき、タグ一時記憶部１１２から、最後に格納された開始タグの位置情報を取り出す。取り出された位置情報は、タグ一時記憶部１１２から削除される。そして、字句解析部１１１は、取り出した位置情報の示す開始タグの位置と、発見した終了タグの位置との組を、引数としてタグ対応登録部１１３を呼び出し、この組をタグ対応登録部１１３に格納する。

ここで、終了タグの位置とは、ＸＭＬテキスト１０１において終了タグの出現位置を一意に特定するに足りる情報であって、例えば、テキストの先頭から文字単位に数えた、終了タグの最終文字のオフセット（変位）値を位置として用いることができる。

マーキング言語においては、開始タグ、文章、対応する終了タグの順で記述される。同じ属性の開始タグ、終了タグの組の間に、別の属性の開始タグ、終了タグの組を挿入することもできるが、文法上、同じ属性の開始タグ、終了タグの組の間に、別の属性の開始タグ、終了タグのいずれか一方のみが挿入されることはない。このため、複数の属性の開始タグ、終了タグが入れ子構造となっている場合、字句解析部１１１が、先頭から順に字句解析を行い、終了タグが出現したとき、その時点を基準として直近に出現した開始タグが、その終了タグと対になる開始タグに相当する。

従って、字句解析部１１１が、開始タグが出現するたびにタグ一時記憶部１１２に格納しておき、終了タグが出現した時点で、タグ一時記憶部１１２に最後に格納した開始タグの位置を取り出した場合、取り出した位置の開始タグが、出現した終了タグと対応するタグに該当することになる。

タグ一時記憶部１１２は、タグ一時記憶部１１２は、後入れ先出し（ＬＩＦＯ；Ｌａｓｔ−Ｉｎ−Ｆｉｒｓｔ−Ｏｕｔ）方式で開始タグの位置を示す位置情報を複数、記憶する。すなわち、時系列に沿って複数の位置情報がタグ一時記憶部１１２に記憶されているときに、字句解析部１１１が、そこから位置情報を１つ取り出すと、もっとも遅い時刻（直近）に記憶された位置情報が取り出される。字句解析部１１１が取り出し操作を行うと、取り出された情報はタグ一時記憶部１１２から削除される。タグ一時記憶部１１２は、例えば、スタック構造を用いて実現することができる。

タグ対応登録部１１３は、字句解析部１１１で求められた開始タグの位置と終了タグの位置との各組を、先行解析表１１３１に記載する。

先行解析表１１３１は、例えば、開始タグ位置をキーとし、それに対応する終了タグ位置を値とする連想記憶装置である。

ここで、開始タグの位置も、終了タグの位置も整数であるから、この連想記憶装置は、開始タグ位置の整数値を適当なハッシュ関数にかけ、その値をインデックス（添字）とする整数配列として、コンピュータ上に容易に実現することができる。

タグ対応登録部１１３は、字句解析部１１１により、一組の開始タグおよび終了タグの位置が引数として呼び出されると、開始タグの位置をキーとして先行解析表１１３１を検索する。該当するデータエントリが存在しなければ、タグ対応登録部１１３は、その開始タグの位置をキーとし、終了タグの位置を値とする新たなデータエントリを先行解析表１１３１に書き込む。

開始タグの位置をキーとする検索の結果、もし該当するデータエントリが既に存在すれば、タグ対応登録部１１３は、新たな登録は行わず、呼出元である字句解析部１１１にエラーを通知する。

図２に、ＸＭＬテキスト１０１の記載内容の一例を示す。同図に示すように、ＸＭＬテキスト１０１には、文章と、その文章の構造やレイアウトを指定するタグとが、記述される。同図においては、ＸＭＬテキスト１０１を、２０文字ごとに折り返し、５列ごと、５行ごとに点線で区切っている。２０文字ごとに折り返して記載しているのは読みやすさのためであり、ＸＭＬテキスト１０１は、２０文字ごとに改行されているとは限らない。

例えば、開始タグとして、「＜ＡＡ＞」、「＜ＢＢ＞」などが記述される。終了タグとして、「＜ＡＡ＞」に対応する「＜／ＡＡ＞」や、「＜ＢＢ＞」に対応する「＜／ＢＢ＞」などが記述される。これらの開始タグと終了タグとの間に、「ｔeｘｔ ｆоｒ ＢＢ」などの文章が記述される。

字句解析部１１１により、テキストの先頭を基準として、開始タグを構成する文字列のうち、「＜」の文字のオフセットが開始タグの位置として取得される。また、終了タグを構成する文字列のうち、「＞」の次の文字のオフセットが開始タグの位置として取得される。

例えば、開始タグ「＜ＡＡ＞」における「＜」の文字は、テキストの先頭の文字である。これに対応する終了タグ「＜／ＡＡ＞」における「＞」の次の文字は、テキストの先頭から数えて２２５番目の文字である。従って、タグ対応登録部１１３には、これらの開始タグ、終了タグの位置の組として、（０、２２５）の組が登録される。

ここで、字句解析部１１１の説明で言及した簡略版のＸＭＬ文法について説明する。この簡略版のＸＭＬ文法は、その文法に基づいて、字句解析部１１１が、開始タグと終了タグを認識できる範囲で、十分高速動作できるものが望ましい。また、簡略版の文法では、開始タグや終了タグの属性名（例えば、開始タグ”＜ＡＡ＞”における名前”ＡＡ”）の対応付けは無視してよい。その理由は、先行パージング部１１は、主パージング部１２の動作よりも十分先行してタグの対応関係を見つけ出す必要があるためである。また、主パージングにて正式なＸＭＬ解析を行うので先行パージングでは必ずしもタグの中身（属性）のチェックを行う必要が無いためである。

この簡略版の文法に基づき、字句解析部１１１は、例えば、図３に示す状態遷移図に従って動作する有限状態機械（有限オートマトン）で実現できる。同図において、初期状態は状態Ｓ１である。

状態Ｓ１において、字句解析した文字が、「ｓ」、「＞」、「／」、「！」、「’」、または「”」であれば、字句解析部１１１は、状態Ｓ１に遷移する。状態Ｓ１において、字句解析した文字が、「＜」であれば、字句解析部１１１は、状態Ｓ２に遷移する。

ここで、「ｓ」はＸＭＬ文法で定義される空白文字（スペース、復帰、改行、タブを表す文字のいずれか）である。

状態Ｓ２において、字句解析した文字が「ｓ」であれば、字句解析部１１１は、状態Ｓ２に遷移し、「／」であれば、字句解析部１１１は、状態Ｓ３に遷移する。また、状態Ｓ２において、字句解析した文字が「ｘ」であれば、字句解析部１１１は、開始タグ（「ｓｔａｒｔｔａｇ」）を発見したときの処理を行い、状態Ｓ４に遷移する。すなわち、開始タグの位置をタグ一時記憶部１１２に格納する。状態Ｓ２において、字句解析した文字が「！」であれば、字句解析部１１１は、状態Ｓ８に遷移する。

ここで、「ｘ」は「＜」、「＞」、「／」、「！」、「’」、「”」、および空白文字以外の有効文字である。

状態Ｓ３において、字句解析した文字が「ｘ」であれば、字句解析部１１１は、状態Ｓ３に遷移し、「＞」であれば、終了タグ（「ｅｎｄｔａｇ」）を発見したときの処理をし、状態Ｓ１に遷移する。すなわち、字句解析部１１１は、一時記憶部１１２から、開始タグの位置を読み出し、終了タグの位置とともに、タグ対応登録部１１３に格納する。

状態Ｓ４において、字句解析した文字が「ｘ」であれば、字句解析部１１１は、状態Ｓ４に遷移し、「＞」であれば、状態Ｓ１に遷移する。状態Ｓ４において、字句解析した文字が「／」であれば、字句解析部１１１は、状態Ｓ５に遷移し、「”」であれば、状態Ｓ６に遷移する。状態Ｓ４において、字句解析した文字が「’」であれば、字句解析部１１１は、状態Ｓ７に遷移する。

状態Ｓ５において、字句解析した文字が「＞」であれば、字句解析部１１１は、終了タグを発見したときの処理をし、状態Ｓ１に遷移する。

状態Ｓ６において、字句解析した文字が「ｓ」、「＞」、「／」、「！」、「’」、または「ｘ」であれば、字句解析部１１１は、状態Ｓ６に遷移し、「”」であれば、状態Ｓ４に遷移する。

状態Ｓ７において、字句解析した文字が「ｓ」、「＞」、「／」、「！」、「”」、または「ｘ」であれば、字句解析部１１１は、状態Ｓ７に遷移し、「’」であれば、状態Ｓ４に遷移する。

状態Ｓ８において、字句解析した文字が「ｓ」、「＜」、「／」、「！」、「’」、「”」、または「ｘ」であれば、字句解析部１１１は、状態Ｓ８に遷移し、「＞」であれば、状態Ｓ１に遷移する。

図４は、タグ一時記憶部１１２の一構成例を示す図である。同図に示すように、タグ一時記憶部１１２には、ＬＩＦＯ方式で、各開始タグの位置を示す位置情報が格納される。

例えば、タグ一時記憶部１１２に「＜ＡＡ＞」、「＜ＣＣ ｐ＝”ｆоо”＞」、「＜ＤＤ＞」の順で、これらの開始タグの位置情報が格納された状態について考える。字句解析部１１１が、このタグ一時記憶部１１２から位置情報を取り出す場合、最も遅くに格納された「＜ＤＤ＞」の位置情報が取り出され、その位置情報がタグ一時記憶部１１２から削除される。

図５は、先行解析表１１３１に記載される内容をまとめた表である。同図を参照すると、先行解析表１１３１には、開始タグの位置と、終了タグの位置とが対応付けて記載される。先行解析表１１３１の各行（データエントリ）に記載された値が、開始タグの位置と、そのタグに対応する終了タグの位置との組である。終了タグが出現した時点で、その終了タグの位置と、対応する開始タグの位置とが格納されるので、同図に示すように、各データエントリにおいて開始タグの位置、終了タグの位置は、必ず対になって記載され、いずれか一方のみが記載されることはない。

図５の先行解析表１１３１では、開始タグの位置の小さい順に、データエントリが並んでいる。しかし、これは、見やすさ、あるいは検索のしやすさのために整列したものであり、整列は必ずしも必要ではない。整列方法についても、開始タグの大きい順に整列するなど、任意の方法を使用できる。

次に、図１を参照して主パージングについて説明する。同図を参照すると、主パージング部１２は、構文解析部１２１、粒度推定部１２２、並列化部１２３、内部表現生成部１２４、および主パージング進捗情報１２５を有する。

主パージング部１２は、新しく入力ＸＭＬテキストの処理を始める際に、構文解析手段１２１、内部表現生成部１２４、および主パージング進捗情報１２５を初期化する。初期化により、構文解析部１２１は初期状態、すなわち入力されたテキストの先頭位置から解析を開始する状態となる。

主パージング実行論理ＣＰＵ群１４における論理ＣＰＵが、構文解析部１２１を呼び出し、構文解析部１２１は、ＸＭＬテキスト１０１の先頭から順にＸＭＬ文法に沿った構文解析を行う。構文解析部１２１による構文解析は、字句解析部１１１による字句解析と並行して行われる。

また、構文解析部１２１は、ＸＭＬテキスト１０１中で、現在構文解析を行っている位置を主パージング進捗情報１２５として保持し、その値を適宜更新する。

構文解析部１２１で使用されるＸＭＬ文法は、先行パージング部１１内の字句解析部１１１で用いられる簡略版文法ではなく、上記非特許文献１に記載されているＸＭＬ規格に沿った正式なＸＭＬ文法である。

コンピュータプログラミング言語の文法分類でみると、ＸＭＬ文法はＬＬ（１）文法に属する。ＬＬ（１）に属する文法は、ＢＮＦ（Backus-Naur Form）と呼ばれる形式で記述することができ、そのＢＮＦ記述から当該文法に対する構文解析プログラムを作成する標準的な手順が存在する。例えば、「中田育男，『コンパイラ』，産業図書，ＩＳＢＮ４−７８２８−５０５７−３， ５．４．３節から５．４．５節まで」（以下、「非特許文献５」という）にＬＬ（１）構文解析手順の作成法が説明されている。

上述したように、上記非特許文献１にはＸＭＬの各構文規則のＢＮＦ記述が記載されている。構文解析部１２１は、上記非特許文献１、５等に記載されたコンパイラ一般技術の説明とあわせた、ＸＭＬ文法の各構文規則に対するＬＬ（１）構文解析手順を利用することにより、ＸＭＬ文法全体に関する構文解析を行う。

ここで、単一ＣＰＵ向けＸＭＬ構文解析における、非終端記号「要素（ｅｌｅｍｅｎｔ）」の構文解析手順について説明する。上記非特許文献１を参照すると、ＸＭＬ文法における非終端記号「要素」の構文規則は下記に示すようなＢＮＦで定義されている。

（ＸＭＬにおける要素の構文規則）
element::＝EmptyElemTag
|STag content ETag
ここで、「element」は「要素」であり、「EmptyElemTag」は、「空き要素タグ」である。「STag」は、「開始タグ」であり、「content」は、「要素の内容」であり、「ETag」は、「終了タグ」である。

このＢＮＦは、ＸＭＬ文法上、「要素」の概念には、「空き要素タグ」が含まれること、また、「要素」の概念には、「開始タグ」、「要素の内容」、「終了タグ」を順にならべたものが含まれることを意味している。

構文解析部１２１が、この空き要素タグ以外の要素の構文解析を開始するとき、粒度推定部１２２を呼び出し、その要素の開始タグの位置を引数として与える。

粒度推定部１２２は、先行解析表１１３１を参照して、引数と一致する開始タグの位置が先行解析表１１３１に登録されているか否かを検索する。引数と一致する開始タグの位置が登録されていれば、粒度推定部１２２は、その開始タグの位置と、対応する終了タグの位置との差（以下、「粒度」という）を構文解析部１２１に返す。

引数と一致する開始タグの位置が登録されていなければ、粒度推定部１２２は、粒度が不明である旨を構文解析部１２１に返す。

粒度が所定の閾値に満たない場合、または粒度が不明である場合、構文解析部１２１は、「開始タグ」以降の「要素の内容」、および「終了タグ」を構文解析する。

粒度が所定の閾値以上であれば、構文解析部１２１は、並列化部１２３を呼び出し、新しい論理ＣＰＵに、粒度が閾値以上の「要素の内容」の部分を解析させるように指示する。並列化部１２３は、構文解析装置１のリソース内において未使用の論理ＣＰＵを主パージング実行論理ＣＰＵ群１４に追加する。追加された論理ＣＰＵは、構文解析部１２１を呼び出す。

以下、並列化部１２３が呼び出された時点で主パージングを実行していた論理ＣＰＵを「親論理ＣＰＵ」といい、親論理ＣＰＵの指示により新たに追加された論理ＣＰＵを「子論理ＣＰＵ」という。

親論理ＣＰＵが実行する構文解析部１２１が、「開始タグ」に対応する「終了タグ」以降の構文解析を行うとともに、追加された子論理ＣＰＵが、構文解析部１２１を呼び出し、指示された「要素の内容」を構文解析する。子論理ＣＰＵは、指示された「要素の内容」の構文解析が終了後に解放される。

ここで、子論理ＣＰＵが追加された場合、前述した主パージング進捗情報１２５として保持される位置は、親論理ＣＰＵによる構文解析が行われる位置である。つまり、並列して行われる構文解析の進行位置のうち、最大値を示す情報が主パージング進捗情報１２５として保持される。

構文解析部１２１は、「終了タグ」を解析したとき、内部表現生成部１２４を呼び出す。内部表現生成部１２４は、構文解析の結果に基づいて、ＸＭＬテキスト１０１を、内部表現であるＸＭＬツリー１６１に変換する。

上記非特許文献１を参照すると、ＸＭＬ文法の非終端記号「要素の内容」の構文規則右辺は非終端記号「要素」を含んでおり、ＬＬ（１）構文解析手順では「要素」の解析と「要素の内容」の解析は相互再帰になる。

上述した「要素」の並列処理手順をそのまま適用すると、「要素」がその内部に、別の「要素」を入れ子構造で持っている場合、「要素の内容」の構文解析を始めた子論理ＣＰＵが再度、新たな子論理ＣＰＵを追加して入れ子構造を解析する。このため、子論理ＣＰＵの追加が再帰的に繰り返される可能性がある。しかし、入れ子構造であるから、その「要素の内容」のサイズは外側から内側に向かうにつれ小さくなり、サイズが閾値以下となった時点で再帰が停止するので、再帰が無限に連鎖することは無い。

先行パージング実行論理ＣＰＵ１３は、先行パージング部１１において、先行パージングを実行する論理ＣＰＵである。

主パージング実行論理ＣＰＵ群１４は、主パージング部１２において主パージングを実行する１組以上の論理ＣＰＵの集合（論理ＣＰＵ１４１、１４２など）である。

ここで論理ＣＰＵとは、コンピュータシステムにおいて、与えられたデータに対して与えられた手順に沿って処理を進める主体である。例えば、マルチタスクコンピュータシステムにおけるスレッドや、ＬＷＰ（Low Weight Process：軽量プロセッサ）が論理ＣＰＵに相当する。

進度調整部１５は、ＣＰＵ配分決定部１５１およびＣＰＵ配分制御部１５２を有する。

ＣＰＵ配分決定部１５１は、先行パージング部１１、および主パージング部１２が新しくＸＭＬテキスト１０１の処理を始める際、各部に、予め定められたＣＰＵ資源を割り当てる。

ＣＰＵ配分決定部１５１は、先行パージング進捗情報１１４および主パージング進捗情報１２５を取得し、それらの情報の示す先行パージングの進度と、主パージングの進度とを比較する。ＣＰＵ配分決定部１５１は、先行パージングの進度が主パージングの進度以上であり、且つ、先行パージング、主パージングの進度の差が所定範囲内となるように、先行パージング部１１、主パージング部１２のそれぞれに配分すべきＣＰＵ資源（１３、１４）の量を決定する。

ここで、ＣＰＵ資源の量とは、複数ＣＰＵ構成のコンピュータシステムにおける、各物理ＣＰＵの台数であってもよいし、オペレーティングシステムや仮想化ソフトウェアが提供する仮想ＣＰＵの台数であってもよい。あるいは、物理ＣＰＵまたは仮想ＣＰＵに対するＣＰＵ時間割当量や処理優先度であってもよい。

ＣＰＵ資源量の割り当てにおいて、ＣＰＵ配分決定部１５１は、事前に各パージングの進度の差について、上限値、および下限値を設定しておく。

ＣＰＵ配分決定部１５１は、先行パージングが主パージングよりも下限値以上先行していなければ、主パージング部１２に割り当てられていたＣＰＵ資源の一部を先行パージング部１１に割り当てる決定を下す。ＣＰＵ配分決定部１５１は、先行パージングが主パージングよりも上限値以上先行していれば、先行パージング部１１に割り当てられていたＣＰＵ資源の一部を主パージング部１２に割り当てる決定を下す。

ＣＰＵ配分制御部１５２は、ＣＰＵ配分決定部１５１で決定された配分量に基づいて、各論理ＣＰＵを、各パージング部（１１、１２）に配分する。

また、ＣＰＵ配分制御部１５２は、主パージング部１２により、並列処理のために論理ＣＰＵの追加を要求された時、主パージング実行論理ＣＰＵ群１４に、論理ＣＰＵを追加する。

主パージング部１２が、追加された論理ＣＰＵを使用して、要素の構文解析を終了したとき、ＣＰＵ配分制御部１５２は、割り当てた論理ＣＰＵを解放する。

出力部１６は、ＸＭＬツリー１６１を、レンダリングエンジンなどに出力する。

図６を参照して、ＸＭＬテキスト１０１から、ＸＭＬツリー１６１への変換手順について詳細に説明する。図６（ａ）は、ＸＭＬテキスト１０１の一部である。図６（ｂ）は、図６（ａ）のテキストに対応するＸＭＬツリー１６１の一部である。同図（ａ）に示すように、ＸＭＬテキスト１０１は、ある「要素」における「要素の内容」の中に、文字データや、別の「要素」が格納されており、「要素」が入れ子構造になっている。

内部表現生成部１２４は、この部分で最初に出現した「開始タグ」の属性名を示すノードを作成する。

例えば、図６（ａ）において、最初に出現する開始タグが「＜ＣＣ ｐ＝”ｆоо”＞」であれば、図６（ｂ）に示すように、このタグの属性名を示すノード「ＣＣ」が作成される。「ｐ＝”ｆоо”」の属性は、このノード「ＣＣ」内のデータフィールドの１つに格納される。

内部表現生成部１２４は、開始タグに対応するノードを親ノードとして、開始タグ以降の「要素の内容」を示すノードを、その親ノードの子ノードとして生成する。

例えば、図６（ａ）において、開始タグ「＜ＣＣ ｐ＝”ｆоо”＞」以降の「要素の内容」が、「ｔｅｘｔ ｆоｒ ＣＣ」の文字データと、要素「ＤＤ」と、「ｔｅｘｔ２ ｆоｒ ＣＣ」の文字データである。この場合、図６（ｂ）に示すように、まず、親ノードとしてノード「ＣＣ」が作成され、その子ノードとして、各文字データに対応するノードと、ノード「ＤＤ」とが作成される。

図７を参照して、本実施形態の構文解析装置１の動作について説明する。同図は、構文解析装置１の動作の一例を示すシーケンス図である。同図を参照すると、先行パージング部１１は先行パージングを開始し（ステップＴ１０）、先行パージング進捗情報１１４を作成する（ステップＴ１１）。

先行パージングと並行して、主パージング部１２は主パージングを開始し（ステップＴ２０）、主パージング進捗情報１２５を作成する（ステップＴ２１）。主パージングにおいては、図７で後述する要素構文解析処理が実行される。

進度調整部１５は、先行パージング進捗情報１１４および主パージング進捗情報１２５を取得し、それらの情報の示す各パージングの進度の差が、所定の範囲内であるか否かを判断する（ステップＴ３０）。

進度の差が範囲内でなければ（ステップＴ３０：ＮＯ）、ＣＰＵ配分決定部１５１は、差が範囲内となるように、各パージング部へのＣＰＵ資源量の割り当てを決定する（ステップＴ３１）。ＣＰＵ配分制御部１５２は、ＣＰＵ配分決定部１５１で決定された配分量に基づいて、各論理ＣＰＵを、各パージング部に配分する（ステップＴ３２）。

図８〜図１０を参照して、主パージング部１２の動作について説明する。図８は、主パージング部１２の実行する要素構文解析処理を示すフローチャートである。この要素構文解析処理は、ＸＭＬテキスト１０１が入力されたときから、ＸＭＬテキスト１０１の全ての構文解析が終了するまでの間、要素ごとに繰り返し実行される。

図８を参照すると、親論理ＣＰＵが実行する構文解析部１２１は、ＸＭＬテキスト１０１のうち、解析されていない部分の先頭の文字を解析し、その文字に続く文字列が開始タグであるか否かを判断する（ステップＵ１）。

開始タグであれば（ステップＵ１：ＹＥＳ）、構文解析部１２１は、その開始タグの構文解析を行う（ステップＵ２）。

構文解析部１２１は、粒度推定部１２２を呼び出して、ステップＵ２で解析した開始タグの位置を引数として与える。粒度推定部１２２は、後述する粒度推定処理を実行し、粒度を返す。先行解析表１１３１に、ステップＵ２で解析した開始タグの位置が登録されていなければ、粒度推定部１２２は、粒度が不明である旨を返す（ステップＵ３）。

構文解析部１２１は、粒度が不明でなく、且つ、粒度が所定の閾値以上であるか否かを判断する（ステップＵ４）。

粒度が不明でなく、所定の閾値以上であれば（ステップＵ４：ＹＥＳ）、構文解析部１２１は、並列化部１２３を呼び出す。並列化部１２３は、主パージング実行論理ＣＰＵ群１４に、未使用の論理ＣＰＵ（子論理ＣＰＵ）を追加する。追加された子論理ＣＰＵは、粒度が閾値以上の要素における「要素の内容」の構文解析を開始する（ステップＵ５）。

粒度が不明、または所定の閾値に達していなければ（ステップＵ４：ＮＯ）、構文解析部１２１は、「要素の内容」を構文解析する（ステップＵ６）。

ステップＴ５またはＴ６の後、構文解析部１２１は、「終了タグ」を構文解析し、内部表現生成部１２４を呼び出す。内部表現生成部１２４は、構文解析の結果に基づいて、ＸＭＬツリー１６１を生成する（ステップＵ７）。

先頭の文字が開始タグでなければ（ステップＵ１：ＮＯ）、構文解析部１２１は、例外処理を行う（ステップＵ８）。ステップＵ７、またはＵ８の後、主パージング部１２は、要素構文解析処理を終了する。

図９は、粒度推定処理を示すフローチャートである。粒度推定部１２２は、まず、先行解析表１１３１を参照し、引数に一致する開始タグの位置を検索する（ステップＵ３１）。粒度推定部１２２は、開始タグの位置が登録されているか否かを判断する（ステップＵ３２）。

開始タグの位置が登録されていれば（ステップＵ３２：ＹＥＳ）、粒度推定部１２２は、開始タグの位置と、対応する終了タグの位置との差である粒度を算出して返す（ステップＵ３３）。開始タグの位置が登録されていなければ（ステップＵ３２：ＮＯ）、粒度推定部１２２は、粒度が不明である旨を返す（ステップＵ３４）。ステップＵ３３、またはＵ３４の後、粒度推定部１２２は、粒度推定処理を終了する。

図１０は、例外処理を示すフローチャートである。同図を参照すると、構文解析部１２１は、要素が空き要素タグであるか否かを判断する（ステップＵ８１）。空き要素タグであれば（ステップＵ８１：ＹＥＳ）、構文解析部１２１は、空き要素タグを構文解析する（ステップＵ８２）。空き要素タグでなければ（ステップＵ８１：ＮＯ）、構文解析部１２１は、構文エラーを出力する（ステップＵ８３）。

図１１は、主パージング部１２の動作結果の一例を示すシーケンス図である。論理ＣＰＵ１４１が構文解析部１２１を呼び出して、要素構文解析処理のステップＵ３までを実行する。

構文解析部１２１は、ステップＵ４において、粒度が所定の閾値以上であれば（ステップＵ４：ＹＥＳ）、論理ＣＰＵ１４２を追加する（ステップＵ５）。

論理ＣＰＵ１４１が実行する構文解析部１２１は、「終了タグ」を構文解析する（ステップＵ６）。このステップＴ６と並行して、論理ＣＰＵ１４２が構文解析部１２１を呼び出し、割り当てられた要素のうち、解析した文字列が開始タグであるか否かを判断する（ステップＵＵ１）。

続いて、図１２〜図２２を参照して、構文解析装置１ａの動作結果の一例について説明する。

図１２（ａ）は、ＸＭＬテキスト１０１におけるパージングの進度を示す図である。同図（ｂ）は、同図（ａ）の時点におけるタグ一時記憶部１１２を示す図である。同図（ｃ）は、同図（ａ）の時点における先行解析表１１３１を示す図である。同図（ｄ）は、同図（ａ）の時点におけるＸＭＬツリー１６１を示す図である。

図１２（ａ）を参照すると、先行パージング部１１は、先頭文字を０文字目として、２０文字目の位置（１０１１）まで解析を進めている。一方、主パージング部１２は、５文字目の位置（１０１２）まで解析を進めている。

図１２（ｂ）に示すように、この時点では、タグ一時記憶部１１２に、「ＡＡ」、「ＢＢ」の開始タグの位置情報が格納されている。

図１２（ｃ）に示すように、この時点では、終了タグが出現していないので、先行解析表１１３１には、開始タグ、終了タグの各位置は１つも記載されていない。

構文解析部１２１は、開始タグ「＜ＢＢ＞」が出現したとき、その位置「５」を引数として粒度推定部１２２を呼び出す。しかし、図１３（ｃ）に示したように先行解析表１１３１は空であるから、粒度推定部１２２は、サイズが不明である旨を返す。そこで、構文解析部１２１は、開始タグ「＜ＢＢ＞」以降の部分を並列化せず、そのまま逐次的に構文解析を継続する。

図１２（ｄ）に示すように、この時点では、主パージング部１２は、開始タグ「＜ＡＡ＞」の解析結果に基づいて、ノード「ＡＡ」を作成している。

図１３（ａ）は、図１２（ａ）以降のパージングの進度を示す図である。図１３（ｂ）は、同図（ａ）の時点におけるタグ一時記憶部１１２を示す図である。図１３（ｃ）は、同図（ａ）の時点における先行解析表１１３１を示す図である。図１３（ｄ）は、同図（ａ）の時点におけるＸＭＬツリー１６１を示す図である。

図１３（ａ）を参照すると、先行パージング部１１は、１０８文字目の位置（１０１３）まで解析を進めており、一方、主パージング部１２は、２８文字目の位置（１０１４）まで解析を進めている。

図１３（ｂ）に示すように、この時点では、図１３（ａ）の時点以降、タグ一時記憶部１１２に「＜ＤＤ＞」、「＜ＣＣ ｐ＝”ｆоо”＞」の位置情報が更に格納され、「＜ＢＢ＞」、「＜ＤＤ＞」、「＜ＣＣ ｐ＝”ｆоо”＞」の位置情報が、この順に取り出されている。

図１３（ｃ）に示すように、この時点では、取り出された「＜ＢＢ＞」、「＜ＤＤ＞」、「＜ＣＣ ｐ＝”ｆоо”＞」の開始タグの位置と、これらに対応する終了タグの位置とが先行解析表１１３１に追加されている。

構文解析部１２１は、要素「ＡＡ」の内容として開始タグ「＜ＢＢ＞」、および「ｔｅｘｔ ｆоｒ ＢＢ」を構文解析する。このため、図１３（ｄ）に示すように、ノード「ＡＡ」の子ノードとして、ノード「ＢＢ」（１６１１）が追加され、ノード「ＢＢ」の子ノードとしてノード「ｔｅｘｔ ｆоｒ ＢＢ」（１６１２）が追加される。

続いて、「＜ＣＣ ｐ＝”ｆоо”＞」の開始タグが出現したとき、構文解析部１２１は、粒度推定部１２２に、その開始タグの位置「２８」を引数として与える。粒度推定部１２２は、その引数と一致する開始タグの位置と、これに対応する終了タグの位置「９４」との差「６６」を粒度として返す。粒度が事前に定めた閾値（例えば、「５０」）を超えるので、構文解析部１２１は、「＜ＣＣ ｐ＝”ｆоо”＞」直後から「＜／ＣＣ＞」直前までの部分を並列処理すべき部分と判断する。図１３（ａ）において一点鎖線で囲まれた部分は、この並列処理の対象となる部分（１０１５）である。

並列化部１２３は、進度調整部１５を呼び出して、論理ＣＰＵを追加させる。追加された論理ＣＰＵ（子論理ＣＰＵ）は、構文解析部１２１を呼び出し、図１３（ａ）において一点鎖線で囲まれた部分を構文解析する。

一方、構文解析部１２１をこれまで実行していた論理ＣＰＵ（親論理ＣＰＵ）は、「＜／ＣＣ＞」の直後から、構文解析を続行する。

ここで、子論理ＣＰＵが構文解析する部分（１０１５）は、ＸＭＬ文法において「要素」（「＜ＡＡ＞」〜「＜／ＡＡ＞」）を構成する「要素の内容」に相当する。このため、図１３（ｄ）に示すように、子論理ＣＰＵが作成するＸＭＬツリー（１６１１）は、親論理ＣＰＵが作成するノード「ＣＣ」の子ノードとなるように、構文解析部１２１は、内部表現生成部１２４に対し、ツリーノードの親ノードの情報を渡す。

例えば、ノードに対応する構造体とノード間のエッジに対応する構造体間リンクポインタによってツリーデータを形成する実装方法を用いる。この方法では、子論理ＣＰＵが作成するＸＭＬツリーのルートノードにある「親ノードへのリンクポインタ」欄に、親論理ＣＰＵが作成するノードＣＣへのポインタ値が設定され、親論理ＣＰＵが作成するノードＣＣにある「子ノードへのリンクポインタのリスト」の末尾に、子論理ＣＰＵが作成するＸＭＬツリーのルートノードへのポインタ値が追加される。このようにして、ノード間の親子関係が実現される。

図１４（ａ）は、図１３（ａ）以降のパージングの進度を示す図である。同図（ｂ）は、同図（ａ）の時点におけるタグ一時記憶部１１２を示す図である。同図（ｃ）は、同図（ａ）の時点における先行解析表１１３１を示す図である。同図（ｄ）は、同図（ａ）の時点におけるＸＭＬツリー１６１を示す図である。

図１４（ａ）を参照すると、先行パージング部１１は、１５３文字目の位置（１０１６）まで字句解析を進めている。親論理ＣＰＵが、９３文字目の位置（１０１７）まで構文解析を進める一方、子論理ＣＰＵが、４０文字目の位置（１０１８）まで構文解析を進めている。

図１４（ｂ）に示すように、この時点では、図１３（ａ）の時点以降、タグ一時記憶部１１２に「＜ＥＥ ｐ＝”ｂａｒ”＞」の開始タグの位置情報が追加され、「＜ＦＦ＞」の開始タグの位置情報が取り出されている。

図１４（ｃ）に示すように、この時点では、取り出された「＜ＦＦ＞」の開始タグの位置と、対応する終了タグの位置とが先行解析表１１３１に追加されている。同図（ｃ）における斜線部分は、追記された部分である。

図１４（ｄ）に示すように、この時点で、親論理ＣＰＵが実行する構文解析部１２１は、開始タグ「＜ＣＣ ｐ＝”ｆоо”＞」の解析を終了している。このため、ＸＭＬツリー１６１において、ノード「ＣＣ」（１６１３）が追加される。

図１５（ａ）は、図１４（ａ）以降のパージングの進度を示す図である。図１５（ｂ）は、同図（ａ）の時点におけるタグ一時記憶部１１２を示す図である。図１５（ｃ）は、同図（ａ）の時点における先行解析表１１３１を示す図である。図１６は、図１５（ａ）の時点におけるＸＭＬツリー１６１を示す図である。

図１５（ａ）を参照すると、先行パージング部１１は、１７０文字目の位置（１０１９）まで字句解析を進めている。親論理ＣＰＵが、１０８文字目の位置（１０２０）まで構文解析を進める一方、子論理ＣＰＵが、８８文字目の位置（１０２１）まで構文解析を進めている。

図１５（ｂ）に示すように、この時点では、図１４（ａ）の時点以降、タグ一時記憶部１１２から「＜ＥＥ ｐ＝”ｂａｒ”＞」の開始タグの位置情報が取り出され、「＜ＧＧ＞」の開始タグの位置情報が追加されている。

図１５（ｃ）に示すように、この時点では、取り出された「＜ＥＥ ｐ＝”ｂａｒ”＞」の開始タグの位置と、対応する終了タグの位置とが先行解析表１１３１に追加されている。同図（ｃ）における斜線部分は、追記された部分である。

この時点で、親論理ＣＰＵが実行する構文解析部１２１は、要素「ＡＡ」の内容として、「ｔｅｘｔ ｆоｒ ＡＡ１」を解析している。このため、図１６に示すように、ノード「ＡＡ」の子ノードとして、ノード「ｔｅｘｔ ｆоｒ ＡＡ１」（１６１４）が追加される。

子論理ＣＰＵが実行する構文解析部１２１は、並行して、要素「ＣＣ」の内容を構文解析し、開始タグ「＜ＤＤ＞」に遭遇する。この開始タグの位置と、対応する終了タグの位置とは、先行解析表１１３１において、それぞれ、「５３」、「７５」であるから、粒度は「２２」である。粒度が閾値以下なので、構文解析部１２１は、並列処理はしないで「＜／ＣＣ＞」直前まで解析を進める。

この結果、図１６に示すように、ノード「ＣＣ」のサブツリー（１６１５）が形成される。構文解析部１２１は、要素「ＣＣ」の内容の解析が終了したとき、進度調整部１５を呼び出して、子論理ＣＰＵを解放する。

図１７（ａ）は、図１５（ａ）以降のパージングの進度を示す図である。図１７（ｂ）は、同図（ａ）の時点におけるタグ一時記憶部１１２を示す図である。図１７（ｃ）は、同図（ａ）の時点における先行解析表１１３１を示す図である。図１８は、図１７（ａ）の時点におけるＸＭＬツリー１６１を示す図である。

図１７（ａ）を参照すると、先行パージング部１１は、１９４文字目の位置（１０２２）まで字句解析を進めている。一方、主パージング部１２は、１６０文字目の位置（１０２３）まで構文解析を進めている。

図１７（ｂ）に示すように、この時点では、図１５（ａ）の時点以降、タグ一時記憶部１１２に「＜ＨＨ＞」の位置情報が格納され、その「＜ＨＨ＞」の位置情報が取り出されている。

図１７（ｃ）に示すように、この時点では、取り出された「＜ＨＨ＞」の開始タグの位置と、対応する終了タグの位置とが先行解析表１１３１に追加されている。同図（ｃ）における斜線部分は、追記された部分である。

構文解析部１２１は、「＜／ＣＣ＞」の直後から、構文解析を進め、開始タグ「＜ＥＥ ｐ＝”ｂａｒ”＞」に遭遇する。この開始タグの位置と、対応する終了タグの位置とは、先行解析表１１３１において、それぞれ、「１０８」、「１６０」であるから、粒度は「５２」である。粒度が閾値（５０）を超えているので、構文解析部１２１は、この開始タグ以降の要素を並列処理する。図１８（ａ）において一点鎖線で囲まれた部分は、この並列処理の対象となる部分である。

並列化部１２３は、進度調整部１５を呼び出して、子論理ＣＰＵを追加させる。子論理ＣＰＵは構文解析部１２１を呼び出し、図１８（ａ）において一点鎖線で囲まれた部分の先頭から、構文解析を行う。

一方、これまで構文解析部１２１を実行してきたＣＰＵ（親論理ＣＰＵ）は、開始タグ「＜ＥＥ ｐ＝”ｂａｒ”＞」を解析後、「＜／ＥＥ＞」の直後から、構文解析を続行する。この結果、図１８に示すように、ノード「ＡＡ」の子ノード「ＥＥ」（１６１６）が作成される。同図において、一点鎖線で囲まれた部分が、子論理ＣＰＵが解析する対象の部分である。

図１９（ａ）は、図１７（ａ）以降のパージングの進度を示す図である。図１９（ｂ）は、同図（ａ）の時点におけるタグ一時記憶部１１２を示す図である。図１９（ｃ）は、同図（ａ）の時点における先行解析表１１３１を示す図である。図２０は、図１９（ａ）の時点におけるＸＭＬツリー１６１を示す図である。

図１９（ａ）を参照すると、先行パージング部１１は、ＸＭＬテキスト１０１の最後の文字の位置（１０２５）まで字句解析を進めて、先行パージングを終了している。親論理ＣＰＵは、１７８文字目の位置（１０２６）まで構文解析を進める一方、子論理ＣＰＵは、１５４文字目の位置（１０２７）まで構文解析を進めている。

図１９（ｂ）に示すように、この時点では、図１７（ａ）の時点以降、タグ一時記憶部１１２から「＜ＧＧ＞」、「＜ＡＡ＞」の位置情報が、この順に取り出されている。

図１９（ｃ）に示すように、この時点では、取り出された「＜ＧＧ＞」、「＜ＡＡ＞」の開始タグの位置と、対応する終了タグの位置とが先行解析表１１３１に追加されている。同図（ｃ）における斜線部分は、追記された部分である。この結果、先行解析表１１３１には、全ての解析結果が記載されたこととなる。

構文解析部１２１は、親論理ＣＰＵを使用して、要素「ＧＧ」の内容として「ｔｅｘｔ ｆоｒ ＧＧ１」を解析する。この結果、図２０に示すように、ノード「ＧＧ」を含むサブツリー（１６１７）が形成される。

親論理ＣＰＵが実行する構文解析部１２１は、「＜ＨＨ＞」の開始タグを見つける。この開始タグの位置と、対応する終了タグの位置とは、先行解析表１１３１において、それぞれ、「１７８」、「１８８」であるから、粒度は「１０」である。粒度が閾値以下なので、構文解析部１２１は、子論理ＣＰＵを追加しないで、この開始タグ以降の構文解析を進める。

また、子論理ＣＰＵが実行する構文解析部１２１は、要素「ＥＥ」の内容を構文解析する。この結果、図２０に示すように、ノード「ＥＥ」を含むサブツリー（１６１８）が形成される。要素「ＥＥ」の構文解析後、子論理ＣＰＵは解放される。

図２１は、図１９（ａ）以降のパージングの進度を示す図である。図２２は、図２１の時点におけるＸＭＬツリー１６１を示す図である。

図２１を参照すると、主パージング部１２は、ＸＭＬテキスト１０１の最後の文字の位置（１０２８）まで解析を進めて、主パージングを終了している。この結果、図２２に示すように、解析された部分に対応するサブツリー（１６１９）が形成される。

なお、本実施形態では、進度調整部１５は、論理ＣＰＵを割り当てているが、論理ＣＰＵの代わりに、コンピュータシステムが有する複数ＣＰＵを構成する場合における各物理ＣＰＵを割り当ててもよいし、タスクやスレッドを割り当ててもよい。

本実施形態では、主パージング部１２は、粒度が閾値以上であれば、再帰回数に関わりなく並列処理を行う構成としているが、粒度が閾値以上であっても、再帰回数が所定の上限値以上であれば、並列処理を行わない構成とすることもできる。この構成によれば、再帰回数が多くなることを防ぐことができる。

また、主パージング部１２は、粒度が閾値以上であっても、未使用のリソース量が所定の下限値以下であれば、並列処理を行わない構成とすることもできる。この構成によれば、並列化によるリソースの不足を防止できる。

本実施形態では、先行パージング、主パージングのそれぞれの進捗を監視し、リソースの配分を決定する進度調整部１５を設けて、各パージングの進度を調整する構成としている。しかし、構文解析装置１は、進度調整部１５を設けない構成とすることもできる。この場合、構文解析装置１を仮想的に内部に構成する装置におけるオペレーティングシステムや仮想化ソフトウェアが提供する仮想ＣＰＵの割り当て機能に、各パージングの進度の調整を行わせる構成とする。

構文解析装置１において、進度調整部１５を用いない実装は、ＸＭＬパージング処理全体の複雑さを軽減し、実装規模を小さくできるメリットがある。他方、本実施形態のように進度調整部１５を導入することで、コンピュータシステム内の限られたＣＰＵ資源を両パージング処理で効率的に利用し、全体的なＸＭＬパージング処理性能を向上させることが期待できる。すなわち、構文解析装置１内に進度調整部１５を導入するか否かは、実装の複雑さと処理性能のトレードオフの上で判断されるべきものである。

本実施形態では、先行パージング部１１が本発明のタグ位置取得手段に相当し、主パージング部１２が本発明の並列解析手段に相当する。先行パージング実行論理ＣＰＵ１３および主パージング実行論理ＣＰＵ群１４が本発明のリソースに相当する。

以上説明したように、本実施形態によれば、構文解析装置は、テキストを字句解析してタグの位置を取得し、並行して、タグで区切られたそれぞれの部分を並列に構文解析し、字句解析と構文解析とに割り当てるリソース量を調整する。構文解析装置は、タグ位置に基づいて並列解析するので、文法に関わらずに並列解析でき、スループットが向上する。また、構文解析装置は、字句解析、構文解析を並行して行い、字句解析において各部分の解析結果を突き合わせる必要がないので、レイテンシが小さくなる。

また、構文解析装置は、パージングを複数のＣＰＵで分担して行うことができるため、同じ要求性能であれば、シングルＣＰＵの方式よりも低い動作周波数（クロック）のＣＰＵでパージングを実行することができる。このため、動作時および待機時のＣＰＵの消費電力を低減し、システム全体を省電力化できる。

（第２の実施形態）
本発明の第２の実施形態について、図２３〜図３０を参照して説明する。本実施形態は、並列処理により、先行パージングを高速に行う点で第1の実施形態と異なる。図２３は、本実施形態の構文解析装置１ａの一構成例を示すブロック図である。構文解析装置１ａは、先行パージング部１１、先行パージング実行論理ＣＰＵ１３の代わりに先行パージング部１１ａ、先行パージング実行論理ＣＰＵ群１３ａを設ける点以外は、第１の実施形態の構文解析装置１の構成と同様である。

先行パージング実行論理ＣＰＵ群１３ａは、字句解析を行う複数の論理ＣＰＵを有する。図２４は、本実施形態の先行パージング部１１ａの一構成例を示すブロック図である。先行パージング部１１ａの構成は、字句解析部１１１の代わりに、主字句解析部１１１１、および副字句解析部１１１２を設け、タグ一時記憶部１１２の代わりに、主タグ一時記憶部１１２１、および副タグ一時記憶部１１２２を設ける点で、第２の実施形態の先行パージング部１１と異なる。

進度調整部１５は、それぞれ、先行パージング実行論理ＣＰＵ群１３ａに含まれる複数の論理ＣＰＵを主字句解析部１１１１および副字句解析部１１１２のそれぞれに割り当てる。進度調整部１５は、主字句解析部１１１１、副字句解析部１１１２が、ＸＭＬテキスト１０１の最後の文字まで字句解析を終了した場合は、それぞれに割り当てた論理ＣＰＵを解放する。

主字句解析部１１１１は、ＸＭＬテキスト１０１の先頭から、字句解析を開始し、副字句解析部１１１２は、ＸＭＬテキスト１０１の中間の位置から、字句解析を開始する。主字句解析部１１１１は、主タグ一時記憶部１１２１に、開始タグの位置情報を一時保存し、副字句解析部１１１２は、副タグ一時記憶部１１２２に、開始タグの位置情報を一時保存する。

主タグ一時記憶部１１２１、副タグ一時記憶部１１２２は、タグ一時記憶部１１２と同様に後入れ先出し方式で位置情報を記憶する。

主タグ一時記憶部１１２１の動作は、開始タグが出現したときの動作以外は、図３に示した、第１の実施形態の状態遷移図と同様である。

主字句解析部１１１１は、開始タグを見つけるたびに、すなわち、状態Ｓ２において「ｘ」を字句解析するたびに、先行解析表１１３１を参照し、その開始タグの位置が記録されているか否かを調べる。記録されていれば、主字句解析部１１１１は、その開始タグに対応する終了タグの位置まで、ＸＭＬテキスト１０１を読み飛ばし、その終了タグの直後から字句解析を続行する。

副字句解析部１１１２の動作は、以下の２点以外は、図３に示した、第１の実施形態の状態遷移図と同様である。

1つ目の違いは、字句解析の開始時の動作の違いである。副字句解析部１１１２は、字句解析の開始時に、「＞」を見つけるまでＸＭＬテキスト１０１を読み飛ばし、次に、「ｓ」が１つ以上続いていれば、それらを読み飛ばす。そして、副字句解析部１１１２は、最後に見つけた「＜」の位置から字句解析を開始する。この動作により、図３における「Ｓ１」相当の地点から、ＸＭＬテキスト１０１の解析を開始できる。

２つ目の違いは、終了タグを見つけたときの動作の違いである。終了タグを見つけたとき、すなわち、状態Ｓ３またはＳ５において、「＜」を字句解析したとき、副字句解析部１１１２は、開始タグの位置情報が１以上記憶されているか否かを、自らに付属している副タグ一時記憶部１１２２に問い合わせる。

副タグ一時記憶部１１２２に位置情報が全く記載されていない場合、副字句解析部１１１２は、見つけた終了タグを単に読み飛ばし、タグ対応登録部１１３にタグの位置の組を登録しない。この場合、副字句解析部１１１２は、その終了タグの直後から字句解析を再開する。

副タグ一時記憶部１１２２に位置情報が記載されている場合、副字句解析部１１１２は、その位置情報を取り出し、開始タグ、終了タグの位置の組をタグ対応登録部１１３に登録する。

図２５（ａ）は、先行パージングの進度を示す図である。同図（ｂ）は、同図（ａ）の時点における主タグ一時記憶部１１２１を示す図である。同図（ｃ）は、同図（ａ）の時点における副タグ一時記憶部１１２２を示す図である。同図（ｄ）は、同図（ａ）の時点における先行解析表１１３１を示す図である。

図２５（ａ）に示すように、主字句解析部１１１１は、ＸＭＬテキスト１０１の先頭の文字（１０５０）から字句解析を開始する。副字句解析部１１１２は、先頭文字を０文字目として、ＸＭＬテキスト１０１のほぼ中央にあたる１１２文字目（１０５１）から、処理を開始する。副字句解析部１１１２は、上述の読み飛ばし処理を行い、１３２文字目（１０５２）から字句解析を開始する。

この読み飛ばしにより、副字句解析部１１１２内の有限状態機械は、ＸＭＬテキストの途中から読み込み始めたにも関わらず、第1の実施形態と同様の字句解析（Ｓ１〜Ｓ８）を行うことができる。

図２５（ｂ）、図２５（ｃ）に示すように、この時点では、主タグ一時記憶部１１２１、副タグ一時記憶部１１２２には、位置情報が１つも格納されていない。

図２５（ｄ）に示すように、この時点では、位置情報が取り出されていないので、先行解析表１１３１には、開始タグ、終了タグの位置は１つも格納されていない。

図２６（ａ）は、先行パージングの進度を示す図である。同図（ｂ）は、同図（ａ）の時点における主タグ一時記憶部１１２１を示す図である。同図（ｃ）は、同図（ａ）の時点における副タグ一時記憶部１１２２を示す図である。同図（ｄ）は、同図（ａ）の時点における先行解析表１１３１を示す図である。

図２６（ａ）を参照すると、主字句解析部１１１１は、４１文字目（１０５３）まで字句解析を進めている。一方、副字句解析部１１１２は、１５３文字目（１０５４）まで字句解析を進めている。

主字句解析部１１１１は、開始タグ「＜ＡＡ＞」、「＜ＢＢ＞」、「＜ＣＣ ｐ＝”ｆоо”＞」が見つけているが、これらの位置情報は、先行解析表１１３１に記載がないので、字句解析部１１１１は字句解析を続行する。

図２６（ｂ）に示すように、この時点では、主字句記憶部１１２１には、「＜ＡＡ＞」、「＜ＢＢ＞」、「＜ＣＣ ｐ＝”ｆоо”＞」の位置情報が格納され、「＜ＢＢ＞」の位置情報が取り出されている。

図２６（ｃ）に示すように、この時点では、副字句記憶部１１２２には、「＜ＦＦ＞」の位置情報が格納され、その「＜ＦＦ＞」の位置情報が取り出されている。

図２６（ｄ）に示すように、この時点では、取り出された「＜ＢＢ＞」、「＜ＦＦ＞」の開始タグの位置と、対応する終了タグの位置とが先行解析表１１３１に記載されている。

図２７（ａ）は、先行パージングの進度を示す図である。同図（ｂ）は、同図（ａ）の時点における副タグ一時記憶部１１２２を示す図である。

図２７（ａ）を参照すると、図２６（ａ）の時点以降、主字句解析部１１１１は、４６文字目（１０５５）まで字句解析を進めている。

一方、副字句解析部１１１２は、終了タグ「＜／ＥＥ＞」を見つけているが、この時点で、図２７（ｂ）に示すように、副タグ一時記憶部１１２２には、開始タグの位置情報が存在しない。これは、副字句解析部１１１２が、「＜ＥＥ＞」より進んだ位置から解析を開始したためである。副字句解析部１１１２は、その終了タグを飛ばし、その直後（１０５６）から字句解析を続行する。

図２８（ａ）は、先行パージングの進度を示す図である。同図（ｂ）は、同図（ａ）の時点における主タグ一時記憶部１１２１を示す図である。同図（ｃ）は、同図（ａ）の時点における副タグ一時記憶部１１２２を示す図である。同図（ｄ）は、同図（ａ）の時点における先行解析表１１３１を示す図である。

図２８（ａ）を参照すると、図２７（ａ）の時点以降、主字句解析部１１１１は、１０８文字目（１０５７）まで字句解析を進めている。一方、副字句解析部１１１２は、ＸＭＬテキストの最後の文字（１０５８）まで字句解析を進めている。この時点で、副字句解析部１１１２に割り当てられた論理ＣＰＵは、解放される。

図２８（ｂ）に示すように、この時点では、主字句記憶部１１２１には、「＜ＤＤ＞」の位置情報が格納され、「＜ＤＤ＞」、「＜ＣＣ ｐ＝”ｆоо”＞」の位置情報が、この順に取り出されている。

図２８（ｃ）に示すように、この時点では、図２７（ａ）の時点以降、副字句記憶部１１２２には、「＜ＧＧ＞」、「＜ＨＨ＞」の位置情報が格納され、「＜ＨＨ＞」、「＜ＧＧ＞」の位置情報が、この順に取り出されている。

図２８（ｄ）に示すように、この時点では、図２７（ａ）の時点以降、取り出された「＜ＤＤ＞」、「＜ＣＣ ｐ＝”ｆоо”＞」、 「＜ＨＨ＞」、および「＜ＧＧ＞」の開始タグの位置と、対応する終了タグの位置とが先行解析表１１３１に追加されている。同図（ｄ）における斜線部分は、追記された部分である。

図２９（ａ）は、先行パージングの進度を示す図である。同図（ｂ）は、同図（ａ）の時点における主タグ一時記憶部１１２１を示す図である。同図（ｃ）は、同図（ａ）の時点における先行解析表１１３１を示す図である。

図２９（ａ）を参照すると、主字句解析部１１１１は、図２８（ａ）の時点以降、１３２文字目（１０５９）まで字句解析を進め、開始タグ「＜ＦＦ＞」を見つける。この開始タグの位置「１３２」は、図２９（ｃ）に示すように、先行解析表１１３１に記載されている。このため、主字句解析部１１１１は、この開始タグと対応する終了タグ「＜／ＦＦ＞」の位置（１０６０）、すなわち１５３文字目までテキストを読み飛ばし、その直後から字句解析を再開する。

図３０（ａ）は、先行パージングの進度を示す図である。同図（ｂ）は、同図（ａ）の時点における主タグ一時記憶部１１２１を示す図である。同図（ｃ）は、同図（ａ）の時点における先行解析表１１３１を示す図である。

図３０（ａ）を参照すると、図２９（ａ）の時点以降、主字句解析部１１１１は、１６０文字目（１０６１）まで字句解析を進め、その直後（１０６２）に、開始タグ「＜ＧＧ＞」を見つける。この開始タグの位置「１６０」は、図３０（ｃ）に示す先行解析表１１３１に記載済みなので、主字句解析部１１１１は、この開始タグと対応する終了タグ「＜／ＧＧ＞」の位置（１０６３）、すなわち２０６文字目までテキストを読み飛ばし、その直後から字句解析を再開する。

図３０（ｂ）に示すように、この時点では、図２９（ａ）の時点以降、主字句記憶部１１２１から、「＜ＥＥ＞」の位置情報が取り出されている。

図３０（ｃ）に示すように、この時点では、図２９（ａ）の時点以降、取り出された「＜ＥＥ＞」の開始タグの位置と、対応する終了タグの位置とが先行解析表１１３１に記載されている。図３０（ｃ）における斜線部分は、追記された部分である。

以降は、主字句解析部１１１１は、字句解析を最後の文字まで進め、「＜ＡＡ＞」の位置と、対応する終了タグの位置とを先行解析表１１３１に記載して、先行パージングが完了する。

なお、本実施形態では、副字句解析部１１１２を１つだけ設ける構成としているが、副字句解析部を複数設ける構成としてもよい。この場合、先行パージング実行論理ＣＰＵ群１３ｂ内の論理ＣＰＵの総数をｎ個、各論理ＣＰＵに割り当てられた番号をｍとする。ここで、ｍは、１、２、・・・ｎー１の自然数である。各副字句解析部は、ＸＭＬテキスト１０１を、ｍ対ｎ−ｍに内分する位置から、処理を開始する。

例えば、副字句解析部を１つだけ設ける場合、ｎ＝２、ｍ＝１であるから、副字句解析部は、ＸＭＬテキスト１０１のちょうど中間地点から処理を開始する。ｍ対ｎ−ｍの内分が整数にならない場合は、適宜整数に丸める。

本実施形態では、主字句解析部１１１１が本発明の主字句解析手段に相当し、副字句解析部１１１２が本発明の副字句解析手段に相当する。主タグ一時記憶部１１２１が主タグ一時記憶部１１２１に相当し、副タグ一時記憶部１１２２が副タグ一時記憶部１１２２に相当する。タグ対応登録部１１３が本発明の記憶手段に相当する。

以上説明したように、本実施形態によれば、主字句解析手段、副字句解析手段が並列に字句解析するので、ＸＭＬテキスト１０１のテキストの行の長さや、タグごとの行数に左右されずに、先行パージングにおいて並列処理を行うことができる。このため、ＸＭＬパージング全体の処理性能が一層向上する。

主字句解析手段は、開始タグを見つけたとき、その開始タグの位置が、記憶手段に記録されていれば、対応する終了タグの位置までスキップする。このため、副字句解析手段が既に解析した部分を字句解析しなくて済み、主字句解析手段は、字句解析を効率的に行うことができる。

また、副字句解析手段は、ＸＭＬテキスト１０１を内分した位置から、タグの末尾文字「＞」が出現するまで、テキストをスキップし、最後に見つけたタグの先頭文字「＜」の位置から字句解析を開始する。このため、副字句解析手段は、テキストの途中から字句解析する場合であっても、図３における初期状態「Ｓ１」から、正しい字句解析処理を開始することができる。

さらに、副字句解析手段は、終了タグを見つけたときに、副タグ一時記憶部に開始タグの位置情報が１つも格納されていなければ、その終了タグをスキップする。このため、要素の途中から字句解析を開始し、対応する開始タグのない終了タグが出現した場合でも、副字句解析手段は、不要な字句解析を行う必要がなくなり、効率的に字句解析できる。

（第３の実施形態）
本発明の第３の実施形態について、図３１を参照して説明する。本実施形態は、ＸＭＬパーザプログラムに本発明を適用した点で第１の実施形態と異なる。

図３１は、本実施形態の構文解析装置１ｂの一構成例を示すブロック図である。同図を参照すると、構文解析装置１ｂの構成は、先行パージング部１１、主パージング部１２ｃ、進度調整部１５の代わりにＸＭＬパーザプログラム２０を設け、コンピュータシステム２１を更に設けた以外は、第１の実施形態の構文解析装置１と同様の構成である。

ＸＭＬパーザプログラム２０は、コンピュータシステム２１上で動作するコンピュータプログラムであり、先行パージング手続き１１ｂ、主パージング手続き１２ｂ、および速度調整手続き１５ｂを有する。

先行パージング手続き１１ｂ、主パージング手続き１２ｂ、および速度調整手続き１５ｂは、コンピュータシステム２１上で、それぞれ、先行パージング部１１、主パージング部１２、および速度調整部１５の動作を実現する手続きである。

コンピュータシステム２１は、オペレーティングシステム２１１、マルチコアＣＰＵ２１２、およびメモリ２１３を有する。

マルチコアＣＰＵ２１２は、複数のＣＰＵコアを内蔵する処理装置である。メモリ２１３は、主記憶装置として使用される。オペレーティングシステム２１１は、マルチコアＣＰＵ２１２およびメモリ２１３を使用して動作し、コンピュータシステム２１全体を制御する。

ＸＭＬツリー１６１は、ツリー構造の形で、メモリ２１３上に生成され、その後、コンピュータシステム２１上の別の処理プログラムによって利用される。別の処理プログラムは、例えば、在庫管理プログラムや人事管理プログラムである。

以上説明したように本実施形態によれば、ＸＭＬパーザプログラム２０はマルチコアＣＰＵ２１２を活かした高速なＸＭＬ処理を行える。このため、ＸＭＬ形式テキストの入力に関わるオーバヘッドを低減し、もってシステム全体の処理性能向上に寄与することができる。

（第４の実施形態）
本発明の第４の実施形態について、図３２を参照して説明する。本実施形態は、Ｗｅｂブラウザに本発明を適用した点で第４の実施形態と異なる。

図３２は、本実施形態の構文解析装置１ｃの一構成例を示すブロック図である。同図を参照すると、構文解析装置１ｄの構成は、ＸＭＬテキスト１０１の代わりにＨＴＭＬテキスト１０１ｃが入力され、ＸＭＬパーザプログラム２０の代わりに、ＨＴＭＬパーザ部２０ｃを設け、出力部１６の代わりにＨＴＭＬレンダラ部１６ｃ、グラフィックサブシステム２２、ディスプレイ装置２３を設けた以外は、第４の実施形態の構文解析装置１ｃと同様の構成である。

ＨＴＭＬテキスト１０１ｄは、ＨＴＭＬ形式のテキストファイルである。

ＨＴＭＬパーザ部２０ｃ、およびＨＴＭＬレンダラ部１６ｄは、ウェブブラウザプログラムに格納される。

ＨＴＭＬパーザ部２０ｃは、先行パージング手続き１１ｃ、主パージング手続き１２ｃ、および速度調整手続き１５ｃを有する。先行パージング手続き１１ｄ、主パージング手続き１２ｃ、および速度調整手続き１５ｃは、コンピュータシステム２１上で、それぞれ、ＸＭＬテキスト１０１の代わりにＨＴＭＬテキスト１０１ｃを処理し、先行パージング部１１、主パージング部１２、および速度調整部１５の動作を実現する手続きである。

ＨＴＭＬレンダラ部１６ｃは、ＨＴＭＬツリー１６１ｃを解釈して、ＨＴＭＬテキストに記述された内容をレンダリング（描画）してグラフィックサブシステム２２を介してディスプレイ装置２３に出力する。

ディスプレイ装置２３は、ＬＣＤ(Liquid Crystal Display)やＣＲＴ(Cathode Rey Tube)などの表示装置である。

以上説明したように、本実施形態によれば、ＨＴＭＬパーザ部２０ｃはマルチコアＣＰＵ２１２を活かした高速なＨＴＭＬ処理を行えるため、ＨＴＭＬテキスト解析に要する時間を低減し、描画性能に優れたウェブブラウザを実現できる。

本発明は、ＸＭＬ形式で互いにデータ交換するコンピュータシステム間で、相手から受信したＸＭＬメッセージをコンピュータ内に取り込むＸＭＬパーザに用いることができる。本発明はまた、ワールド・ワイド・ウェブ・コンソーシアム（Ｗ３Ｃ）が勧告したＳＯＡＰ（Simple Object Access Protocol：ソープ）プロトコルを用いたウェブサービス（Ｗｅｂサービス）において、ＳＯＡＰメッセージを解釈する用途に適用することもできる。

本発明はまた、ＸＭＬ形式をファイル形式としてもちいるコンピュータ文書（ワードプロセッサ文書、スプレッドシートや電子プレゼンテーション文書等）において、そのＸＭＬ形式の文書ファイルをコンピュータ内に読み込む処理に適用することができる。

本発明はまた、ＨＴＭＬ形式の文書を画面表示するＨＴＭＬブラウザ（ウェブブラウザ）におけるＨＴＭＬデータ読み込み部分に適用することもできる。

１、１ａ、１ｂ、１ｃ 構文解析装置
１０ 入力部
１１、１１ｂ 先行パージング部
１１ｂ、１１ｃ 先行パージング手続き
１２ 主パージング部
１２ｂ、１２ｃ 主パージング手続き
１３ 先行パージング実行論理ＣＰＵ
１３ｂ 先行パージング実行論理ＣＰＵ群
１４ 主パージング実行論理ＣＰＵ群
１５ 進度調整部
１５ｃ、１５ｄ 進度調整手続き
１６ 出力部
２０ ＸＭＬパーザプログラム
２０ｄ ＨＴＭＬパーザ部
２１ コンピュータシステム
２２ グラフィックサブシステム
２３ ディスプレイ装置
１０１ ＸＭＬテキスト
１０１ｄ ＨＴＭＬテキスト
１０２ 入力一時記憶部
１１１ 字句解析部
１１２ タグ一時記憶部
１１３ タグ対応登録部
１１４ 先行パージング進捗情報
１２１ 構文解析部
１２２ 粒度推定部
１２３ 並列化部
１２４ 内部表現生成部
１２５ 主パージング進捗情報
１４１、１４２ 論理ＣＰＵ
１５１ ＣＰＵ配分決定部
１５２ ＣＰＵ配分制御部
１６１ ＸＭＬツリー
１６１ｄ ＨＴＭＬツリー
２１１ オペレーティングシステム
２１２ マルチコアＣＰＵ
２１３ メモリ
１１１１ 主字句解析部
１１１２ 副字句解析部
１１２１ 主タグ一時記憶部
１１２２ 副タグ一時記憶部
１１３１ 先行解析表
Ｓ１〜Ｓ８ 状態
Ｔ１０〜Ｔ３２、Ｕ１〜Ｕ７、Ｕ８１〜Ｕ８３、ＵＵ６ ステップ

Claims (13)

1. 割り当てられたリソースを使用して、マークアップ言語で記述されたテキストを順次、字句解析していき、該テキストにおける、開始タグの位置と、該開始タグに対応する終了タグの位置とを取得し、取得した前記開始タグの位置と、前記終了タグの位置とを対応付けてタグ位置記憶手段に格納するタグ位置取得手段と、
   前記テキストを、前記タグ位置記憶手段に記憶された前記開始タグの位置まで構文解析したとき、該開始タグと対応する前記終了タグの位置を該タグ位置記憶手段から読み出し、該開始タグと、該開始タグに対応する終了タグと間の文字数を算出し、該文字数が閾値以上であれば、該開始タグと該終了タグとの間の部分と、該終了タグ以降の部分とを異なるリソースで並列に構文解析する並列解析手段と、
   前記タグ位置取得手段による前記字句解析の処理速度をできるだけ速くし、前記テキストにおける、該字句解析が終わり、前記構文解析手段による前記構文解析が終わっていない部分の文字数を所定の範囲内にするように、前記タグ位置取得手段に割り当てるリソース量と前記並列解析手段に割り当てるリソース量とを調整する調整手段と、
   を有する構文解析装置。
2. 前記タグ位置取得手段は、
   前記テキストの先頭から順に字句解析して、前記開始タグの位置と、前記終了タグの位置とを取得する主字句解析手段と、
   前記主字句解析手段による字句解析と並行して、前記テキストの途中の所定の位置から順に字句解析して、前記開始タグの位置と、前記終了タグの位置とを取得する副字句解析手段と、
   を有する、請求項１に記載の構文解析装置。
3. 前記主字句解析手段は、
   開始タグの位置を一時記憶する主タグ一時記憶手段と、
   前記テキストのうち、解析されていない部分を先頭から順に開始タグが出現するまで字句解析し、該開始タグの位置が前記タグ位置記憶手段に記憶されていない場合、該開始タグの位置を前記主タグ一時記憶手段に格納する主開始タグ解析手段と、
   前記主開始タグ解析手段による字句解析において、前記開始タグの位置が前記タグ位置記憶手段に記憶されている場合、該開始タグに対応する前記終了タグを該タグ位置記憶手段から読み出し、該開始タグの位置から、読み出した該終了タグの位置までの部分をスキップする主スキップ手段と、
   前記テキストのうち、解析されていない部分を先頭から順に、終了タグが出現するまで字句解析し、該終了タグの位置と、前記主タグ一時記憶部に最後に格納された前記開始タグの位置とを対応付けて前記タグ位置記憶手段に格納する主終了タグ解析手段と、
   を有する請求項２に記載の構文解析装置。
4. 前記副字句解析手段は、
   開始タグの位置を一時記憶する副タグ一時記憶部と、
   前記所定の位置からの前記テキストのうち、解析されていない部分を、先頭から順に開始タグが出現するまで字句解析し、出現した該開始タグの位置が前記タグ位置記憶手段に記憶されていない場合、該開始タグの位置を前記副タグ一時記憶部に格納する副開始タグ解析手段と、
   前記副開始タグ解析手段による字句解析において、前記開始タグの位置が前記タグ位置記憶手段に記憶されている場合、該開始タグに対応する前記終了タグを該タグ位置記憶手段から読み出し、該開始タグの位置から、読み出した該終了タグの位置までの部分をスキップする副スキップ手段と、
   前記所定の位置からの前記テキストのうち、解析されていない部分を、先頭から順に終了タグが出現するまで字句解析し、該終了タグの位置と、前記副タグ一時記憶部に最後に格納された前記開始タグの位置とを対応付けて前記タグ位置記憶手段に記憶する副終了タグ解析手段と、
   を有する請求項３に記載の構文解析装置。
5. 前記副字句解析手段は、前記所定の位置から、タグの末尾の文字が出現するまで、前記テキストをスキップし、該スキップ後、タグの先頭の文字が出現するまで、該テキストをスキップする開始時スキップ手段を更に有する、請求項４に記載の構文解析装置。
6. 前記並列解析手段は、使用できるリソース量が所定値以上であれば、前記テキストを並列に構文解析する、請求項１乃至５のいずれか１項に記載の構文解析装置。
7. 前記並列解析手段は、前記構文解析において、並列化した回数が上限値以下であれば、前記テキストを並列に構文解析する、請求項１乃至６のいずれか１項に記載の構文解析装置。
8. 前記リソースは、ＣＰＵ、タスク、スレッド、又はＣＰＵの使用時間を含む、請求項１乃至７のいずれか１項に記載の構文解析装置。
9. 前記並列解析手段により構文解析された結果に基づいて前記テキストを表示するブラウザを更に有する、請求項１乃至８のいずれか１項に記載の構文解析装置。
10. 前記マークアップ言語は、ＸＭＬ(Extensible Markup Language)である、請求項１乃至９のいずれか１項に記載の構文解析装置。
11. 前記マークアップ言語は、ＨＴＭＬ(Hyper Text Markup Language)であり、
    前記ブラウザは、ＨＴＭＬブラウザである、請求項９に記載の構文解析装置。
12. タグ位置取得手段が、割り当てられたリソースを使用して、マークアップ言語で記述されたテキストを順次、字句解析していき、該テキストにおける、開始タグの位置と、該開始タグに対応する終了タグの位置とを取得し、取得した前記開始タグの位置と、前記終了タグの位置とを対応付けてタグ位置記憶手段に格納し、
    並列解析手段が、前記テキストを、前記タグ位置記憶手段に記憶された前記開始タグの位置まで構文解析したとき、該開始タグと対応する前記終了タグの位置を該タグ位置記憶手段から読み出し、該開始タグと、該開始タグに対応する終了タグと間の文字数を算出し、該文字数が閾値以上であれば、該開始タグと該終了タグとの間の部分と、該終了タグ以降の部分とを異なるリソースで並列に構文解析し、
    調整手段が、前記テキストにおける、前記タグ位置取得手段により前記字句解析が行われている位置から、前記並列解析手段により前記構文解析が行われている位置を引いた値が、正の値で所定の範囲内であり、且つ前記構文解析の処理速度ができるだけ速くなるように、該タグ位置取得手段と該並列解析手段とに割り当てるリソースの割合を調整する、構文解析方法。
13. コンピュータに、
    割り当てられたリソースを使用して、マークアップ言語で記述されたテキストを順次、字句解析していき、該テキストにおける、開始タグの位置と、該開始タグに対応する終了タグの位置とを取得し、取得した前記開始タグの位置と、前記終了タグの位置とを対応付けてタグ位置記憶手段に格納するタグ位置取得手順、
    前記テキストを、前記タグ位置記憶手段に記憶された前記開始タグの位置まで構文解析したとき、該開始タグと対応する前記終了タグの位置を該タグ位置記憶手段から読み出し、該開始タグと、該開始タグに対応する終了タグと間の文字数を算出し、該文字数が閾値以上であれば、該開始タグと該終了タグとの間の部分と、該終了タグ以降の部分とを異なるリソースで並列に構文解析する並列解析手順、及び
    前記タグ位置取得手順における前記字句解析の処理速度をできるだけ速くし、前記テキストにおける、該字句解析が終わり、前記構文解析手順における前記構文解析が終わっていない部分の文字数を所定の範囲内にするように、前記タグ位置取得処理に割り当てるリソース量と前記並列解析処理に割り当てるリソース量とを調整する調整手順、
    を実行させるためのプログラム。

Images