Please enable JavaScript.
Coggle requires JavaScript to display documents.
構文解析（２） (CKY法 (チョムスキー標準形 (書き換えの規則が２つ (A → B C, A → a, A，B，Cは非終端記号 …
構文解析（２）
CKY法
計算量：O(n^3)
nは入力文の長さ（単語数）
ボトムアップアルゴリズム
アルゴリズムが単純で理解しやすい
チョムスキー標準形
書き換えの規則が２つ
A → B C
A → a
A，B，Cは非終端記号
aは終端記号
構文木の復元
完成したCKY表の履歴を辿る
アーリー法
計算量：O(n^3)
任意の文脈自由文法が作れる
トップダウンアルゴリズム
文法の予測能力が使えるため効率が良い
無駄な弧を生成しない
アーリー法のアルゴリズム
チャート
構文解析の過程で生成された弧を記録する配列
Chart[i]
終点が位置iで終わる弧を記録
新しい弧の生成
非活性弧に対して行う
Completer
２つの弧をつなげて新しい弧を生成
始点と終点を更新して
前の方にあった規則のドットを一つ右にずらす
活性弧に対して行う
ドットの右が
前終端記号
Scanner
ひとつ右のChartに新しい弧を生成
辞書規則があった場合，非活性弧を作る
前終端記号じゃない
Predictor
同じChartに新しい弧を生成
規則を全て探して，新しい活性弧を作る