椎名広光,山川栄樹
単純順位文法に対する並列構文解析アルゴリズムのCM-5への実装とその性能評価
Abstract:構文解析は，コンパイラや自然言語処理における処理の1フェーズであり，入力文字があらかじめ与えられた文法の生成する言語のクラスに属しているか否かを調べる認識処理と，入力文字列が文法に対してもつ構造を調べる構文解析木作成処理とからなる．
本稿ではまず，1個の制御プロセッサを含む複数個のプロセッサと共有メモリとで構成される理論的な並列計算機のモデルにおいて，共有メモリに対する同時書き込みが不可能である場合を考え，コンパイラで使われる文法の一つである単純順位文法を並列的に構文解析するアルゴリズムを構築する．そして，入力文字数をnとするとき，O(n2)個のプロセッサを使用することにより，提案した並列構文解析アルゴリズムはO(log2n)時間で単純順位文法の構文解析を終了し得ることを示す．
さらに，理論的な並列計算機を前提として考案された並列アルゴリズムを，現実の並列計算機コネクションマシンCM-5上に実装し，その処理時間を計測することによって実際的な性能の評価を行う．