文脈自由文法の並列構文解析法

概要

論文の詳細を見る
文脈自由文法の構文解析法としては,CYK法やEarley法が良く知られている.これらは,いずれも逐次処理を想定したアルゴリズムであり,Earley法では入力文字列の長さをnとして,O(n^2)空間,O(n^3)時間(文法が曖昧で無い場合はO(n^2)時間)で構文解析を行うことができる.また,並列構文解析の手法に関しては,Chomsky標準形文法に対して,CYK法に"gap"という概念を導入することによって,入力文をO(log n)時間で認識するアルゴリズムRytterによって示されている.本稿では,まずCYK法とEarley法の長所を生かすことで,O(n)時間,O(n^2)空間,O(n^2)プロセッサで並列解析を行う方法を示す.また,この方法にRytterの手法を適用して,任意の文脈自由文法に対するO(log n)時間並列認識アルゴリズムを示し,さらに,並列化が困難であるEarley法に"gap"を導入して並列化したアルゴリズムを示し,それらの手法の比較を行う.
1989-10-16