問題

文脈自由文法の構文解析は, 入力として入力文および文法規則を与えられて, その入力文が, 開始記号から文法規則を繰り返し適用することによって得られ る(導出される)かどうかを検査する問題である. もちろん実際にはその導出の 過程が後から再現できるだけの情報(解析木)を答えとして残さなくてはならな い. 以下のように記号を定める.

• S: 非終端記号の集合.
• : 開始記号. .
• T: 終端記号(単語)の集合.
• : 入力文(長さn). .
• : 以下を満たす非終端記号の集合である.

  から入力文の部分単語列 が 導出できる.

文法はチョムスキー標準形とする. すなわち, 文法は辞書規則と 句構造規則からなり, 辞書規則は,

という形をしている. ここで, , . 句構造規則(生成規則) は,

という形をしている. ここで, .

この記号のもとで, 与えられるのは および文法であり, 求めるものは集合 らである. もちろん構文解析という目的からは, 「 であるかどうかを判定し, そうであれば導出過程(ま たは同じことだが, 解析木)を出力する」ことが問題になるが, CKYアルゴリズ ムにおいては, 結局アルゴリズム中全ての を全て求めることになる ため, このようにしておく. 逆に が求まってしまえば後はアルゴリ ズムの各過程で用いた文法規則を覚えておくことで, 導出過程は再現でき る. 具体的に蓄える必要があるデータはアルゴリズムの説明をする時に述べる.

さて, ( )は以下の条件を満たすような最小 の集合である.

1. ならば, .
2. , , かつ ならば,

1.は, は1単語からなる部分単語列 を導出可能な非終端記号 の集合であるから, となる各sに対して, でなければならない, ということを表している. これは図で書け ば, 1単語 からなる単語列に対し, 図5.1左のような解 析木が構築可能であることを示している. 一方2.は, s'から単語列 が導出可能, s''から単語列 が導 出可能で, かつ句構造規則 が存在する時は, 結局s から, 両者を結合した部分文字列 が導出可能であること を表している. これは解析木の図でいえば, 図5.1右のよう に, に対する解析木A, に対する 解析木Bがあり, 各々の木の根における記号がs', s''であり, 文法規則 存在する時は, に対する, より 大きな解析木Cが, A, Bを子供に持つ木として構築可能であることを表し ている.

     図5.1: