• 検索結果がありません。

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

N/A
N/A
Protected

Academic year: 2021

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

Copied!
1
0
0

読み込み中.... (全文を見る)

全文

(1)Vol. 44. No. SIG 2(PRO 16). Feb. 2003. 情報処理学会論文誌:プログラミング. 発表概要. カテゴリ理論による構文解析アルゴリズムの導出 森. 本. 真. 一†. 本発表では,文脈自由文法に対するボトムアップ型構文解析アルゴ リズムのカテゴ リ理論に基づく 導出を行う.カテゴ リ理論は,問題の本質的な部分を自然に記述できるため,高水準の使用記述や仕 様変換に適している.このためカテゴ リを用いた仕様記述も行われているが,それらはデータ構造の 記述が中心であり,データを扱う制御構造に対する記述はあまり行われていない.そこで本発表では 制御構造に対する仕様記述の例として,文脈自由文法に対するボトムアップ型構文解析アルゴ リズム をカテゴ リ理論に基づいて導出する.文脈自由文法に対する構文解析は実際的な問題であり,これま で多くのアルゴ リズムが提案されてきたが,仕様記述という点からは論理式( 集合論)に基づく検討 以外はあまり行われていなかった.本発表では,構文解析アルゴ リズムをカテゴ リ理論によって導出 することにより,論理式による導出との比較を行う.本発表では,文脈自由文法の構文記号や構文規 則などを対象とし,それらの間の射から,最左導出の逆としてボトムアップ型構文解析アルゴ リズム を導出する.さらに,対象となる文法を LR 文法に限定した場合に,このアルゴ リズムがどのように 簡略化されるか( LR 構文解析アルゴ リズムに帰着されるか )を述べる.. Derivation of Parsing Algorithms by Categorical Approach Shin-ichi Morimotoi† 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.. ( 平成 14 年 6 月 18 日発表). † NEC 航空宇宙システム NEC Aerospace Systems, Ltd.. 41.

(2)

参照

関連したドキュメント

ている。本論文では、彼らの実践内容と方法を検討することで、これまでの生活指導を重視し

2 解析手法 2.1 解析手法の概要 本研究で用いる個別要素法は計算負担が大きく,山

外声の前述した譜諺的なパセージをより効果的 に表出せんがための考えによるものと解釈でき

うことが出来ると思う。それは解釈問題は,文の前後の文脈から判浙して何んとか解決出 来るが,

節の構造を取ると主張している。 ( 14b )は T-ing 構文、 ( 14e )は TP 構文である が、 T-en 構文の例はあがっていない。 ( 14a

C−1)以上,文法では文・句・語の形態(形  態論)構成要素とその配列並びに相互関係

名の下に、アプリオリとアポステリオリの対を分析性と綜合性の対に解消しようとする論理実証主義の  

 この論文の構成は次のようになっている。第2章では銅酸化物超伝導体に対する今までの研