(12) 一般化LR法を用いた頑健な並列構文解析に関する研究

平成８年度委託研究中間報告

１　研究テーマ、研究代表者：

　（１）研究テーマ

            「一般化 LR 法を用いた頑健な並列構文解析に関する研究」

　（２）研究代表者（氏名、所属、役職）

　　　　　國藤  進　北陸先端科学技術大学院大学教授

２　記述項目：

　（１）研究進捗状況

本研究では，PIMOS 上および UNIX 上で不適格文を解析する頑健な構文解析ツー
ルの開発・整備を行なう．現段階では，具体的には逐次マシン上で最高速の構
文解析法である一般化 LR 構文解析システムを UNIX 上に実現した．prolog 
言語で記述した本パーザは Brill により開発された品詞付け器(Tagger)と連
結し，通常の品詞なしの任意の文を解析できるようになっている．また，不適
格文解析の並列アルゴリズムの基本的な設計は大部分終了している．現時点で
は，prolog 版の頑健な一般化 LR 構文解析システムのデータ構造の改良を行
ない，並列処理に適切なデータ構造への修正作業を取り込んでいる．

　（２）現在までの主な成果

現在までの主な成果は，UNIX 上における prolog 版の LR 構文解析システム
の実装およびその並列アルゴリズムの設計である．本システムの不適格性（エ
ラー）同定メカニズムは，構文木内のエラー発生箇所に依存した形で構文解析
木を出力するように設計されている．Brill により開発された品詞付け器
(Tagger)と連結することにより，約 9 万単語の辞書から入力文中の各単語に
語彙カテゴリを決定的に付加できる．また，prolog 版の LR 構文解析システ
ムを並列アルゴリズムの改良に取り込み中である．

　（３）今後の研究概要

今後の研究課題としては，現在の UNIX 上で開発したシステムを改良し，不適
格文解析の並列パーザを実現する．その際，3 つの負荷分散方式（動的負荷分
散，静的負荷分散，要求駆動型動的負荷分散）がどのように並列化の効率に影
響を与えるかについて検討する．また，平成６年度に開発したチャート法に基
づく並列非文構文解析システムの実現から得られた技法を本システムの構築に
適用してみる．KL1 言語を用いた PIM 上における並列一般化 LR構文解析シス
テムを実装し，特に一般化 LR 法のスタック管理の並列化による種々の負荷分
散方式を考察し，PIM による評価実験を行ない解析速度に関する台数効果を調
べる．

　（４）今年度目標成果ソフトウェアイメージ

目標成果ソフトウェアは，逐次環境および並列環境上で，予め与えられた文脈
自由文法のもとで，入力文(自然言語)に対して高速に構文解析を実行し，構文
木を出力する．また，並列環境において，動的負荷分散方式，静的負荷分散方
式，要求駆動による動的負荷分散方式などを実装し，これらの負荷分散方式か
らユーザが自由に選択し実行できるような機能を用意する．また，解析結果が
複数得られる場合，それらの結果に統語構造に基づくスコアをつけ，スコアの
低い結果を妥当でないものとして排除し，妥当な結果のみを，その妥当性の順
に出力する機能を提供する．