順位グラフ文法の並列構文解析
スポンサーリンク
概要
- 論文の詳細を見る
順位グラフ文法は,頂点のラベル間に順位関係をもつグラフ文法である.これまでに,制限された順位グラフ文法に対する逐次構文解析アルゴリズムが提案されており,頂点数nの入力グラフに対して0(n)時間で解析できることが示されている.それらの制限のうち,順位関係に関する反射的な非終端記号をもたないという制限は,逐次構文解析においてハンドルを線形時間で見つけるために必要な条件である.一般の順位グラフ文法の構文解析は,ハンドルを還元する際にうめ込み規則に従って辺を張りかえる必要があるため,構文解析全体をO(n)時間以下に抑えることは困難である.加えて反射的関係を含むため,ハンドルを見つけるためにO(n^2)いつ時間を必要とる.本稿では,O(log n)時間でハンドルを見つけるCBEW-PBAM(Concurrent Read Exclusive Write-Parallel Random Access Machine)上の並列アルゴリズムを提案する.
- 1995-03-15