# 文脈自由文法と構文解析
# 目次
# はじめに
文脈自由文法について構文解析の視点からまとめました。
# 句構造文法
句構造文法とは、句構造規則で定義された文法のことで、自然言語処理において広く用いられています。
このような規則を書き換え規則とよびます。この規則は S（文）は NP（名詞句）VP（動詞句）に書き換えられることを示しています。
例として、「You read a book.」という英文に書き換え規則を適用させてみます。
このように、ある文に対して書き換え規則を適用していく様子を示した木構造のことを導出木といいます。また、構文構造の表現方法の 1 つである句構造に基づいて構文解析を行うことを句構造解析といいます。
句構造文法において、導出木の葉を終端記号とよびます。この記号からの書き換え規則はなく、自然言語では単語に相当します。また、終端記号以外のものを非終端記号とよび、導出の際の中間的に用いられる記号で、自然言語では品詞に相当します。
# 文脈自由文法（CFG）
句構造文法から、書き換え規則の左辺を非終端記号の 1 つに制限したものを文法自由文法といいます。書き換えの規則を制限することで、表現能力は下がりますが、取り扱いがしやすくなります。
文脈自由文法
は、下記の 4 つの組で定義されます。
- N：非終端記号の集合。
- Σ：終端記号の集合。
- P：α → β という形式の生成ルールの集合で、α ∈ N, β ∈ {N ∪ Σ} である。
- S：開始記号 S ∈ N。
# チョムスキー標準形
文脈自由文法で、さらに書き換え規則の右辺が非終端記号 2 つ、または終端記号 1 つであるという制限を設けた物をチョムスキー標準系とよびます。
上の導出木もチョムスキー標準系を用いています。規則はこんな感じです。
| 句構造規則 | 辞書規則 |
|---|---|
| S→NP VP | PRON→you |
| VP→VT NP | VT→read |
| NP→DET N | DET→a |
| NP→PRON | N→book |
# CKY 法
今までの方法は、開始記号から順規則を適用していき、与えられた文を得られるまで繰り返すという、トップダウンで構文解析をしていました。しかし、この方法では入力文の長さに対して指数時間の計算量を必要とします。 それに対して、途中経過をテーブルとして記録して、ボトムアップで構文解析を行う方法のことを CKY 法とよびます。この方法では、入力文の長さ n に対して O(n^3) で計算可能です。
三角行列をテーブルとして用いて、途中経過を記録します。CKY 法での文法はチョムスキー標準形に限ります。
# アルゴリズム
入力文 := w1 w2 ・・・ wn
for i := 1 to n do
a(i, i) = {A | A → wi ∈ 辞書規則}
for d := 1 to n-1 do
for i := 1 to n-d do
j = i + d
for k := i to j - 1 do
a(i, j) = a(i, j) ∪ {A | A → B C ∈ 句構造規則, B ∈ a(i, k), C ∈ a(k + 1, j)}
a(1, n) に開始記号 S がある場合、解析は成功です。