JP7702933B2

JP7702933B2 - 解析装置、解析方法及び解析プログラム

Info

Publication number: JP7702933B2
Application number: JP2022501600A
Authority: JP
Inventors: 忠賢千田
Original assignee: Nippon Telegraph and Telephone Corp; NTT Inc USA
Current assignee: NTT Inc; NTT Inc USA
Priority date: 2020-02-21
Filing date: 2020-02-21
Publication date: 2025-07-04
Anticipated expiration: 2040-02-21
Also published as: JPWO2021166271A1; WO2021166271A1; US20230071959A1; US11947907B2

Description

本発明は、解析装置、解析方法及び解析プログラムに関する。

データをコンピュータで扱える形に変換する構文解析器が知られている。構文解析器は、変換元のパターンを記述する言語（以降、単に言語と呼ぶ）に従ってデータを解析し、変換する。

例えば、構文解析器には、正規表現を拡張した言語でパターンを記述し、バックトラッキングに基づく構文解析アルゴリズムを用いてデータを解析するものがある。また、例えば、PEG（Parsing Expression Grammar）を拡張した言語でパターンを記述するStateful Packrat Parsingと呼ばれる構文解析アルゴリズムを用いて、文脈に依存したパターンを解析する構文解析器が知られている（例えば、非特許文献１及び２を参照）。

KURAMITSU, K. Nez : Open grammar language and tools. （URL: http://nez-peg.github.io/） GIETZEN, J. Pegasus: Super-easy peg parsing for .net. （URL: http://otac0n.com/Pegasus/）

しかしながら、従来の文脈に依存したパターンに対応した構文解析器には、解析に膨大な時間がかかる場合があるという問題がある。例えば、非特許文献１及び２に記載の構文解析器では、データのサイズに対して指数関数時間の動作が必要になる場合がある。

上述した課題を解決し、目的を達成するために、解析装置は、所定の終端記号に変数を対応付けたPEGで記述された文法を基に、第１の文字列の構文解析を行う解析部と、前記第１の文字列の一部であって、前記解析部により前記終端記号に対応することが解析された第２の文字列に所定の属性を付与した要素を、前記変数に追加する追加部と、前記変数から、各属性の最新の要素を抽出する抽出部と、前記抽出部によって抽出された要素が文脈に関する所定の条件に合致するか否かを判定する判定部と、を有することを特徴とする。

本発明によれば、文脈に依存したパターンに対応した構文解析にかかる時間を短縮することができる。

図１は、第１の実施形態に係る表示システムの構成例を示す図である。図２は、第１の実施形態に係る解析装置の構成例を示す図である。図３は、V-PEGの構文を示す図である。図４は、構文解析の入出力を説明する図である。図５は、parse関数のアルゴリズムを示す図である。図６は、第１の実施形態に係る解析装置の処理の流れを示すフローチャートである。図７は、parse関数の処理の流れを示すフローチャートである。図８は、メモテーブルの一例を示す図である。図９は、メモテーブルの一例を示す図である。図１０は、メモテーブルの一例を示す図である。図１１は、メモテーブルの一例を示す図である。図１２は、メモテーブルの一例を示す図である。図１３は、メモテーブルの一例を示す図である。図１４は、メモテーブルの一例を示す図である。図１５は、メモテーブルの一例を示す図である。図１６は、メモテーブルの一例を示す図である。図１７は、解析プログラムを実行するコンピュータの一例を示す図である。

以下に、本願に係る解析装置、解析方法及び解析プログラムの実施形態を図面に基づいて詳細に説明する。なお、本発明は、以下に説明する実施形態により限定されるものではない。

［第１の実施形態の構成］
図１は、第１の実施形態に係る表示システムの構成例を示す図である。図１に示すように、表示システムは、解析装置１０及び表示装置２０を有する。解析装置１０は、例えばサーバである。表示装置２０は、例えばパーソナルコンピュータである。

解析装置１０は、パターンを記述した言語の情報、及び、所定の形式の文字列のデータ（以降、単に文字列と呼ぶ場合がある）の入力を受け付ける。解析装置１０の解析部１３１は、文字列の構文解析を行う。そして、解析装置１０の表示制御部１３５は、構文解析の結果を基にウェブページの情報を生成し、表示装置２０に送信する。

表示装置２０は、解析装置１０から受信したウェブページの情報を基に、ブラウザ等の機能を用いてウェブページを表示する。なお、解析装置１０は、表示装置２０によるウェブページへのアクセス要求に応じて構文解析処理を始めてもよい。

図１の例では、解析装置１０は、JSONのパターンを記述した言語の情報及びJSON形式のデータの入力を受け付ける。解析部１３１は、JSON形式のデータから人物名を抽出する。表示制御部１３５は、抽出された人物名を表示するウェブページのレンダリングを行う。

図２は、第１の実施形態に係る解析装置の構成例を示す図である。図２に示すように、解析装置１０は、インタフェース部１１、記憶部１２及び制御部１３を有する。

インタフェース部１１は、データの入出力のためのインタフェースである。インタフェース部１１は、例えばマウスやキーボード等の入力装置を介してデータの入力を受け付ける。また、インタフェース部１１は、例えばディスプレイ等の出力装置にデータを出力する。また、インタフェース部１１は、他の装置との間でデータの通信を行うためのNIC（Network Interface Card）等の通信インタフェースであってもよい。

記憶部１２は、HDD（Hard Disk Drive）、SSD（Solid State Drive）、光ディスク等の記憶装置である。なお、記憶部１２は、RAM（Random Access Memory）、フラッシュメモリ、NVSRAM（Non Volatile Static Random Access Memory）等のデータを書き換え可能な半導体メモリであってもよい。記憶部１２は、解析装置１０で実行されるOS（Operating System）や各種プログラムを記憶する。記憶部１２は、例えば文法情報１２１及び解析結果情報１２２を記憶する。

文法情報１２１は、所定のパターンを記述した言語の情報である。例えば、文法情報１２１は、後述するV-PEGで記述された情報である。なお、文法情報１２１は、あらかじめ記憶部１２に記憶されていてもよいし、解析対象の文字列とともに解析装置１０に入力されてもよい。

解析結果情報１２２は、構文解析の途中経過及び最終的な結果を示す情報である。例えば、解析結果情報１２２は、後述するPackrat Parsingで用いられるメモテーブルを含むものであってもよい。

制御部１３は、解析装置１０全体を制御する。制御部１３は、例えば、CPU（Central Processing Unit）、MPU（Micro Processing Unit）等の電子回路や、ASIC（Application Specific Integrated Circuit）、FPGA（Field Programmable Gate Array）等の集積回路である。また、制御部１３は、各種の処理手順を規定したプログラムや制御データを格納するための内部メモリを有し、内部メモリを用いて各処理を実行する。また、制御部１３は、各種のプログラムが動作することにより各種の処理部として機能する。例えば、制御部１３は、解析部１３１、追加部１３２、抽出部１３３、判定部１３４及び表示制御部１３５を有する。

解析部１３１は、所定の終端記号に変数を対応付けたPEGで記述された文法を基に、第１の文字列の構文解析を行う。解析部１３１は、文法情報１２１及び解析対象の入力を受け付け、解析結果情報１２２を出力する。

ここで、本実施形態では、所定の終端記号に変数を対応付けたPEGをV-PEG（Parsing Expression Grammar with Variable Bindings）と呼ぶ。V-PEGにおける文法Gは、G=(N,Σ,R,V,e_S)のように表される。Nは非終端記号の有限集合である。Σは終端記号の有限集合である。Rはルールの有限集合である。Vは変数の有限集合である。e_Sは開始表現である。ルールはA=eのように記述される。ただし、A∈Nである。また、eは図３に示す通りである。図３は、V-PEGの構文を示す図である。

図４は、構文解析の入出力を説明する図である。図４に示すように、解析部１３１は、V-PEGで記述された情報２０１と文字列２０２の入力を受け付ける。そして、解析部１３１は、解析結果を出力する。ここでは、解析部１３１は、CSVのパターンをV-PEGで記述した情報の入力を受け付け、最終的な解析結果として、date、name、ageといった項目名と各項目値を対応付けたデータを出力する。

ここで、文脈に依存しないパターンを解析する構文解析手法として、Packrat Parsingが知られている。Packrat Parsingでは、再帰下降構文解析とバックトラッキング及びメモ化が行われる。Packrat Parsingを実装した構文解析器であるPackrat Parserは、文法と対応した解析用のparse関数を有する。parse関数は、Nを非終端記号の集合とし、Iを入力上の位置の集合とすると、以下のように表現される。
parse : N ×I → I

Packrat Parsingでは、終端記号に対応付けられた変数は不要なので、例えばHTMLの文法であれば以下のように記述される。
HTML::=‘<’Name‘>’HTML*‘</’Name‘>’|‘<’Name‘>’
Name::=[a-zA-Z]+

一方、Packrat Parsingを拡張した構文解析手法であるStateful Packrat Parsingは、文脈に依存するパターンを解析する。Stateful Packrat Parsingでは、下記のようにEBNF（Extended Backus-Naur Form）と３つの関数(scope、bind、match)で文法が記述される。
<EBNF>
HTML=scope(‘<’bind(v,Name)‘>’HTML*‘</’match(v,Name)‘>’)|‘<’Name‘>’
Name=[a-zA-Z]+

scope、bind、matchはHTMLファイルのタグの対応関係を調べるために使われる関数である。このとき、開きタグが連続したHTMLファイル(例えば<a><c>…)を従来のStateful Packrat Parsing構文解析器の入力として与えると、開きタグの数に比例して処理時間が指数的に遅くなることが知られている。

ここで、実用上必要となる文脈に依存したパターンはいくつかの関数さえあれば表現できることが知られている（例えば、参考文献１を参照）。
参考文献１：KURAMITSU, K. A symbol-based extension of parsing expression grammars and context-sensitive packrat parsing. In Proceedings of the 10thACM SIGPLAN International Conference on Software Language Engineering (New York, NY, USA, 2017), SLE 2017, ACM, pp. 26-37.

そこで、本実施形態では、Stateful Packrat Parsingのように任意の関数を組み込めるようにするのではなく、必要最小限の関数のみ組み込めるようにしたV-PEGを用いて文法が記述される。例えば、V-PEGでは下記のように文法が記述される。
<V-PEG>
HTML=scope(‘<’bind(v,Name)‘>’HTML*‘</’match(v,Name)‘>’)/‘<’Name‘>’
Name=[a-zA-Z]+

この例では、文法Gは以下のように表される。
G=(N,Σ,R,V,e_S)
N={HTML,Name}
Σ={‘<’,’>’,’/’,’a’,…,’z’,’A’,…,’Z’}
R：上記のHTMLとNameのルールの集合
V={v}
e_S=HTML

EBNFでは、複数の表現が記号「|」により区分されているのに対し、V-PEGでは、複数の表現が記号「/」により区分されている。例えば、上記のV-PEGでは、HTMLの２つの表現「scope(‘<’bind(v,Name)‘>’HTML*‘</’match(v,Name)‘>’)」と「‘<’Name‘>’」が、記号「/」により区分されている。

例えば、α、βという２つの表現がある場合に、EBNFでは、「α|β」のように記述される。一方、V-PEGでは、「α/β」のように記述される。ここで、α|βは文字列がαにマッチした場合であってもβにマッチするか否かを試行する一方で、α/βは文字列がαにマッチした場合、βにマッチするか否かを試行しない。

例えば、本実施形態において、解析部１３１は、文字列が表現「scope(‘<’bind(v,Name)‘>’HTML*‘</’match(v,Name)‘>’)」にマッチしない場合、「‘<’Name‘>’」にマッチするか否かを解析する。

追加部１３２は、第１の文字列の一部であって、解析部１３１により終端記号に対応することが解析された第２の文字列に所定の属性を付与した要素を、変数に追加する。例えば、追加部１３２は、属性をキーとし、第２の文字列をバリューとするキーバリュー形式の要素を、配列である変数の右端に追加する。追加部１３２は、文字列及び属性の入力を受け付け、要素又は要素を追加した変数を出力する。

ここで、HTMLの場合を例に挙げると、属性は「開きタグ」及び「閉じタグ」であってもよい。この場合、HTMLの開きタグは、[a-zA-Z]+、すなわち１文字以上の大文字と小文字のアルファベットのみを囲む「<」及び「>」である。一方、HTMLの閉じタグは、[a-zA-Z]+、すなわち１文字以上の大文字と小文字のアルファベットのみを囲む「</」及び「>」である。

例えば、「<a><c>」という文字列をHTMLの文法を基に解析する場合、追加部１３２は、配列である変数E_mに(v₁,ａ)、(v₂,b)、(v₁,c)のような要素を追加する。v₁は属性「開きタグ」に対応するキーである。v₂は属性「閉じタグ」に対応するキーである。また、追加部１３２は、新しい要素を配列の右側に追加していく。

抽出部１３３は、変数から、各属性の最新の要素を抽出する。例えば、抽出部１３３は、配列のキーが同じである要素のうち、最も右側にある要素を抽出する。例えば、変数E_m＝[(v₁,ａ),(v₂,b),(v₁,c)]である場合を考える。この場合、v₁がキーである要素が２つあり、抽出部１３３は、より新しい(v₁,c)を抽出する。抽出部１３３は、抽出前の変数の入力を受け付け、抽出後の変数を出力する。例えば、抽出部１３３は、変数E_m＝[(v₁,ａ),(v₂,b),(v₁,c)]の入力を受け付け、抽出後の変数E_m＝[(v₁,c),(v₂,b)]を出力する。

判定部１３４は、抽出部１３３によって抽出された要素が文脈に関する所定の条件に合致するか否かを判定する。HTMLの例では、判定部１３４は、抽出部１３３によって抽出された要素の文字列と、第１の文字列における閉じタグの中の文字列が一致するか否かを判定する。前述の例では、抽出部１３３は、要素(v1,c)を抽出する。すなわち、抽出部１３３によって抽出された要素の文字列はcである。cは開きタグの中の文字列である。一方、文字列「<a><c>」は第１の文字列の一例である。この場合、bは閉じタグの中の文字列である。

抽出部１３３による抽出後の変数が、E_m＝[(v₁,c),(v₂,b)]である場合、判定部１３４は、開きタグと閉じタグの中にある文字列が同じであるか否かを判定する。この場合、開きタグの文字列はcであり、閉じタグの文字列はbであるため、判定部１３４は、開きタグと閉じタグの中にある文字列が同じでないと判定する。HTMLのシンタックスでは、開きタグと対応する閉じタグの中の文字列は同じであるため、この判定は、HTMLの文脈上の依存関係に基づいたものである。

図５は、parse関数のアルゴリズムを示す図である。本実施形態のparse関数は、図５の１行目に示すように、変数E_mに対しfilter関数がかけられる。従来のStateful Packrat Parsingにおけるparse関数（参考文献２を参照）には、filter関数は含まれない。filter関数は、抽出部１３３が実行する処理を表すものである。本実施形態のparse関数は、もう１つのグローバル変数E_eの記録は行われない。
参考文献２：FORD, B. Packrat parsing:: Simple, powerful, lazy, linear time, functional pearl. In Proceedings of the Seventh ACM SIGPLAN International Conference on Functional Programming (New York, NY, USA, 2002), ICFP’02, ACM, pp. 36-47.

従来のStateful Packrat Parsingにおけるparse関数では、入力上の位置i、非終端記号A及びグローバル変数の全体が記録される。一方、本実施形態のparse関数では、入力上の位置i、非終端記号A及びグローバル変数の一部が記録される。M_Sはメモテーブルであり、４つ組を引数に取り３つ組(i’,E_m’,E_e’)を返す関数である。domはM_Sの定義域を返す関数である。５行目のkeyと(j,E_m’,E_e’)との間にある棒付きの矢印は、M_Sの要素を置き換えることを示す記号である。

［第１の実施形態の処理］
図６は、第１の実施形態に係る解析装置の処理の流れを示すフローチャートである。図６に示すように、まず、解析装置１０は、V-PEGと文字列の入力を受け付ける（ステップＳ１１）。次に、解析装置１０は、parse関数を実行し解析を行う（ステップＳ１２）。そして、解析装置１０は、解析結果を出力する（ステップＳ１３）。

図７は、parse関数の処理の流れを示すフローチャートである。図７は、図６のステップＳ１２の処理を詳細を示すフローチャートである。ここでは、解析部１３１が、parse(A,i,E_m,E_e)を実行するものとする。変数E_mは配列であるものとする。また、iの初期値は０とする。また、Aは例えばHTMLである。

まず、抽出部１３３は、A,iとE_mにfilter関数を適用したものからなる３つ組(A,i,filter(Em))を用意する（ステップＳ１０１）。次に、判定部１３４は、メモテーブルM_sの中に(A,i,filter(Em))に対応する要素が存在するか否かを判定する（ステップＳ１０２）。

解析部１３１は、メモテーブルM_sの中に(A,i,filter(Em))に対応する要素が存在する場合（ステップＳ１０２、Yes）、M_sの中の(A,i,filter(Em))に対応する要素を返す（ステップＳ１０３）。一方、解析部１３１は、メモテーブルM_sの中に(A,i,filter(E_m))に対応する要素が存在しない場合（ステップＳ１０２、No）、A=eとしてparse(e,i,E_m,E_e)を実行する（ステップＳ１０４）。

そして、解析部１３１は、parse(e,i,E_m,E_e)の戻り値(j,E'_m,E'_e)をメモテーブルM_sに記録する（ステップＳ１０５）。さらに、解析部１３１は、parse(e,i,E_m,E_e)の戻り値(j,E'_m,E'_e)を返す（ステップＳ１０６）。

［第１の実施形態の効果］
これまで説明してきたように、解析部１３１は、所定の終端記号に変数を対応付けたPEGで記述された文法を基に、第１の文字列の構文解析を行う。また、追加部１３２は、第１の文字列の一部であって、解析部１３１により終端記号に対応することが解析された第２の文字列に所定の属性を付与した要素を、変数に追加する。また、抽出部１３３は、変数から、各属性の最新の要素を抽出する。また、判定部１３４は、抽出部１３３によって抽出された要素が文脈に関する所定の条件に合致するか否かを判定する。このように、解析装置１０は、変数に格納された要素のうち、最新でないものを抽出しないようにする。このため、本実施形態によれば、文脈に依存したパターンに対応した構文解析にかかる時間を短縮することができる。本実施形態によれば、従来の技術では指数関数時間で増加していた処理時間を、多項式時間に抑えることができる。

追加部１３２は、属性をキーとし、第２の文字列をバリューとするキーバリュー形式の要素を、配列である変数の右端に追加する。また、抽出部１３３は、配列のキーが同じである要素のうち、最も右側にある要素を抽出する。このように、配列を変数として用いることで、最新の要素を容易に抽出することができる。

解析部１３１は、HTMLの文法を基に第１の文字列の構文解析を行う。また、追加部１３２は、第１の文字列における開きタグの中の文字列に、開きタグを示す属性を付与した要素を変数に追加する。また、抽出部１３３は、開きタグを示す属性の要素のうち最新の要素を抽出する。また、判定部１３４は、抽出部１３３によって抽出された要素の文字列と、第１の文字列における閉じタグの中の文字列が一致するか否かを判定する。これにより、HTMLのシンタックスに沿った構文解釈ができる。

［Packrat Parsing］
ここで、本実施形態との対比のために、従来のPackrat Parsingを説明する。ここでは、HTMLの文法が以下のように記述されているものとする。
HTML::=‘<’Name‘>’HTML*‘</’Name‘>’|‘<’Name‘>’
Name::=[a-zA-Z]+

解析対象の文字列を「<a></a>」とする。また、parse(HTML,i)は、入力上の位置iからHTMLを解析する関数である。また、parse(Name,i)は、入力上の位置iからNameを解析する関数である。parse関数は引数が定まると返り値が一意に定まる。また、Packrat Parsingでは、parse関数の解析結果を全てメモテーブルに記録しておき、parse関数を既に解析した引数で呼び出した際は解析を実施せずに記録した解析結果を返す。

図８から図１６は、メモテーブルの一例を示す図である。図８の上段のテーブルには、解析対象の文字列の各文字とその位置が示されている。下段のテーブルは、HTMLの解析結果（H）とNameの解析結果（N）を記録するメモテーブルである。「？」は初期値（例えばNull）である。ここでは、解析装置１０ａが解析を行うものとする。

まず、解析装置１０ａは、parse(HTML,0)を実行する。ここで、i=1の位置にある「a」は、終端記号のNameに対応するため、解析装置１０ａは、parse(Name,1)を実行する。そして、i=2の位置にある「>」はNameにマッチしないため、解析装置１０ａは、図９に示すように、parse(Name,1)の解析結果として、Nameのテーブルのi=1の位置に2を記録する。

さらに、i=3の位置にある「<」は、終端記号のHTMLに対応するため、解析装置１０ａは、parse(HTML,3)を実行する。そして、i=4の位置で、解析装置１０ａはさらにparse(Name,4)を実行する。i=5の位置にある「>」はNameにマッチしないため、解析装置１０ａは、図１０に示すように、parse(Name,4)の解析結果として、Nameのテーブルのi=4の位置に5を記録する。

さらに、i=6の位置にある「<」は、終端記号のNameに対応するため、解析装置１０ａは、parse(HTML,6)を実行する。そして、i=7の位置で、解析装置１０ａはさらにparse(Name,7)を実行する。i=7の位置にある「/」はNameにマッチしないため、解析装置１０ａは、図１１に示すように、parse(Name,7)の解析結果として、Nameのテーブルのi=7の位置にfailを記録する。

parse(HTML,6)は、マッチ失敗になったが、次の条件があるため、解析装置１０ａは次の条件を試行する。解析装置１０ａは、i=6にバックトラックし、i=7に進んだところでparse(Name,7)を実行する。図１１に示すように、i=7の位置の解析結果は既に存在するので、解析装置１０ａは再度解析はしない。

その結果、図１２に示すように、解析装置１０ａは、parse(HTML,6)の解析結果であるfailを、HTMLのテーブルのi=6の位置に記録する。さらに、解析装置１０ａは、i=8に進んだところでparse(Name,8)を実行する。parse(Name,8)の結果、i=9の位置にある「>」はNameにマッチしないため、図１３に示すように、解析装置１０ａは、parse(Name,8)の解析結果として、Nameのテーブルのi=8の位置に9を記録する。

さらに、解析装置１０ａは、parse(HTML,3)がi=9の位置でHTMLに完全にマッチするため、図１４に示すように、parse(HTML,3)の解析結果として、HTMLのテーブルのi=3の位置に10を記録する。ここでは、解析装置１０ａは、仮にi=10の位置を仮定し、i=10の位置ではHTMLマッチしなかったとみなしている。また、図１６のように、parse(HTML,10)の解析結果についても、failとして記録される。

解析装置１０ａは、i=0にバックトラックする。図１６に示すように、i=4の位置の解析結果は既に存在するので、解析装置１０ａは再度解析はしない。そして、解析装置１０ａは、parse(HTML,0)の解析結果として、HTMLのテーブルのi=0の位置に3を記録する。

この解析結果によれば、「<a>」と「</a>」がそれぞれ別々のHTMLということになる。しかしながら、HTMLでは開きかっこと閉じかっこの中の文字列は同一である必要がある。そこで、このような解析結果を回避するために、本実施形態の判定部１３４は、文脈に関する所定の条件に合致するか否かの判定を行う。さらに、抽出部１３３による抽出処理により、判定のための処理時間を短縮することができる。

［その他の実施形態］
第１の実施形態では、グローバル変数が配列である場合を例に挙げて説明した。一方で、グローバル変数は配列以外のデータであってもよい。例えば、グローバル変数はスタックであってもよい。

この場合、追加部１３２は、属性に対応するスタックに、第２の文字列をpushする。そして、抽出部１３３は、スタックのtopをpopすることによって抽出する。例えば、スタックが、HTMLの開きかっこに対応するものとする。このとき、追加部１３２は、開きかっこの中の文字列を第２の文字列としてスタックにpushすることで追加する。このため、最新の要素はスタックのtopに存在することになる。

判定部１３４は、以下のcheck関数を実行することで開きタグと閉じタグの中の文字列が同じであるか否かを判定する。なお、抽出部１３３は、文字列が閉じタグにマッチした場合にスタックSのtopをpushする。
check(opening_tag):
if S.empty():
return false
closing_tag= S.top()
return opening_tag==closing_tag

［システム構成等］
また、図示した各装置の各構成要素は機能概念的なものであり、必ずしも物理的に図示のように構成されていることを要しない。すなわち、各装置の分散及び統合の具体的形態は図示のものに限られず、その全部又は一部を、各種の負荷や使用状況等に応じて、任意の単位で機能的又は物理的に分散又は統合して構成することができる。さらに、各装置にて行われる各処理機能は、その全部又は任意の一部が、CPU及び当該CPUにて解析実行されるプログラムにて実現され、あるいは、ワイヤードロジックによるハードウェアとして実現され得る。

また、本実施形態において説明した各処理のうち、自動的に行われるものとして説明した処理の全部又は一部を手動的に行うこともでき、あるいは、手動的に行われるものとして説明した処理の全部又は一部を公知の方法で自動的に行うこともできる。この他、上記文書中や図面中で示した処理手順、制御手順、具体的名称、各種のデータやパラメータを含む情報については、特記する場合を除いて任意に変更することができる。

［プログラム］
一実施形態として、解析装置１０は、パッケージソフトウェアやオンラインソフトウェアとして上記の解析処理を実行する解析プログラムを所望のコンピュータにインストールさせることによって実装できる。例えば、上記の解析プログラムを情報処理装置に実行させることにより、情報処理装置を解析装置１０として機能させることができる。ここで言う情報処理装置には、デスクトップ型又はノート型のパーソナルコンピュータが含まれる。また、その他にも、情報処理装置にはスマートフォン、携帯電話機やPHS（Personal Handyphone System）等の移動体通信端末、さらには、PDA（Personal Digital Assistant）等のスレート端末等がその範疇に含まれる。

また、解析装置１０は、ユーザが使用する端末装置をクライアントとし、当該クライアントに上記の解析処理に関するサービスを提供する解析サーバ装置として実装することもできる。例えば、解析サーバ装置は、グラフデータを入力とし、グラフ信号処理又はグラフデータの分析結果を出力とする解析サービスを提供するサーバ装置として実装される。この場合、解析サーバ装置は、Webサーバとして実装することとしてもよいし、アウトソーシングによって上記の解析処理に関するサービスを提供するクラウドとして実装することとしてもかまわない。

図１７は、解析プログラムを実行するコンピュータの一例を示す図である。コンピュータ１０００は、例えば、メモリ１０１０、CPU１０２０を有する。また、コンピュータ１０００は、ハードディスクドライブインタフェース１０３０、ディスクドライブインタフェース１０４０、シリアルポートインタフェース１０５０、ビデオアダプタ１０６０、ネットワークインタフェース１０７０を有する。これらの各部は、バス１０８０によって接続される。

メモリ１０１０は、ROM（Read Only Memory）１０１１及びRAM１０１２を含む。ROM１０１１は、例えば、BIOS（BASIC Input Output System）等のブートプログラムを記憶する。ハードディスクドライブインタフェース１０３０は、ハードディスクドライブ１０９０に接続される。ディスクドライブインタフェース１０４０は、ディスクドライブ１１００に接続される。例えば磁気ディスクや光ディスク等の着脱可能な記憶媒体が、ディスクドライブ１１００に挿入される。シリアルポートインタフェース１０５０は、例えばマウス１１１０、キーボード１１２０に接続される。ビデオアダプタ１０６０は、例えばディスプレイ１１３０に接続される。

ハードディスクドライブ１０９０は、例えば、ＯＳ１０９１、アプリケーションプログラム１０９２、プログラムモジュール１０９３、プログラムデータ１０９４を記憶する。すなわち、解析装置１０の各処理を規定するプログラムは、コンピュータにより実行可能なコードが記述されたプログラムモジュール１０９３として実装される。プログラムモジュール１０９３は、例えばハードディスクドライブ１０９０に記憶される。例えば、解析装置１０における機能構成と同様の処理を実行するためのプログラムモジュール１０９３が、ハードディスクドライブ１０９０に記憶される。なお、ハードディスクドライブ１０９０は、SSDにより代替されてもよい。

また、上述した実施形態の処理で用いられる設定データは、プログラムデータ１０９４として、例えばメモリ１０１０やハードディスクドライブ１０９０に記憶される。そして、CPU１０２０は、メモリ１０１０やハードディスクドライブ１０９０に記憶されたプログラムモジュール１０９３やプログラムデータ１０９４を必要に応じてRAM１０１２に読み出して、上述した実施形態の処理を実行する。

なお、プログラムモジュール１０９３やプログラムデータ１０９４は、ハードディスクドライブ１０９０に記憶される場合に限らず、例えば着脱可能な記憶媒体に記憶され、ディスクドライブ１１００等を介してCPU１０２０によって読み出されてもよい。あるいは、プログラムモジュール１０９３及びプログラムデータ１０９４は、ネットワーク（LAN（Local Area Network）、WAN（Wide Area Network）等）を介して接続された他のコンピュータに記憶されてもよい。そして、プログラムモジュール１０９３及びプログラムデータ１０９４は、他のコンピュータから、ネットワークインタフェース１０７０を介してCPU１０２０によって読み出されてもよい。

１０解析装置
２０表示装置
１１インタフェース部
１２記憶部
１３制御部
１２１文法情報
１２２解析結果情報
１３１解析部
１３２追加部
１３３抽出部
１３４判定部
１３５表示制御部

Claims

文字列をマッチさせるための表現であって、終端記号と非終端記号により属性に対応する部分が示された表現に、第１の文字列がマッチするか否かを解析する解析部と、
前記第１の文字列が前記表現にマッチした場合、前記第１の文字列の前記属性に対応する部分のうちの非終端記号にマッチする第２の文字列に前記属性を付与した要素を、変数に追加する追加部と、
前記変数から、各属性の最新の要素を抽出する抽出部と、
前記抽出部によって抽出された要素が文脈に関する所定の条件に合致するか否かを判定する判定部と、
を有することを特徴とする解析装置。
前記追加部は、前記属性をキーとし、前記第２の文字列をバリューとするキーバリュー形式の要素を、配列である前記変数の右端に追加し、
前記抽出部は、前記配列のキーが同じである要素のうち、最も右側にある要素を抽出することを特徴とする請求項１に記載の解析装置。
前記追加部は、前記属性に対応するスタックに、前記第２の文字列をpushし、
前記抽出部は、前記スタックのtopをpopすることによって抽出することを特徴とする請求項１に記載の解析装置。
前記解析部は、HTMLの文法を基に前記第１の文字列の構文解析を行い、
前記追加部は、前記第１の文字列における開きタグの中の文字列に、開きタグを示す属性を付与した要素を前記変数に追加し、
前記抽出部は、開きタグを示す属性の要素のうち最新の要素を抽出し、
前記判定部は、前記抽出部によって抽出された要素の文字列と、前記第１の文字列における閉じタグの中の文字列が一致するか否かを判定することを特徴とする請求項１から３のいずれか１項に記載の解析装置。
解析装置によって実行される解析方法であって、
文字列をマッチさせるための表現であって、終端記号と非終端記号により属性に対応する部分が示された表現に、第１の文字列がマッチするか否かを解析する解析工程と、
前記第１の文字列が前記表現にマッチした場合、前記第１の文字列の前記属性に対応する部分のうちの非終端記号にマッチする第２の文字列に前記属性を付与した要素を、変数に追加する追加工程と、
前記変数から、各属性の最新の要素を抽出する抽出工程と、
前記抽出工程によって抽出された要素が文脈に関する所定の条件に合致するか否かを判定する判定工程と、
を含むことを特徴とする解析方法。
コンピュータを、請求項１から４のいずれか１項に記載の解析装置として機能させるための解析プログラム。