GLR法
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/01/06 06:26 UTC 版)
ナビゲーションに移動 検索に移動GLR法または一般化LR法（英: GLR parser）とは、非決定的で曖昧な文法を扱うようLR法を拡張したもの（"Generalized LR parser"）である。1986年、冨田勝が発表した。冨田法、並列構文解析法とも呼ばれる。
元々の形から進化し続けているが、その基本は変わっていない。冨田は自然言語を完全かつ効率的に構文解析することを目標としている。標準のLR法では自然言語の非決定的で曖昧な性質に対処できないが、GLR法では可能である。
アルゴリズム
大まかに言えば、GLR法はLR法と同じ作法で作用する。ただし、ある文法を与えられたとき、GLR法は入力に幅優先探索を使い、全ての可能な解釈を処理する。フロントエンドでの GLR 構文解析器生成は入力された文法から LR法と同様の構文解析表を作成する。ただし、LR法の構文解析表は一度に一つの状態しか許さないが、GLR法の構文解析表は複数の遷移先を許す。従って、LR法では許されない shift/reduce 衝突や reduce/reduce 衝突も GLR 法では問題にならない。
遷移先が複数存在する状態になったとき、構文解析器のスタックが複製され、それぞれに取りうる状態群のうちの1つが置かれる。そして、次の入力はそれぞれのスタックに渡され、処理される。状態と入力の組合せで遷移先が全く存在しないようになった場合、その経路は捨てられる。
共通の接尾辞や接頭辞に関するスタック部分を共有するなどの最適化によって、メモリ使用量や探索空間の節約をすることが可能である。このような改良によって構造が複雑化し、スタックは一種のノードの束のようになる。
利点
注意深く実装すれば、GLR法の時間計算量はCYK法やアーリー法と同じ O(n3）となる。しかし、GLR法には他に次のような2つの利点がある。
- このアルゴリズムの実行時間は文法の非決定性の度合いに比例する。決定的な文法では、GLR法は O(n) の時間計算量となる（アーリー法やCYK法では、そうはならない）。
- GLR法はオンラインアルゴリズムである。すなわち、入力を順次消費し、処理を行っていく。
実際、多くのプログラミング言語は決定的であるか「ほぼ決定的」であり、非決定性があったとしても少数の（ただし、個数が不明な）トークンを解析することで解決可能である。完全な文脈自由文法を扱う他のアルゴリズム（アーリー法やCYK法）に比較して、GLR法は「ほぼ決定的」な文法を扱うのに適しており、その場合はほとんど1つのスタックだけで処理が行われる。
- GLR法のページへのリンク
