GLR法
注意深く実装すれば、GLR法の時間計算量はCYK法やアーリー法と同じ O(n)となる。しかし、GLR法には他に次のような2つの利点がある。
このアルゴリズムの実行時間は文法の非決定性の度合いに比例する。決定的な文法では、GLR法は O(n) の時間計算量となる(アーリー法やCYK法では、そうはならない)。
GLR法はオンラインアルゴリズムである。すなわち、入力を順次消費し、処理を行っていく。
実際、多くのプログラミング言語は決定的であるか「ほぼ決定的」であり、非決定性があったとしても少数の(ただし、個数が不明な)トークンを解析することで解決可能である。完全な文脈自由文法を扱う他のアルゴリズム(アーリー法やCYK法)に比較して、GLR法は「ほぼ決定的」な文法を扱うのに適しており、その場合はほとんど1つのスタックだけで処理が行われる。
表示
編集