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

概要

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

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

スポンサーリンク

概要

著者

関連論文

スポンサーリンク