[解決済み] LLパーサーとRecursive Descentパーサーの違いとは？

質問

私は最近、パーサー（言語/文脈自由文法）がどのように機能するかを独学で勉強しようとしています。私は特に LL(k) 文法 この文法には、2つの主要なアルゴリズムがあります。 LLパーサー (スタック/パーステーブルを使用) と 再帰的降下パーサ (単に再帰を使う)。

私が見る限り、再帰的降下アルゴリズムはすべての LL(k) 文法とおそらくそれ以上の文法で動作しますが、LL パーサーはすべての LL(k) 文法で動作します。しかし、再帰的降下パーサーは明らかに LL パーサーよりも実装が簡単です（LL パーサーが LR パーサーよりも簡単なのと同じです）。

そこで質問ですが、どちらのアルゴリズムを使用する場合に、どのような利点や問題があるのでしょうか？再帰的降下法が同じ文法セットで動作し、実装がよりトリッキーであることを考えると、なぜ LL を選ぶことがあるのでしょうか?

どのように解決するのですか？

LL は通常、再帰的降下よりも効率的な構文解析手法です。 実際、素朴な再帰降下パーサーは実際には O(k^n) (となります（ここで n は入力サイズ）。 メモ化のようないくつかの技術（これは パックラット パーサーを生成します）のようないくつかのテクニックは、パーサーが受け入れる文法のクラスを拡張するだけでなく、これを改善することができますが、常に空間とのトレードオフがあります。 LL パーサーは (私の知る限り) 常に線形時間です。

一方、再帰的降下パーサーは LL よりも多くの文法を扱うことができるという直観は正しいです。 再帰的降下は LL(*) である任意の文法を扱うことができます (つまり。 無制限 である)文法も扱うことができる。 これは、再帰的降下が実際にはPEGの直接エンコードされた実装であること、つまり パーサ式文法(s) . 具体的には、接続演算子( a | b ) は可換でない、つまり a | b とは等しくないということです。 b | a . 再帰的降下パーサーは、それぞれの選択肢を順番に試します。 ですから、もし a が入力にマッチすれば、たとえ b であったとしても は入力にマッチします。 これは、古典的な最長一致のあいまいさ、例えば、ダングリングな else のような古典的な曖昧さが、単に接続解除を正しく並べることで処理されるようになります。

以上のことから、それは 可能 は、線形時間で実行されるように再帰的降下を使用して LL(k) パーサーを実装することが可能です。 これは、各解析ルーチンが与えられた入力に対して適切な生成を一定時間で決定するように、予測セットを本質的にインライン化することによって行われます。 残念ながら、このような手法では、ある種の文法が扱えなくなります。 いったん予測構文解析に入ると、ダングリング(dangling) else のような問題は、もはやそのような容易さでは解決できません。

再帰的降下法ではなく LL を選択する理由については、主に効率と保守性の問題です。 再帰的降下パーサーは実装が著しく簡単ですが、表現する文法が宣言形式で存在しないため、通常、保守が困難になります。 自明でないパーサーの使用例のほとんどは、ANTLR や Bison などのパーサー ジェネレーターを使用しています。 このようなツールでは、アルゴリズムが直接エンコードされた再帰的降下法であるか、テーブル駆動型の LL(k) であるかは、実際には重要ではありません。

興味深かったのは、この他にも recursive-ascent これは recursive-descent の流儀で直接エンコードされた構文解析アルゴリズムですが、どんな LALR 文法でも扱うことができます。 また、私は パーサーコンビネーター これは、再帰的降下パーサーを結合するための機能的な方法です。