GLR法

GLR法（一般化LR法）は、標準的なLR構文解析法を拡張したもので、非決定的で曖昧な文法を扱うことができます。これは、1986年に冨田勝によって発表され、冨田法や並列構文解析法とも呼ばれています。GLR法は、自然言語のように複数の解釈が可能な文法を解析する際に特に有効です。

GLR法の基本原理

GLR法は、LR法の基本的な動作原理を踏襲していますが、大きな違いは、構文解析中に複数の可能性を同時に扱う点にあります。LR法では、構文解析表に基づいて単一の解析パスを進めますが、GLR法では、複数の遷移先が存在する場合、スタックを複製してそれぞれの可能性を追跡します。このため、LR法ではエラーとなるshift/reduce衝突やreduce/reduce衝突も、GLR法では問題なく処理できます。

具体的には、GLR法は以下の手順で動作します。

1. 入力文法に基づいて、LR法と同様の構文解析表を作成します。ただし、GLR法の構文解析表は、一つの状態から複数の遷移先を持つことができます。
2. 構文解析中に複数の遷移先が存在する場合、スタックを複製し、それぞれのスタックに異なる遷移先を割り当てます。
3. 各スタックに対して、次の入力を処理します。遷移先が存在しない場合は、そのスタックを破棄します。
4. 必要に応じて、共通の接尾辞や接頭辞を持つスタック部分を共有し、メモリ使用量や探索空間を削減します。これにより、スタックは一種のノードの束のような構造になります。

GLR法の利点

GLR法は、注意深く実装すれば、時間計算量はCYK法やアーリー法と同様にO(n^3)となります。しかし、GLR法にはそれ以外にも、以下のような利点があります。

非決定性の度合いに比例した実行時間: GLR法の実行時間は、文法の非決定性の度合いに比例します。決定的な文法に対しては、GLR法はO(n)の時間計算量で動作します。これは、アーリー法やCYK法では達成できない利点です。
オンラインアルゴリズム: GLR法はオンラインアルゴリズムであり、入力を順次処理していくことができます。

多くのプログラミング言語は、その文法が決定的であるか、または「ほぼ決定的」です。つまり、少数の非決定性がある場合でも、GLR法は効率的に処理できます。このため、完全な文脈自由文法を扱う他のアルゴリズムと比較して、GLR法は「ほぼ決定的」な文法を扱うのに非常に適しています。多くの場合、ほとんど単一のスタックだけで構文解析を完了させることができます。

まとめ

GLR法は、非決定性と曖昧さを許容する文法を扱うための強力な構文解析手法です。自然言語処理をはじめとする様々な分野で活用されており、特に「ほぼ決定的」な文法の解析においては、その効率性が際立っています。冨田勝によるこの手法は、構文解析の分野における重要な進歩の一つであり、現在でもその基本原理は広く用いられています。

もう一度検索