カテゴリ理論による構文解析アルゴリズムの導出

概要

論文の詳細を見る
本発表では,文脈自由文法に対するボトムアップ型構文解析アルゴリズムのカテゴリ理論に基づく導出を行う.カテゴリ理論は,問題の本質的な部分を自然に記述できるため,高水準の使用記述や仕様変換に適している.このためカテゴリを用いた仕様記述も行われているが,それらはデータ構造の記述が中心であり,データを扱う制御構造に対する記述はあまり行われていない.そこで本発表では制御構造に対する仕様記述の例として,文脈自由文法に対するボトムアップ型構文解析アルゴリズムをカテゴリ理論に基づいて導出する.文脈自由文法に対する構文解析は実際的な問題であり,これまで多くのアルゴリズムが提案されてきたが,仕様記述という点からは論理式(集合論)に基づく検討以外はあまり行われていなかった.本発表では,構文解析アルゴリズムをカテゴリ理論によって導出することにより,論理式による導出との比較を行う.本発表では,文脈自由文法の構文記号や構文規則などを対象とし,それらの間の射から,最左導出の逆としてボトムアップ型構文解析アルゴリズムを導出する.さらに,対象となる文法をLR文法に限定した場合に,このアルゴリズムがどのように簡略化されるか(LR構文解析アルゴリズムに帰着されるか)を述べる.
一般社団法人情報処理学会の論文
2003-02-15

カテゴリ理論による構文解析アルゴリズムの導出

スポンサーリンク

概要

著者

関連論文

スポンサーリンク