第5章 コンピュータで文の構造を解析する方法

5.1 文脈自由文法

  • 構文解析で最も多く使われる方法
  • 文法(S→PP* Vなど)と辞書(それぞれの品詞について単語が記録されている)を用いる
  • 実際の文は文脈に依存することが多いが、近似的に文脈に依存していない文法で文を解析すると格段に処理が簡単になる

5.2 トップダウン法とボトムアップ法

  • 構文解析した結果は構文木で表す
  • 終端記号:構文木の葉(いわゆる辞書の項目にあたる部分)
  • 前終端記号:終端記号より一階層上にある、品詞にあたる部分
  • 非終端記号:品詞をまとめて句にしたもの
  • 文脈自由文法を用いる構文解析アルゴリズムにはトップダウン法、ボトムアップ法、両者の融合法の3種類がある
  • トップダウン法(予測駆動型):抽象的な規則から順に適用する
    • 文を句、品詞、単語の順に展開していき、最終的に入力文と字面、品詞が一致したものを予測できたときに、その部分を確定する
    • トップダウン法では唯一の解析結果しか生まれないので、曖昧性がある場合でも複数の解析結果を得ることはできない
    • 解析結果を保持したうえで、その結果を失敗として強制的にバックトラックを行うことで、複数個の解析結果を得る
    • バックトラック:さかのぼって再度解析を行うこと
  • ボトムアップ法(データ駆動型):入力されたデータより文法規則の矢印の向きを逆にたどってまとめ上げていく
    • 文法規則に曖昧さが存在する場合、すべての解析結果が生成される
    • すべての解析結果が生成されるため、不必要な構文木が生成されてしまう
  • トップダウン法とボトムアップ方の融合法:両手法の欠点を解決する
    • トップダウン法により次に解析すべき文法カテゴリを予測する
    • ボトムアップに成長する木のうちで合致しないものを除く
    • これらの操作により不要な枝を除去する

Comments