(57)【要約】      （修正有）【課題】形式言語処理パーサーにFP以外の文字列処理関数、例えば、自然言語処理パーサーを組み合わせたパーサーを自動的に生成する手法を提供する。【解決手段】文法記述は、第１の文法記述(P1)に関連付けられた第１のパーサーを使用して、入力文字列(str)の先頭文字列から第２の文法記述(P2)に関連付けられた第２のパーサーで最初に受理可能な少なくとも１つのstrの直前の入力文字列までをパーズし、P2を使用して、当該第２のパーサーで最初に受理可能な少なくとも１つのstrをパーズする文法記述P1 U P2； P2に関連付けられた第２のパーサーを使用して、当該第２のパーサーで受理可能であり且つstrの先頭文字列を含む少なくとも１つのstrをパーズし、P1に関連付けられた第１のパーサーを使用して、当該パーズされた少なくとも１つのstrをパーズする文法記述P1 F P2である。【選択図】図３
2012063868.tif 000002
【特許請求の範囲】
【請求項１】
少なくとも２の言語処理パーサーを組み合わせて、組み合わせパーサーを生成する方法であって、コンピュータが、
下記に特定された文法記述の少なくとも１つに関連付けられた各パーサーを組み合わせて、組み合わせパーサーを生成するステップを実行する、前記方法：
第１の文法記述（Ｐ１）に関連付けられた第１のパーサーを使用して、入力文字列の先頭文字列から第２の文法記述（Ｐ２）に関連付けられた第２のパーサーで最初に受理可能な少なくとも１つの入力文字列の直前の入力文字列までをパーズし、前記第２のパーサーを使用して、当該第２のパーサーで前記最初に受理可能な少なくとも１つの入力文字列をパーズする文法記述Ｐ１ Ｕ Ｐ２、及び
第２の文法記述（Ｐ２）に関連付けられた第２のパーサーを使用して、当該第２のパーサーで受理可能であり且つ入力文字列の先頭文字列を含む少なくとも１つの入力文字列をパーズし、第１の文法記述（Ｐ１）に関連付けられた第１のパーサーを使用して、当該パーズされた少なくとも１つの入力文字列をパーズする文法記述Ｐ１ Ｆ Ｐ２。
【請求項２】
前記コンピュータが、
複数の文法記述を含む宣言的記述を受け取るステップと、
前記受け取った宣言的記述をパーズして、当該宣言的記述中に示される各文法記述の組み合わせを特定するステップであって、前記文法記述は、前記文法記述Ｐ１ Ｕ Ｐ２及び文法記述Ｐ１ Ｆ Ｐ２から選ばれる少なくとも１つを有している、前記特定するステップと
を実行することをさらに含み、
前記組み合わせパーサーを生成するステップにおいて、前記特定するステップにおいて特定された各文法記述に関連付けられた各パーサーが組み合わされて、組み合わせパーサーが生成される、請求項１に記載の方法。
【請求項３】
前記文法記述Ｐ１ Ｕ Ｐ２又は前記文法記述Ｐ１ Ｆ Ｐ２において、Ｐ１又はＰ２のうちの一方の文法記述が、受理言語を持たず且つ入力文字列の全てを受理してパーズする文字列処理関数（以下、当該文法記述をＮともいう）である、請求項１又は２に記載の方法。
【請求項４】
前記文法記述Ｎにおいて、前記文字列処理関数が自然言語処理名である、請求項３に記載の方法。
【請求項５】
前記文法記述Ｐ１ Ｕ Ｐ２又は前記文法記述Ｐ１ Ｆ Ｐ２において、Ｐ１又はＰ２のうちの一方の文法記述が受理言語を持たず且つ入力文字列の全てを受理してパーズする文字列処理関数（以下、当該文法記述をＮともいう）であり、及び他方の文法記述が形式言語処理パーサーの指定である、請求項１又は２に記載の方法。
【請求項６】
前記文法記述Ｎにおいて、前記文字列処理関数が自然言語処理名である、請求項５に記載の方法。
【請求項７】
前記文法記述Ｐ１ Ｆ Ｐ２において、前記第２の文法記述（Ｐ２）で受理可能であり且つ前記入力文字列の先頭文字列を含む少なくとも１つの入力文字列が、当該先頭文字列から最長の文字列である、請求項１又は２に記載の方法。
【請求項８】
前記特定するステップが、前記宣言的記述中の文法記述のトップレベルでの組み合わせを特定することを含む、請求項２に記載の方法。
【請求項９】
前記文法記述のトップレベルでの組み合わせを特定した後に、当該特定された組み合わせの少なくとも一方をパーズして、当該一方中に示される各文法記述の組み合わせをさらに特定するステップをさらに含む、請求項８に記載の方法。
【請求項１０】
請求項１〜９のいずれか一項に記載の組み合わせパーサーを使用する方法であって、コンピュータが、
情報が抽出されるべきデータを受け取るステップと、
前記第２の文法記述（Ｐ２）に関連付けられた第２のパーサーを使用して、当該第２のパーサーが受理可能な部分文字列を前記データ中から見つけるステップと、
前記データの先頭文字列から前記見つけられた部分文字列の先頭直前までの部分文字列を前記第１の文法記述（Ｐ１）に関連付けられた第１のパーサーでパーズするステップと、
前記見つけられた部分文字列を前記第２のパーサーでパーズするステップと、
前記第１のパーサーでパーズして得られる第１の解析結果と、前記第２のパーサーでパーズして得られる第２の解析結果とから構文木を作成するステップと
を実行することを含む、前記方法。
【請求項１１】
請求項１〜９のいずれか一項に記載の組み合わせパーサーを使用する方法であって、コンピュータが、
検査されるべきデータを受け取るステップと、
前記第２の文法記述（Ｐ２）に関連付けられた第２のパーサーを使用して、当該第２のパーサーが受理可能であり且つ前記データの先頭文字列を含む少なくとも１つの部分文字列を前記データ中から見つけるステップと、
前記見つけられた部分文字列を前記第１の文法記述（Ｐ１）に関連付けられた第１のパーサーでパーズするステップと、
前記第１のパーサーでパーズして得られる第１の解析結果から構文木を作成するステップと
を実行することを含む、前記方法。
【請求項１２】
少なくとも２の言語処理パーサーを組み合わせて、組み合わせパーサーを生成するコンピュータであって、
プロセッサと、
前記プロセッサに接続されたメモリと、
下記に特定された各文法記述の少なくとも１つに関連付けられた各パーサーを組み合わせて、組み合わせパーサーを前記メモリ内に生成するパーサー生成部
を備えている、前記コンピュータ：
第１の文法記述（Ｐ１）に関連付けられた第１のパーサーを使用して、入力文字列の先頭文字列から第２の文法記述（Ｐ２）に関連付けられた第２のパーサーで最初に受理可能な少なくとも１つの入力文字列の直前の入力文字列までをパーズし、前記第２のパーサーを使用して、当該第２のパーサーで前記最初に受理可能な少なくとも１つの入力文字列をパーズする文法記述Ｐ１ Ｕ Ｐ２、及び
第２の文法記述（Ｐ２）に関連付けられた第２のパーサーを使用して、当該第２のパーサーで受理可能であり且つ入力文字列の先頭文字列を含む少なくとも１つの入力文字列をパーズし、第１の文法記述（Ｐ１）に関連付けられた第１のパーサーを使用して、当該パーズされた少なくとも１つの入力文字列をパーズする文法記述Ｐ１ Ｆ Ｐ２。
【請求項１３】
前記コンピュータが、
複数の文法記述を含む宣言的記述を記述するためのエディタ部と、
宣言的記述をパーズして、当該宣言的記述中に示される各文法記述の組み合わせを特定する解釈部であって、前記文法記述は、前記文法記述は、前記文法記述Ｐ１ Ｕ Ｐ２及び文法記述Ｐ１ Ｆ Ｐ２から選ばれる少なくとも１つを有している、前記解釈部と
をさらに備えており、
前記パーサー生成部が、前記解釈部において特定された各文法記述に関連付けられた各パーサーを組み合わせて、組み合わせパーサーを生成する、請求項１２に記載のコンピュータ。
【請求項１４】
前記文法記述Ｐ１ Ｕ Ｐ２又は前記文法記述Ｐ１ Ｆ Ｐ２において、Ｐ１又はＰ２のうちの一方の文法記述が、受理言語を持たず且つ入力文字列の全てを受理してパーズする文字列処理関数（以下、当該文法記述をＮともいう）である、請求項１２又は１３に記載のコンピュータ。
【請求項１５】
前記文法記述Ｐ１ Ｕ Ｐ２又は前記文法記述Ｐ１ Ｆ Ｐ２において、Ｐ１又はＰ２のうちの一方の文法記述が受理言語を持たず且つ入力文字列の全てを受理してパーズする文字列処理関数（以下、当該文法記述をＮともいう）であり、及び他方の文法記述が形式言語処理パーサーの指定である、請求項１２又は１３に記載のコンピュータ。
【請求項１６】
前記文法記述Ｐ１ Ｆ Ｐ２において、前記第２の文法記述（Ｐ２）で受理可能であり且つ前記入力文字列の先頭文字列を含む少なくとも１つの入力文字列が、当該先頭文字列から最長の文字列である、請求項１２又は１３に記載のコンピュータ。
【請求項１７】
前記解釈部が、前記宣言的記述中の文法記述のトップレベルでの組み合わせを特定する、請求項１３に記載のコンピュータ。
【請求項１８】
前記解釈部が、前記文法記述のトップレベルでの組み合わせを特定した後に、当該特定された組み合わせの少なくとも一方をパーズして、当該一方中に示される各文法記述の組み合わせをさらに特定する、請求項１７に記載のコンピュータ。
【請求項１９】
少なくとも２の言語処理パーサーを組み合わせて、組み合わせパーサーを生成するコンピュータ・プログラムであって、コンピュータに請求項１〜９のいずれか一項に記載の方法の各ステップを実行させる前記コンピュータ・プログラム。
【請求項２０】
組み合わせパーサーを使用するコンピュータ・プログラムであって、コンピュータに請求項１０又は１１に記載の方法の各ステップを実行させる前記コンピュータ・プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、少なくとも２つの言語処理パーサーを組み合わせて、組み合わせパーサー（ハイブリッド・パーサーともいう）を生成する方法、並びにそのコンピュータ及びコンピュータ・プログラムに関する。また、本発明は、上記組み合わせパーサーを使用する方法、並びにそのコンピュータ及びコンピュータ・プログラムに関する。
【背景技術】
【０００２】
言語処理において、言語における文法上の構造を解析するために構文解析器（パーサー）が使用される。パーサーには、主に、自然言語処理パーサー（以下、npパーサー(an NLP parser)ともいう）と形式言語処理パーサー（以下、fpパーサー(a parser for formal grammar)ともいう）とがある。自然言語処理パーサーは、自然文を解釈するパーサーである。自然文は自然言語テキストとも呼ばれ、自然言語テキストは人間によって日常の意思疎通のために用いられる、文化的背景を持って自然に発展してきた記号体系である。一方、形式言語処理パーサーは、形式文を含む文を解釈するのに適したパーサーである。形式文は自然文又は自然言語テキストに対比される語であり、形式文は、プロジェクト成果物文書、ソフトウェアの仕様書、数式又はプログラミング言語を含む文書など人工的に定義されたもののである。プロジェクト成果物文書は、例えば、要求仕様書、設計書、技術書を含む。
【０００３】
言語処理パーサー同士を組み合わせて、組み合わせパーサーを宣言的記述データ（以下単に、宣言的記述ともいう）から自動的に生成する技術が知られている。当該技術は例えば、パーサー・ジェネレータ（パーサー生成器）及びパーサー・コンビネーター・ライブラリである。パーサー・ジェネレータは例えば、Yacc（Yet Another Compiler-Compiler）、ANTLR（ANother Tool for Language Recognition）、CUPS、及びJava（登録商標）CC（Java（登録商標） Compiler Compiler）である。パーサー・コンビネーター・ライブラリは例えば、Parsec（parallax of one arcsecond）、JParsec、及びScala標準ライブラリーである。最近では、Yaccなどのツールの普及により、文法を記述するだけで、パーサーを自動的に生成すること、すなわちパーサーのプログラムのソースコードを出力することが可能である。
【０００４】
また、宣言的に記述できないパターンの組み合わせ、例えば形式言語処理パーサーと他の処理（例えば自然言語処理）との組み合わせをその都度個別にプログラミングして対応するアプローチが知られている。この理由は、自然言語処理パーサーが、形式言語処理パーサーと異なる性質を持っているために、従来の方法では自然言語処理パーサーと形式言語処理パーサーとを組み合わせることが出来ないからである。
【０００５】
下記特許文献１は、入力された日本語文を形態素解析し、形態素解析の結果の一部分に適用できる構文規則が、ただ１つかどうかの判断を行い、当該判断による出力を用いて形態素解析結果に構文規則を適用し、当該適用後の形態素列を構文解析する旨を記載する（問題点を解決するための手段）。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開昭６３−１３８４６５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
形式言語処理パーサー同士を組み合わせた組み合わせパーサー、及び形式言語処理パーサーと他の処理である自然言語処理パーサーとを組み合わせた組み合わせパーサーでは、組み合わせるパーサーが受理言語を持つことを前提にしている。従って、各種の自然言語処理パーサーの適用の仕方の多くが、既存の文法、例えばPEG（Parsing Expression Grammar）のみで記述できない。図１ａ及びｂは、その一例を示す。
【０００８】
図１ａは、形式言語処理パーサー同士を組み合わせて、組み合わせパーサーを宣言的記述から自動的に生成する例である。図１ａのパーサーの組み合わせパターン（FP1;FP2）は、形式言語処理パーサーFP1及びFP2同士の組み合わせである。
図１ａの例では、入力文字列はsであり、具体的には、s = s1s2s’である。図１ａの組み合わせパーサーの処理は次の通りである：（１）FP1;FP2は、入力文字列ｓを受け取る：（２）FP1;FP2はそれぞれs1及びs2を受理し、残りの文字列s’を返す。
図１ａの組み合わせパターンでは、形式言語処理パーサー同士を組み合わせて、組み合わせパーサーを宣言的記述から自動的に生成するために、少ないコストですむ。しかしながら、図１ａの組み合わせパターンでは、FP1;FP2がそれぞれs1及びs2を受理しているとおり、組み合わせるパーサーが受理言語を持つことが前提である。従って、図１ａの組み合わせパターンでは、既存の文法記述で自然言語処理を宣言することができない。
【０００９】
図１ｂは、形式言語処理パーサーと他の処理である自然言語処理パーサーとを組み合わせて、組み合わせパーサーを宣言的記述から自動的に生成する例である。図１ｂのパーサーの組み合わせパターン（FP3;NP;FP5）は、形式言語処理パーサーFP3、自然言語処理パーサーNP及び形式言語処理パーサーFP5の組み合わせである。
図１ｂの例では、入力文字列はｓであり、具体的にはs = s3s4s5である。図１ｂの組み合わせパーサーの処理は次の通りである：（１）FP3；NPは、入力文字列sを受け取る：（２）FP3がs3を受理し、NPが残りの全ての文字列（s4及びs5）を受理する。
図１ｂの組み合わせパーサーにおいて、NPが受理言語を持たないためにs4及びs5をまとめて受理する。従って、FP5はs5を受理できないので、FP5はs5に適用されない。さらに、既存の文法記述では、FP5をs5に適用する組み合わせパターンを記述することは出来ない。
【００１０】
また、宣言的に記述できないパターンの組み合わせをその都度個別にプログラミングする方法では、プログラムは概して複雑である。そのために、そのプログラムを再利用したり又は変更したりする対処が困難である。従って、当該プログラムの保守にコストがかかり、また当該プログラムは汎用性がない。
【００１１】
また、例えばプロジェクト成果物文書は、形式的な部分（例えば、独自記法及びテンプレート）と自然文が混在した記法であるという特徴を有する。そのために、プロジェクト成果物文書から情報を抽出するに際して、形式言語処理パーサー（fp）だけでは必要な情報が抽出できない。また、例えばプロジェクト成果物文書の種類及び形式はプロジェクトに依存し、またその種類又は形式の変更が多いという特徴を有する。そのために、各プロジェクト成果物文書に対応し組み合わせパーサーの生成にはコストを要する。また、各プロジェクト成果物文書に対応して組み合わせパーサーを生成するために、組み合わせパーサーに汎用性がない。
【００１２】
従って、個別にプログラミングするのではなく、ライブラリーに既にある形式言語処理パーサー（fp）に、文字列処理関数（N）、例えば自然言語処理パーサー（NP）をそのまま適用できるように自動的に組み合わせパーサーを生成する手法が、コスト及び汎用性の観点からも望まれている。
【課題を解決するための手段】
【００１３】
本発明は、少なくとも２の言語処理パーサーを組み合わせて、組み合わせパーサーを自動的に生成する方法、並びにそのコンピュータ及びコンピュータ・プログラムを提供する。
本発明は、組み合わせパーサーを自動的に生成するに際して、下記に特定された文法記述の少なくとも１つに関連付けられた各パーサーを組み合わせる：
（１）文法記述Ｐ１ Ｕ Ｐ２は、第１の文法記述（Ｐ１）に関連付けられた第１のパーサーを使用して、入力文字列の先頭文字列から第２の文法記述（Ｐ２）に関連付けられた第２のパーサーで最初に受理可能な少なくとも１つの入力文字列の直前の入力文字列までをパーズし、当該第２のパーサーを使用して、当該第２のパーサーで最初に受理可能な少なくとも１つの入力文字列をパーズする：
（２）文法記述Ｐ１ Ｆ Ｐ２は、第２の文法記述（Ｐ２）に関連付けられた第２のパーサーを使用して、当該第２のパーサーで受理可能であり且つ入力文字列の先頭文字列を含む少なくとも１つの入力文字列をパーズし、第１の文法記述（Ｐ１）に関連付けられた第１のパーサーを使用して、当該パーズされた少なくとも１つの入力文字列をパーズする。
【００１４】
また、本発明の１つの実施態様において、本発明は、形式言語処理パーサー（fp）にfp以外の文字列処理関数（N）、例えば各種の自然言語処理関数（NP）を組み合わせて、組み合わせパーサーを自動的に生成する方法、並びにそのコンピュータ及びコンピュータ・プログラムを提供する。
【００１５】
また、本発明の１つの実施態様において、本発明は、複数の文法記述を含む宣言的記述から、形式言語処理パーサー（fp）と文字列処理関数（N）とを組み合わせて、組み合わせパーサーを自動的に生成する方法、並びにそのコンピュータ及びコンピュータ・プログラムを提供する。
【００１６】
また、本発明の１つの実施態様において、本発明は、既存の文法記述、例えばPEGで解析できない入力文字列の部分を解析できるように、当該既存の文法記述を拡張する方法、並びにそのコンピュータ及びコンピュータ・プログラムを提供する。
【００１７】
また、本発明の１つの実施態様において、本発明は、拡張された文法記述に関連付けられたパーサーを含む組み合わせパーサーを使用して、情報が抽出されるべきデータから情報を抽出する方法、並びにそのコンピュータ及びコンピュータ・プログラムを提供する。
【００１８】
また、本発明の１つの実施態様において、本発明は、拡張された文法記述に関連付けられたパーサーを含む組み合わせパーサーを使用して、データが固有の記法に従って記述されているかどうかを検査する方法、並びにそのコンピュータ及びコンピュータ・プログラムを提供する。
【発明の効果】
【００１９】
本発明の実施態様に従う文法記述Ｐ１ Ｕ Ｐ２及び／又は文法記述Ｐ１ Ｆ Ｐ２を既存の文法に追加することによって、既存の文法では解析出来ない部分を明示的に扱うことが可能であるパーサーを自動的に生成することが可能になる。また、本発明の実施態様に従う文法記述Ｐ１ Ｕ Ｐ２及び／又は文法記述Ｐ１ Ｆ Ｐ２は、パーサーにより受理可能な言語を増加させる。
また、本発明の実施態様に従う組み合わせパーサーは、組み合わせ元のパーサー自体をカスタマイズすることなく、入力文字列の指定部分に適用することが可能になる。
【図面の簡単な説明】
【００２０】
【図１】従来技術である組み合わせパーサーの例を示す。
【図２】本発明の実施形態において使用されうるコンピュータ・ハードウェアの基本的なブロック図を示す。
【図３】図２に示すコンピュータ・ハードウェアのうち、本発明の実施態様である、言語処理パーサーを組み合わせて、組み合わせパーサーを自動的に生成するパーサー生成装置の機能ブロック図を示す。
【図４】図３に示すパーサー生成装置によって生成された組み合わせパーサーを使用して、入力文字列から情報を抽出し又は検査する情報抽出装置の機能ブロック図を示す。
【図５】図３に示す形式言語処理パーサー生成部で使用されうる既存の文法記述の例を示す。
【図６】図５に示す既存の文法記述に、本発明の実施態様において新たに追加される文法記述の例を示す。
【図７】図６に示す新たに追加された文法記述に関連付けられたパーサーのパーズ動作を模式図で示す。
【図８】図６に示す文法記述を使用して、本発明の実施態様である組み合わせパーサーを生成する処理のフローチャートを示す。
【図９】図８において生成される処理関数Until[p1,p2]のパーズ動作を示すフローチャートを示す。
【図１０】図８において生成される処理関数For[p1,p2]のパーズ動作を示すフローチャートを示す。
【図１１】図９に示すP = P1 U P2がP = NP U FPである場合の処理関数Until[np,fp]のパーズ動作を示すフローチャートを示す。
【図１２】図１０に示すP = P1 F P2がP = NP F FPである場合の処理関数For[np,fp]のパーズ動作を示すフローチャートを示す。
【図１３】図８に記載の本発明の実施態様に従い生成された組み合わせパーサーを使用して、入力テキストから情報を抽出する例を示す。
【図１４】図１３に示す文法記述の例のために、ユーザによって作成される文法記述の例を示す。
【図１５】図１３に示す例において生成される組み合わせパーサーのパーズ動作を示すフローチャートを示す。
【図１６】図１５に示すフローチャートのステップ１５０４におけるサブルーチンのフローチャートを示す。
【図１７】本発明の実施態様に従う組み合わせパーサーでテストケース記述データをパーズし、パラメータ名と値とを取り出し、組み合わせテストの最適化を行う例を示す。
【図１８】本発明の実施態様に従い、特定の記述部分のみをパーズすることを可能にすることを示すための画面仕様書の例を示す。
【図１９】本発明の実施態様に従い、あるプロジェクトにおいて、特定の設計文書中の特定の記述部分をパーズした場合を説明するための表を示す。
【図２０】図６に示す新たに追加された文法記述から生成される組み合わせパーサーを使用して生成される抽象構文木の例を示す。
【図２１】図５に示す既存の文法記述PEGと図６に示す本発明の実施態様において新たに追加される文法記述との文法の記述力の関係を示す。
【発明を実施するための形態】
【００２１】
以下に、本発明の代表的な実施態様を説明するとともに、当該実施態様が後に述べる各図面とどのように対応するかについて括弧書きで説明する。次に、各図面に従って本発明の実施形態をさらに説明する。なお、本発明の実施形態は、本発明の好適な形態を説明するためのものであり、本発明の範囲をここで示すものに限定する意図はないことを理解されたい。
【００２２】
本発明は、少なくとも２の言語処理パーサーを組み合わせて、組み合わせパーサーを生成する方法、並びにそのコンピュータ及びコンピュータ・プログラムを提供する。
【００２３】
本発明の方法の実施態様では、下記に特定された文法記述Ｐ１ Ｕ Ｐ２及びＰ１ Ｆ Ｐ２の少なくとも１つに関連付けられた各パーサーを組み合わせて、組み合わせパーサーをメモリ内に生成するステップを含む。
【００２４】
本発明のコンピュータの実施態様では、プロセッサと、当該プロセッサに接続されたメモリと、下記に特定された各文法記述の少なくとも１つに関連付けられた各パーサーを組み合わせて、組み合わせパーサーを前記メモリ内に生成するパーサー生成部とを含む。
【００２５】
文法記述は、下記の通りである：
文法記述Ｐ１ Ｕ Ｐ２（図６）は、第１の文法記述（Ｐ１）に関連付けられた第１のパーサーを使用して、入力文字列の先頭文字列から第２の文法記述（Ｐ２）に関連付けられた第２のパーサーで最初に受理可能な少なくとも１つの入力文字列の直前の入力文字列までをパーズし、第２のパーサーを使用して、当該第２のパーサーで最初に受理可能な少なくとも１つの入力文字列をパーズすることを意味する。
文法記述Ｐ１ Ｆ Ｐ２（図６）は、第２の文法記述（Ｐ２）に関連付けられた第２のパーサーを使用して、当該第２のパーサーで受理可能であり且つ入力文字列の先頭文字列を含む少なくとも１つの入力文字列をパーズし、第１の文法記述（Ｐ１）に関連付けられた第１のパーサーを使用して、当該パーズされた少なくとも１つの入力文字列をパーズすることを意味する。
【００２６】
本発明の実施態様では、組み合わせパーサーを生成する方法は、宣言的記述を使用することなしに、汎用のプログラム言語、例えばＣ言語、Ｃ＋＋言語及びＪａｖａ（登録商標）言語を用いて上記文法記述に対応する動作を行うプログラミングを行い、そして各パーサーを組み合わせて、組み合わせパーサーを生成するステップを実行することによっても実現可能である。
【００２７】
本発明の他の実施態様では、組み合わせパーサーを生成する上記方法は、複数の文法記述を含む宣言的記述をメモリ内に受け取るステップと、当該受け取った宣言的記述をパーズして、当該宣言的記述中に示される各文法記述の組み合わせを特定するステップとをさらに含む。ここで、当該宣言的記述中に示される文法記述は、前記文法記述Ｐ１ Ｕ Ｐ２及び文法記述Ｐ１ Ｆ Ｐ２から選ばれる少なくとも１つを有している。
【００２８】
本発明の他の実施態様では、組み合わせパーサーを生成する方法は、複数の文法記述を含む宣言的記述を受け取るステップと、当該受け取った宣言的記述をパーズして、当該宣言的記述中に示される各文法記述の組み合わせを特定するステップと、前記特定された各文法記述に関連付けられた各パーサーを組み合わせて、組み合わせパーサーを生成するステップとを含む。当該宣言的記述中に示される文法記述は、前記文法記述Ｐ１ Ｕ Ｐ２及び文法記述Ｐ１ Ｆ Ｐ２から選ばれる少なくとも１つを有している。
【００２９】
本発明の実施態様では、宣言的記述は複数の文法記述を含む。本発明の実施態様では、宣言的記述中の複数の文法記述の夫々に関連付けられた各パーサーを組み合わせて、組み合わせパーサーを生成する。宣言的記述は、例えば、一連のルールを用いて記述された文法記述を組み合わせて記述された文法記述の組み合わせパターンを含みうる。宣言的記述は、所定の文法に従い、ユーザによって記述されるか、あるいはコンピュータによって自動的に生成されてもよい。文法は、例えばPEGに従う文法記述を含みうる（図５及び図６を参照）。本発明の実施態様では、当該文法記述は、本発明の実施態様に従い下記から選ばれる少なくとも１つを有していることを特徴とする（図６の新たに追加された文法記述）。
【００３０】
本発明の実施態様では、文法は、文法記述Ｐ１ Ｕ Ｐ２及び／又は文法記述Ｐ１ Ｆ Ｐ２に加えて、既存の文法記述、例えばPEG（図５）を含んでもよい。
【００３１】
本発明の実施態様において、本発明は、宣言的記述に含まれる文法記述が、（１）受理言語を持たず且つ入力文字列の全てを受理してパーズする文字列処理パーサー名である文法記述（以下、当該文法記述をＮという）と、
（２）文法記述Ｐ１ Ｕ Ｐ２及び文法記述Ｐ１ Ｆ Ｐ２から選ばれる少なくとも１つを有していてもよい。
【００３２】
本発明の実施態様では、文法記述Ｐ１ Ｕ Ｐ２において、Ｐ１又はＰ２の一方の文法記述が、文法記述Ｎでありうる（図１３の１３０４「[is-a-NLP]」を参照）。同様に、本発明の実施態様では、文法記述Ｐ１ Ｆ Ｐ２において、Ｐ１又はＰ２の一方の文法記述が、文法記述Ｎでありうる。文法記述Ｎは、受理言語を持たず且つ入力文字列の全てを受理してパーズする文字列処理関数である。文字列処理関数は自然言語処理名であってよい。また、当該文字列処理関数に対応するパーサーは、自然言語処理登録ストアに登録されうる。本発明の実施態様において、自然言語処理関数は、自然言語処理パーサーともみなすことが可能である。
【００３３】
さらに、本発明の実施態様では、文法記述Ｐ１ Ｕ Ｐ２において、Ｐ１又はＰ２の少なくとも他方の文法記述が、形式言語処理パーサーの指定でありうる。同様に、本発明の実施態様では、文法記述Ｐ１ Ｆ Ｐ２において、Ｐ１又はＰ２の少なくとも他方の文法記述が、形式言語処理パーサーの指定でありうる。
【００３４】
本発明の実施態様では、文法記述Ｐ１ Ｆ Ｐ２において、第２の文法記述（Ｐ２）で受理可能であり且つ上記入力文字列の先頭文字列を含む少なくとも１つの入力文字列が、当該先頭文字列から最長の文字列でありうる。最長の文字列とは、文法記述Ｐ１に対応するパーサーｐ１の強度である。パーサーｐ１は、先頭文字列から受理可能な複数の文字列がある場合に、最長の文字列を受理する。最長の文字列を受理するとは、例えばパーサーｐ１がパーサーa*である場合に、パーサーa*は、文字列a、aa、aaaのいずれをも受理する。しかし、パーサーa*が、文字列aaabをパーズすると必ずaaaが受理されて、残りの文字列としてbがパーズ結果として返されることである。これは、パーズ結果が必ず一意になるようにするためである。
【００３５】
本発明の実施態様では、特定するステップが、上記宣言的記述中の文法記述のトップレベルでの組み合わせを特定することを含んでもよい。また、本発明の実施態様では、特定するステップが、上記トップレベルでの組み合わせを特定した後に、当該特定された組み合わせの少なくとも一方をパーズして、当該一方中に示される各文法記述の組み合わせをさらに特定するステップをさらに含んでもよい。
【００３６】
本発明の実施態様では、形式言語処理パーサー（fp）は、受理言語を持つパーサーである。形式言語処理パーサー（fp）は入力文字列に対して、受理又は不受理を行うために、受理言語が事前に定まっている必要がある。形式言語処理パーサー（fp）は、入力文字列を受け取り、パーズ結果として例えば抽象構文木を返す関数又は、抽象構文木とパーズし切れなかった残りの文字列を返す関数として定式化されるものである。
FP以外の文字列処理である自然言語処理(N)は、文法記述Ｎに関連付けられている。自然言語処理(N)は、受理言語を持たずに、全ての入力文字を受理する文字列処理関数である。自然言語処理(N)は、ブラックボックス化された各種の自然言語処理関数を表す。自然言語処理(N)の特徴は、形式言語処理パーサー（fp）と異なり受理言語を持っていないこと、及び形式的に定められる受理言語を持たなくて良いために、入力文字列に対して、自然言語的な知見に基づいた統計処理、辞書引き処理などを自然言語処理関数の内部で自由に行うことが可能である。そのために、各種の実用的な自然言語処理をNで表すことが可能になる。自然言語処理(N)として例えば、各種の自然言語処理関数（NP）を指定出来る。自然言語処理(N)は、入力文字列を受け取り、パーズ結果として例えば抽象構文木を返す関数として定式化されるものである。
【００３７】
本発明の実施態様では、自然言語処理(N)は例えばis-a-NLPとして記述され、is-a-NLPは、入力文字列全体を文とみなして、is-a関係にあるペアを取り出し、構文木抽出として返す自然言語処理関数である（図１３の１３０４を参照）。
【００３８】
また、本発明は、組み合わせパーサーを使用する方法を提供する。
（１）当該方法の１つの実施態様は、情報が抽出されるべきデータをメモリ内に受け取るステップと、第２の文法記述（Ｐ２）に関連付けられた第２のパーサーを使用して、当該第２のパーサーが受理可能な部分文字列を上記データ中から見つけるステップと、上記データの先頭文字列から上記見つけられた部分文字列の先頭直前までの部分文字列を第１の文法記述（Ｐ１）に関連付けられた第１のパーサーでパーズするステップと、上記見つけられた部分文字列を上記第２のパーサーでパーズするステップと、上記第１のパーサーでパーズして得られる第１の解析結果と、上記第２のパーサーでパーズして得られる第２の解析結果とから構文木を上記メモリ内に作成するステップとを含む。
（２）当該方法の他の実施態様は、検査されるべきデータをメモリ内に受け取るステップと、第２の文法記述（Ｐ２）に関連付けられた第２のパーサーを使用して、当該第２のパーサーが受理可能であり且つ上記データの先頭文字列を含む少なくとも１つの部分文字列を上記データ中から見つけるステップと、上記見つけられた部分文字列を第１の文法記述（Ｐ１）に関連付けられた第１のパーサーでパーズするステップと、当該第１のパーサーでパーズして得られる第１の解析結果から構文木を上記メモリ内に作成するステップとを含む。
【００３９】
情報が抽出されるべき又は検査されるべきデータ（以下、単に対象データともいう）は例えば、プロジェクト成果物文書、ソフトウェアの仕様書、数式又はプログラミング言語を含む文書であるがこれらに限定されない。
対象データでは、重要な情報がしばしば独自の記法を取り入れた自然文で記述されうる。また、対象データでは、全体の構造は既存の形式言語パーサーで扱えるような規則性をもっていることを仮定できるケースが多く、一方個々の中身の記述は自由度が高いことが多い。
【００４０】
本発明の実施態様において、本発明の実施態様に従う組み合わせパーサーは、情報が抽出されるべきデータ、例えばプロジェクト成果物文書データ、数式又はプログラミング言語を含む文書データから情報を抽出するために使用されうる。
【００４１】
また、本発明の実施態様において、本発明の実施態様に従う組み合わせパーサーは、データを機械的に検査するために使用されうる。機械的な検査は、例えば、検査されるべきデータ、例えばプロジェクト成果物文書データ、数式又はプログラミング言語を含む文書データから、当該文書データの形式、内容の検査のために使用されうる。
【００４２】
以下では、図面に従って、本発明の実施形態をさらに説明する。また、以下の図を通して、特に断らない限り、同一の符号は、同一の対象を指す。
【００４３】
図２は、本発明の実施形態において使用されうるコンピュータ・ハードウェアの基本的なブロック図を示す。
コンピュータ（２０１）は、ＣＰＵ（２０２）とメイン・メモリ（２０３）とを備えており、これらはバス（２０４）に接続されている。ＣＰＵ（２０２）は好ましくは、３２ビット又は６４ビットのアーキテクチャに基づくものであり、例えば、インテル社のＣｏｒｅ  ｉ（商標）シリーズ、Ｃｏｒｅ  ２（商標）シリーズ、Ａｔｏｍ（商標）シリーズ、Ｘｅｏｎ（商標）シリーズ、Ｐｅｎｔｉｕｍ（登録商標）シリーズ、Ｃｅｌｅｒｏｎ（登録商標）シリーズ、ＡＭＤ社のＰｈｅｎｏｍ（商標）シリーズ、Ａｔｈｌｏｎ（商標）シリーズ、Ｔｕｒｉｏｎ（商標）シリーズ又はＳｅｍｐｒｏｎ（商標）が使用されうる。バス（２０４）には、ディスプレイ・コントローラ（２０５）を介して、ディスプレイ（２０６）、例えば液晶ディスプレイ（ＬＣＤ）が接続されうる。ディスプレイ（２０６）は、コンピュータの管理のために、通信回線を介してネットワークに接続されたコンピュータについての情報と、そのコンピュータ上で動作中のソフトウェアについての情報を、適当なグラフィック・インタフェースで表示するために使用される。バス（２０４）にはまた、ＳＡＴＡ又はＩＤＥコントローラ（２０７）を介して、ディスク（２０８）、例えばハードディスク又はシリコン・ディスクと、ドライブ（２０９）、例えばＣＤ、ＤＶＤ又はＢＤドライブとが接続されうる。バス（２０４）にはさらに、キーボード・マウスコントローラ（２１０）又はＵＳＢバス（図示せず）を介して、キーボード（２１１）及びマウス（２１２）が接続されうる。
【００４４】
ディスク（２０８）には、オペレーティング・システム、Ｊ２ＥＥなどのＪａｖａ（登録商標）処理環境、Ｊａｖａ（登録商標）アプリケーション、Ｊａｖａ（登録商標）仮想マシン（ＶＭ）、Ｊａｖａ（登録商標）ＪＩＴコンパイラを提供するプログラム、その他のプログラム、及びデータが、メイン・メモリにロード可能に記憶されうる。
ドライブ（２０９）は、必要に応じて、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ又はＢＤからプログラムをディスク（２０８）にインストールするために使用される。
【００４５】
通信インタフェース（２１４）は、例えばイーサネット（登録商標）・プロトコルに従う。通信インタフェース（２１４）は、通信コントローラ（２１３）を介してバス（２０４）に接続され、コンピュータ（２０１）を通信回線（２１５）に物理的に接続する役割を担い、コンピュータ（２０１）のオペレーティング・システムの通信機能のＴＣＰ／ＩＰ通信プロトコルに対して、ネットワーク・インタフェース層を提供する。なお、通信回線は、有線ＬＡＮ環境、或いは例えばＩＥＥＥ８０２．１１ａ／ｂ／ｇ／ｎなどの無線ＬＡＮ接続規格に基づく無線ＬＡＮ環境であってもよい。
【００４６】
図３は、図２に示すコンピュータ（２０１）のうち、本発明の実施態様である、言語処理パーサーを組み合わせて、組み合わせパーサー（３１０）を自動的に生成するパーサー生成装置（３０１）の機能ブロック図を示す。
パーサー生成装置（３０１）は、宣言的記述エディタ部（３０２）（以下、単に、第１のエディタ部（３０２）ともいう）、自然言語処理登録エディタ部（３０３）（以下、単に、第２のエディタ部（３０３）ともいう）、組み合わせパターン登録ストア（３０４）、自然言語処理登録ストア（３０５）、組み合わせパターン解釈部（３０６）（以下、単に、解釈部（３０６）ともいう）、自然言語処理関数割当部（３０７）（以下、単に、割当部（３０７）ともいう）、組み合わせパターンに従ってコードを生成するパーサー生成部（３０８）（以下、第１のパーサー生成部ともいう）、及び形式言語処理パーサー生成部（３０９）（以下、第２のパーサー生成部ともいう）を備えている。なお、パーサー生成装置（３０１）は、１又は複数のコンピュータから構成されていてもよい。また、登録ストア（３０４、３０５）は、パーサー生成装置（３０１）と無線又は有線ネットワーク（図示せず）を介して接続された外部記憶媒体、例えばＮＡＳであってもよい。
【００４７】
第１のエディタ部（３０２）はパターン記述エディタを含み、ユーザが当該パターン記述エディタを用いて組み合わせ文法記述パターンを含む宣言的記述を編集することを許すためのインターフェイス装置である。組み合わせ文法記述は、パーサーの動作を表す式でもある。この組み合わせ文法記述は、情報の抽出対象である入力テキストの特徴又は目的に応じて、下記に述べる本発明で追加され且つ拡張された文法記述を用いて記述される。ユーザは、第１のエディタ部（３０２）を使用し、情報の抽出対象であるテキストの特徴又は目的に応じて、図６に記載の文法記述を使用して宣言的記述を作成する。
【００４８】
第２のエディタ部（３０３）はエディタを含み、ユーザが当該エディタを用いて自然言語処理(N)（例えば自然言語処理関数(NP)）を自然言語処理登録ストア（３０５）へ登録すること、及び自然言語処理(N)を自然言語処理登録ストア（３０５）から削除することなどを許すためのインターフェイス装置である。なお、パーサー生成装置（３０１）は、第１のエディタ部（３０２）と第２のエディタ部（３０３）との各機能が統合されたエディタ部を備えていてもよい。なお、第２のエディタ部（３０３）のエディタは、第１のエディタ部（３０２）によって実現されてもよい。
【００４９】
組み合わせパターン登録ストア（３０４）は、第１のエディタ部（３０２）において入力された組み合わせ文法記述パターンを記録する。当該記録によって、組み合わせ文法記述の保守が容易になり、また組み合わせ文法記述の再利用が可能となる。
【００５０】
自然言語処理登録ストア（３０５）は、利用可能な自然言語処理(N)、例えば自然言語処理関数（NP）の名前と、当該Nの実際の処理関数との対応関係を保存する。
【００５１】
解釈部（３０６）は、宣言的記述をメモリ（２０３）内に受け取り、宣言的記述中に記載された組み合わされたパターンを解釈する。そして、解釈されたパターンに基づいて、組み合わせパーサーのコードが、割当部（３０７）、第１のパーサー生成部（３０８）若しくは第２のパーサー生成部（３０９）、又はそれらの組み合わせによって生成される。「組み合わせパーサー」の「組み合わせ」とは、一方のパーサーが受理できなかった入力文字列のパーズを他のパーサーが引き受けてパーズすることをまた意味しうる。
【００５２】
割当部（３０７）は、宣言的記述において文字列処理関数、例えば自然言語処理名が記述されている場合に、当該自然言語処理名に関連付けられた処理関数を自然言語処理登録ストア（３０５）から取り出し、組み合わせパーサー（３１０）のコード中に当該取り出された処理関数又は当該処理関数の呼び出しコードを挿入する。
【００５３】
第１のパーサー生成部（３０８）は、宣言的記述において上記拡張された文法記述が記述されている場合、各拡張された文法記述に従った処理を行うコードをメモリ（２０３）内に自動的に生成し、組み合わせパーサー（３１０）のコード中に当該生成されたコード又は当該コードの呼び出しコードを挿入する。
【００５４】
第２のパーサー生成部（３０９）は、宣言的記述において従来技術である文法記述、例えばPEGが記述されている場合、当該各PEGに従った処理を行うコードをメモリ（２０３）内に自動的に生成し、組み合わせパーサー（３１０）のコード中に当該生成されたコード又は当該コードの呼び出しコードを挿入する。
【００５５】
組み合わせパターンから作成された組み合わせパーサー（３１０）は、入力文字列から情報を抽出するために使用される。なお、当該抽出の前に、組み合わせパーサー（３１０）は、コンパイラによって実行コードに変換される。
【００５６】
図４は、図３に示すパーサー生成装置（３０１）によって生成された組み合わせパーサー（３１０）を使用して、入力文字列（４１３）から情報を抽出し又は検査する情報抽出装置（４０１）の機能ブロック図を示す。
情報抽出装置（４０１）は、コンパイラ（４０２）及びパーサー実行部（４０３）を備えている。
コンパイラ（４０２）は、図３に示すパーサー生成装置によって生成された組み合わせパーサー（コードである）（４１１）をコンパイルして実行可能なコード（実行コード）（４１２）を生成する。
パーサー実行部（４０３）は、成果物文書（４１３）を実行コード（４１２）でパーズし、例えば抽象構文木（４１４）をパーズ結果として返す。
【００５７】
本発明の実施態様として、パーサー実行部（４０３）は、文字列検索部（４０４）、ｆｐによるパーズ処理部（４０５）、ｎによるパーズ処理部（４０６）、及び構文木構築部（４０７）を含みうる。
以下では、パーサー実行部（４０３）を、P = P1 F P2において、P1がNPであり且つP2がFPである場合（P = NP F FP）の処理関数For[np,fp]を例として、その動きを説明する。なお、s(i,j)は、入力文字列sのうちのindex i〜(j-1)の文字列である。また、s(k,..)は、入力文字列sのうちのindex k〜(s.length()-1)の文字列である。
文字列検索部（４０４）は、成果物文書（４１３）を受け取り、成果物文書中の文字列について、FPが受理可能な最初の部分文字列str(k,l)を見つける。
fpによるパーズ処理部（４０５）は、パーサーfpで文字列str(k,..)をパーズする。
nによるパーズ処理部（４０６）は、パーサーnで文字列str(0,k-1)をパーズする。
構文木構築部（４０７）は、fpによるパーズ処理部（４０５）からのパーズ結果として抽象構文木AST1を生成し、且つnによるパーズ処理部（４０６）からのパーズ結果として抽象構文木AST2を生成する。構文木構築部（４０７）は、またルートをFとし、AST1及びAST2を子ノードとする抽象構文木AST（４１４）を生成する。
そして、パーサー実行部（４０３）は、抽象構文木AST（４１４）と残りの部分文字列（４１５）とを返す。
【００５８】
図５は、図３に示す形式言語処理パーサー生成部（３０９）で使用されうる既存の文法記述の例を示す。
以下は、PEGを例にして示すが、本発明はPEGのみに限定されるものではないことを理解されたい。
文法Gは、（A,S,Σ,Z,R）で定義される。文法Gは、Pの定義の一部、及びZを除いてPEGと同様の意味を持つ。定義A,S,Σ,Z及びRの各意味は、図５に記載されている通りである。
【００５９】
文法Gから、各パーサーは下記のように生成される。すなわち、パーサーの生成は、各ルール X::=P ∈R に対して、Pの形によって図５に定義されている各ルールの処理を再帰的に行うことによって行われる。
ルールX::=P のPから生成されるコードをXに関連付けられたパーサーとする。なお、X::= … の形のルールはR内に１つしかない。この制限は、PEGの制限によるものである。
また、sに関連付けられたパーサーが、文法Gに従うパーズを行うパーサーとなる。
【００６０】
文法記述P = sの場合、第２のパーサー生成部（３０９）は、入力文字列が文字列sを先頭文字列として含むか検査し、入力文字列の先頭が文字列sから始まる場合はsを受理し、この受理した部分の構文木と入力文字列から先頭文字列sを除いた文字列を返す。例えば入力文字列abcdefをパーサーabでパーズした場合、先頭文字列abが受理されて、この受理された部分の構文木が作られて、入力文字列からabが消費される。そして、abの構文木と残りの文字列cdefとがパーズ結果として返される。一方、第２のパーサー生成部（３０９）は、入力文字列の先頭が文字列sから始まっていない場合には、パーズ・エラーを返す、というコードを生成する。
文法記述P = eoiの場合、第２のパーサー生成部（３０９）は、入力文字列が空の場合にはパーズ成功を返し、一方、入力文字列が空でない場合にはパーズ・エラーを返す、というコードを生成する。
文法記述P = Xの場合、第２のパーサー生成部（３０９）は、Rの中に含まれる X::=P’ のP’から生成したコード（Xに対するパーサー）を呼び出す、というコードを生成する。
文法記述P = P1 ; P2の場合、第２のパーサー生成部（３０９）は、P1,P2から部分パーサーp1,p2を再帰的に作成し、入力文字列をp1でまずパーズし、残りの入力文字列をp2でパーズする、というコードを生成する。
文法記述P = P1 / P2の場合、第２のパーサー生成部（３０９）は、P1,P2から部分パーサーp1,p2を再帰的に作成し、入力文字列をp1でパーズし、p1でのパーズが失敗したら同じ入力文字列をp2でパーズする、というコードを生成する。
文法記述P = P*の場合、第２のパーサー生成部（３０９）は、Pから部分パーサーpを再帰的に生成し、pに従って任意回数グリーディー（greedy）に繰り返しパーズする、というコードを生成する。
文法記述P = &(P1)P2の場合、第２のパーサー生成部（３０９）は、P1,P2から部分パーサーp1,p2を再帰的に作成し、入力文字列をパーサーp1で肯定先読み（p1によるパーズが成功することをチェックすること）を行い、肯定先読みが成功した場合には同じ入力文字列をp2でパーズし、一方、肯定先読みが失敗した場合には何も行わない、というコードを生成する。
文法記述P = !(P1)P2の場合、第２のパーサー生成部（３０９）は、P1,P2から部分パーサーp1,p2を再帰的に作成し、入力文字列をパーサーp1で否定先読み（p1によるパーズが失敗することをチェックすること）を行い、否定先読みが成功した場合には同じ入力文字列をp2でパーズし、一方、否定先読みが失敗した場合には何も行わない、というコードを生成する。
【００６１】
図６は、図５に示す既存の文法記述に、本発明の実施態様において新たに追加される文法記述の例を示す。
図６は、文法Ｇのうち、Ｒを示す。当該Ｒにおいて、本発明の実施態様において新たに導入される文法記述の３種類が示されている。
導入された文法記述は、下記の３種類である：
文法記述P = N：文法記述Nは、FP以外の文字列処理（N）、例えば自然言語処理関数（NP）によりパーズすることを示す。FP以外の文字列処理（N）は、具体的には自然言語処理名Nに割り当てられる処理関数を呼び出すことによって行われる。
文法記述P = P1 U P2：文法記述P1 U P2は、P1 until P2の意味である。文法記述P1 U P2は、入力文字列に対して、入力文字列の先頭文字列から、P2で最初に受理可能な入力文字列の直前の入力文字列までをP1でパーズすること、その後、残りの入力文字列をP2でパーズすることを示す。一方、入力文字列に対して、P2で受理可能な部分文字列がない場合、パーズ・エラーが返される。
文法記述P = P1 F P2：文法記述P1 F P2は、P1 for P2の意味である。文法記述P1 F P2は、入力文字列に対して、入力文字列の先頭文字列からP2で受理可能な部分文字列までをパーズすること、その後、P2で受理した部分文字列をP1でパーズすることを示す。一方、入力文字列に対して、入力文字列の先頭文字列にP2で受理可能な文字列がない場合、パーズ・エラーが返される。
【００６２】
文法Gに新たに追加された上記文法記述から、各パーサーは下記のように生成される。
文法記述P = Nの場合、割当部（３０７）は、自然言語処理ストアから名前Nに関連付けられた自然言語処理関数np（例えば、自然言語処理パーサーである）を取り出し、入力文字列をnpでパーズする、というコードを生成する。
文法記述P = P1 U P2の場合、第１のパーサー生成部（３０８）は、P1,P2から部分パーサーp1,p2を再帰的に作成し、例えば下記図９に示すフローチャートに従い動作するコードを生成する。
文法記述P = P1 F P2の場合、第１のパーサー生成部（３０８）は、P1,P2から部分パーサーp1,p2を再帰的に作成し、例えば下記図１０に示すフローチャートに従い動作するコードを生成する。
【００６３】
図７は、図６に示す新たに追加された文法記述に関連付けられたパーサーのパーズ動作を模式図で示す。
図７ａの例では、入力文字列はｓであり、具体的には、s = s1s2s3s4である。既存のPEGのみでは、図７ａのNで示される部分にNを適用することを指定することができない。そこで、本発明の実施態様では、組み合わせパターンN U FPを使用する。N U FPは、文法記述P1 U P2に従っている。図7ａの組み合わせパーサーの処理は次の通りである：（１）入力文字列の先頭文字列から部分文字列s3の直前までに、FPで最初に受理可能な部分文字列が存在せず、文字列ｓ3部分がＦＰにより受理可能な最初の部分文字列であるとする；（２）よって、先頭文字列から部分文字列s3の直前まで、すなわち部分文字列s1s2がNでパーズされ、残りの文字列s3s4において、s3部分がFPによりパーズされる；（３）Nにより部分文字列s1s2から抽象構文木1（以下、AST1ともいう）が構築される；FPにより部分文字列s3から抽象構文木2（以下、AST2ともいう）が構築される；そして、AST1とAST2はルートUによって結合されて、Uをルートとする抽象構文木a（以下、ASTaともいう）が構築される；（４）結果として、ASTaと、残りの部分文字列s4が、N U FPによる文字列s1s2s3s4に対するパーズ結果として返される。
図７ｂの例では、入力文字列はｓであり、具体的には、s = s1s2である。既存のPEGのみでは、図７ｂのNで示される部分にNを適用することを指定することができない。そこで、本発明の実施態様では、組み合わせパターンN F FPを使用する。N F FPは、文法記述P1 F P2に従っている。図7ａの組み合わせパーサーの処理は次の通りである：（１）入力文字列の先頭文字列s1がFPにより受理可能である；（２）FPにより受理可能な先頭文字列s1が切り出され、当該切り出されたs1がNによりパーズされる；（３）Nによるパーズの結果、部分文字列s1から抽象構文木b（以下、ASTbともいう）が構築される；（４）結果として、ASTbと、残りの部分文字列s2がN F FPによる文字列s1s2に対するパーズ結果として返される。
【００６４】
図８は、図５に示す文法記述を使用して、本発明の実施態様である組み合わせパーサーを生成する処理Main[STORE]のうち、パーサーpを生成する処理Gen[STORE](p)のフローチャートを示す。
以下に、Main[STORE]及びGen[STORE](p)の各処理で使用されている定義を説明する。
STORE：自然言語処理登録ストア（３０５）である。
P：文法記述である。文法記述は、例えばユーザによって、所定の文法に従い宣言的記述中に記載される。
Main[STORE]：自然言語処理登録ストア（３０５）のもとで、文法記述Pから組み合わせパーサーpを生成する処理である。
Gen[STORE](P)：Main[STORE]のうち、文法記述Pの組み合わせを特定し，当該特定された文法記述に従ってパーサーpを生成する処理である。
【００６５】
まず、Main[STORE]を説明する。
ステップ１  解釈部（３０６）は、第１のエディタ部（３０２）から文法記述Pを含む宣言的記述を受けとる。また、宣言的記述は、宣言的記述ライブラリーに予め登録されていてもよい。
ステップ２  解釈部（３０６）は、Gen[STORE](P)を実行する。
ステップ２−１  宣言的記述をパーズして、文法記述Pのトップレベルでの組み合わせパターンを特定する。文法記述Pは例えば、図６に示すs, eoi, X, P1;P2, P1/P2, P*, &(P1)P2, !(P1)P2, N, P1 U P2及びP1 F P2 の何れかである。トップレベルとは、文法記述が表している、一番外側の組み合わせである。例えば、文法記述Pが((P1;P2) U P3)である場合にトップレベルでの組み合わせは、Uで組み合わされている(P1;P2)とP3とである。また、特定された文法記述PがP1; (P2 U P3)である場合にトップレベルでの組み合わせは、;で組み合わされているP1と(P2 U P3)とである。トップレベル以下の下位レベルにおける組み合わせパターンの特定は、図８のステップ８０８、８１０、８１３、８１５、及び８１８のGenの再帰的な適用により行われる。
ステップ２−２−１  文法記述Pが、s, eoi, X及びNの何れかである場合、当該特定された文法記述Pからパーサーpが生成されうる。s, eoi及びXのパーサーについては、第２のパーサー生成部（３０９）が、PEGにおける既存技術に従い生成しうる。Nのパーサーについては、割当部（３０７）が図８のステップ８０８〜８１２に示す処理に従い生成しうる。
ステップ２−２−２−１  第１のパーサー生成部（３０８）が、文法記述P1からパーサーp1を生成する。例えば、特定された文法記述Pが((P1；P2) U P3)である場合に、P1は(P1；P2)である。また、特定された文法記述PがP1; (P2 U P3)である場合に、P1はP1である。第１のパーサー生成部（３０８）は、Gen[STORE](p1)を再帰的に呼び出す。
ステップ２−２−２−２  第１のパーサー生成部（３０８）が、文法記述P2からパーサーp2を生成する。例えば、特定された文法記述Pが((P1；P2) U P3)である場合に、P2はP3である。また、特定された文法記述PがP1; (P2 U P3)である場合に、P2は(P2 U P3)である。第１のパーサー生成部（３０８）は、Gen[STORE](P2 U P3))を再帰的に呼び出し、この呼び出しにおいてはトップレベルの組み合わせパターンがP2とP3がUで組み合わされていると特定されてさらに分解される。
ステップ２−２−２−３  第１のパーサー生成部（３０８）が、特定された組み合わせパターンに従って、パーサーp1とパーサーp2とを組み合わせて組み合わせパーサーpを生成する。ここで、組み合わせパーサーpの生成は、ステップ２−１で特定された組み合わせパターンごとに決定される。
ステップ３  解釈部（３０６）は、ステップ２−２−２−３からのパーサーpのコード又は、パーサーpの実行オブジェクト（例えば、関数への参照）を返す。
【００６６】
以下に、上記ステップ２に記載のGen[STORE](p)の例をステップ８０１〜８２０に従い説明する。
ステップ８０１では、解釈部（３０６）は、第１のエディタ部（３０２）から文法記述Pを含む宣言的記述を受け取り、パーサーpを生成するために、Gen[STORE](P)を開始する。解釈部（３０６）は、宣言的記述をパーズして、まず文法記述のトップレベルでの組み合わせパターンを特定する。
【００６７】
ステップ８０２では、解釈部（３０６）は、特定された文法記述Pが自然言語処理Nであるかどうかを判定する。解釈部（３０６）は、Pが自然言語処理Nである場合にステップ８０３に進み、一方PがNでない場合にステップ８０４に進む。
ステップ８０３では、割当部（３０７）は、特定された文法記述Pが自然言語処理Nであることに応じて、STOREに登録された名前Nの自然言語処理関数を見つけ、変数nlpに代入する。
ステップ８０５では、割当部（３０７）は、nlpが空(null)でない場合にステップ８０６に進み、一方、nlpが空である場合にステップ８０７に進む。ステップ８０７はエラー処理であり、nlpが空であることに応じて、パーサー生成エラーのメッセージをパーサー生成装置に返す。そして、当該処理は、ステップ８２０に進む。
ステップ８０６では、割当部（３０７）は、nlpが空でないことに応じて、パーサーnlpを返す。返されるnlpは、自然言語処理関数Nに関連付けられた上記処理関数である。
【００６８】
ステップ８０４では、解釈部（３０６）は、特定された文法記述Pが自然言語処理Nでないことに応じて、PがP1 U P2であるかどうかを判定する。解釈部（３０６）は、PがP1 U  P2である場合にステップ８０８に進み、一方PがP1 U P2でない場合にステップ８０９に進む。
ステップ８０８では、第１のパーサー生成部（３０８）は、文法記述P1からパーサーp1を生成する。当該生成の処理はGen[STORE](P1)で示される。
ステップ８１０では、第１のパーサー生成部（３０８）は、文法記述P2からパーサーp2を生成する。当該生成の処理はGen[STORE](P2)で示される。
ステップ８１１では、第１のパーサー生成部（３０８）は、ステップ８０８からのパーサーp1とステップ８１０からのパーサーp2とを組み合わせて、処理関数Until[p1,p2]を生成する。Until[p1,p2]は、組み合わせパーサーであり、strを引数とする関数のコードである。Until[p1,p2]の生成は、図９のUntil[p1,p2]のパーズ動作を示すフローチャートに該当する処理（コード）を生成することによって実現可能である。すなわち、図９のフローチャートはパラメータp1,p2を持つ関数を表しているので、p1,p2が与えられれば図９に対応する処理（コード）が決定されて実現可能である。
ステップ８１２では、第１のパーサー生成部（３０８）は、Until[p1,p2]を返す。そして、当該処理は、ステップ８２０に進む。
【００６９】
ステップ８０９では、解釈部（３０６）は、特定された文法記述PがP1 U P2でないことに応じて、PがP1 F P2であるかどうかを判定する。解釈部（３０６）は、特定された文法記述PがP1 F P2である場合にステップ８１３に進み、一方PがP1 F P2でない場合にステップ８１４に進む。
ステップ８１３では、第１のパーサー生成部（３０８）は、文法記述P1からパーサーp1を生成する。当該生成の処理はGen[STORE](P1)で示される。
ステップ８１５では、第１のパーサー生成部（３０８）は、文法記述P2からパーサーp2を生成する。当該生成の処理はGen[STORE](P2)で示される。
ステップ８１６では、第１のパーサー生成部（３０８）は、ステップ８１３からのパーサーp1とステップ８１５からのパーサーp2とを組み合わせて、処理関数For[p1,p2]を生成する。For[p1,p2]は、組み合わせパーサーであり、strを引数とする関数のコードである。For[p1,p2]の生成は、図１０のFor[p1,p2]のパーズ動作を示すフローチャートに該当する処理（コード）を生成することによって実現可能である。すなわち、図１０のフローチャートはパラメータp1,p2を持つ関数を表しているので、p1,p2が与えられれば図１０に対応する処理（コード）が決定されて実現可能である。
ステップ８１７では、第１のパーサー生成部（３０８）は、処理関数For[p1,p2]を返す。そして、当該処理は、ステップ８２０に進む。
【００７０】
ステップ８１４では、解釈部（３０６）は、特定された文法記述PがP1 F P2でないことに応じて、N, P1 U P2及びP1 F P2以外のルール（図６の点線で囲まれた部分以外のルール、すなわち既存のルール）であるかどうかを判定する。解釈部（３０６）は、Pが既存のルールである場合にステップ８１８に進み、一方Pが既存のルールでない場合にステップ８０７に進む。ステップ８０７はエラー処理であり、Pが既存のルールでない場合にことに応じて、パーサー生成エラーのメッセージをパーサー生成装置に返す。そして、当該処理は、ステップ８２０に進む。
ステップ８１８では、第２のパーサー生成部（３０９）は、既存のルールに従い、パーサーpを生成する。既存のルールに従いパーサーを生成するプロセスは、図５に記載の文法記述に関連付けられたパーサーの生成方法として上記したとおりである。そして、解釈部（３０６）は、必要に応じて、Gen[STORE]を再帰的に呼び出す。例えば、P = P1;P2の場合には、Gen[STORE](P1), Gen[Store](P2)が呼ばれるので、この２つの結果のパーサーを図６に示す文法記述；に従って組み合わせてパーサーを生成する。
ステップ８１９では、第２のパーサー生成部（３０９）は、パーサーpを返す。そして、当該処理は、ステップ８２０に進む。
ステップ８２０では、解釈部（３０６）は、Gen[STORE](P)を終了し、上記ステップ３に進む。
【００７１】
ステップ８０６、ステップ８１２、ステップ８１７、ステップ８１９で返された処理関数はそのまま返されるか、宣言的記述中の文法記述に従って他に生成されたパーサーと組み合わされる。例えば、宣言的記述中の文法記述が、P1;(P2 U P3)である場合、再帰的に呼ばれたGen[STORE](P1)からパーサーp1が生成され、ステップ８１９で(P2 U P3)が返される。また、再帰的に呼ばれたGen[STORE](P2 U P3)から パーサーp23が生成され、ステップ812でパーサーUntil[p1,p2]が返される。その後、パーサーp1とパーサーp23が；により組み合わされたパーサーが、ステップ818において生成される。
【００７２】
図９は、図８のステップ８１１において生成される処理関数Until[p1,p2]のパーズ動作を示すフローチャートを示す。
以下に、フローチャートで使用されている定義を説明する。
p1,p2：パーサー関数である。
s(i,j)：入力文字列sのうちのindex i〜(j-1)の文字列である。
s(k,..)：入力文字列sのうちのindex k〜(s.length()-1)の文字列である。
AST(“U”,R1,R2)：ラベルUを親ノードとし、抽象構文木R1とR2とを子ノードとして設定した新たな抽象構文木を作成する処理である。
【００７３】
ステップ９０１では、パーサー実行部（４０３）は、Until[p1,p2]で入力文字列をパーズする処理を開始する。
ステップ９０２では、パーサー実行部（４０３）は、Until[p1,p2]でパーズする入力文字列sを変数strに代入する。
ステップ９０３では、パーサー実行部（４０３）は、文字列のポインタを示す変数xを初期化する。当該初期化によって、文字列のポインタは入力文字列の先頭をさすように設定される。
ステップ９０４では、パーサー実行部（４０３）はstr.length()が変数xよりも大きい場合、すなわち入力文字列sの長さが文字列のポインタ位置よりも大きい場合に処理すべき文字列があることからステップ９０５に進み、一方、変数xがstr.length()よりも大きい場合、すなわち入力文字列sの長さが文字列のポインタ位置よりも小さい場合に処理すべき文字列がないことからステップ９０６に進む。ステップ９０４〜９０９の各処理は、入力文字列sの先頭から末端までのそれぞれの入力文字列について繰り返し行われる。ステップ９０６は、エラーを返すエラー処理である。
ステップ９０５では、パーサー実行部（４０３）は、入力文字列sのうち、変数xの位置から最後の文字列までの部分文字列を切り出し、当該切り出した部分文字列をS1に格納する。
ステップ９０７では、パーサー実行部（４０３）は、切り出した部分文字列S1をp2でパーズし、当該パーズが正常に終了した場合にp2でパーズされた部分の文字列についてのパーズ結果を抽象構文木(R_1)として返し、且つ部分文字列S1のうちp2で処理されなかった残りの文字列を部分文字列str2として返す。
ステップ９０８では、パーサー実行部（４０３）は、p2が部分文字列S1を受理出来ないものであるかどうかを判定する。パーサー実行部（４０３）は、R_1がエラーである場合には、p2でパーズ可能な部分文字列がまだ見つかっておらず、p2でパーズ可能な部分文字列を探すためにステップ９０９に進む。一方、パーサー実行部（４０３）は、R_1がエラーでない場合には、入力文字列にp2でパーズ可能な部分が見つかったのでステップ９１０に進む。
ステップ９０９では、パーサー実行部（４０３）は、変数xに１を加えて、文字列のポインタ位置を１ずらす。そして、当該処理はステップ９０４に戻り、ステップ９０４〜９０８が繰り返される。
ステップ９１０では、パーサー実行部（４０３）は、入力文字列ｓのうち、先頭文字列から変数xの位置の直前までの部分文字列を切り出し、当該切り出した部分文字列をS2に格納する。
ステップ９１１では、パーサー実行部（４０３）は、切り出した文字列S2をp1でパーズし、当該パーズが正常に終了した場合にp1でパーズされた結果を抽象構文木(R_2)として返し、且つ部分文字列S2のうちp1が処理しなかった残りの文字列をstr3として返す。str3は、p2が自然言語処理関数である場合に空の文字列εである。
ステップ９１２では、パーサー実行部（４０３）は、ステップ９０７からの抽象構文木(R_1)とステップ９１１からの抽象構文木(R_2)とをルートUで統合して、抽象構文木(R)を作成する。
ステップ９１３では、パーサー実行部（４０３）は、ステップ９１２からの抽象構文木(R)と、部分文字列S1のうちp2が処理しなかった残りの文字列str2（ステップ９０７から）とをパーズ結果として返す。
ステップ９１４では、パーサー実行部（４０３）は、Until[p1,p2]によるパーズ処理を終了する。
【００７４】
図１０は、図８のステップ８１６において生成される処理関数For[p1,p2]のパーズ動作を示すフローチャートを示す。
以下に、フローチャートで使用されている定義を説明する。
p1,p2：P1,P2からそれぞれ生成されたパーサー関数である。
s(i,j)：入力文字列sのうちのindex i〜(j-1)の文字列である。
s(k,..)：入力文字列sのうちのindex k〜(s.length()-1)の文字列である。
AST(“F”,R1,R2)：ラベルFを親ノードとし、抽象構文木R1とR2とを子ノードとして設定した新たな抽象構文木を作成する処理である。
【００７５】
ステップ１００１では、パーサー実行部（４０３）は、For[p1,p2]で入力文字列をパーズする処理を開始する。
ステップ１００２では、パーサー実行部（４０３）は、For[p1,p2]でパーズする入力文字列sを変数strに代入する。
ステップ１００３では、パーサー実行部（４０３）は、文字列strをp2でパーズし、当該パーズが正常に終了した場合にp2でパーズされた部分の文字列についてのパーズ結果を抽象構文木(R_2)として返し（図示せず）、且つ入力文字列のうちp2が処理しなかった残りの文字列を部分文字列str2として返す。
ステップ１００４では、パーサー実行部（４０３）は、p2が部分文字列str2を受理出来ないものであるかどうかを判定する。パーサー実行部（４０３）は、R_2がエラーである場合には、入力文字列にまだp2で処理しうる部分がありうるのでステップ１００５に進む。一方、パーサー実行部（４０３）は、R_2がエラーでない場合には、入力文字列にp2で処理しうる部分がないのでステップ１００６に進む。ステップ１００６は、エラーを返すエラー処理である。
ステップ１００５では、パーサー実行部（４０３）は、入力文字列ｓのうち、先頭文字列から部分文字列str1の直前までの部分文字列を全体の入力文字列から差し引いた部分文字列str(0,str.length() - str2.length())を切り出し、当該切り出した部分文字列をS1に格納する。str(0,str.length() - str2.length())のうちのstr2はステップ９０３のstr2と同じである。
ステップ１００７では、パーサー実行部（４０３）は、切り出した文字列S1をp1でパーズし、当該パーズが正常に終了した場合にp1でパーズされた結果を抽象構文木(R_1)として返し、且つ部分文字列S1のうちp1が処理しなかった残りの文字列をstr1として返す。str1は、Nが自然言語処理関数である場合に空の文字列εである。
ステップ１００８では、パーサー実行部（４０３）は、ステップ１００３からの抽象構文木(R_2)とステップ１００６からの抽象構文木(R_1)とをルートFで統合して、抽象構文木(R)を作成する。なお、抽象構文木(R)を作成せずに、ステップ１００６からの抽象構文木(R_1)と、ステップ１００３でp2が処理しなかった残りの文字列str2とをパーズ結果として返すようにしてもよい。抽象構文木として、ステップ１００６からの抽象構文木(R_1)のみを返すのは、抽象構文木を統合するとした場合、必要のない情報が抽象構文木に含まれることになり、後の後処理が煩雑になる場合も考えられるからである。
ステップ１００９では、パーサー実行部（４０３）は、ステップ１００８からの抽象構文木(R)と、ステップ１００３で部分文字列S1のうちp2が処理しなかった残りの文字列str2とを返す。
ステップ１０１０では、パーサー実行部（４０３）は、For[p1,p2]によるパーズ処理を終了する。
【００７６】
図１１は、図９に示すP = P1 U P2において、P1がNPであり且つP2がFPである場合（P = NP U FP）の処理関数Until[np,fp]のパーズ動作を示すフローチャートを示す。
図１１のフローチャートは、図７ａの模式図で示されるパーズ動作に対応する。
以下に、図１１のフローチャートで使用されている定義を説明する。
str：パーズしたい入力文字列（εは空の文字列）である。
fp：文法記述FPから生成されたパーサーであり、例えば形式言語処理パーサーである。
np：文法記述NPから生成されたパーサーであり、例えば自然言語処理関数である。
s(i,j)：入力文字列sのうちのindex i〜(j-1)の文字列である。
s(k,..)：入力文字列sのうちのindex k〜(s.length()-1)の文字列である。
AST(R1,R2)：構文木R1とR2とを子ノードとして合わせた構文木の作成する関数である。
fp(S), np(S)：文字列Sをfp又はnpでパーズして結果を返すことを示す。
【００７７】
ステップ１１０１では、パーサー実行部（４０３）は、Until[np,fp]で入力文字列をパーズする処理を開始する。
ステップ１１０２では、パーサー実行部（４０３）は、Until[np,fp]でパーズする入力文字列sを変数strに代入する。
ステップ１１０３では、パーサー実行部（４０３）は、文字列のポインタを示す変数xを初期化する。当該初期化によって、文字列のポインタは入力文字列の先頭をさすように設定される。
ステップ１１０４では、パーサー実行部（４０３）はstr.length()が変数xよりも大きい場合、すなわち入力文字列sの長さが文字列のポインタ位置よりも大きい場合に処理すべき文字列があることからステップ１１０５に進み、一方、変数xがstr.length()よりも大きい場合、すなわち入力文字列の長さが文字列のポインタ位置よりも小さい場合に処理すべき文字列がないことからステップ１１０６に進む。ステップ１１０４〜１１０９の各処理は、入力文字列sの先頭から末端までのそれぞれの入力文字列について繰り返し行われる。ステップ１１０６は、エラーを返すエラー処理である。
ステップ１１０５では、パーサー実行部（４０３）は、入力文字列sのうち、変数xの位置から最後の文字列までの部分文字列を切り出し、当該切り出した部分文字列をS1に格納する。
ステップ１１０７では、パーサー実行部（４０３）は、切り出した部分文字列S1をfpでパーズし、当該パーズが正常に終了した場合にfpでパーズされた部分の文字列についてのパーズ結果を抽象構文木(R_FP)として返し、且つ部分文字列S1のうちfpで処理されなかった残りの文字列を部分文字列str2として返す。ステップ１１０７を図７ａに従い説明すると、次の通りである：パーサー実行部（４０３）は、切り出した部分文字列 s3及びs4をFPでパーズし、当該パーズが正常に終了した場合にFPでパーズされた部分の文字列（s3）についてのパーズ結果を抽象構文木AST2として返し、且つ部分文字列sのうちFPで処理されなかった残りの文字列 s4を部分文字列として返す。
ステップ１１０８では、パーサー実行部（４０３）は、fpが部分文字列S1を受理出来ないものであるかどうかを判定する。パーサー実行部（４０３）は、R_FPがエラーである場合には、fpでパーズ可能な部分文字列がまだ見つかっておらず、fpでパーズ可能な部分文字列を探すためにステップ１１０９に進む。一方、パーサー実行部（４０３）は、R_FPがエラーでない場合には、入力文字列にfpでパーズ可能な部分が見つかったのでステップ１１１０に進む。
ステップ１１０９では、パーサー実行部（４０３）は、変数xに１を加えて、文字列のポインタ位置を１ずらす。そして、当該処理はステップ１１０４に戻り、ステップ１１０４〜１１０８が繰り返される。
ステップ１１１０では、パーサー実行部（４０３）は、入力文字列ｓのうち、先頭文字列から変数xの位置の直前までの部分文字列を切り出し、当該切り出した部分文字列をS2に格納する。ステップ１１１０を図７ａに従い説明すると、次の通りである：パーサー実行部（４０３）は、入力文字列ｓのうち、先頭文字列から変数3の位置の直前の変数2までの部分文字列s1及びs2を切り出し、当該切り出した部分文字列s1及びs2をS2に格納する。
ステップ１１１１では、パーサー実行部（４０３）は、切り出した文字列S2をnpでパーズし、当該パーズが正常に終了した場合にnpでパーズされた結果を抽象構文木(R_NP)として返し、且つ部分文字列S2のうちnpが処理しなかった残りの文字列を空の文字列εとして返す。npは文字列処理関数であるので空の文字列εがパーズ結果として返される。ステップ１１１１を図７ａに従い説明すると、次の通りである：パーサー実行部（４０３）は、切り出した文字列s1及びs2をNPでパーズし、当該パーズが正常に終了した場合にNPでパーズされた結果を抽象構文木AST1として返す。
ステップ１１１２では、パーサー実行部（４０３）は、ステップ１１０７からの抽象構文木(R_FP)とステップ１１１１からの抽象構文木(R_NP)とを例えばルートUで統合して、抽象構文木(R)を作成する。ステップ１１１２を図７ａに従い説明すると、次の通りである：パーサー実行部（４０３）は、ステップ９０７からの抽象構文木AST2とステップ９１１からの抽象構文木AST1とをルートUで統合して、抽象構文木ASTaを作成する。
ステップ１１１３では、パーサー実行部（４０３）は、ステップ１１１２からの抽象構文木(R)と部分文字列S1のうちfpが処理しなかった残りの文字列str2（ステップ１１０７から）とをパーズ結果として返す。
ステップ１１１４では、パーサー実行部（４０３）は、Until[np,fp]によるパーズ処理を終了する。
【００７８】
図１２は、図１０に示すP = P1 F P2において、P1がNPであり且つP2がFPである場合（P= NP F FP）の処理関数For[np,fp]のパーズ動作を示すフローチャートを示す。
図１２のフローチャートは、図７ｂの模式図で示されるパーズ動作に対応する。
図１２のフローチャートで使用されている定義は、図１１のフローチャートで使用されている定義と同じである。
【００７９】
ステップ１２０１では、パーサー実行部（４０３）は、For[np,fp]で入力文字列（変数str）をパーズする処理を開始する。
ステップ１２０２では、パーサー実行部（４０３）は、For[np,fp]でパーズする入力文字列sを変数strに代入する。
ステップ１２０３では、パーサー実行部（４０３）は、文字列strをfpでパーズし、当該パーズが正常に終了した場合にfpでパーズされた部分の文字列についてのパーズ結果を抽象構文木(R_FP)として返し（図示せず）、且つ入力文字列のうちfpが処理しなかった残りの文字列を部分文字列str1として返す。ステップ１２０３を図７ｂに従い説明すると、次の通りである：パーサー実行部（４０３）は、文字列s1s2をFPでパーズし、入力文字列のうちFPが処理しなかった残りの文字列s2を部分文字列str2として返す。
ステップ１２０４では、パーサー実行部（４０３）は、fpが部分文字列strを受理出来ないものであるかどうかを判定する。パーサー実行部（４０３）は、R_FPがエラーでない場合には、入力文字列にまだfpで処理しうる部分がありうるのでステップ１２０５に進む。一方、パーサー実行部（４０３）は、R_FPがエラーである場合には、入力文字列にfpで処理しうる部分がないのでステップ１２０６に進む。ステップ１２０６は、エラーを返すエラー処理である。
ステップ１２０５では、パーサー実行部（４０３）は、入力文字列ｓのうち、先頭文字列から部分文字列str1の直前までの部分文字列を全体の入力文字列から差し引いた部分文字列str(0,str.length() - str1.length())を切り出し、当該切り出した部分文字列をS1に格納する。str(0,str.length() - str1.length())のうちのstr1はステップ１２０３のstr1と同じである。
ステップ１２０７では、パーサー実行部（４０３）は、切り出した文字列S1をnpでパーズし、当該パーズが正常に終了した場合にnpでパーズされた結果を抽象構文木(R_NP)として返し、且つ部分文字列S1のうちnpが処理しなかった残りの文字列を空の文字列εとして返す。ステップ１２０７を図７ｂに従い説明すると、次の通りである：パーサー実行部（４０３）は、切り出した文字列s1をNでパーズし、当該パーズが正常に終了した場合に抽象構文木ASTb をパーズ結果として返す。なお、図７ｂの場合、Ｎのパーズ結果の一部として返される文字列は空の文字列である。
ステップ１２０８では、パーサー実行部（４０３）は、ステップ１２０３からの抽象構文木(R_FP)とステップ１２０６からの抽象構文木(R_NP)とをルートFで統合して、抽象構文木(R)を作成する。なお、抽象構文木(R)を作成せずに、ステップ１２０６からの抽象構文木(R_NP)と、ステップ１２０３でfpが処理しなかった残りの文字列str1とを返すようにしてもよい。
ステップ１２０９では、パーサー実行部（４０３）は、ステップ１２０８からの抽象構文木(R)と、ステップ１２０３で部分文字列S1のうちfpが処理しなかった残りの文字列str1とを返す。
ステップ１２１０では、パーサー実行部（４０３）は、For[np,fp] によるパーズ処理を終了する。
【００８０】
図１３は、図８に記載の本発明の実施態様に従い生成された組み合わせパーサーを使用して、入力テキストから情報を抽出する例を示す。
固有（Result-And-Conditions Pattern）の記法は例えば、あるＷｅｂシステムの画面仕様書において、画面上の項目値の設定を記述するために使用される。１３０１は、固有の記法に従ったテキストの例を２つ示す。
テキスト１３０２及びテキスト１３０３は、全体の構造（但し、下線部を除く）が固有の記法に従って記載されている。すなわち、テキスト１３０２は、「次のすべてが成り立つ場合、」という形式的な記述を有し、その次に個々の中身の自由度が高い記述を有する。また、テキスト１３０３は、「以下の全てが成り立つ場合、」という形式的な記述を有し、その次に個々の中身の自由度が高い記述を有する。
ユーザは、このテキストを下記のようにパーズしたいと考える：
（１）テキストの全体の構造（但し、下線部を除く）が固有の記法に従っているかどうかについて検査できるようにしたい：及び
（２）テキストの特定部分（テキスト１３０２及びテキスト１３０３の下線部分）のみに、特定の自然言語処理is-a-NLPを適用し、is-a関係のペアを抽出できるようにしたい。
そこで、ユーザは、第１のエディタ部（３０２）を使用して、文法記述の組み合わせパターンを含む宣言的記述（１３０４）を作成する。文法記述の組み合わせ１３０４では、文法記述のルールP1 U P2（すなわち、FP U NP）が使用されている。また、文法記述の組み合わせ１３０４では、[is-a-NLP]が、is-a-NLPパーサー名を指定し、そして当該is-a-NLPパーサーの適用箇所を示す。（次のすべてが成り立つ場合／以下のすべてが成り立つ場合）の「／」は、優先順位が付いた“又は”を意味し、「次のすべてが成り立つ場合」でパーズし、パーズ出来なければ「以下のすべてが成り立つ場合」でパーズすることを意味する。また、文法記述の組み合わせ１３０４において、＋は、[is-a-NLP]U<改行>の１回以上の繰り返しを示す。
宣言的記述が、第１のエディタ部（３０２）からパーサー生成装置（１３０５）に渡される。パーサー生成装置（１３０５、図３の３０１に対応する）は、宣言的記述（１３０４）中の文法記述の組み合わせパターンに従い組み合わせパーサー（コード）（１３０６）を自動的に生成する。コンパイラ−（４０２）は、生成された組み合わせパーサー（コード）（１３０６）をその実行コードに変換する。
１３０７は、テキスト１３０２及びテキスト１３０２を上記実行コードでパーズした結果を示す。組み合わせパーサーは、固有の記法を持つテキストを次のようにパーズすることが可能である：（１）全体のテキスト構造（但し、下線部分を除く）が、固有の記法に従っていることを検査するためにパーズする；（２）テキストの特定部分（下線部分である）にのみ、特定の自然言語処理（is-a-NLP）を適用し、is-a関係のペアを抽出するためにパーズする。
パーズの結果は、１３０７に示すようなテキスト形式（例えばＸＭＬ形式）、又は当該テキスト形式に対応する抽象構文木（AST）で示されうる。パーズの結果をどのような手法で表現するかは、当業者に知られている方法を任意に使用することが可能である。
【００８１】
図１４は、図１３の１３０１に示す例のために、ユーザによって作成される文法記述例を示す。
宣言的記述１４０１は、複数の文法記述を含む。文法記述は、図６の記載に従う。
図１４に示す宣言的記述において、文法記述のトップレベルでの組み合わせは、S :: = P1 ; P2である。
トップレベルにある文法記述のP1はさらに、P12 / P13の文法記述からなる（第１のサブレベル）。
サブレベルにある文法記述のP12は形式言語部分の特定であり、「次のすべてが成り立つ場合」によって特定されている。
サブレベルにある文法記述のP13は形式言語部分の特定であり、「以下のすべてが成り立つ場合」によって特定されている。
トップレベルにある文法記述のP2はさらに、P3 ; P4の文法記述からなる（第１のサブレベル）。
サブレベルにある文法記述のP3は形式言語部分の特定であり、「、」（「場合」という語に続いている文字である）によって特定されている。
サブレベルにある文法記述のP4はさらに、P5 ; P6の文法記述からなる（第２のサブレベル）。
サブレベルにある文法記述のP5はさらに、Pn U P8の文法記述からなる（第３のサブレベル）。
サブレベルにある文法記述のP6はさらに、P7 ; P7*の文法記述からなる（第３のサブレベル）。
文法記述Pnは、自然言語処理関数[is-a-NLP]を指定する。
文法記述P8は、改行を指定する。
文法記述P7は、Pn U P8の文法記述からなる（第４のサブレベル）。
以上のように、宣言的記述は、図６に示す文法記述に従っており、トップレベルからサブレベルまで順次分解されてその文法記述が特定される。
【００８２】
図１５は、図１３に示す文法記述（１３０４）の例において生成される組み合わせパーサー（１３０５）のパーズ動作を示すフローチャートを示す。
ステップ１５０１では、パーサー実行部（４０３）は、組み合わせパーサーで図１３に示すテキスト（１３０２、１３０３）をパーズする処理を開始する。
ステップ１５０２〜１５０６は、図１３の１３０４の（次のすべてが成り立つ場合／以下のすべてが成り立つ場合）  部分をパーズする処理を示す。
ステップ１５０２では、パーサー実行部（４０３）は、文字列“次のすべてが成り立つ場合、”を変数str1に格納する。
ステップ１５０３では、パーサー実行部（４０３）は、文字列“以下のすべてが成り立つ場合、”を変数str2に格納する。
ステップ１５０４では、パーサー実行部（４０３）は、パーサー(str1/str2)で文字列sをパーズする。Or(str1,str2,s)は、パーサー(sr1/str2)で文字列ｓをパーズする処理を表す。パーサー実行部（４０３）は、文字列sの先頭文字列がstr1であるか又はstr2であるかをチェックする。先頭文字列がstr1である場合に、パーサー実行部（４０３）は、str1部分の抽象構文木Rhと、文字列ｓの先頭文字列からstr1を除いた文字列とをパーズ結果として返す。先頭文字列がstr2である場合に、パーサー実行部（４０３）は、str2部分の抽象構文木Rhと、文字列ｓの先頭文字列からstr2を除いた文字列とをパーズ結果として返す。
ステップ１５０５では、パーサー実行部（４０３）は、ステップ１５０４で返された結果を調べるために、パーサー(str1/str2)が文字列sを受理出来ないものであるかどうかを判定する。パーサー実行部（４０３）は、Rhがエラーでない場合には、ステップ１５０４で返された結果から抽象構文木と残りの文字列とを取出すために、ステップ１５０６に進む。一方、パーサー実行部（４０３）は、Rhがエラーである場合には、パーズ・エラーとなるために、ステップ１５０７に進む。ステップ１５０７はエラー処理である。
ステップ１５０６では、パーサー実行部（４０３）は、ステップ１５０４で返された結果から、抽象構文木Ah1と残りの文字列ｓｔｒ１を取り出している。なお、ステップ１５０６は、ステップ１５０４の結果を取り出しているだけなので省略してもよい。
ステップ１５０８では、パーサー実行部（４０３）は、is-a-NLPの名前を持つ自然言語処理関数を自然言語処理登録ストア（３０５）から取り出す。パーサー実行部（４０３）は、当該取り出した自然言語処理関数を、関数npに格納する。
ステップ１５０９では、パーサー実行部（４０３）は、改行文字列のみを受理するパーサー関数を生成し、関数retに格納する。
ステップ１５１０では、パーサー実行部（４０３）は、ステップ１５０６からの部分文字列sr1をUntil[np,ret]でパーズし、抽象構文木R2をパーズ結果として返す。
ステップ１５１１では、パーサー実行部（４０３）は、パーサーretが部分文字列sr1を受理出来ないものであるかどうかを判定する。パーサー実行部（４０３）は、R2がエラーである場合には、全体としての結果がパーズ・エラーとなるのでステップ１５０７に進む。一方、パーサー実行部（４０３）は、R2がエラーでない場合には、この部分のパーズが成功しているので次のパーズに進むためにステップ１５１２に進む。
ステップ１５１２では、パーサー実行部（４０３）は、ステップ１５１０の結果から抽象構文木Ah2及びsr2を取り出して、ステップ１５１３へ進む。
ステップ１５１３では、パーサー実行部（４０３）は、変数srに格納されている文字列を変数ｓに格納しなおす。また、パーサー実行部（４０３）は、ステップ１５０６からの抽象構文木(Ah1)とステップ１５１２からの抽象構文木(Ah2)とをルートseqで統合して、抽象構文木(Ah)を作成する。
ステップ１５１４〜１５１８は、図１３の１３０４の  (・[is-a-NLP]U <改行>)+  部分をパーズする処理を示す。
ステップ１５１４では、パーサー実行部（４０３）は、パーズした・[is-a-NLP] U <改行> の個数を保持している変数iを初期化する。
ステップ１５１５では、パーサー実行部（４０３）は、ステップ１５１３からの部分文字列sをUntil[np,ret]でパーズし、抽象構文木Rをパーズ結果として返す。
ステップ１５１６では、パーサー実行部（４０３）は、Util[np,ret]が文字列sをパーズできるかどうかを判定する。パーサー実行部（４０３）は、Rがエラーである場合には、全体としての結果がパーズ・エラーとなるのでステップ１５０７に進む。一方、パーサー実行部（４０３）は、Rがエラーでない場合には、この部分のパーズが成功しているので次のパーズに進むためにステップ１５１７に進む。
ステップ１５１７では、パーサー実行部（４０３）は、変数ｉに１を加える。また、パーサー実行部（４０３）は、ステップ１５１５のパーズ結果Rから抽象構文木Aiと残りの文字列sとをパーズ結果として返す。
ステップ１５１８では、パーサー実行部（４０３）は、sが空白文字のみであるかどうかを判定する。パーサー実行部（４０３）は、sが空白文字のみでない場合にステップ１５１５に戻り、一方、sが空白文字である場合にステップ１５１９に進む。
ステップ１５１９では、パーサー実行部（４０３）は、ステップ１５１７からの各A1,…,Aiを子ノードとし、ルートrepで統合して、抽象構文木(Ac)を作成する。また、パーサー実行部（４０３）は、ステップ１５１３からの抽象構文木(Ah)とステップ１５１９からの抽象構文木(Ac)とを子ノードとし、ルートseqで統合して、抽象構文木(AR)を作成する。
ステップ１５２０では、パーサー実行部（４０３）は、パーズが成功である場合に、ステップ１５１９からの抽象構文木(AR)をパーズ結果として返す。
ステップ１５２１では、パーサー実行部（４０３）は、組み合わせパーサーのパーズ処理を終了する。
【００８３】
図１６は、図１５に示すフローチャートのステップ１５０４におけるサブルーチンのフローチャートを示す。
ステップ１６０１では、パーサー実行部（４０３）は、Or(str1,str2,s)の処理を開始する。
ステップ１６０２では、パーサー実行部（４０３）は、str1がsの前方部分文字列であるかどうかを検査する。str1がsの前方部分文字列でない場合にステップ１６０３に進み、一方、str1がsの前方部分文字列である場合にステップ１６０４に進む。
ステップ１６０４では、パーサー実行部（４０３）は、str1がsの前方部分文字列である場合にstr1をstrに格納する。
ステップ１６０３では、パーサー実行部（４０３）は、str2がsの前方部分文字列でない場合にステップ１６０５に進み、一方、str2がsの前方部分文字列である場合にステップ１６０６に進む。
ステップ１６０６では、パーサー実行部（４０３）は、str2がsの前方部分文字列である場合にstr2をstrに格納する。
ステップ１６０５では、パーサー実行部（４０３）は、str2がsの前方部分文字列でないことに応じて、エラー処理をし、ステップ１６１０に進む。
ステップ１６０７では、パーサー実行部（４０３）は、sから前方部分文字列strを除いた部分文字列をs’に格納する。
ステップ１６０８では、パーサー実行部（４０３）は、前方部分文字列strの構文木Aを作成する。
ステップ１６０９では、パーサー実行部（４０３）は、ステップ１６０８からの構文木Aとステップ１６０７からの文字列s’を返す。文字列s’は、その後、図１５のステップ１５０６において、sr1に代入される。
ステップ１６１０では、パーサー実行部（４０３）は、Or(str1,str2,s)の処理を終了する。
【００８４】
実施例１
図１７は、本発明の実施態様に従う組み合わせパーサーでテストケース記述データをパーズし、パラメータ名と値（Value）とを取り出し、組み合わせテストの最適化を行う例を示す。
組み合わせテストとは、可能性のあるパラメータ名と値との組み合わせを全てテストすることである。実施例１では、どのパラメータがどの値を取り得るのかをドキュメント（テストケース記述のデータ）から収集することを目的としている。
表１７０１は、テストケース記述のデータ例を示す。テストケース記述は１９２個用意された（１７０１−１、１７０１−２、１７０１−３、・・・、１７０１−１９２）。各テストケース記述は、類似のデータ構造を有する。
ユーザは、本発明の実施態様に従う、複数の文法記述を含む宣言的記述を下記の通り作成した。作成された宣言的記述は、自然言語処理関数と形式言語処理パーサーとの組み合わせ適用を示す文法記述を含む。当該宣言的記述において、文法記述のトップレベルは「;」である。
【００８５】
（複数の文法記述の組み合わせ）
S ::= [(For keyword-NLP)?] U (validate/Validate that);[is-a-NLP]U eoi 
【００８６】
複数の文法記述の組み合わせSは、形式言語処理「For」の後ろに自然言語処理「keyword-NLP」を含み、そして形式言語処理「validate」及び「validate that」を含み、さらにその後ろに自然言語処理「is-a-NLP」を適用することを記述する。当該文法記述の組み合わせSにおいて、テストケース記述に関する知見に基づき、必要な箇所に必要なNLPが適用されている。
そして、当該文法記述の組み合わせSから、本発明の実施態様に従う組み合わせパーサー（コード）sが生成され、そして当該組み合わせパーサー（コード）sがコンパイラによって実行コードに変換された。
【００８７】
各テストケース記述（１７０１−１、１７０１−２、１７０１−３、・・・、１７０１−１９２）を上記実行コードでパーズした（１７０２）。当該パーズにより、テストケース記述の特定の文脈からのみ、パラメータ名と値を抽出可能である。それによって、テストで用いるパラメータを示す値を収集できる。その結果、パラメータ名と値の対が９２個得られた。収集した値を当該値中の最後の単語でソートした結果が表１７０３である。表１７０３をみることで、組み合わせテストのためのパラメータ−値が定義しやすくなる。表１７０１と表１７０３との間には、各テストケース記述からパラメータと値とがどのように抽出されたかを示す点線矢印が記載されている。そして、表１７０３において、パラメータ値が同じものの値について、表１７０４が新たに作成された。表１７０４は、組み合わせテスト最適化の入力例を示す。
【００８８】
各テストケース記述（１７０１−１、１７０１−２、１７０１−３、・・・、１７０１−１９２）を従来技術に従うパーサーを適用してキーワードを抽出した（１７０５）。従来技術は、テストケース記述全体に対して、is-a-NLP（is-a関係を取り出す処理関数である）及びkeyword-NLP（特定のキーワードを取り出す処理関数である）を適用する方法である。その結果、パラメータ名と値の対が４１５個得られた（１７０６）。そして、パラメータ値が同じものの値について、表１７０４が新たに作成された。
【００８９】
本発明の実施態様に従い作成された組み合わせパーサーを適用した場合、既存のパーサーを使用するように文法記述を記述可能である。そのために、言語処理パーサーを抽出目的によってカスタマイズする必要がない。一方、既存の技術では、言語処理パーサーを抽出目的によってカスタマイズする必要がある。従って、本発明の実施態様に従い作成された組み合わせパーサーを使用することで、言語処理パーサーをカスタマイズするコストを軽減ないしは削減することが可能である。
また、本発明の実施態様に従い作成された組み合わせパーサーを適用した場合、既存のパーサーを適用した場合に比べて、抽出されたキーワードの数が少ない。従って、抽出されたキーワードから、表１７０４を作成するコストを軽減ないしは削減することが可能である。また、本発明の実施態様に従い作成された組み合わせパーサーを適用した場合、必要な情報を含んだ状態で対象を絞り込むことが可能であり、モデル作成の作業を軽減することが可能である。
【００９０】
実施例２
図１８は、本発明の実施態様に従い、特定の部分のみをパーズすることを可能にすることを示すための画面仕様書の例を示す。なお、以下では、隅付き括弧を［］で示す。
画面仕様書１８０１は、ＸＭＬ形式で記載されている。そして、ユーザは、画面仕様書１８０１のうち、隅付き括弧内に［項目表示処理］で示される１８０２で示す部分のみをパーズしたいと考える。１８０２で示される部分のみのパーズ結果を有する抽象構文木を返すパーサー<item-process>は、下記のように記述される。
【００９１】
<item-process>::= ｛◇［項目表示処理］｝； FD ； ｛［画面遷移処理］｝
但し、パーサー◇FPは、（ε U FP）であり、
パーサー｛FP｝は、（ε F FP）であり、
パーサーFDは、１８０２の部分をパーズする形式言語処理パーサーである。
◇FPは、FPが成功する部分（すなわち、［項目表示処理］）までを無視して捨て、当該成功する部分をFPでパーズする、という文法記述である。上記例において◇FPは［項目表示処理］である。
パーサー｛FP｝は、FPでパーズして、パーズ結果であるASTを捨てる、という文法記述である。上記例において｛FP｝は［画面遷移処理］である。従って、｛［画面遷移処理］｝では、パーサー｛FP｝は、パーズ結果の［画面遷移処理］部分のＡＳＴを捨てる。
【００９２】
上記に説明したように、本発明の実施態様では、テキストの特定部分のみをパーズし、抽象構文木として抽出することが可能である。
なお、従来の文法記述では、テキスト全体がパーズの処理対象であるためにテキストの特定部分のみをパーズして抽象構文木として抽出することが出来ず、従って、パーズ結果を別途のプログラムで処理して特定部分のみの抽象構文木を作成する必要がある。
【００９３】
図１８に示す本発明の実施態様は、テキストが例えば、ＸＭＬ文書、特許、意匠、又は商標出願文書においても適用可能である。
【００９４】
実施例３
図１９は、本発明の実施態様に従い、あるプロジェクトにおいて、特定の設計文書中の特定の記述部分についてパーズした場合を説明するための表を示す。
図１９はあるプロジェクトの特定の設計文書である画面仕様書の項目表示処理部分の記法に対する文法を示す。なお、実例の記載は省略している。
記法中、Ｂの部分を自然言語処理で解析し、可能であれば（条件、結果）のペアを得たいとする。
記法中、Ｃ及びＲの部分を自然言語処理で解析し、可能であれば（項目、値）のペアを得たいとする。
【００９５】
記法中、Ｂ、Ｃ及びＲの部分を全て形式的に書き下す場合、そのプログラミングは大変である。そこで、既存の自然言語処理を本発明の実施態様に従い適用可能とするために、本発明の実施態様に従う文法記述を使用し、宣言的記述を作成した。そして、作成された宣言的記述から、自動的に組み合わせパーサーを生成した。
図１９に示す設計文書を、上記組み合わせパーサーでパーズしたところ、画面仕様書に対して、必要なパターン数が２０数個に抑えることができた。また、PEGで処理しない部分に自然言語処理関数を適用するために、抽象構文木処理のためのプログラムを個別に作り込む必要がない。
【００９６】
（比較例）
記法中、Ｂ、Ｃ及びＲの部分を全て形式的に書き下す場合、書き下すパターンの数が約５０〜６０個であった（但し、該当部分の自然文として妥当な全てのパターンをカバーしているものではない）。
また、自然言語処理関数を利用する場合においても、既存のPEGに従う方法では、書き下す抽出パターンは約２０個であった。ただし、自然言語処理関数を利用する場合、そのパーズ結果の抽象構文木の処理のためのプログラミングが別途必要であり、さらに当該プログラミングは抽出パターンごとに必要であった。抽象構文木の処理は、ツリーマッチング等による必要部分の抽出、及び必要部分への自然言語処理を含む。
このように、従来技術による方法では、自然文を含むテキストを全て形式的に書き下すことは労力を必要とし、また設計ごとに記法が異なったり、又は設計文書若しくは要求文書で使われる独自記法又はテンプレートなどの形式的な部分の記法の変更が頻繁に生じたりするので、パターン以外の部分を作り込むことが難しい。
【００９７】
実施例４
図２０は、本発明の実施態様に従い、拡張された文法記述から生成される組み合わせパーサーを使用して生成される抽象構文木の例を示す。
【００９８】
従来のPEGのみでは、PEGによるパーズでない他の処理（例えば、受理言語を有しない既存の自然言語処理）でパーズする部分を文法上で明示的に指定することができない。
発明の実施態様に従うと、他の処理でパーズする部分を文法上で明示的に指定することが可能である。すなわち、他の処理でパーズしない部分をスキップすることが可能である。
抽象構文木２００１は、本発明の実施態様に従う組み合わせパーサーによる処理結果として生成されたものである。組み合わせパーサーの例は、下記の通りである。
【００９９】
<Result-And-Conditions>::= 
（次のすべてが成り立つ場合／以下のすべてが成り立つ場合）、(（!<改行>）.)* <改行>
( ・ ((!<改行>).)* <改行> ) +
【０１００】
((!<改行>）.)*  の部分（２箇所）が、否定先読み等により、スキップする部分を明示的に指定するための記述である。なお、「.」は、任意の文字を示す。
【０１０１】
抽象構文木２００１では、形式言語部分が受理しない部分の処理結果を含む木が直接得られる。従って、本発明の実施態様に従えば、分析対象に即して少ない労力で処理をすることが可能になる。
【０１０２】
（比較例）
抽象構文木２００２は、既存のPEG記法に従うパーサーによる処理結果として生成されたものである。抽象構文木２００２では、形式言語処理パーサーが入力文字全体をパーズするために、スキップさせたい部分を含む構文木が出力される（２００２）。
そこで、スキップさせたい部分を適切に処理するためには、既存のPEG記法での処理を個別に作成する必要がある。
処理１として、構文木の構造及び文字列パターンマッチングにより、ラベルを付与する（２００３）。処理１では、スキップさせたい部分のパターン及びPEG外処理でのマッチングパターンが文法と適切に連動するように個々に定義するのが煩雑であり、また、スキップさせたい部分のパターン及びPEG外の処理でのマッチングパターンが複雑になりやすい。
処理２として、ラベルS1に自然言語処理関数を適用し、ラベルS2に自然言語処理関数をさらに適用する。
【０１０３】
図２１は、既存の文法記述PEG（図５）と本発明の実施態様において新たに追加される文法記述（図６）との文法の記述力の関係を示す。
本発明の実施態様において、PEGと呼ばれる文法記述を使用しうる。当該文法は、パーサーの処理手順を記述する。PEGの形式に従って文法を記述することで下記の特徴がある；
（１）PEGの形式に従って文法を記述すると、そこから生成したパーサーのパーズ処理結果が必ず一意に決定されることが証明されており、シフト還元衝突（shift/reduce conflict）のような問題が生じない。
（２）PEGの記述できる文法は、LALR(1)パーサーの扱える文法を網羅していることが証明されている。LALR(1)は、一般的なLALRパーサーであり、正規表現を用いた字句解析と先読み１のLALRパーサーとの組み合わせたものである。
なお、図２１中、CFG（Context Free Grammar）は文脈自由文法を示す。
本発明の実施態様において、PEGの形式に従ってルール群を拡張した場合、拡張された（追加された）文法記述は、上記（１）及び（２）の特徴を保持したまま拡張されている。
【図１】
2012063868.tif 000003
【図２】
2012063868.tif 000004
【図３】
2012063868.tif 000005
【図４】
2012063868.tif 000006
【図５】
2012063868.tif 000007
【図６】
2012063868.tif 000008
【図７】
2012063868.tif 000009
【図８】
2012063868.tif 000010
【図９】
2012063868.tif 000011
【図１０】
2012063868.tif 000012
【図１１】
2012063868.tif 000013
【図１２】
2012063868.tif 000014
【図１３】
2012063868.tif 000015
【図１４】
2012063868.tif 000016
【図１５】
2012063868.tif 000017
【図１６】
2012063868.tif 000018
【図１７】
2012063868.tif 000019
【図１８】
2012063868.tif 000020
【図２０】
2012063868.tif 000021
【図２１】
2012063868.tif 000022
【図１９】
2012063868.tif 000023