(57)【特許請求の範囲】
【請求項１】
単語に関連する構文木の集合を格納した構文木プールと、前記構文木プールに属する構文木からなる列をオートマトンで記述した構文木列受理部と、
単語の綴りや統語的性質を含む単語情報とを有する単語辞書を単語毎に備えた辞書を記憶手段に記憶保持しており、
入力手段から入力された原文の解析処理を進めるにあたり、
（ａ）前記原文を単語に分割し、この分割された各単語の該単語辞書の内容を前記辞書からロードして、エッジとしてチャートに登録するステップと、
（ｂ）前記チャート上で、すべての部分区間の間に、包含関係による順序を付与するステップと、
（ｃ）前記チャート上で、前記（ｂ）のステップで付与された順序に従って、動的計画法に基づいて小さな区間から大きな区間へと注目区間を変えながら、各注目区間に対して
（ｃ１）注目区間に含まれるエッジの中から注目エッジを決めるステップ
（ｃ２）前記（ｃ１）のステップで決められた注目エッジに対応するオートマトンの状態を、該注目エッジ内の前記構文木列受理部を参照して調べ、このオートマトンの現在の状態から次の状態への遷移により受理可能な構文木を選択するステップ
（ｃ３）前記（ｃ２）のステップで選択された構文木がチャート上で成立するかどうかを判断するステップ
（ｃ４）前記（ｃ３）のステップで構文木が成立すると判断した場合、前記構文木を受理して前記オートマトンの状態遷移を行い、状態遷移後のオートマトンに対応する新たなエッジを作成してチャートに登録するステップ
の各ステップ（ｃ１〜ｃ４）を実行するステップと、
（ｄ）前記チャートの内容を解析することによって、前記原文の言語解析結果を出力するステップと、
を含むことを特徴とする言語解析方法。
【請求項２】
単語に関連する構文木の集合を格納した構文木プールと、前記構文木プールに属する構文木からなる列をオートマトンで記述した構文木列受理部と、
単語の綴りや統語的性質を含む単語情報とを有する単語辞書を単語毎に備えた辞書を記憶手段に記憶保持しており、
入力手段から入力された原文の解析処理を進めるにあたり、
（ａ）前記原文を単語に分割し、この分割された各単語の該単語辞書の内容を前記辞書からロードして、エッジとしてチャートに登録するステップと、
（ｂ）前記チャート上で、すべての部分区間の間に、包含関係による順序を付与するステップと、
（ｃ）前記チャート上で、前記（ｂ）のステップで付与された順序に従って、動的計画法に基づいて小さな区間から大きな区間へと注目区間を変えながら、各注目区間に対して
（ｃ１）注目区間に含まれるエッジの中から注目エッジを決めるステップ
（ｃ２）前記（ｃ１）のステップで決められた注目エッジに対応するオートマトンの状態を、該注目エッジ内の前記構文木列受理部を参照して調べ、このオートマトンの現在の状態から次の状態への遷移により受理可能な構文木を選択するステップ
（ｃ３）前記（ｃ２）のステップで選択された構文木がチャート上で成立するかどうかを判断するステップ
（ｃ４）前記（ｃ３）のステップで構文木が成立すると判断した場合、前記構文木を受理して前記オートマトンの状態遷移を行い、状態遷移後のオートマトンに対応する新たなエッジを作成してチャートに登録するステップ
の各ステップ（ｃ１〜ｃ４）を実行するステップと、
（ｄ）前記（ｃ４）のステップで作成したエッジを登録する際に、前記オートマトンが現在の状態を含めて全く同じ状態である別のエッジが登録予定区間に既に存在すれば、該エッジをこの既存エッジにパックして登録し、そのような別のエッジが存在しなければ、該エッジをチャートに登録するステップと、
（e）前記チャートの内容を解析することによって、前記原文の言語解析結果を出力するステップと、
を含むことを特徴とする言語解析方法。
【請求項３】
原文を入力する入力手段と、単語情報を格納した辞書と、前記辞書を参照しながら前記入力した原文の解析を行う解析手段と、前記解析手段による部分解析結果を登録するチャートを保持する記憶手段と、解析結果を出力する出力手段と、を備え、
前記記憶手段には、単語に関連する構文木の集合を格納した構文木プールと、前記構文木プールに属する構文木からなる列をオートマトンで記述した構文木列受理部と、単語の綴りや統語的性質を含む単語情報とを有する単語辞書を単語毎に備えた辞書を記憶手段に記憶保持しており、
前記解析手段が前記入力手段から入力された原文の解析処理を進めるにあたり、
（ａ）前記原文を単語に分割し、この分割された各単語の該単語辞書の内容を前記辞書からロードして、エッジとしてチャートに登録する機能と、
（ｂ）前記チャート上で、すべての部分区間の間に、包含関係による順序を付与する機能と、
（ｃ）前記チャート上で、前記（ｂ）の機能により付与された順序に従って、動的計画法に基づいて小さな区間から大きな区間へと注目区間を変えながら、各注目区間に対して
（ｃ１）注目区間に含まれるエッジの中から注目エッジを決めるステップ
（ｃ２）前記（ｃ１）の機能により決められた注目エッジに対応するオートマトンの状態を、該注目エッジ内の前記構文木列受理部を参照して調べ、このオートマトンの現在の状態から次の状態への遷移により受理可能な構文木を選択するステップ
（ｃ３）前記（ｃ２）のステップで選択された構文木がチャート上で成立するかどうかを判断するステップ
（ｃ４）前記（ｃ３）のステップで構文木が成立すると判断した場合、前記構文木を受理して前記オートマトンの状態遷移を行い、状態遷移後のオートマトンに対応する新たなエッジを作成してチャートに登録するステップ
の各ステップ（ｃ１〜ｃ４）を実行する機能と、
（ｄ）前記チャートの内容を解析することによって、前記原文の言語解析結果を出力する機能と、
を有することを特徴とする言語解析装置。
【請求項４】
原文を入力する入力手段と、単語情報を格納した辞書と、前記辞書を参照しながら前記入力した原文の解析を行う解析手段と、前記解析手段による部分解析結果を登録するチャートを保持する記憶手段と、解析結果を出力する出力手段と、を備え、
前記記憶手段には、単語に関連する構文木の集合を格納した構文木プールと、前記構文木プールに属する構文木からなる列をオートマトンで記述した構文木列受理部と、
単語の綴りや統語的性質を含む単語情報とを有する単語辞書を単語毎に備えた辞書を記憶手段に記憶保持しており、
前記解析手段が前記入力手段から入力された原文の解析処理を進めるにあたり、
（ａ）前記原文を単語に分割し、この分割された各単語の該単語辞書の内容を前記辞書からロードして、エッジとしてチャートに登録する機能と、
（ｂ）チャートに登録されたエッジの中から注目エッジを決める機能と、
（ｃ）前記（ｂ）の機能により決められた注目エッジに対応するオートマトンの状態を、該注目エッジ内の前記構文木列受理部を参照して調べ、このオートマトンの現在の状態から次の状態への遷移により受理可能な構文木を選択する機能と、
（ｄ）前記（ｃ）の機能により選択された構文木がチャート上で成立するかどうかを判断する機能と、
（ｅ）前記（ｄ）の機能により構文木が成立すると判断した場合、前記構文木を受理して前記オートマトンの状態遷移を行い、状態遷移後のオートマトンに対応する新たなエッジを作成する機能と、
（ｆ）前記（ｅ）の機能により作成したエッジを登録する際に、前記オートマトンが現在の状態を含めて全く同じ状態である別のエッジが登録予定区間に既に存在すれば、該エッジをこの既存エッジにパックして登録し、そのような別のエッジが存在しなければ、該エッジをチャートに登録する機能と、
（ｇ）前記チャートの内容を解析することによって、前記原文の言語解析結果を出力する機能と、
を有することを特徴とする言語解析装置。
【請求項５】
単語に関連する構文木の集合を格納した構文木プールと、前記構文木プールに属する構文木からなる列をオートマトンで記述した構文木列受理部と、
単語の綴りや統語的性質を含む単語情報とを有する単語辞書を単語毎に備えた辞書をコンピュータの記憶手段に記憶保持しており、
コンピュータの入力手段から入力された原文の解析処理をコンピュータで進めるにあたり、
（ａ）前記原文を単語に分割し、この分割された各単語の該単語辞書の内容を前記辞書からロードして、エッジとしてチャートに登録するステップと、
（ｂ）前記チャート上で、すべての部分区間の間に、包含関係による順序を付与するステップと、
（ｃ）前記チャート上で、前記（ｂ）のステップで付与された順序に従って、動的計画法に基づいて小さな区間から大きな区間へと注目区間を変えながら、各注目区間に対して
（ｃ１）注目区間に含まれるエッジの中から注目エッジを決めるステップ
（ｃ２）前記（ｃ１）のステップで決められた注目エッジに対応するオートマトンの状態を、該注目エッジ内の前記構文木列受理部を参照して調べ、このオートマトンの現在の状態から次の状態への遷移により受理可能な構文木を選択するステップ
（ｃ３）前記（ｃ２）のステップで選択された構文木がチャート上で成立するかどうかを判断するステップ
（ｃ４）前記（ｃ３）のステップで構文木が成立すると判断した場合、前記構文木を受理して前記オートマトンの状態遷移を行い、状態遷移後のオートマトンに対応する新たなエッジを作成してチャートに登録するステップ
の各ステップ（ｃ１〜ｃ４）を実行するステップと、
（ｄ）前記チャートの内容を解析することによって、前記原文の言語解析結果を出力するステップと、
をコンピュータで実行させるプログラムを記録した記録媒体。
【請求項６】
単語に関連する構文木の集合を格納した構文木プールと、前記構文木プールに属する構文木からなる列をオートマトンで記述した構文木列受理部と、
単語の綴りや統語的性質を含む単語情報とを有する単語辞書を単語毎に備えた辞書をコンピュータの記憶手段に記憶保持しており、
コンピュータの入力手段から入力された原文の解析処理をコンピュータで進めるにあたり、
（ａ）前記原文を単語に分割し、この分割された各単語の該単語辞書の内容を前記辞書からロードして、エッジとしてチャートに登録するステップと、
（ｂ）チャートに登録されたエッジの中から注目エッジを決めるステップと、
（ｃ）前記（ｂ）のステップで決められた注目エッジに対応するオートマトンの状態を、該注目エッジ内の前記構文木列受理部を参照して調べ、このオートマトンの現在の状態から次の状態への遷移により受理可能な構文木を選択するステップと、
（ｄ）前記（ｃ）のステップで選択された構文木がチャート上で成立するかどうかを判断するステップと、
（ｅ）前記（ｄ）のステップで構文木が成立すると判断した場合、前記構文木を受理して前記オートマトンの状態遷移を行い、状態遷移後のオートマトンに対応する新たなエッジを作成するステップと、
（ｆ）前記（ｅ）のステップで作成したエッジを登録する際に、前記オートマトンが現在の状態を含めて全く同じ状態である別のエッジが登録予定区間に既に存在すれば、該エッジをこの既存エッジにパックして登録し、そのような別のエッジが存在しなければ、該エッジをチャートに登録するステップと、
（ｇ）前記チャートの内容を解析することによって、前記原文の言語解析結果を出力するステップと、
をコンピュータで実行させるプログラムを記録した記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、言語の解析装置に関し、特に、文法規則を単語の辞書の中に保持する語彙化文法に基づく言語の解析装置に関する。
【背景技術】
【０００２】
文法を構成する基本要素、一般には、構文木のすべてがいずれかの単語と関連付けられているとき、その文法は語彙化されているという。すなわち、文法規則を単語に関連付けすることを文法の語彙化といい、語彙化された文法を語彙化文法という。
【０００３】
語彙化文法に基づく自然言語の解析装置として、例えば特開平７−５６９2１号公報（以下「文献１」という）には、文脈自由文法を「語彙化文脈自由文法（LCFG;LexicalizedContextFreeGrammar）」と呼ばれる語彙化形式に変換してから文の解析を行う文解析システムが記載されている。
【０００４】
また、刊行物（1996年8月、プロシーディングス・オブ・ザ・フォース・インターナショナル・コンファランス・オン・スポークン・ランゲージ・プロセッシング（ProceedingsofICSLP96,theFourthInternationalConferenceonSpokenLanguageProcessing,Philadelphia,Pennsylvania,1996））に記載の「ヘッド・オートマタ・アンド・バイリンガル・タイリング：トランスレーション・ウイズ・ミニマル・リプレゼンテーションズ」（HeadAutomataandBilingualTiling:TranslationwithMinimalRepresentations）と題する論文（以下「文献２」という）には、単語に付随するオートマトンにより依存文法の解析と言語間の構文変換を行う解析装置が記載されている。
【０００５】
また、語彙化文法の解析を効率化するために語彙化したオートマトンを使用する方法が知られており、例えば、刊行物（1998年4月、プロシーディングス・オブ・ザ・ファースト・ワークショップ・オン・タビュレーション・イン・パーシング・アンド・ディダクション（ProceedingsofthefirstTabulationinParsingandDeduction,Paris,France,INRIA主催)）に記載の「グラマー・コンパクション・アンド・コンピューテーション・シェアリング・イン・オートマトン・ベースド・パーシング（GrammarCompactionandComputationSharinginAutomaton−basedParsing）」と題する論文（以下「文献３」という）には、単語に関連付けられた構文木の葉の非終端記号の列を受理する有限オートマトンを構成し、同じ単語に付随するこれらの有限オートマトンのマージと最小化を行うことにより、解析を効率化する手法が示されている。
【０００６】
この方法では、上記文献３の第3．4節に述べられているように、構文木自体ではなく、その葉（leaf）の列を抽出し一列に並べた、フラットな非終端記号列（non-terminalsymbols）を処理対象としている。
【０００７】
この列を受理する有限オートマトンを構文木ごとに一つずつ作成し、マージ・最小化することにより、複数の木に共通の解析処理を共通化して処理の効率化を図るというものである。
【発明の開示】
【発明が解決しようとする課題】
【０００８】
しかしながら、上記した各文献等に記載された語彙化文法の解析装置には、取り扱える文法形式がシステム全体を通じて固定であり、柔軟な文法記述が難しい、という問題点を有している。
【０００９】
例えば、上記文献１に記載される解析装置では、解析可能な文法形式は、文脈自由文法（contextfreegrammar）に限定されている。このことは、文法を語彙化文脈自由文法に変換してから解析を進めるという構成からも明らかである。
【００１０】
ところで、よく知られているように、文脈自由文法には、語順の任意性を簡潔に表現できない、という問題がある。
【００１１】
例えば日本語では、「私が夕食をゆっくり食べた」も、「夕食をゆっくり私が食べた」も正しい文であり、解析に成功しなければならない。
【００１２】
日本語では、一般に、「が」格、「を」格のような動詞の格要素、および「ゆっくり」のような任意修飾要素の語順は自由であり、どのような順序で現れることもある。
【００１３】
ところが、文脈自由文法では、ルール右辺の構成要素の語順は固定であるため、このような語順の自由性（任意性）を簡潔に表現することはできず、すべての語順の可能性を、あらかじめルールとして展開しておかなければならない。
【００１４】
同様に、上記文献２に記載される解析装置においても、解析可能な文法形式は、依存文法に限定されている。
【００１５】
また上記文献３に記載される解析装置では、対象となる文法形式は特に限定されない旨の記述があるものの、しかしながら、構文木の葉の非終端記号の列を受理する有限オートマトンを構成するという構成によれば、上記文献３の手法が適用可能な文法形式が限定されるものであることは明らかである。これは、非終端記号の列に対して制約を設けているためである。具体的には、この列を有限オートマトンで受理するという構成をとっているため、構文解析を終えた後、ある単語をヘッドとする構文木が持つ葉の非終端記号列として許容されるのは、有限オートマトンで受理可能な文法形式相当にほぼ限定される。
【００１６】
また、構文解析においては、従来より、動的計画法に基づき、解析順序を制御することにより、部分解を共有し、解析の効率化を図ることが、一般に行われるが、単語に解析順序を制御するオートマトンを有する上記文献２および３の構成では、これら二つの解析順序の制御をどのように統合して、動的計画法に基づく効率的解析を可能とするかについての記載はなく、不明である。
【００１７】
したがって本発明は、上記問題点に鑑みてなされたものであって、その目的は、単語ごとに付随する文法のクラスが実質的に異なるような語彙化文法をも取り扱える言語解析装置及び方法を提供することにある。
【００１８】
本発明の別の目的は、特定の文法形式の制約にとらわれることなく一般の語彙化文法の記述と受理を可能とするとともに、動的計画法に基づく効率的な解析の全体制御を可能とする言語解析装置及び方法を提供することにある。これ以外の本発明の他の目的、特徴等は以下の説明で容易に明らかとされるであろう。
【課題を解決するための手段】
【００１９】
前記目的を達成するため本発明の言語解析装置は、辞書中の単語が、その単語に関連付けられた構文木の集合と、構文木集合に属する構文木の並びが作る構文木列を受理する構文木列受理手段を有するように構成された辞書と、前記構文木列受理手段を用いて入力文の解析を進める解析手段とを備える。
本発明に係る方法は、辞書内の単語が、該単語に関連付けされる構文木の集合と、前記構文木の集合に属する構文木の並びが作る構文木列を受理する構文木列受理部と、を備えてなる辞書を備え、入力手段から入力された文を解析する際に、（ａ）前記辞書中の単語ごとに、該単語に関連付けされる構文木の成立をチェックするステップと、（ｂ）前記辞書中の単語ごとに、前記ステップ（ａ）で成立した前記構文木の作る構文木列の中から統語的に許されるものを受理するステップと、（ｃ）前記ステップ（ａ）及び（ｂ）を動的計画法による制御に基づき繰り返すステップと、を含む。
【発明の効果】
【００２０】
以上説明したように、本発明によれば、文法形式を実質的に支配する、構文木の組み合わせ方に関する情報を、構文木列受理部として、単語ごとに持つように構成したため、その単語が従う実質的な文法形式を単語ごとに柔軟に変更することができ、このため、個々の単語の振る舞いに応じた、柔軟で簡潔な文法記述を行うことができる、という効果を奏する。
一般に、記述能力の高い文法形式は、受理に必要な計算量が多く、実用の観点から問題が多いが、本発明によれば、そのような受理部が置かれ、実際に処理が行われるのは、真にその記述能力を必要とする少数の単語に留まる。
多くの一般的な単語においては、処理の軽い受理処理を行えば十分であり、本発明によれば、実際に、このような構成とすることができるので、実際の計算量は、従来のシステムのようにすべてを一つの文法形式で統一する構成と比べて、はるかに縮減することができることが期待される。
さらに、本発明によれば、こ特定の文法形式にとらわれない柔軟な文法記述を可能とするとともに、文脈自由文法と同様、動的計画法に基づく、効率的な解析の制御を可能としている、という効果を奏する。
本発明の上記効果は、構文木自体の成立のチェックと、構文木列の受理のチェックを分離したことによるものであり、上記効果は、従来システムでは得られなかったものである。
【発明を実施するための最良の形態】
【００２１】
本発明の実施の形態について説明する。本発明の実施の形態においては、辞書内の単語が、該単語に関連付けられた構文木の集合と、構文木集合に属する構文木の並びが作る構文木列を受理する構文木列受理部と、単語情報を有する単語辞書を備え、入力文の解析を進める解析部は、単語に対応する構文木列受理部を用いて解析を実行する。
【００２２】
このように、本発明の実施の形態においては、構文木だけでなく、構文木の組み合わせを制御する構文木列受理部を、単語ごとに備えたことにより、単語を中心としたまとめあげに最も適切な文法形式を選択して用いることができる。
【００２３】
例えば、日本語の動詞の格要素と自由修飾要素の取り込みについては、語順の自由性が簡潔に記述できる文法形式を採用し、動詞構文木列受理部として実装する一方、名詞への前置修飾のように、語順が固定の場合に対して、単純な文脈自由文法を採用して構文木列受理部として実装することも容易である。
【００２４】
また、本発明の実施の形態においては、一つの構文木にまとめあげる処理と、構文木間の組み合わせ処理が、別のオートマトンで制御される構成とされており、動的計画法に基づき、解析順序を制御することにより、効率的に解析を進めることができ、且つ、部分解から全体の解として最適な解を得ることができる。
【００２５】
具体的には、一つの構文木がまとめあがった段階で、構文木列受理部の状態をインデックスとする部分解としてチャートに登録し、インデックスを同じくする部分解をパックする（詰め合わせる）ことにより、部分解の共有と動的計画法に基づく解析順序制御とを矛盾なく進めることができる。
【００２６】
さらに、本発明の実施の形態においては、辞書中の単語に関連付けられた構文木が、構文木列受理部の終状態列を受理するオートマトンとして構成されており、構文木列受理部が、オートマトンとして構成された前記構文木の終状態列を受理するオートマトンとして構成されている。
【００２７】
かかる構成により、構文木を、任意のオートマトンとして構成することができ、柔軟な文法記述を行うことができる。
【００２８】
以下では、本発明の実施の形態について図面を参照してより詳細に説明する。
【００２９】
図１は、本発明の第１の実施の形態の構成を示す図である。図１を参照すると、この自然言語解析装置は、原文を入力する入力部１と、辞書2と、辞書２を参照しながら原文の解析を進める解析部３と、部分解析結果を登録するチャート４と、解析結果を出力する出力部５とを備えて構成されている。
【００３０】
図２は、辞書２の内容の一例を示す図である。図２を参照すると、辞書２の中の単語は、構文木の集合を格納する構文木プール２１と、文法で許容される構文木の列を受理する構文木列受理部２２と、単語の綴りや統語的性質等の単語情報２３とを備えて構成されている。
【００３１】
図３は、本発明の第１の実施の形態の動作を説明するための流れ図である。図１乃至図３を参照して、本発明の第１の実施の形態の動作について説明する。
【００３２】
入力部１に入力された原文が解析部３に送られると（ステップ3‐1）、解析部３は辞書２を参照して、原文を単語に分割し、各単語の辞書の内容を辞書２からロードして、チャート４に登録する（ステップ3‐2）。
【００３３】
原文の解析は、解析部３の制御に基づき、チャート４の上で、動的計画法に従って、すべての部分区間の間に包含関係により、線形順序を付け、部分区間に対する部分解析結果をすべて求める処理を、小さな区間から大きな区間へと注目する区間を動かしながら繰り返して行われる。
【００３４】
具体的には、包含関係による線形順序に従って、未処理区間を一つ選ぶ（ステップ3‐3）。そのような区間が残っていれば（ステップ3‐4でYes）、この区間の部分解をすべて求め（ステップ3‐5）、区間の選択の処理（ステップ3‐3）に戻る。
【００３５】
すべての区間に対する部分解が求まり、未処理区間がなくなったら（ステップ3‐4でNo）、全体の区間を張る部分解を解析結果として、出力部５に送る（ステップ3‐6）。
【００３６】
出力部５は、送られてきた解析結果を外部に出力する（ステップ3‐7）。
【００３７】
図４は、図３のステップ３−５の処理の詳細を示す流れ図である。図４を参照して、ある区間に対する部分解をすべて求める処理（ステップ3‐５）の詳細について説明する。
【００３８】
まず、処理済みの区間に含まれない単語に注目する（ステップ4‐1）。そのような単語が選べない場合（ステップ4−2でNo）、処理を終了する。
【００３９】
処理済みの区間に含まれない単語が選択できた場合（ステップ4−2でYes）、当該単語の処理を開始する。
【００４０】
まず、この単語の構文木列受理部の状態を調べ、次に受理できる構文木を一つ選ぶ（ステップ4‐3）。
【００４１】
次に受理できる構文木が選択できた場合（ステップ4−3でYes）、構文木が成立するかどうかチェックする。
【００４２】
構文木の葉は、単語の構文木列受理部の終状態に対応しており、構文木自身は、チャート４上に登録されている終状態列を受理するオートマトンとして実装されている。
【００４３】
構文木が成立するかどうかは、このオートマトンが終状態に到達するか否かで判定される。
【００４４】
ステップ4−5では、選択された構文木のオートマトンを起動して、葉に対応する終状態列の受理を試みる。
【００４５】
オートマトンが終状態に到達した場合（ステップ4−6でYes）、構文木列受理部は、その構文木を受理して、構文木列受理部の新しい状態を持つエッジを新たにチャート４に登録し（ステップ4−8）、元の単語において受理可能な別の構文木を選択する処理（ステップ4−3）に戻る。一般に、ある状態で受理可能な構文木は一つとは限らないためである。
【００４６】
一方、受理できなかった場合（ステップ4−6でNo）、受理できなかった理由を分析し、今後解析が進み、新たなエッジが作成されてくると受理可能な状態になり得るか否かを判定する（ステップ4−7）。
【００４７】
今後受理できる可能性があると判定された場合（ステップ4−7でYes）、中途まで状態遷移が進んだ構文木オートマトンを、活性エッジとして、チャート４に登録する（ステップ4−9）。
【００４８】
一方、今後とも成立の見込みがないと判定された場合（ステップ4−7でNo）、受理可能な他の構文木を選択する処理（ステップ4−3）に戻る。
【００４９】
このように、構文木列受理部が次に受理可能な構文木を選択し、その構文木が本当に成立しているかどうかについて、構文木自身のオートマトンがチェックする、という二つの処理を繰り返しながら解析処理が進む。
【００５０】
構文木列受理部２２は、単純な事例では、有限オートマトンとして構成されるが、これに限らず、プッシュダウンオートマトンや、さらに複雑なオートマトンであってもよい。例えば、自由語順が扱えるように、状態遷移の集合に対して、その遷移回数を管理する補助テーブルを備えたオートマトンを用いることができる。
【００５１】
ある単語の構文木と別の単語の構文木は、構文木列受理部２２の終状態を介してのみ関わるため、内部の処理は、単語独自に決めてもよい。
【００５２】
そこで、ある単語に対しては、プッシュダウンオートマトンを用いて構文木列受理部を構成し、別の単語に対しては有限オートマトンを、さらに他の単語には異なった形式のオートマトンを用いて構文木列受理部２２を構成することができる。これは、構文木列受理部２２を、構文木自身の受理の処理から独立させ、両者ともに単語ごとに語彙化して格納するという、本発明の構成の大きな特徴であり、かつ利点でもある。
【００５３】
さらに以上の説明からも明らかなように、単語ごとのオートマトンによる構文木の受理の処理と、構文木の成立の有無のチェック処理をそれぞれ別の処理として分離しているため、構文木および構文木列受理部２２の具体的な構成にかかわらず、チャート４を利用した動的計画法の処理手順（アルゴリズム）で解析全体を統御し、部分結果を共有しながら、効率的に解析を進めることができる。
【００５４】
これは、構文木列受理部２２を、構文木自身の受理の処理から独立させた本発明の構成によりはじめて可能となったものであり、本発明の大きな特徴であり、利点でもある。
【００５５】
図５は、本発明の第２の実施の形態を説明する図である。図５を参照すると、本発明の第３の実施の形態は、入力装置１０１と、コンピュータから構成されるデータ処理装置１０２と、出力装置１０３と、記憶装置１０４と、自然言語解析プログラムを記録した記憶媒体１０５とを備える。記録媒体１０５は、磁気ディスク、磁気テープ、光ディスク、半導体メモリその他の記録媒体よりなる。
【００５６】
自然言語解析プログラムは、記録媒体１０５からデータ処理装置１０２の主記憶装置に読み込まれ、データ処理装置１０２の動作を制御する。データ処理装置１０２は、自然言語解析プログラムの制御により以下の処理を行う。
【００５７】
入力文が入力装置１０１から読み込まれると、解析部１０３が起動される。解析部１０３は辞書１０２を参照して、文中の単語を認定し、対応する単語辞書をロードしてチャート４に登録する。
【００５８】
チャート４に入力文中のすべての単語の辞書が登録されたら、解析部１０３は、動的計画法に基づく制御に従って、解析を開始する。解析部１０３は、制御戦略に従って注目単語を一つ決め、該単語中の構文木列受理部２２を起動する。
【００５９】
構文木列受理部２２は、次に受理可能な構文木を一つ決め、その構文木がチャート４上で成立するかどうかのチェックを開始する。構文木の葉は単語の構文木列受理部の終状態として表現されているので、注目している構文木の葉に対応する終状態がその順序で並んでいれば、その構文木はチャート４上で成立する。
【００６０】
成立した場合には、構文木列受理部２２はその構文木を受理する。
【００６１】
構文木を受理したら、受理した構文木の下部構造を構造化し、対応するチャート４の区間にその単語を登録する。
【００６２】
さらに、次に受理可能な構文木を一つ選んでその構文木に対して成立条件のチェックを開始する。構文木の成立条件が満たされなかった場合は、状況により処理が二つに分かれる。解析処理が進んで他の単語の構文木列受理部２２が新たに終状態に到達すれば成立条件が満たされるようになる可能性がある場合には、解析中途の活性エッジとしてチャート４上に登録する。そのような可能性がない場合には条件チェックは失敗とする。
【００６３】
こうして解析を進め、全体を張るエッジで、構文木列受理部２２が終状態にあるものが得られれば、そのエッジが解析結果として出力部１０３から出力される。
［実施例］
【００６４】
次に本発明の実施例について図面を参照して説明する。
【００６５】
図６は、本発明を、英語（英文）の構文解析装置に適用した第１の実施例の構成を示す図である。図６を参照すると、演算処理を行うＣＰＵ７と、辞書等を格納する記憶装置８と、原文を入力するキーボード９と、キーボード９からＣＰＵ７に原文を取り込む入力部１と、記憶装置内に格納された辞書２と、解析の途中結果を記録するチャート４と、辞書２を参照して入力文を辞書引きしチャート４に登録する辞書ローダ６と、解析処理の全体制御を行う解析制御部３と、解析結果をＣＰＵ７の外部に出力する出力部５と、出力結果を表示するＣＲＴ又はＬＣＤ等のディスプレイ装置１０と、を備えて構成されている。
【００６６】
さらに、辞書２中の各々の単語の辞書は、図６に示すように、構文木プール２１と、文法的に正しい構文木列を受理する構文木列受理部２２と、単語の統語的性質をはじめとする各種の情報である単語情報２３とを備えて構成されている。各構成要素の間は、データ線・制御線（通信線）を介して接続されている。
【００６７】
図７は、本発明の第１の実施例における単語“eats”の辞書２の内容の一部を示す図である。３人称単数現在形の動詞“eats”の構文木プール２１には、自身に直接関わる構文木として、直接目的語の取り込みをあらわす構文木7a、副詞や前置詞句による後方自由修飾をあらわす構文木7b、主語の取り込みをあらわす構文木7cが登録されている。構文木プール２１に含まれている、単語“eats”に関連付けられた構文木7a、7b、7cは、いずれも、深さ（レベル）１の構文木（素片）よりなる。
【００６８】
こららの構文木は、ルート（root）ノードとその子供のノードの一つがselfとして特別にマークされている。
【００６９】
構文木が二つ与えられたときには、二つの構文木におけるselfのノード（一方はルートノード、他方は葉のノード）を互いに重ね合わせることで、これら二つの構文木を連結する。
【００７０】
あるいは、構文木のselfノードの位置に単語自身が現れてもよい。
【００７１】
これらの構文木7a、7b、7cが、連結されて大きな構文木となったとき、ルートのselfのノードからselfのノードを下方に辿り、単語自身に終わるパスは、その単語をヘッドとする構文木の背骨(spine)であることに注意されたい。
【００７２】
構文木の他の葉のノードにあらわれるsubjectやdobといった記号は、他の単語の構文木列受理部の終状態に対応する。
【００７３】
構文木は、selfの左右に指定された終状態を持つ単語（すなわちチャート上のエッジ）が表れることで、成立可能となる。
【００７４】
例えば、構文木7aは、自分の直後に、終状態dob（直接目的語の意味）に到達した構文木列受理部を持つエッジがあらわれた場合に限り、成立する。
【００７５】
構文木7bは、selfの直後に終状態postmod（後置任意修飾要素の意味）があらわれた場合に、成立条件を満たす。
【００７６】
これらの構文木は、構文木列受理部の終状態を入力として状態遷移を行うオートマトンとして実装されている。
【００７７】
また、構文木列受理部２２は、これら３つの構文木の列のうち、列7a・7b*・7cのみを受理するように構成されている。
【００７８】
ここで、記号「・」は構文木の連結をあらわし、「＊」は任意回数の繰り返しを表している。
【００７９】
すなわち、列7a・7b*・7cを受理する構文木列受理部２２は、まず、構文木7aを受理し、次に構文木7bを０回以上任意回数繰り返して受理し、最後に、構文木7cを受理して終状態に至るように構成されている。
【００８０】
構文木列は、上述のselfを媒介として連結することにより、大きな構文木と同一視される。
【００８１】
例えば、列7a・7b*・7cに対応する構文木を表わすと、図８に示すような構文木となる。
【００８２】
言い換えれば、“eats”の構文木列受理部２２は、図８に示す構文木を受理するように構成されており、これら二つの表現は等価である。
【００８３】
図９は、本発明の第１の実施例における単語“he”の辞書内容の一部を表す図である。“he”の構文木プールは空であり、構文木列受理部２２は始状態から終状態subjectへと空（ε）の入力で遷移する。単語情報には、綴り：“he”、原型：“he”、品詞：pronounが格納される。
【００８４】
図１０は、本発明の第１の実施例における単語“dinner”の辞書内容の一部を示す図である。“dinner”の構文木プールは、形容詞前置修飾をあらわすTd1、名詞前置修飾をあらわすTd2、限定詞による修飾をあらわすTd3、前置詞句による後置修飾をあらわすTd4からなり、構文木列受理部は、構文木列(Td1|Td2)*Td3*{Td4}を受理するように構成されている。
【００８５】
ここで、記号「｜」はオア、｛｝は省略可能であることをあらわす。
【００８６】
すなわち、構文木列受理部は、形容詞前置修飾の構文木Td1または名詞前置修飾の構文木Td2を任意回受理した後、限定詞句による修飾の構文木Ｔd3を任意回受理し、最後に前置詞句による後置修飾の構文木Td4を０ないし１回受理して終状態に至る。
【００８７】
終状態は、subject、dob、prepobjの重ね合わせである。
【００８８】
次に本発明の第１の実施例の解析処理について、具体的に説明する。
【００８９】
文“Heeatsdinner”がキーボード９から入力されると、ＣＰＵ７が起動され、通信線を介して入力部１に入力される。
【００９０】
入力部１は、キーボード９からの入力をＣＰＵ７が理解可能な形式に変換し、通信線を介して辞書ローダ６に送る。
【００９１】
辞書ローダ６は、記憶装置８に格納された辞書２を参照して、入力文中の単語境界を認定し、各単語の辞書内容をロードし、通信線を介してチャート４に送る。
【００９２】
チャート４は、単語単位に、その辞書内容をチャート４の上に登録する。
【００９３】
図１１は、辞書ロード直後のチャート４の様子を示す図である。
【００９４】
チャート４の先頭を位置０、末尾を位置３として、“he”が位置０から１に(e1)、“eats”が位置１から２に(e2)、“dinner”が位置２から３に(e3)登録されている。各単語には、図１１に示すように、各々始状態にある構文木列受理部が付随している。以下、オートマトンの状態を囲む二重線は、その状態が現在の状態であることを示すものとする。なお、図１１では、簡単のため、構文木プールと単語情報は省略したが、これらも構文木列受理部と同様に単語に付随している。
【００９５】
チャート４への登録が終了したら、解析部３が起動される。
【００９６】
解析処理は、解析部３の制御の下に、基本的には、左から右方向への文脈自由文法のボトムアップチャート法と同様に行われる。
【００９７】
また解析すべき部分区間を選択する順序や、活性エッジと非活性エッジを使って解析を進めることは文脈自由文法の場合と同じである。しかし、文脈自由文法の場合には、チャートの部分区間に登録される部分解析結果は非終端記号により区別されるのに対し、本発明では、単語の構文木列受理部のオートマトンの状態により区別される。
【００９８】
さらに、部分解析結果（非活性エッジ）に対して、次に適用可能な文法規則が、非終端記号の一致を条件にグローバルな文法規則のプールから選択されるのではなく、そのエッジに付随する構文木列受理部のオートマトンにより決定される。
【００９９】
まず、先頭の未処理区間[0,1]に対し、この区間のすべての部分解を求める。
【０１００】
そのために、この区間に存在する単語“he”に注目し、単語“he”の構文木列受理部を起動する。
【０１０１】
上述したように、“he”の構文木列受理部は、空（ε）の構文木入力で終状態へと遷移するので、構文木の成立チェックを行うことなく、オートマトンが終状態subjectに到達する。
【０１０２】
構文木列受理部の終状態は、受理を終えたエッジがどのような文法機能を持てるかによって名前が付けられており、subjectは、この終状態を持つエッジが主語としての文法機能を果たすことができることをあらわす。
【０１０３】
こうして、構文木列の受理が終了したので、構文木列受理部が終状態にあるエッジを新規に作成して区間[0,1]に登録する(e4)。
【０１０４】
この新規エッジは、構文木列受理部が終状態にある以外は、辞書ロード直後の“he”と同じ情報を持つ。
【０１０５】
区間[0,1]ではこれ以上解析は進まないので、解析部３は注目区間を[1,2]に移し、この区間の全部分解を求める処理を開始する。
【０１０６】
区間[1,2]には、唯一の単語“eats”（正確にはエッジe2）があるので、まず単語“eats”の構文木列受理部が起動される。
【０１０７】
単語“eats”の構文木列受理部は、構文木列7a・7b*・7cを受理するように構成されており、始状態の直後に受理可能な構文木は7aしかないので、まず構文木7aが成立するかどうかのチェックを行う。
【０１０８】
構文木7aの成立条件は、自分（self）の右に終状態dobを持つエッジが存在することである。しかし、この時点では、このようなエッジは登録されていないので、構文木7aは成立しない。しかし、今後右方に解析が進めば、このようなエッジが新規に登録される可能性があるので、解析部３は、構文木7aから次にマッチングすべき終状態がdobである旨の活性エッジを作成し、区間[1,2]に登録する。
【０１０９】
次に、解析部３は、注目区間を[0,2]とし、この区間に存在するすべての部分解析結果を求めようとするが、この区間内部に新たに成立する構文木はないので、次のステップに進む。
【０１１０】
解析部３は、注目区間を[2,3]とし、この区間に存在するすべての部分解析結果を求める。この区間の唯一の単語“dinner”（正確にはエッジe3）に焦点を移し、構文木の受理を開始する。
【０１１１】
e3の構文木列受理部は、(Td1|Td2)*Td3*{Td4}を受理するように構成された有限オートマトンである。
【０１１２】
最初に受理可能な構文木としては、Td1、Td2、Td3、Td4のいずれも許されるが、これらの中で成立可能な状況にあるものは一つもない。
【０１１３】
一方、構文木列受理部は空の構文木を受理して終状態に移行することも可能であり、これによって終状態（dob|sub|prepobj）に遷移する。
【０１１４】
この終状態は、sub、dob、prepobjの重ね合わせとしての状態を持ち、直接目的語、主語、前置詞の目的語としての文法機能を持つことが表現されている。この終状態を持ったエッジがエッジe5として区間[2,3]に登録される。
【０１１５】
区間[2,3]の処理が終わると、新しく部分解析結果が登録されたので、コンプリーション処理に移る。
【０１１６】
コンプリーション処理は、新たに登録されたエッジが、以前登録された活性エッジとマッチング可能かどうかをチェックし、マッチング可能な場合には、新たにエッジを作成する。
【０１１７】
ここでは、区間[1,2]に構文木7aから作られた活性エッジが登録されており、dobの終状態を待っているので、解析部３は、7aの構文木のオートマトンを再起動する。このオートマトンは、dobの終状態を持つエッジe5を受理することにより、構文木自身の終状態に到達する。
【０１１８】
その結果、構文木7aが受理され、解析部３は、“eats”の構文木列受理部の状態を一つ進めたエッジe6をチャート４に登録する。その内容は、基本的に“eats”の単語と同じで、構文木列受理部の状態が、構文木7aの受理直後の状態であり、次に受理する構文木は7b又は7cである点だけが異なる。図１２は、この時点のチャートの状態を示す図である。
【０１１９】
次に、解析部３は、区間[1,3]の処理に入る。この区間には、直前のコンプリーション処理で登録されたエッジe6が登録されているので、これに焦点を移し、構文木列受理部を起動して、次の構文木が受理できるか否かチェックを開始する。
【０１２０】
e6において、次に受理可能な構文木は7b又は7cである。構文木7bは右方に自由修飾要素である終状態postmodをもつ単語があれば成立条件を満たし、7cは左方にsubjの終状態に達した単語があれば成立条件を満たす。ここでは、直前に終状態subjectを持つエッジe4が存在するため、構文木7cの成立条件が満たされて、これを受理して、区間[0,3]に新たなエッジe7が登録される。
【０１２１】
e7の構文木列受理部は終状態(sentence)にある。図１３は、この状態のチャートを示す図である。
【０１２２】
図１３に示す構文木は、e2にはじまり、e7に至る過程で“eats”に付随する構文木列受理部が受理した構文木の列から組み上げたものである。
【０１２３】
こうして、チャートの全区間を張り、構文木列受理部が終状態に達したエッジが作成されたので、構文解析に成功したことになる。解は、このエッジが受理した構文木列である。
【０１２４】
前述したように、構文木列は、selfのノードを重ね合わせて一つの構文木としてまとめあげることができ、こうして作られる構文木は解と等価である。図１３には後者の形で示してある。
【０１２５】
出力部５は、この構文木を受け取って、ディスプレイ装置１０の画面に表示可能な形へとデータ形式の変換を行う。変換結果をディスプレイ装置１０に通信線を介して送付すると、ディスプレイ装置１０が受け取った結果をユーザに表示し、解析処理が終了する。
【０１２６】
なお、上記の例では表れなかったが、同じ区間に、以後の解析処理に関わる情報が同じエッジが登録された場合には、これらをパックすることにより、動的計画法の利点を活かした効率的な解析を進めることができる。
【０１２７】
ここで、「以後の解析処理に関わる情報が同じ」とは、エッジに付随する構文木列受理オートマトンが、現在の状態を含めて全く同じであることをいう。すなわち、エッジの登録の際に、自分と等価な構文木列受理オートマトンを持ち、その状態が自分と等価であるエッジがすでに同じ区間に登録されている場合には、チャートに登録するのをやめて、既登録のエッジにパックして登録し、以後の解析処理を共通化することにより、文脈自由文法の場合によく知られたチャート法やＣＫＹ法など、動的計画法に基づく効率的な解析アルゴリズムをそのまま流用できる。異なるのは、文脈自由文法の場合は、この条件が非終端記号の一致により判定されるのに対し、本発明では、これを構文木列受理オートマトンの状態の一致により判定する点のみである。これは、本発明の言語解析装置が、文脈自由文法にとどまらず、はるかに広い範囲の文法形式を受理できることを考えると、本発明の大きな特徴である。
【０１２８】
図１４は、本発明を実施して、日本語の解析装置を構成した第２の実施例における単語辞書の内容を示す図である。本発明の第２の実施例の構成は、前記第１の実施例と同様とされ、図６を参照すると、演算処理を行うＣＰＵ７と、辞書等を格納する記憶装置８と、原文を入力するキーボード９と、キーボード９からＣＰＵ７に原文を取り込む入力部１と、記憶装置内に格納された辞書２と、解析の途中結果を記録するチャート４と、辞書２を参照して入力文を辞書引きしてチャート４に登録する辞書ローダ６と、解析処理の全体制御を行う解析部３と、解析結果をＣＰＵ７の外部に出力する出力部5と、出力結果を表示するディスプレイ装置１０と、を備えて構成されている。
【０１２９】
さらに、辞書２中の各々の単語の辞書は、構文木プール２１と、文法的に正しい構文木列を受理する構文木列受理部２２と、単語の統語的性質をはじめとする各種の情報である単語情報２３とを備えて構成されている。各構成要素の間は、通信線を介して接続されている。
【０１３０】
本発明の第２の実施例においては、解析装置を日本語の解析装置として実施するために、単語辞書内容を、図１４に示すように、日本語のものに変更した点が前記第１の実施例と相違している。単に言語を変えただけでなく、日本語の解析に適するように構文木列受理部のオートマトンの構成を変更している。以下、こ本発明の第２の実施例について、図１４を参照して説明する。
【０１３１】
図１４には、動詞「食べる」の辞書内容の一部が示されている。構文木プールは、前方の連用要素を取り込む構文木であるTdただ一つからなる。
【０１３２】
「食べる」が「〜が〜を食べる」の必須格パターンを持つことは、構文木としてではなく、構文木列受理部内に設けられた補助テーブル（受理回数制約テーブル）に表現されている。
【０１３３】
構文木列受理部は、骨格を成す有限オートマトンと、受理回数制約テーブルの状態の積を状態とするオートマトンである。有限オートマトンの側でTdを受理するたびに、受理回数制約テーブルの対応する「回数」の欄がインクリメントされていく。
【０１３４】
「回数」の欄が、「回数制約」の欄の制約を満たさなくなると、受理失敗として終了する。
【０１３５】
この仕組みにより、単語「食べる」が、助詞「が」を一回、助詞「を」を一回、他の任意修飾要素を任意回、任意の順番で取り込むことができる、という構造制約を簡潔な形で表現することができる。
【０１３６】
一方、例えば名詞と助詞の連接や、助動詞が動詞を取り込むという現象のように、語順が固定されている文法現象の記述には、英語の場合と同様、複数の構文木の受理の順序を有限オートマトンで表現することが自然であり、本発明の第２の実施例でも、これに従う。このように、単語に関わる文法現象の性質に応じて、最も適切な文法形式を単語単位に採用することができることは、本発明の大きな特徴である。
【０１３７】
語順の自由性を許す語彙化文法形式として、従来、いくつかの形式が提案されている。例えば、1994年、米国ペンシルベニア州立大学計算機科学科に提出された博士論文「フォーマル・アンド・コンピューテーショナル・アスペクツ・オブ・ナチュラル・ランゲージ・シンタックス」(FormalandComputationalAspectsofNaturalLanguageSyntax,PhDdissertationtoUniverstiyofPennsylvania,USA.1994)（「文献５」という）を参照されたい。
【０１３８】
その中に一例として挙がっているUVG−DL(UnorderedVectorGrammarwithDominanceLinks)は、複数の構文木を組（ベクトル）にしたものを単位とするベクトル文法であり、構文木の間に支配関係リンク(dominancelink)が与えられているのが特徴である。
【０１３９】
この文法では、一つの組の中の構文木は同じ回数だけ使われること、および、支配関係リンクで結ばれた構文木は、これと矛盾しない形で先祖・子孫の関係（構文木の上での上位下位関係）になければならない、という制約を満たさなければならない。
【０１４０】
この形式を少し修正すれば、例えば日本語の動詞格要素の自由語順を簡潔に表現することは容易である。しかし、このような表現形式は、特に、日本語やドイツ語の格要素の振る舞いの記述に適合するように決められたものであり、その他の語の振る舞いの記述に対しては、必ずしも適切とは言えない。文法形式全体を、ある特定の文法現象の記述が容易になるように選択すると、他の現象の記述に対して適切でなくなるのは当然のことである。
【０１４１】
これに対して、本発明では、構文木列受理部を単語ごとに持つことにより、該単語が従う実質的な文法形式を、単語ごとに、柔軟且つ容易に、変更することができる。
【０１４２】
本発明の第２の実施例では、動詞の文法を、適用回数制約テーブルで拡張した有限状態オートマトンにより実装したが、これを例えばUVG−DLで実装してもよい。他の語との関係は、構文木列受理部の終状態のシンボルを通じてのみ発生するので、終状態に至るまでにどのような処理が行われようと、影響はその単語に閉じている。
【０１４３】
さらに、前記第１の実施例で説明したように、構文木の成立のチェック（構文木オートマトンによる終状態の受理処理）と、構文木列の受理処理とを分離することにより、構文木列受理部の実装にかかわわらず、チャート等を使用した動的計画法に基づく効率的な解析を行うことができることも、本発明の特徴である。
【０１４４】
本発明の第３の実施例について説明する。図１５は、本発明の第３の実施例を説明するための図である。図３に示すD−TreeGrammarと同等な解析を行う場合について説明する。
【０１４５】
D−TreeGrammarsの詳細については、1995年、インターナショナル・ワークショップ・オン・パーシング・テクノロジーズ(InternationalWorkshoponParsingTechnologies)で発表された「パーシング・ディー・ツリー・グラマーズ」(ParsingD−TreeGrammars)（「文献５」という）の記載が参照される。
【０１４６】
図１５に示す構文木は、Sの間、およびVPの間のリンクが点線で表現されている。これは、このリンクが長さ１の固定リンクではなく、０以上任意の数の構文木が間に割って入ることを許すことを表現している。ただし、割って入った構文木が、この構文木と連結される二つのノードにおいて、その品詞は（割って入った位置に応じて）SまたはVPでなければならない。
【０１４７】
このような表現は、WH移動等の遠距離依存現象や、“sothat”等の呼応を表現するのに有用である。
【０１４８】
本発明では、構文木プールを少し拡張してプッシュダウンスタック中に構文木を格納し伝播させることで、同じことを実現できる。
【０１４９】
図１６は、図１５を実現するための単語辞書の内容である。この内容が、図１５で最下部にあるVに対応する単語の辞書中に記述されている。
【０１５０】
構文木プールには、図１５の最下部の木T1だけが構文木プールに入っており、その他の、破線より上の二つの部分の木は、プッシュダウンスタックに格納されている。また、構文木列受理部は、T1を一回だけ受理したら終状態に遷移するように構成されている。
【０１５１】
構文木列受理部が終状態に到達したら、構文木プールからプッシュダウンスタックが取り出され、終状態に関連付けられる。この状態で、構文木列受理部は、受理を継続する形で、スタックから構文木を取り出して受理を試みてもよいし、そのまま自分を子供として取り込んだ構文木列受理部に渡してもよい。ただし、いずれも、取り出した構文木の非終端記号が終状態のシンボルと一致することを条件とする。後者の場合、スタックが上方へ伝播していき、どこかの時点でスタック中の構文木の受理が試みられることになる。
【０１５２】
図１７は、この様子を模式的にあらわしたものであり、最下部のVPが別の構文木の子供となって成長していった（太い鎖線）後、スタック中の上位の構文木がポップされて受理される様子を表している。
【０１５３】
このように、本発明の構成において、構文木をスタックに入れて伝播させ、後の処理で、構文木列の受理処理が終わった時点においてこれをポップし、受理処理を行うことにより、図１５で表現されているような、遠距離における支配関係を容易に処理することができる。
【０１５４】
なお、ここでは、スタックにプッシュするのは単独の構文木としたが、一般には、構文木プールと構文木列受理部の組を単位としてスタックにプッシュするように拡張できる。
【０１５５】
また、図１８は、“so(adjective)that(sentence)”の呼応関係の処理を説明するための図である。原文が、“Sheissokindthateverybodylikesher．”のとき、“so”の辞書に、“that”節以下をまとめあげる構文木（図１８(b)）を持たせ、これを図１８(a)の構文木上で矢印で示すように伝播させ、全体がsentenceとしてまとめあがった時点で受理を起動することにより、正しく“that”節以下をまとめあげることができる。
【０１５６】
“So”と“that”節の呼応関係は、“that”節の構文木の起源から明らかである。
【０１５７】
なお、一般に、文脈自由文法が与えられたとき、以下の手順により、元の文法と強同値になるように、本発明による解析装置を構成することができることを注意しておく。
【０１５８】
まず、各単語に対して、その単語に付随する構文木プールを以下のように構成する。
【０１５９】
単語を固定（FIX）した時、プレターミナルからその単語を導く規則はすべて構文木プールに入れる。その際、仮に、規則のルートに、プレターミナルシンボルにあわせて記号selfを与えておく。
【０１６０】
次に、構文木プール中の規則のルートとなっている非終端記号に対し、その記号を葉に持つすべての規則を集め、構文木プールに追加する。ただし、注目した葉とルートに、仮に記号selfを与えておく。同じ規則でも、注目した葉が異なれば、selfの位置が異なるので、別の規則として追加する。
【０１６１】
構文木プール中の規則のルートとなっている非終端記号に対し、この追加作業を規則の追加が止まるまで繰り返す。これで、構文木プールの作成が終了する。
【０１６２】
構文木列受理部は、以下のように構成される非決定性有限状態オートマトンである。構文木プール中の規則のルートとなっている非終端記号の各々が状態となる。始状態からは、プレターミナルに対応する状態に遷移可能とし、各遷移において、遷移先のプレターミナルから単語を生成する規則が受理されるように構成する。
【０１６３】
さらに、状態１から状態２への遷移においては、状態２をルート、状態１を記号selfのついたリーフとする構文木が構文木プールの中に存在するとき、この構文木を受理して遷移するように構成する。また、すべての状態から終状態へと、空の構文木を受理して遷移を可能とする。
【０１６４】
以上の構成により、元の文脈自由文法と全く同一の構文木集合を受理する本発明による解析装置が構成できる。
【０１６５】
本発明は、上記に説明した以外にも種々に変形して実施することができる。
【０１６６】
前記各実施例では、単語に記述する文法として、もっぱら構文木を単位とする句構造文法（ＰＳＧ；phrasestructuregrammar）を採用したが、依存関係による記述を採用し、依存文法形式により構文木プールの内容と構文木列受理部を構成することも容易である。この形式を単語ごとに変化させてもよい。
【０１６７】
また、構文木列受理部として、有限オートマトンではなく、プッシュダウンオートマトンを採用するように構成することも容易である。さらには、構文木列受理部に、一般のオートマトンを採用することにより、さらに記述能力の高い文法形式をアクセプトするように構成することも容易である。
【０１６８】
また、本発明に係る言語解析装置を組み込んで、翻訳装置や情報検索装置さらに音声認識等に適用することができることは勿論である。また、本発明は、自然言語の解析に限定されるものでなく、例えばコンピュータのプログラミング言語等の人工言語（形式言語）に適用することも容易であることは明らかである。
【０１６９】
以上のように、本発明は、本発明の原理に準ずる範囲内での各種変形を含む。
【図面の簡単な説明】
【０１７０】
【図１】本発明の第１の実施の形態をなす自然言語処理装置の構成を示すブロック図である。
【図２】本発明の第１の実施の形態をなす自然言語処理装置の辞書の構成を示すブロック図である。
【図３】本発明の第１の実施の形態をなす自然言語処理装置の処理を示す流れ図である。
【図４】本発明の第１の実施の形態をなす自然言語処理装置の処理を示す流れ図である。
【図５】本発明の第２の実施の形態をなす自然言語処理装置の構成を示すブロック図である。
【図６】本発明の第１の実施例をなす自然言語処理装置の構成を示すブロック図である。
【図７】本発明の第１の実施例をなす自然言語処理装置における単語辞書の構成を示すブロック図である。
【図８】本発明の第１の実施例をなす自然言語処理装置が受理する構文木の一例を示す図である。
【図９】本発明の第１の実施例をなす自然言語処理装置における単語辞書の構成を示すブロック図である。
【図１０】本発明の第１の実施例をなす自然言語処理装置におけるチャートの内容を示す図である。
【図１１】本発明の第１の実施例をなす自然言語処理装置におけるチャートの内容を示す図である。
【図１２】本発明の第１の実施例をなす自然言語処理装置におけるチャートの内容を示す図である。
【図１３】本発明の第１の実施例をなす自然言語処理装置におけるチャートの内容を示す図である。
【図１４】本発明の第２の実施例をなす自然言語処理装置における単語辞書の構成を示すブロック図である。
【図１５】本発明の第３の実施例をなす自然言語処理装置が処理可能な構文木の一例を示す図である。
【図１６】本発明の第３の実施例をなす自然言語処理装置における辞書内容の一例を示す図である。
【図１７】本発明の第３の実施例をなす自然言語処理装置の処理を説明するための図である。
【図１８】本発明の第３の実施例をなす自然言語処理装置の処理を説明するための図である。
【符号の説明】
【０１７１】
１  入力部
２  辞書
３  解析部
４  チャート
５  出力部
６  辞書ローダ
７  ＣＰＵ
８  記憶装置
９  キーボード
１０  ＣＲＴ
２１  構文木プール
２２  構文木列受理部
２３  単語情報
１０１  入力装置
１０２  データ処理装置
１０３  出力装置
１０４  記憶装置
１０５  記録媒体
【図１】
0004624338.tif 000002
【図２】
0004624338.tif 000003
【図３】
0004624338.tif 000004
【図４】
0004624338.tif 000005
【図５】
0004624338.tif 000006
【図６】
0004624338.tif 000007
【図７】
0004624338.tif 000008
【図８】
0004624338.tif 000009
【図９】
0004624338.tif 000010
【図１０】
0004624338.tif 000011
【図１１】
0004624338.tif 000012
【図１２】
0004624338.tif 000013
【図１３】
0004624338.tif 000014
【図１４】
0004624338.tif 000015
【図１５】
0004624338.tif 000016
【図１６】
0004624338.tif 000017
【図１７】
0004624338.tif 000018
【図１８】
0004624338.tif 000019