多重文脈自由文法のある部分クラスに対する効率の良い構文解析法について

概要

論文の詳細を見る
自然言語の構文記述のための形式文法として,多重文脈自由文法(以下mcfgと略記)が提案されている.mcfgでは,respectively文や倒置文のような互いに割り込んだ構文を自然に記述することができる.その生成能力は,文脈自由文法(以下cfgと略記)や,同じく自然言語の構文記述のためにPollardによって導入されたhead grammarよりも真に大きく,文脈規定文法よりも真に小さい.また,mcfg Gに対して,入力系列αがGの生成する言語に属するかどうかを判定する時間計算量0(n^e)(nは入力系列長)のアルゴリズムが提案されている.ここで,eはGのみに依存して定まる定数であるが,その上界は知られていない.本稿では,mcfgのある部分クラスに対する時間計算量0(n^2)の構文解析アルゴリズムを提案する.この部分クラスに属するmcfgの生成する言語のクラスは,あいまいでないcfgの生成する言語をすべて含み,言語{a_1^pb_1^qa_2^pb_2^q…a_m^pb_m^q|p,q≧1}(m≧1),{wcw|∈{O,1}^+}等も含む.
一般社団法人情報処理学会の論文
1990-03-14