著者

植木 正裕 徳永 健伸 田中 穂積

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告自然言語処理(NL)

巻号頁・発行日

vol.1997, no.85, pp.45-51, 1997-11-12

---

本論文は、GLR法における圧縮共有の効率を改善する手法を提案する。GLR法では、圧縮共有統語森により解析の高速化をはかつているが、冨田によるGLR法の実誇では、アクションのコンフリクトによって枝分かれした複数のスタックの間で解析のタイミングがずれるために、共有できるシンボルの生成のタイミングもずれることがある。このため、スタックの完全な圧縮共有ができているとは限らず、同じ解析動作が重複して行なわれたり、完全な圧縮共有統語森が生成できないこともある。本論文で提案するGLRパーズの手法では、枝分かれしたスタックの間での解析のタイミングを制御し、スタックの共有化のタイミングを早め、完全な圧縮共有統語森を作成することができる。これにより、解析の高速化と使用メモリ空間の削減を同時に実現できる。In this paper we propose a method to improve efficiency of GLR parsing. Tomita's GLR implementation uses two data structures, graph-structured stack and packed-shared parse forest. Both structures help us avoid applying same parsing action repeatedly to save parsing time and memory space. However, his implementation misses a chance to share data structures. To the contrary, our method not only keeps the advantage of Tomita's implementation but also allows data structures to be completely shared. Experiments show our method exceeds in both time and space efficiency compared to Tomita's method.