|
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つが置かれる。そして、次の入力はそれぞれのスタックに渡され、処理される。状態と入力の組合せで遷移先が全く存在しないようになった場合、その経路は捨てられる。 共通の接尾辞や接頭辞に関するスタック部分を共有するなどの最適化によって、メモリ使用量や探索空間の節約をすることが可能である。このような改良によって構造が複雑化し、スタックは一種のノードの束のようになる。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「GLR法」の詳細全文を読む スポンサード リンク
|