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

• Item type: Trans(1)
• 公開日: 2003-02-15
• タイトル: カテゴリ理論による構文解析アルゴリズムの導出
• タイトル / 言語: en
• タイトル: Derivation of Parsing Algorithms by Categorical Approach
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 発表概要
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: NEC航空宇宙システム
• 著者所属(英): en
• 著者所属(英): NEC Aerospace Systems, Ltd.
• 著者名: 森本真一
• 著者名(英): Shin-Ichi, Morimotoi
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本発表では，文脈自由文法に対するボトムアップ型構文解析アルゴリズムのカテゴリ理論に基づく導出を行う．カテゴリ理論は，問題の本質的な部分を自然に記述できるため，高水準の使用記述や仕様変換に適している．このためカテゴリを用いた仕様記述も行われているが，それらはデータ構造の記述が中心であり，データを扱う制御構造に対する記述はあまり行われていない．そこで本発表では制御構造に対する仕様記述の例として，文脈自由文法に対するボトムアップ型構文解析アルゴリズムをカテゴリ理論に基づいて導出する．文脈自由文法に対する構文解析は実際的な問題であり，これまで多くのアルゴリズムが提案されてきたが，仕様記述という点からは論理式（集合論）に基づく検討以外はあまり行われていなかった．本発表では，構文解析アルゴリズムをカテゴリ理論によって導出することにより，論理式による導出との比較を行う．本発表では，文脈自由文法の構文記号や構文規則などを対象とし，それらの間の射から，最左導出の逆としてボトムアップ型構文解析アルゴリズムを導出する．さらに，対象となる文法をLR 文法に限定した場合に，このアルゴリズムがどのように簡略化されるか（LR 構文解析アルゴリズムに帰着されるか）を述べる．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464814
• 書誌情報: 情報処理学会論文誌プログラミング（PRO）; 巻 44, 号 SIG02(PRO16), p. 41-41, 発行日 2003-02-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7802
• 出版者 / 言語: ja
• 出版者: 情報処理学会