著者

森本真一

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌プログラミング(PRO) (ISSN:18827802)

巻号頁・発行日

vol.44, no.2, pp.41-41, 2003-02-15

---

本発表では,文脈自由文法に対するボトムアップ型構文解析アルゴリズムのカテゴリ理論に基づく導出を行う.カテゴリ理論は,問題の本質的な部分を自然に記述できるため,高水準の使用記述や仕様変換に適している.このためカテゴリを用いた仕様記述も行われているが,それらはデータ構造の記述が中心であり,データを扱う制御構造に対する記述はあまり行われていない.そこで本発表では制御構造に対する仕様記述の例として,文脈自由文法に対するボトムアップ型構文解析アルゴリズムをカテゴリ理論に基づいて導出する.文脈自由文法に対する構文解析は実際的な問題であり,これまで多くのアルゴリズムが提案されてきたが,仕様記述という点からは論理式(集合論)に基づく検討以外はあまり行われていなかった.本発表では,構文解析アルゴリズムをカテゴリ理論によって導出することにより,論理式による導出との比較を行う.本発表では,文脈自由文法の構文記号や構文規則などを対象とし,それらの間の射から,最左導出の逆としてボトムアップ型構文解析アルゴリズムを導出する.さらに,対象となる文法をLR 文法に限定した場合に,このアルゴリズムがどのように簡略化されるか(LR 構文解析アルゴリズムに帰着されるか)を述べる.In this presentation, I derive bottom up parsing algorithms for context free grammars by categorical approach. For a context free grammar G, I consider a category whose objects are symbols and rules of G. From this category, I derive bottom up parsing algorithms for G by categorical operations. I also show how this algorithms are reduced to the LR parsing algorithm if G is an LR grammar. Finally I compare this categorical approach for derivation of parsing algorithms with a set theoretic (logical) approach.