文脈自由文法の解析方法

• トップダウン縦型探索

  ATN(Augmented Transition Network), DCG

• トップダウン横型探索 アーリー法
• ボトムアップ横型探索 チャート法
• 決定的解析 LR(k)法、富田法

  ※富田法…決定的、conflictをスタック分岐により解決、平均的に

    
  図: 簡単な日本語CFG
  

    
  図: LR表
  

○構文解析の問題点…曖昧性(複数の導出木の可能性)

　　''Time flies like an arrow.''

　→入力長nのCatalan数程度 (n項式に括弧を挿入する組合せの数 1, 2, 5, 14, 42, 132, 469, 1430,…)