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

概要

論文の詳細を見る
本稿では、LR構文解析の並列ア上ゴリズム、およぴLR文法にL属性を付加した属性文法の意味解析の並列アルゴリズムについて述べる。本並列アルゴリズムは、並列計算の理論的なモデルであるCREW PRAM上で実現している。付加したL属性とは、属性の評価が解析木を先がけ順の処理できる屈性の部分クラスである。L属性は、逐次処理のLL(k)構文解析の中で同時に処理できるが、LR構文解析では、同時に処理できない。そこで、同時に処理するためにL属性に制限をつけたLR属性が提案されている。一方、構文解析の実行中に意味解折を同時に行う並列アルゴリズムを開発しようとすると、プロセッサ数が多くなってしまう。そのため、プロセッサ数の増大を押えるために、構文解析を終了してから意味解析を行うことにした。そのことにより、プロセッサ数の削減と同時に、LR文法に付加する属性のクラスをLR属性からL属性に広げることが可能になった。本研究で考案したLR構文解析の並列アルゴリズムは、入力文字数をn個とすると、O(n^3)個のプロセッサを用いて。O(log n)時間を要する。一方、意味解析の並列アルゴリズムは、入力文字数をn個とし、L属性の種類をm個とすると、O(n^4m^4)個のプロセッサを用いてO(log^2n *log m)時間を要する。この並列アルゴリズムにより、L属性文法による意味解析がクラスNCに属することが明らかになった。また、ここで示す並列アルゴリズムは、つぎの仮定を設けている。1.文法がChomsky標準形となっている。2.属性の評価式は、多項式で表される。
一般社団法人情報処理学会の論文
1992-02-24

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

スポンサーリンク

概要

著者

関連論文

スポンサーリンク