属性文法に基づく意味解析の並列アルゴリズム

概要

論文の詳細を見る
属性による意味解析[4]は、コシパイラにおける意味解析の1つの手法である。属性とは意味情報のことで意味規則で表現され、文法規則に意味規則を付加したものを属性文法という。属性文法は、1968年Knuth[1]により初めて提案され、これまでにそれを用いた意味解析の手法が幾つか考案されている。これらの手法は、属性の評価能力に制限をつけて逐次計算機におけるコンパイラ内部の意味解祈部で用いられている。従って属性文法は、コンパイラの構文解析に基づきクラス分けされている。(このクラス分けの例を、2に示す。)このように属性のクラス分け[5]は、逐次アルゴリズムからみた解析によって多くなされている。ところが、並列アルゴリズムからみた属性クラス分けや属性文法を用いた意味情報の並列アルゴリズムの解析は、従来あまりなされていない。そこそ、本研究では、幾つかの属性文怯に基づく意味解析の並列アルゴリズムをそれぞれ示し、それらの意味解析の問題が全てクラスNCに属することを明らかにする。なお、本研究に於ける属性による意味解析では、次のような条件を課している。1.意味解析に対応している構文解析の文法はChomsky 標準形[3]で表現されているものとする。2.属性を評価する前に、構文解析木は作成されるものとする。3.属性の評価式は多項式で表現されるものとする。また、本研究で扱う並列アルゴリズムは、並列計算の理論的なモデルであるCREW PRAM[2](Concurrent Read Exclusive Write Pnrallel Random Access Machine)上で表現している。(PRAMとは、共有メモリを持つSIMD型の並列計算機モデルで、並列アルゴリズムの理論的な解析によく用いられる。なお、CREWは、1つのメモリの番地に瞬時読み込み可かつ、書き込みは1つのプロセッサのみ可であることを示す。)
一般社団法人情報処理学会の論文
1992-09-28

属性文法に基づく意味解析の並列アルゴリズム

スポンサーリンク

概要

著者

関連論文

スポンサーリンク