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
著者
関連論文
- 係り元文節からの相対的な距離を反映した統計的日本語係り受け解析(自然言語処理)
- Cross-Bootstrapping:特許文書からの課題・効果表現対の自動抽出手法(テキストマイニング,情報爆発論文)
- 公開特許公報の特許権成立の成否に関するテキスト情報を用いた推定手法の基礎的検討(自然言語処理)
- Techniques to accelerate request processing for Byzantine fault tolerance (コンピュテーション)
- 新聞記事中の文が因果関係を含むか否かの判定 (言語理解とコミュニケーション)
- 改良taintモデルに基づくオブジェクト指向言語を用いたアプリケーション開発
- オブジェクトごとにセキュリティ制御可能なtaintモデル
- 1-B-3 新幹線の終端駅に着目した列車発着スケジューリング(輸送・交通)
- 経済新聞記事内容の個々の企業におけるインパクトの判定(文書分類・評判分析)
- 可読性の向上を目的とした片仮名表記外来語の換言知識獲得(自然言語処理)