本研究では、不適格文を一般的に「文中に n 箇所の、終端記号(単語)あるい は、非終端記号(句)レベルの、脱落、挿入および置換誤りを含んだ文」として 捉え、そのような不適格文を解析し、誤り箇所と誤り種別を同定し、その誤り を修正する、頑健な構文解析ツールを開発する。
我々は、1993 年から 1995までの 2 年間の受託研究(東工大、田中研究室)で、 チャート法に基づく並列で頑健な構文解析法を PIM 上で開発した。256 プロ セッサを用いて長さ 6-18 の不適格文を解析した結果、60-170 という、高い 台数効果が得られた。本研究では、この研究から得られた知見を生かしながら、 逐次マシンでもっとも高速な構文解析アルゴリズムの一つといわれている一般 化 LR 法をベースにした頑健な並列構文解析法を提案し、並列マシン上および 汎用計算機上で動作するツールを開発する。
1990 年に沼崎らは、一般化 LR 法を並列論理型言語により実装する手法を提 案し、64 台構成の並列マシン Multi-PSI 上で実験を行ない、10 倍程度の台 数効果を得ている。本研究では、この研究を踏まえ、一般化 LR 法を用いて不 適格文を解析するアルゴリズムを並列論理型言語を用いて並列環境に実装する。 その際、これまでの不適格文解析研究で扱ってきた終端記号(単語)レベルの誤 りだけでなく、非終端記号(句)レベルの誤りにも対処できる枠組を実現し、よ り多様な誤りを含む文をも扱える構文解析ツールを目指す。
また、不適格文解析では、通常の構文的曖昧性だけでなく、誤りの位置とタイ プによる曖昧性も存在するため、得られる解析結果の数が非常に多くなり、そ れらをすべて出力した場合、その中から妥当なものを選択するのは容易なこと ではない。そこで、頑健な構文解析ツールでは、解析結果にスコアをつけ、 スコアの低い結果を妥当でないものとして排除し、妥当な結果のみを、その妥 当性の順に出力する機能が必要である。本研究では、誤りの位置、誤りのタイ プ、誤りの数、そして、誤りの(入力文中での)範囲を尺度として、解析結果に スコア付けを行なう。
開発環境は、UNIX 上と PIMOS 上の両方である。前者において Prolog でプロ グラムを記述し、動作の確認を行なう。後者では、前者から得られたプログラ ムを元として KL1 で並列アルゴリズムを実装する。