JP3339741B2 - 言語解析装置 - Google Patents
言語解析装置Info
- Publication number
- JP3339741B2 JP3339741B2 JP00210294A JP210294A JP3339741B2 JP 3339741 B2 JP3339741 B2 JP 3339741B2 JP 00210294 A JP00210294 A JP 00210294A JP 210294 A JP210294 A JP 210294A JP 3339741 B2 JP3339741 B2 JP 3339741B2
- Authority
- JP
- Japan
- Prior art keywords
- sentence
- grammar
- state
- word
- terminal
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Fee Related
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F40/00—Handling natural language data
- G06F40/20—Natural language analysis
- G06F40/253—Grammatical analysis; Style critique
Landscapes
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Health & Medical Sciences (AREA)
- Artificial Intelligence (AREA)
- Audiology, Speech & Language Pathology (AREA)
- Computational Linguistics (AREA)
- General Health & Medical Sciences (AREA)
- Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Machine Translation (AREA)
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Description
【発明の詳細な説明】
【０００１】
【産業上の利用分野】本発明は、言語解析装置に関し、
より詳細には、終端記号列に対して文脈自由文法で規定
された構成素を抽出する言語解析装置に関する。例え
ば、機械翻訳や文書検索に適用されるものである。
より詳細には、終端記号列に対して文脈自由文法で規定
された構成素を抽出する言語解析装置に関する。例え
ば、機械翻訳や文書検索に適用されるものである。
【０００２】
【従来の技術】自然言語を構文解析する場合、構文的多
義の問題がある。例えば、次の英文 Ａ of Ｂ of Ｃ に対し、英語文法にかなった構文として、次の２通りの
場合が考えられる。 （(Ａ of (Ｂ of Ｃ))) （((Ａ of Ｂ) of Ｃ)) ただし、上記では（ ）によって構成素（ここでは、構
文的なまとまりを指す）を表している。上例のように、
単一の表現に複数の構文が考えられる場合、それらを構
文的多義と呼ぶ。英文がＡ of Ｂ of Ｃ of Ｄ…のよう
に長くなるにつれ、その構文的多義の総数は急激に増大
する。したがって、その文を構文解析し、全ての構文を
得る場合、構文的多義のために、処理時間又は処理に必
要な記憶量が非常に増大してしまうという問題が生じ
る。
義の問題がある。例えば、次の英文 Ａ of Ｂ of Ｃ に対し、英語文法にかなった構文として、次の２通りの
場合が考えられる。 （(Ａ of (Ｂ of Ｃ))) （((Ａ of Ｂ) of Ｃ)) ただし、上記では（ ）によって構成素（ここでは、構
文的なまとまりを指す）を表している。上例のように、
単一の表現に複数の構文が考えられる場合、それらを構
文的多義と呼ぶ。英文がＡ of Ｂ of Ｃ of Ｄ…のよう
に長くなるにつれ、その構文的多義の総数は急激に増大
する。したがって、その文を構文解析し、全ての構文を
得る場合、構文的多義のために、処理時間又は処理に必
要な記憶量が非常に増大してしまうという問題が生じ
る。
【０００３】そこで、自然言語の文法のように、構文的
多義が発生する文法に対して、なるべく効率よく全ての
句構造を抽出する方式が従来より提案されてきた。その
一つに、次の文献で提案された方式がある。すなわち、
「Efficient Parsing for Natural Language」(M.Tomita.
Kluwer Academic Publishers, 1985, p.33)に記載され
ているこの方式は、構文的多義が生じないプログラミン
グ言語用に開発されたＬＲ法を、構文的多義を生じる自
然言語用に拡張したもので、一般化ＬＲ法と呼ばれてい
る。従来のＬＲ表を用いないアーリ法やチャート法など
と比べ、効率よく解析を行うことができる。
多義が発生する文法に対して、なるべく効率よく全ての
句構造を抽出する方式が従来より提案されてきた。その
一つに、次の文献で提案された方式がある。すなわち、
「Efficient Parsing for Natural Language」(M.Tomita.
Kluwer Academic Publishers, 1985, p.33)に記載され
ているこの方式は、構文的多義が生じないプログラミン
グ言語用に開発されたＬＲ法を、構文的多義を生じる自
然言語用に拡張したもので、一般化ＬＲ法と呼ばれてい
る。従来のＬＲ表を用いないアーリ法やチャート法など
と比べ、効率よく解析を行うことができる。
【０００４】なお、ＬＲ法については、「自然言語解析
の基礎」（田中穂積著，1989年11月27日発行，産業図
書，pp83〜104）に記載されている。このＬＲ法はスタ
ックを用い、左（先頭）から右（文末）に向けて入力文
を走査し、前記スタックの状態と先読みしたＫ語とから
得られる情報とを参照にしながらスタックに対してシフ
ト操作とレデュース操作を織り混ぜた解析を決定的に行
う。ＬＲ法のＬは文を左から右（Left-to-right）に向
けて走査することを言い、また、Ｒは最右導出（Right
most derivation）を行うことを意味している。ＬＲ法
では、与えられたＬＲ文法からＬＲ表（ＬＲパーズ表）
を予め抽出しておく。該ＬＲ表は二分されており、シフ
トの場合にどの状態に推移し、レデュースの場合にどの
規則を用いるかを書いた ACTION部と、レデュース操作
の結果としてどの状態へ推移するかを書いた GOTO部と
に分かれている。
の基礎」（田中穂積著，1989年11月27日発行，産業図
書，pp83〜104）に記載されている。このＬＲ法はスタ
ックを用い、左（先頭）から右（文末）に向けて入力文
を走査し、前記スタックの状態と先読みしたＫ語とから
得られる情報とを参照にしながらスタックに対してシフ
ト操作とレデュース操作を織り混ぜた解析を決定的に行
う。ＬＲ法のＬは文を左から右（Left-to-right）に向
けて走査することを言い、また、Ｒは最右導出（Right
most derivation）を行うことを意味している。ＬＲ法
では、与えられたＬＲ文法からＬＲ表（ＬＲパーズ表）
を予め抽出しておく。該ＬＲ表は二分されており、シフ
トの場合にどの状態に推移し、レデュースの場合にどの
規則を用いるかを書いた ACTION部と、レデュース操作
の結果としてどの状態へ推移するかを書いた GOTO部と
に分かれている。
【０００５】
【発明が解決しようとする課題】しかしながら、前述し
た従来の方式では、graph-structured stack と呼ぶデ
ータ構造を用いるため、機構が複雑になるという問題点
があった。また、このデータ構造のデータ記憶量が解析
実行時に無視できないほどに増大してしまうという問題
点があった。さらに、対象とする言語の種類によって
は、このデータ構造のデータを頻繁に生成消去すること
になり、処理時間効率が低下するという問題点があっ
た。
た従来の方式では、graph-structured stack と呼ぶデ
ータ構造を用いるため、機構が複雑になるという問題点
があった。また、このデータ構造のデータ記憶量が解析
実行時に無視できないほどに増大してしまうという問題
点があった。さらに、対象とする言語の種類によって
は、このデータ構造のデータを頻繁に生成消去すること
になり、処理時間効率が低下するという問題点があっ
た。
【０００６】本発明は、このような実情に鑑みてなされ
たもので、ＬＲ表によって解析を進めることにより、効
率の良い解析を行うとともに、機構が単純で必要な記憶
量が小さく、かつ言語の種類によらずに高速な言語解析
を可能とする言語解析装置を提供することを目的として
いる。
たもので、ＬＲ表によって解析を進めることにより、効
率の良い解析を行うとともに、機構が単純で必要な記憶
量が小さく、かつ言語の種類によらずに高速な言語解析
を可能とする言語解析装置を提供することを目的として
いる。
【０００７】
【課題を解決するための手段】本発明は、上記目的を達
成するために、文を構成する各語に割り当てられた終端
記号と文中の各語の位置関係を表すために語間に付され
た位置番号とを定め、入力された文の各語に対し、その
語の開始および終了位置番号と終端記号とを構成素とし
て記憶する入力部と、文脈自由文法を表現する文法規則
から生成される状態遷移ネットワークをＬＲ構文解析用
の動作表として記憶する動作表部と、文から抽出した句
構造ごとに終端記号または非終端記号とこの句構造の開
始および終了位置とを記憶するチャート部と、前記入力
部で記憶した前記構成素を先頭から順次取り出し、その
取り出した構成素を前記動作表に適用してＬＲ構文解析
を行って抽出された句構造を前記チャート部に記憶する
解析部とを備えることを特徴としたものである。
成するために、文を構成する各語に割り当てられた終端
記号と文中の各語の位置関係を表すために語間に付され
た位置番号とを定め、入力された文の各語に対し、その
語の開始および終了位置番号と終端記号とを構成素とし
て記憶する入力部と、文脈自由文法を表現する文法規則
から生成される状態遷移ネットワークをＬＲ構文解析用
の動作表として記憶する動作表部と、文から抽出した句
構造ごとに終端記号または非終端記号とこの句構造の開
始および終了位置とを記憶するチャート部と、前記入力
部で記憶した前記構成素を先頭から順次取り出し、その
取り出した構成素を前記動作表に適用してＬＲ構文解析
を行って抽出された句構造を前記チャート部に記憶する
解析部とを備えることを特徴としたものである。
【０００８】このような構成により、ＬＲ表によって解
析を進めるので、アーリ法やチャート法などに比べて効
率の良い解析を行うことができる。また、数字の１次元
リストを操作するため、多次元グラフである graph-str
uctured stack を操作するのに比べて機構が単純にな
る。さらに、数字の１次元リストを記憶するため、多次
元グラフである graph-structured stack を記憶するの
に比べて記憶量が小さくてすむ。
析を進めるので、アーリ法やチャート法などに比べて効
率の良い解析を行うことができる。また、数字の１次元
リストを操作するため、多次元グラフである graph-str
uctured stack を操作するのに比べて機構が単純にな
る。さらに、数字の１次元リストを記憶するため、多次
元グラフである graph-structured stack を記憶するの
に比べて記憶量が小さくてすむ。
【０００９】
【実施例】実施例について、図面を参照して以下に説明
する。図１は、本発明による言語解析装置の一実施例を
説明するための構成図で、図中、１は入力部、２はチャ
ート部、３は文法部、４は動作表部、５は状態リスト
部、６は解析部である。
する。図１は、本発明による言語解析装置の一実施例を
説明するための構成図で、図中、１は入力部、２はチャ
ート部、３は文法部、４は動作表部、５は状態リスト
部、６は解析部である。
【００１０】本発明による言語解析装置は、位置番号毎
に状態番号のリストを記憶して、利用するもので、次の
ような構成を有している。すなわち、入力部１は、終端
記号と２つの位置番号からなる句構造を記憶する。チャ
ート部２は、終端記号又は非終端記号と２つの位置番号
からなる句構造を記憶する。文法部３は文脈自由文法を
記憶し、動作表部４はＬＲ表を記憶する。また、状態リ
スト部５は、位置番号毎に状態番号のリストを記憶す
る。解析部６は、終端記号列に対して文脈自由文法で規
定された句構造を抽出する。
に状態番号のリストを記憶して、利用するもので、次の
ような構成を有している。すなわち、入力部１は、終端
記号と２つの位置番号からなる句構造を記憶する。チャ
ート部２は、終端記号又は非終端記号と２つの位置番号
からなる句構造を記憶する。文法部３は文脈自由文法を
記憶し、動作表部４はＬＲ表を記憶する。また、状態リ
スト部５は、位置番号毎に状態番号のリストを記憶す
る。解析部６は、終端記号列に対して文脈自由文法で規
定された句構造を抽出する。
【００１１】次に、本発明による言語解析装置の動作に
ついて説明する。次の文を、次の文脈自由文法（文法Ｊ
と呼ぶ）を用いて構文解析する場合の動作を示す。 文 ：文化がきたから伝わった。 文法Ｊ：Ｓ→ＰＰ Ｓ Ｓ→Ｖ ＰＰ→Ｎ Ｐ ＰＰ→Ｓ Ｐ この文を構成する各語に関して、次の表１に示すよう
に、終端記号が割り当てられているものとする。
ついて説明する。次の文を、次の文脈自由文法（文法Ｊ
と呼ぶ）を用いて構文解析する場合の動作を示す。 文 ：文化がきたから伝わった。 文法Ｊ：Ｓ→ＰＰ Ｓ Ｓ→Ｖ ＰＰ→Ｎ Ｐ ＰＰ→Ｓ Ｐ この文を構成する各語に関して、次の表１に示すよう
に、終端記号が割り当てられているものとする。
【００１２】
【表１】
【００１３】また、終端記号間の位置関係を表すため、
次のように語間に識別番号を定める。これを位置番号と
呼ぶ。 これに対応して、入力部には、図２に示す情報が記憶さ
れる。ただし、図２において、開始／終了位置番号と
は、その終端記号が対応する語が開始／終了する位置番
号である。終了位置が小さい順に終端記号が記憶されて
いる。
次のように語間に識別番号を定める。これを位置番号と
呼ぶ。 これに対応して、入力部には、図２に示す情報が記憶さ
れる。ただし、図２において、開始／終了位置番号と
は、その終端記号が対応する語が開始／終了する位置番
号である。終了位置が小さい順に終端記号が記憶されて
いる。
【００１４】例えば、以下の表２に示すように、最初の
終端記号Ｎの開始位置番号は、それに対応する語“文
化”が開始する位置番号、つまり１になる。また、＄は
文の最後を表す終端記号で、文の最後の位置に設定され
る。
終端記号Ｎの開始位置番号は、それに対応する語“文
化”が開始する位置番号、つまり１になる。また、＄は
文の最後を表す終端記号で、文の最後の位置に設定され
る。
【００１５】
【表２】
【００１６】文法Ｊは、図３に示すように、文法部３に
記憶される。つまり、文法は、文法の識別子である文法
番号と共に左辺と右辺に分けて記憶される。また、文法
Ｊから得られるＬＲ表が、図４に示すように、動作表部
４に記憶される。表の内容は通常のＬＲ表と同じであ
る。すなわち、ＬＲ表は解析の状態に応じて、次にどの
ような動作を取るべきかを記録したもので、状態は状態
番号によって識別される。
記憶される。つまり、文法は、文法の識別子である文法
番号と共に左辺と右辺に分けて記憶される。また、文法
Ｊから得られるＬＲ表が、図４に示すように、動作表部
４に記憶される。表の内容は通常のＬＲ表と同じであ
る。すなわち、ＬＲ表は解析の状態に応じて、次にどの
ような動作を取るべきかを記録したもので、状態は状態
番号によって識別される。
【００１７】動作には、（１）状態の遷移、
（２）文法の適用、 （３）受理の３種類がある。
そして、状態番号ｎに対応する状態から、終端記号Ｔに
よって、状態番号ｍに対応する状態に状態遷移すること
は、状態番号ｎの行のACTION部のＴの列に sh m と記憶
することで表される。状態番号ｎに対応する状態から、
非終端記号Ｎによって、状態番号ｍに対応する状態に状
態遷移することは、状態番号ｎの行のGOTO部のＮの列に
ｍと記憶することで表される。状態番号ｎに対応する状
態で、次の終端記号がＴの場合に、文法番号ｇの文法を
適用することは、状態番号ｎの行のACTION部のＴ列に r
e g と記憶することで表される。状態番号ｎに対応する
状態で、次の終端記号が＄の場合に、この文を受理する
場合は、状態番号ｎの行のACTION部の＄の列に受理と記
憶することで表される。
（２）文法の適用、 （３）受理の３種類がある。
そして、状態番号ｎに対応する状態から、終端記号Ｔに
よって、状態番号ｍに対応する状態に状態遷移すること
は、状態番号ｎの行のACTION部のＴの列に sh m と記憶
することで表される。状態番号ｎに対応する状態から、
非終端記号Ｎによって、状態番号ｍに対応する状態に状
態遷移することは、状態番号ｎの行のGOTO部のＮの列に
ｍと記憶することで表される。状態番号ｎに対応する状
態で、次の終端記号がＴの場合に、文法番号ｇの文法を
適用することは、状態番号ｎの行のACTION部のＴ列に r
e g と記憶することで表される。状態番号ｎに対応する
状態で、次の終端記号が＄の場合に、この文を受理する
場合は、状態番号ｎの行のACTION部の＄の列に受理と記
憶することで表される。
【００１８】解析部の動作概要は以下のとおりである。
入力部１に記憶されている終端記号を先頭から１つずつ
取り出し、図５〜図７に示す操作を行い、その結果を図
８に示すチャート部、又は、図９に示す状態リスト部に
記憶していく。最終的に受理の動作を行えば、その文が
文法にかなっていたことになる。また、チャート部には
文法で正しいと規定された全ての句構造が抽出されて記
録されることになる。図５〜図７は、解析部の動作のト
レースを説明するためのフローチャートである。以下、
各フローチャートのステップに従って順に説明する。
入力部１に記憶されている終端記号を先頭から１つずつ
取り出し、図５〜図７に示す操作を行い、その結果を図
８に示すチャート部、又は、図９に示す状態リスト部に
記憶していく。最終的に受理の動作を行えば、その文が
文法にかなっていたことになる。また、チャート部には
文法で正しいと規定された全ての句構造が抽出されて記
録されることになる。図５〜図７は、解析部の動作のト
レースを説明するためのフローチャートである。以下、
各フローチャートのステップに従って順に説明する。
【００１９】図５は、＜ＰＲＯＣ１＞を説明するための
フローチャートである。まず、以下の表３に示すよう
に、文頭の位置番号、すなわち、１の状態リストに開始
状態番号を格納する（step1）。開始状態番号は、ＬＲ
表を作成する際に設定されるが、ここでは、それを０と
する。
フローチャートである。まず、以下の表３に示すよう
に、文頭の位置番号、すなわち、１の状態リストに開始
状態番号を格納する（step1）。開始状態番号は、ＬＲ
表を作成する際に設定されるが、ここでは、それを０と
する。
【００２０】
【表３】
【００２１】次に、入力部１の終端記号とその開始／終
了位置番号の組を先頭から順に取り出し（step2)、ＰＲ
ＯＣ２を行う（step,3）。全ての組について終了したら
（step4）、構文解析は終了する。最初の組は（Ｎ,１,
２）である。したがって、ＰＲＯＣ２（Ｎ,１,２）を行
う。
了位置番号の組を先頭から順に取り出し（step2)、ＰＲ
ＯＣ２を行う（step,3）。全ての組について終了したら
（step4）、構文解析は終了する。最初の組は（Ｎ,１,
２）である。したがって、ＰＲＯＣ２（Ｎ,１,２）を行
う。
【００２２】図６は、図５におけるstep３のフローチャ
ートである。 ＜ＰＲＯＣ２（Ｎ,１,２）＞組（Ｎ,１,２）が句構造と
して既にチャート部に記憶されているかどうかを調べる
（step5）。記憶されていれば、成功して終了する（ste
p6）。組（Ｎ,１,２）は記憶されていないので、ＰＲＯ
Ｃ３（Ｎ,１,２）を実行する（step7）。
ートである。 ＜ＰＲＯＣ２（Ｎ,１,２）＞組（Ｎ,１,２）が句構造と
して既にチャート部に記憶されているかどうかを調べる
（step5）。記憶されていれば、成功して終了する（ste
p6）。組（Ｎ,１,２）は記憶されていないので、ＰＲＯ
Ｃ３（Ｎ,１,２）を実行する（step7）。
【００２３】図７は、図６におけるstep７のフローチャ
ートである。 ＜ＰＲＯＣ３（Ｎ,１,２）＞step11 ：位置番号１の状態リストを取り出す。前記トレ
ース表（フローチャート）からもわかるように、［０］
が取り出される。次に、動作表（図４）から終端記号Ｎ
による状態遷移を調べると、sh４、つまり４が遷移先状
態番号であることがわかる。そこで、４をリストＬに加
える。つまりＬ＝［４］となる。step12：次に、変数Ｒ
etにフラグ０をセットする。
ートである。 ＜ＰＲＯＣ３（Ｎ,１,２）＞step11 ：位置番号１の状態リストを取り出す。前記トレ
ース表（フローチャート）からもわかるように、［０］
が取り出される。次に、動作表（図４）から終端記号Ｎ
による状態遷移を調べると、sh４、つまり４が遷移先状
態番号であることがわかる。そこで、４をリストＬに加
える。つまりＬ＝［４］となる。step12：次に、変数Ｒ
etにフラグ０をセットする。
【００２４】step13：リストＬ中の状態番号、つまり４
に対して、２を開始位置とする入力部中の終端記号であ
るＰによって、状態遷移が可能かどうかを動作表（図
４）から調べるとsh７なので可能であるとわかる。そこ
で、４を位置番号２の状態リストに記憶し、変数Ｒetに
フラグ１をセットする。step14 ：リストＬ中の状態番号、つまり４に対して、２
を開始位置とする入力部中の終端記号であるＰが次に来
る場合に、適用できる文法番号を動作表（図４）から調
べると、ないのでＲＬは空リスト［ ］となる。step15 ：リストＲＬが空なので何もしない。step16 ：変数Ｒetは１なので、成功して終了し（step1
7）、ＰＲＯＣ２に戻る。ここまでで、次の表４のよう
になる。
に対して、２を開始位置とする入力部中の終端記号であ
るＰによって、状態遷移が可能かどうかを動作表（図
４）から調べるとsh７なので可能であるとわかる。そこ
で、４を位置番号２の状態リストに記憶し、変数Ｒetに
フラグ１をセットする。step14 ：リストＬ中の状態番号、つまり４に対して、２
を開始位置とする入力部中の終端記号であるＰが次に来
る場合に、適用できる文法番号を動作表（図４）から調
べると、ないのでＲＬは空リスト［ ］となる。step15 ：リストＲＬが空なので何もしない。step16 ：変数Ｒetは１なので、成功して終了し（step1
7）、ＰＲＯＣ２に戻る。ここまでで、次の表４のよう
になる。
【００２５】
【表４】
【００２６】＜ＰＲＯＣ２（Ｎ,１,２）＞ＰＲＯＣ３
（Ｎ,１,２）が成功して終了したので（step7）、表５
に示す組（Ｎ,１,２）をチャート部に記憶し（step
8）、成功して終了し（step10）、ＰＲＯＣ１に戻る。
（Ｎ,１,２）が成功して終了したので（step7）、表５
に示す組（Ｎ,１,２）をチャート部に記憶し（step
8）、成功して終了し（step10）、ＰＲＯＣ１に戻る。
【００２７】
【表５】
【００２８】＜ＰＲＯＣ１＞次の組（Ｐ,２,３）を入力
部から取り出し、ＰＲＯＣ２（Ｐ,２,３）を行う（step
3）。 ＜ＰＲＯＣ２（Ｐ,２,３）＞組（Ｐ,２,３）が句構造と
して既にチャート部に記憶されているかどうかを調べる
（step5）。されていれば、成功して終了する（step
6）。組（Ｐ,２,３）は記憶されていないので、ＰＲＯ
Ｃ３（Ｐ,２,３）を実行する（step7）。
部から取り出し、ＰＲＯＣ２（Ｐ,２,３）を行う（step
3）。 ＜ＰＲＯＣ２（Ｐ,２,３）＞組（Ｐ,２,３）が句構造と
して既にチャート部に記憶されているかどうかを調べる
（step5）。されていれば、成功して終了する（step
6）。組（Ｐ,２,３）は記憶されていないので、ＰＲＯ
Ｃ３（Ｐ,２,３）を実行する（step7）。
【００２９】＜ＰＲＯＣ３（Ｐ,２,３）＞step11 ：位置番号２の状態リストを取り出す。前記トレ
ース表（フローチャート）からもわかるように、［４］
が取り出される。次に、動作表（図４）から終端記号Ｐ
による状態遷移を調べると、sh７、つまり７が遷移先状
態番号であることがわかる。そこで、７をリストＬに加
える。つまりＬ＝［７］となる。step12 ：次に、変数Ｒetにフラグ０をセットする。
ース表（フローチャート）からもわかるように、［４］
が取り出される。次に、動作表（図４）から終端記号Ｐ
による状態遷移を調べると、sh７、つまり７が遷移先状
態番号であることがわかる。そこで、７をリストＬに加
える。つまりＬ＝［７］となる。step12 ：次に、変数Ｒetにフラグ０をセットする。
【００３０】step13：リストＬ中の状態番号、つまり７
に対して、３を開始位置とする入力部中の終端記号であ
るＶとＮによって状態遷移が可能かどうかを動作表（図
４）から調べると、両者とも不可能であるとわかる。step14 ：リストＬ中の状態番号、つまり７に対して、３
を開始位置とする入力部中の終端記号であるＶとＮが次
に来る場合に適用できる文法番号を動作表（図４）から
調べると、両者とも re３なので、ＲＬ＝［３］とな
る。
に対して、３を開始位置とする入力部中の終端記号であ
るＶとＮによって状態遷移が可能かどうかを動作表（図
４）から調べると、両者とも不可能であるとわかる。step14 ：リストＬ中の状態番号、つまり７に対して、３
を開始位置とする入力部中の終端記号であるＶとＮが次
に来る場合に適用できる文法番号を動作表（図４）から
調べると、両者とも re３なので、ＲＬ＝［３］とな
る。
【００３１】step15：リストＲＬ中の文法番号３から文
法部より文法（ＰＰ,[Ｎ,Ｐ]）を取り出す。右辺［Ｎ,
Ｐ］の最右要素Ｐを除いてできるＲｈ′＝［Ｎ］を位置
番号２から文頭方向に順にチャート部の句構造と照合す
ると、［Ｎ］と（Ｎ,１,２）が照合する。最左要素に照
合された文法記号、ここではＮの開始位置番号は上記よ
り１だとわかるので、ＰＲＯＣ２（ＰＰ,１,３）を実行
する。
法部より文法（ＰＰ,[Ｎ,Ｐ]）を取り出す。右辺［Ｎ,
Ｐ］の最右要素Ｐを除いてできるＲｈ′＝［Ｎ］を位置
番号２から文頭方向に順にチャート部の句構造と照合す
ると、［Ｎ］と（Ｎ,１,２）が照合する。最左要素に照
合された文法記号、ここではＮの開始位置番号は上記よ
り１だとわかるので、ＰＲＯＣ２（ＰＰ,１,３）を実行
する。
【００３２】＜ＰＲＯＣ２（ＰＰ,１,３）＞組（ＰＰ,
１,３）はチャート部には記憶されていないので（step
5）、ＰＲＯＣ３（ＰＰ,１,３）を実行する（step7）。
１,３）はチャート部には記憶されていないので（step
5）、ＰＲＯＣ３（ＰＰ,１,３）を実行する（step7）。
【００３３】＜ＰＲＯＣ３（ＰＰ,１,３）＞step11 ：位置番号１の状態リストを取り出す。前記トレ
ース表（フローチャート）からもわかるように、［０］
が取り出される。次に、動作表（図５）から非終端記号
ＰＰによる状態遷移を調べると、GOTO部より２が遷移先
状態番号であることがわかる。そこで、２をリストＬに
加える。つまり、Ｌ＝［２］となる。step12 ：次に、変数Ｒetにフラグ０をセットする。
ース表（フローチャート）からもわかるように、［０］
が取り出される。次に、動作表（図５）から非終端記号
ＰＰによる状態遷移を調べると、GOTO部より２が遷移先
状態番号であることがわかる。そこで、２をリストＬに
加える。つまり、Ｌ＝［２］となる。step12 ：次に、変数Ｒetにフラグ０をセットする。
【００３４】step13：リストＬ中の状態番号、つまり２
に対して３を開始位置とする入力部中の終端記号である
ＶとＮによって状態遷移が可能かどうかを動作表（図
４）から調べると、それぞれsh４とsh３であることから
可能であるとわかる。したがって、位置番号３の状態リ
ストに２を加える。Ｒetに１を代入する。
に対して３を開始位置とする入力部中の終端記号である
ＶとＮによって状態遷移が可能かどうかを動作表（図
４）から調べると、それぞれsh４とsh３であることから
可能であるとわかる。したがって、位置番号３の状態リ
ストに２を加える。Ｒetに１を代入する。
【００３５】step14：リストＬ中の状態番号、つまり２
に対して３を開始位置とする入力部中の終端記号である
ＶとＮが次に来る場合に適用できる文法番号を動作表
（図４）から調べると、ないので、ＲＬ＝［ ］とな
る。step15 ：リストＲＬが空なので、何もしない。step16 ：変数Ｒetは１なので、成功して終了し、ＰＲＯ
Ｃ２に戻る。
に対して３を開始位置とする入力部中の終端記号である
ＶとＮが次に来る場合に適用できる文法番号を動作表
（図４）から調べると、ないので、ＲＬ＝［ ］とな
る。step15 ：リストＲＬが空なので、何もしない。step16 ：変数Ｒetは１なので、成功して終了し、ＰＲＯ
Ｃ２に戻る。
【００３６】＜ＰＲＯＣ２（ＰＰ,１,３）＞ＰＲＯＣ３
（ＰＰ,１,３）が成功して終了したので、組（ＰＰ,１,
３）をチャート部に記憶し（step8）、成功して終了し
（step10）、ＰＲＯＣ３（Ｐ,２,３）に戻る。
（ＰＰ,１,３）が成功して終了したので、組（ＰＰ,１,
３）をチャート部に記憶し（step8）、成功して終了し
（step10）、ＰＲＯＣ３（Ｐ,２,３）に戻る。
【００３７】＜ＰＲＯＣ３（ＰＰ,１,３）＞step15 ：ＰＯＲＣ２（ＰＰ,１,３）が成功したので、Ｒ
etに１を代入する。step16 ：変数Ｒetは１なので、成功して終了し（step1
7）、ＰＲＯＣ２（Ｐ,２,３）に戻る。 ここまでで、次の表６のようになる。
etに１を代入する。step16 ：変数Ｒetは１なので、成功して終了し（step1
7）、ＰＲＯＣ２（Ｐ,２,３）に戻る。 ここまでで、次の表６のようになる。
【００３８】
【表６】
【００３９】＜ＰＲＯＣ２（Ｐ,２,３）＞ＰＲＯＣ３
（Ｐ,２,３）が成功して終了したので、以下の表７に示
す組（Ｐ,２,３）をチャート部に記憶し（step8）、成
功して終了し（step10）、ＰＲＯＣ１に戻る。
（Ｐ,２,３）が成功して終了したので、以下の表７に示
す組（Ｐ,２,３）をチャート部に記憶し（step8）、成
功して終了し（step10）、ＰＲＯＣ１に戻る。
【００４０】
【表７】
【００４１】以下、同様に処理を進め、最終的には以下
の表８のようになり、この文は受理される。
の表８のようになり、この文は受理される。
【００４２】
【表８】
【００４３】最終的に計１４個の句構造が抽出され、チ
ャート部に記憶される。なお、本実施例は、日本語に関
するものであるが、英語や仏語など、別の自然言語やＣ
言語などのプラグラミング言語の解析についても同様に
有効である。また、本実施例は、構文解析に関するもで
あるが、形態素解析や意味解析などにも有効である。要
するに、文脈自由文法によって記述される言語の様々な
解析について、同様に有効である。以下に、英語の形態
素解析のための文脈自由文法の例を示しておく。
ャート部に記憶される。なお、本実施例は、日本語に関
するものであるが、英語や仏語など、別の自然言語やＣ
言語などのプラグラミング言語の解析についても同様に
有効である。また、本実施例は、構文解析に関するもで
あるが、形態素解析や意味解析などにも有効である。要
するに、文脈自由文法によって記述される言語の様々な
解析について、同様に有効である。以下に、英語の形態
素解析のための文脈自由文法の例を示しておく。
【００４４】Ｓ→ＷＳ ＰＲＤ ＷＳ→ＷＳ ＤＬＭ Ｗord ＷＳ→Ｗｏｒｄ ここで、Ｓは文を、ＷＳは語列を、ＰＲＤは文末記号
を、ＤＬＭは区切り文字を、Ｗｏｒｄは語を各々表す文
法記号で、英文は語を区切って並べたものであることが
文脈自由文法で記述されている。
を、ＤＬＭは区切り文字を、Ｗｏｒｄは語を各々表す文
法記号で、英文は語を区切って並べたものであることが
文脈自由文法で記述されている。
【００４５】以上、自然言語の構文解析に本件を適用す
る場合を例にして説明したが、本発明は、文脈自由文法
で定義される言語の様々な解析に適用できる。また、本
実施例では、文頭から文末方向の解析に関するものであ
るが、ＬＲ表の作成方法を変更することで、文末から文
頭への解析にも同様に適用できる。
る場合を例にして説明したが、本発明は、文脈自由文法
で定義される言語の様々な解析に適用できる。また、本
実施例では、文頭から文末方向の解析に関するものであ
るが、ＬＲ表の作成方法を変更することで、文末から文
頭への解析にも同様に適用できる。
【００４６】
【発明の効果】以上の説明から明らかなように、本発明
によると、ＬＲ表によって解析を進めるので、アーリ法
やチャート法などに比べて、効率の良い解析を行うこと
ができる。また、数字の１次元リストを操作するため、
多次元グラフである graph-structured stack を操作す
るのに比べて、機構が単純になる。さらに、数字の１次
元リストを記憶するため、多次元グラフである graph-s
tructured stack を記憶するのに比べて、記憶量が小さ
いという利点がある。
によると、ＬＲ表によって解析を進めるので、アーリ法
やチャート法などに比べて、効率の良い解析を行うこと
ができる。また、数字の１次元リストを操作するため、
多次元グラフである graph-structured stack を操作す
るのに比べて、機構が単純になる。さらに、数字の１次
元リストを記憶するため、多次元グラフである graph-s
tructured stack を記憶するのに比べて、記憶量が小さ
いという利点がある。
【図１】 本発明による言語解析装置の一実施例を説明
するための構成図である。
するための構成図である。
【図２】 本発明における入力部の例を示す図である。
【図３】 本発明における文法部の例を示す図である。
【図４】 本発明における動作表部の例を示す図であ
る。
る。
【図５】 本発明による言語解析装置における解析部の
動作を説明するためのフローチャート（その１）であ
る。
動作を説明するためのフローチャート（その１）であ
る。
【図６】 本発明による言語解析装置における解析部の
動作を説明するためのフローチャート（その２）であ
る。
動作を説明するためのフローチャート（その２）であ
る。
【図７】 本発明による言語解析装置における解析部の
動作を説明するためのフローチャート（その３）であ
る。
動作を説明するためのフローチャート（その３）であ
る。
【図８】 本発明におけるチャート部の例を示す図であ
る。
る。
【図９】 本発明における状態リスト部の例を示す図で
ある。
ある。
１…入力部、２…チャート部、３…文法部、４…動作表
部、５…状態リスト部、６…解析部。
部、５…状態リスト部、６…解析部。
フロントページの続き (58)調査した分野(Int.Cl.7，ＤＢ名) G06F 17/21 - 17/28 ＪＩＣＳＴファイル（ＪＯＩＳ)
Claims (1)
- 【請求項１】 文を構成する各語に割り当てられた終端
記号と文中の各語の位置関係を表すために語間に付され
た位置番号とを定め、入力された文の各語に対し、その
語の開始および終了位置番号と終端記号とを構成素とし
て記憶する入力部と、文脈自由文法を表現する文法規則
から生成される状態遷移ネットワークをＬＲ構文解析用
の動作表として記憶する動作表部と、文から抽出した句
構造ごとに終端記号または非終端記号とこの句構造の開
始および終了位置とを記憶するチャート部と、前記入力
部で記憶した前記構成素を先頭から順次取り出し、その
取り出した構成素を前記動作表に適用してＬＲ構文解析
を行って抽出された句構造を前記チャート部に記憶する
解析部とを備えることを特徴とする言語解析装置。
Priority Applications (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP00210294A JP3339741B2 (ja) | 1994-01-13 | 1994-01-13 | 言語解析装置 |
| US08/371,798 US5649215A (en) | 1994-01-13 | 1995-01-12 | Language parsing device and method for same |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP00210294A JP3339741B2 (ja) | 1994-01-13 | 1994-01-13 | 言語解析装置 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH07210555A JPH07210555A (ja) | 1995-08-11 |
| JP3339741B2 true JP3339741B2 (ja) | 2002-10-28 |
Family
ID=11519985
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP00210294A Expired - Fee Related JP3339741B2 (ja) | 1994-01-13 | 1994-01-13 | 言語解析装置 |
Country Status (2)
| Country | Link |
|---|---|
| US (1) | US5649215A (ja) |
| JP (1) | JP3339741B2 (ja) |
Families Citing this family (34)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6760695B1 (en) * | 1992-08-31 | 2004-07-06 | Logovista Corporation | Automated natural language processing |
| US6658624B1 (en) * | 1996-09-24 | 2003-12-02 | Ricoh Company, Ltd. | Method and system for processing documents controlled by active documents with embedded instructions |
| US8478732B1 (en) | 2000-05-02 | 2013-07-02 | International Business Machines Corporation | Database aliasing in information access system |
| US6714905B1 (en) * | 2000-05-02 | 2004-03-30 | Iphrase.Com, Inc. | Parsing ambiguous grammar |
| US6704728B1 (en) | 2000-05-02 | 2004-03-09 | Iphase.Com, Inc. | Accessing information from a collection of data |
| US6711561B1 (en) * | 2000-05-02 | 2004-03-23 | Iphrase.Com, Inc. | Prose feedback in information access system |
| US9699129B1 (en) | 2000-06-21 | 2017-07-04 | International Business Machines Corporation | System and method for increasing email productivity |
| US6408277B1 (en) | 2000-06-21 | 2002-06-18 | Banter Limited | System and method for automatic task prioritization |
| US8290768B1 (en) | 2000-06-21 | 2012-10-16 | International Business Machines Corporation | System and method for determining a set of attributes based on content of communications |
| US7225467B2 (en) * | 2000-11-15 | 2007-05-29 | Lockheed Martin Corporation | Active intrusion resistant environment of layered object and compartment keys (airelock) |
| US7213265B2 (en) * | 2000-11-15 | 2007-05-01 | Lockheed Martin Corporation | Real time active network compartmentalization |
| US7644057B2 (en) | 2001-01-03 | 2010-01-05 | International Business Machines Corporation | System and method for electronic communication management |
| US7136846B2 (en) | 2001-04-06 | 2006-11-14 | 2005 Keel Company, Inc. | Wireless information retrieval |
| US7181386B2 (en) * | 2001-11-15 | 2007-02-20 | At&T Corp. | Systems and methods for generating weighted finite-state automata representing grammars |
| EP1331630A3 (en) * | 2002-01-07 | 2006-12-20 | AT&T Corp. | Systems and methods for generating weighted finite-state automata representing grammars |
| US7289948B1 (en) * | 2002-01-07 | 2007-10-30 | At&T Corp. | Systems and methods for regularly approximating context-free grammars through transformation |
| US7343372B2 (en) * | 2002-02-22 | 2008-03-11 | International Business Machines Corporation | Direct navigation for information retrieval |
| US7146643B2 (en) * | 2002-10-29 | 2006-12-05 | Lockheed Martin Corporation | Intrusion detection accelerator |
| US7080094B2 (en) * | 2002-10-29 | 2006-07-18 | Lockheed Martin Corporation | Hardware accelerated validating parser |
| US20040083466A1 (en) * | 2002-10-29 | 2004-04-29 | Dapp Michael C. | Hardware parser accelerator |
| US20070061884A1 (en) * | 2002-10-29 | 2007-03-15 | Dapp Michael C | Intrusion detection accelerator |
| US7603661B2 (en) * | 2003-01-30 | 2009-10-13 | Hamilton Sunstrand | Parse table generation method and system |
| JP4001283B2 (ja) * | 2003-02-12 | 2007-10-31 | インターナショナル・ビジネス・マシーンズ・コーポレーション | 形態素解析装置および自然言語処理装置 |
| WO2004079571A2 (en) * | 2003-02-28 | 2004-09-16 | Lockheed Martin Corporation | Hardware accelerator state table compiler |
| US8495002B2 (en) | 2003-05-06 | 2013-07-23 | International Business Machines Corporation | Software tool for training and testing a knowledge base |
| US20050187913A1 (en) | 2003-05-06 | 2005-08-25 | Yoram Nelken | Web-based customer service interface |
| US7970600B2 (en) * | 2004-11-03 | 2011-06-28 | Microsoft Corporation | Using a first natural language parser to train a second parser |
| US20060277028A1 (en) * | 2005-06-01 | 2006-12-07 | Microsoft Corporation | Training a statistical parser on noisy data by filtering |
| US7778957B2 (en) * | 2006-06-14 | 2010-08-17 | Research In Motion Limited | Handheld electronic device with assisted text entry using existing message thread, and associated method |
| US7669614B2 (en) * | 2006-08-21 | 2010-03-02 | Dan Cohen | Systems and methods for installation inspection in pipeline rehabilitation |
| US8707252B1 (en) | 2008-09-03 | 2014-04-22 | Emc Corporation | Techniques for automatic generation of parsing code |
| US20100228538A1 (en) * | 2009-03-03 | 2010-09-09 | Yamada John A | Computational linguistic systems and methods |
| US9569425B2 (en) | 2013-03-01 | 2017-02-14 | The Software Shop, Inc. | Systems and methods for improving the efficiency of syntactic and semantic analysis in automated processes for natural language understanding using traveling features |
| US9372846B1 (en) * | 2013-11-20 | 2016-06-21 | Dmitry Potapov | Method for abstract syntax tree building for large-scale data analysis |
Family Cites Families (7)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5105353A (en) * | 1987-10-30 | 1992-04-14 | International Business Machines Corporation | Compressed LR parsing table and method of compressing LR parsing tables |
| JP2963463B2 (ja) * | 1989-05-18 | 1999-10-18 | 株式会社リコー | 対話型言語解析装置 |
| US5095432A (en) * | 1989-07-10 | 1992-03-10 | Harris Corporation | Data processing system implemented process and compiling technique for performing context-free parsing algorithm based on register vector grammar |
| US5193192A (en) * | 1989-12-29 | 1993-03-09 | Supercomputer Systems Limited Partnership | Vectorized LR parsing of computer programs |
| US5511213A (en) * | 1992-05-08 | 1996-04-23 | Correa; Nelson | Associative memory processor architecture for the efficient execution of parsing algorithms for natural language processing and pattern recognition |
| JP2534600B2 (ja) * | 1992-06-19 | 1996-09-18 | 松下電器産業株式会社 | 文字列照合装置 |
| US5475588A (en) * | 1993-06-18 | 1995-12-12 | Mitsubishi Electric Research Laboratories, Inc. | System for decreasing the time required to parse a sentence |
-
1994
- 1994-01-13 JP JP00210294A patent/JP3339741B2/ja not_active Expired - Fee Related
-
1995
- 1995-01-12 US US08/371,798 patent/US5649215A/en not_active Expired - Lifetime
Non-Patent Citations (1)
| Title |
|---|
| 伊東秀夫，ＬＲ表を用いたチャートパーシングアルゴリズム，情報処理学会研究報告９４−ＮＬ−９９，日本，情報処理学会，１９９４年 １月２１日，Ｖｏｌ．９４，Ｎｏ．９，ｐ．４９−ｐ．５６ |
Also Published As
| Publication number | Publication date |
|---|---|
| US5649215A (en) | 1997-07-15 |
| JPH07210555A (ja) | 1995-08-11 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP3339741B2 (ja) | 言語解析装置 | |
| JP4459443B2 (ja) | 中国語テキストにおける単語分割 | |
| EP1488338B1 (en) | Phrase-based joint probability model for statistical machine translation | |
| US7809744B2 (en) | Method and system for approximate string matching | |
| EP0424032B1 (en) | Naturel language processing apparatus | |
| US5774834A (en) | System and method for correcting a string of characters by skipping to pseudo-syllable borders in a dictionary | |
| US5895446A (en) | Pattern-based translation method and system | |
| JP3695191B2 (ja) | 翻訳支援装置及びその方法並びにコンピュータ可読記録媒体 | |
| US6108620A (en) | Method and system for natural language parsing using chunking | |
| US20030125928A1 (en) | Method for retrieving similar sentence in translation aid system | |
| JPH0567144A (ja) | 前編集支援方法およびその装置 | |
| US20100228538A1 (en) | Computational linguistic systems and methods | |
| US7379862B1 (en) | Method and apparatus for analyzing and debugging natural language parses | |
| US12333245B2 (en) | Methods and apparatus to improve disambiguation and interpretation in automated text analysis using structured language space and transducers applied on automatons | |
| JPH0685150B2 (ja) | コンピユータ・プログラム変換装置および方法 | |
| US20030187829A1 (en) | Content retrieval apparatus and method | |
| JP2000148756A (ja) | 対訳文誤り検出装置 | |
| JPH052605A (ja) | 機械翻訳方式 | |
| JP3832613B2 (ja) | 自動要約装置および自動要約プログラムを記録した記録媒体 | |
| JPH05250405A (ja) | 構文解析装置 | |
| JPH06243162A (ja) | 機械翻訳装置 | |
| JP4021813B2 (ja) | 複合語登録プログラムおよび登録装置 | |
| JP6058513B2 (ja) | 語順並び替え装置、翻訳装置、方法、及びプログラム | |
| JPH07271792A (ja) | 日本語形態素解析装置及び日本語形態素解析方法 | |
| Chen | Parsing with Context-Free Grammars |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20080816 Year of fee payment: 6 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20080816 Year of fee payment: 6 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20090816 Year of fee payment: 7 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20090816 Year of fee payment: 7 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20100816 Year of fee payment: 8 |
|
| LAPS | Cancellation because of no payment of annual fees |