文脈自由言語より広い言語に対する構文解析アルゴリズムとシステム開発

比上下文无关语言更广泛的语言的解析算法和系统开发

基本信息

批准号：
12780248
负责人：
椎名広光
金额：
$ 0.83万
依托单位：
Okayama University of Science
依托单位国家：
日本
项目类别：
Grant-in-Aid for Encouragement of Young Scientists (A)
财政年份：
2000
资助国家：
日本
起止时间：
2000 至 2001
项目状态：
已结题

项目摘要

本研究では,文脈自由言語より広いクラスの言語に対する新しい構文解析法を考案した.大きく分けて,構文解析法に確率を導入しないで解析できる言語のクラス解析する方式(1.)と,確率を導入して構文解析木の生起確率や情報の抽出をおこなう方式(2.)の二つ手法を提案している.1.文脈自由言語より広い言語の構文解析アルゴリズムの展開文脈自由言語の部分クラスを構文解析する方法としてLR構文解析法が知られているが,そのLR構文解析の拡張として,文法規則の導出のとき,先読み文字列を非終端記号とし,導出する文法規則より右側の非終端記号列を部分木の親とする構文解析法(unrestricted LR(k)構文解析)を提案した.加えて,この構文解析法は,先読み文字列数k>1となるような複数個必要な文法でも,先読み文字をk=1に削減する文法規則の変換法ついて明らかにした.2.確率構文解析アルゴリズムの展開これまで構文解析木の生成確率には,文法規則の生起確率を利用していたが,構文解析木の高さ方向の情報を考慮していない.そのため,必ずしも精密な構文解析木の生起確率が求められてはいなかった.それに対し,本研究では,入力文字のLC親と1つ前の入力時に生成される生成規則の組み合わせを数え上げることによって,入力文字列や部分文字列から得られる構文解析木の生起確率をこれまでよりも精密に求めることができることを示した.日本電子化辞書研究所(EDR)の日本語コーパスを用いて,非文(構文解析木の存在しない入力)の構文解析の生起確率はすべての文で正しい生起確率を求めることができた.また,毎日新聞94年度版を利用して数値情報を抽出して,適合率83.2%,再現率74.8%を得た.

在这项研究中，我们设计了一种新的解析方法，用于与无上下文的语言更宽的语言。从广义上讲，我们提出了两种方法：一种用于语言类别分析的类分析方法，可以分析，而无需将概率引入解析方法（1.），以及一种通过引入概率提取解析树的发生概率和信息的方法。1。 Expanding parsing algorithms for languages with wider than context-free language The LR parsing method is known as a method for parsing partial classes of a context-free language, but as an extension of LR parsing, when deriving grammar rules, when deriving grammar rules, the parsing method is unrestricted, in which the non-terminal string on the right side of the derivation grammar rules are the parent of the subtree （不受限制的）其中衍生语法规则右侧的非末端字符串是子树的父母。此外，已经提出了这种解析方法来创建一种语法规则转换方法，该方法将预读字符的数量减少到k = 1，即使对于需要多个语法的语法，例如预读字符串k> 1.2的语法数量。扩展概率分析算法到目前为止，使用语法规则发生的概率用于生成解析树的概率，但是在解析树高度方向上的信息尚未考虑。因此，不一定确定出现精确解析树的概率。相反，在这项研究中，输入特征的LC母体以及通过计算上一个输入期间产生的发电规则的组合，这表明可以比以前更精确地获得从输入字符串和子字中获得的解析树的概率。使用电子词典研究所（EDR）的日本语料库，可以确定出现非句子的解析的可能性（在解析树中不存在的输入）可以确定以获得所有句子中解析树发生的出现的正确概率。此外，使用Mainichi Shimbun的1994年版提取数值信息，并且匹配率为83.2％，并获得了召回率。