私は最近、パーサー（言語/文脈自由文法用）がどのように機能するかを自分自身に教えようとしていますが、1つを除いて、そのほとんどは理にかなっているようです。特にLL（k）文法に注目しています。このアルゴリズムでは、2つの主要なアルゴリズムがLLパーサー（スタック/解析テーブルを使用）と再帰下降パーサー（単に再帰を使用）のようです。
私が見る限り、再帰下降アルゴリズムはすべてのLL（k）文法で機能し、場合によってはそれ以上で機能しますが、LLパーサーはすべてのLL（k）文法で機能します。ただし、再帰下降パーサーは、LLパーサーよりも実装がはるかに簡単です（LLパーサーがLRパーサーよりも単純であるのと同じです）。
だから私の質問は、どちらかのアルゴリズムを使用するときに遭遇する可能性のある利点/問題は何ですか？同じ文法セットで機能し、実装が難しいのに、なぜ再帰下降よりもLLを選ぶのでしょうか。
LLは通常、再帰下降よりも効率的な解析手法です。実際、ナイーブな再帰下降パーサーは、最悪の場合、実際にはO（k ^ n）（nは入力サイズ）になります。メモ化（ Packratパーサーを生成する）などのいくつかの手法は、これを改善し、パーサーが受け入れる文法のクラスを拡張することができますが、常にスペースのトレードオフがあります。LLパーサーは（私の知る限り）常に線形時間です。
反対に、再帰下降パーサーはLLよりも多くのクラスの文法を処理できるという直感は正しいです。再帰下降は、LL（*）（つまり、無制限の先読み）であるすべての文法と、あいまいな文法の小さなセットを処理できます。これは、再帰下降が実際にはPEGまたはパーサー式文法の直接エンコードされた実装であるためです。具体的には、選言演算子（a | b）は可換ではありません。つまり、a | bは等しくありませんb | a。再帰下降パーサーは、各選択肢を順番に試します。したがって、入力と一致する場合はa、入力と一致したとしても成功します。これにより、ぶら下がりのような古典的な「最長一致」のあいまいさが可能になりますb else論理和を正しく順序付けるだけで処理される問題。
そうは言っても、再帰下降を使用してLL（k）パーサーを実装し、線形時間で実行することができます。これは、基本的に予測セットをインライン化することによって行われ、各解析ルーチンが一定時間内に特定の入力に対して適切な生成を決定します。残念ながら、このような手法では、クラス全体の文法が処理されなくなります。予測構文解析に入ると、ぶら下がりのような問題はそれほどelse簡単には解決できなくなります。
再帰下降よりもLLが選択される理由については、主に効率と保守性の問題です。再帰下降パーサーは実装が非常に簡単ですが、それらが表す文法が宣言形式で存在しないため、通常は保守が困難です。ほとんどの重要なパーサーのユースケースでは、ANTLRやBisonなどのパーサージェネレーターを使用しています。このようなツールでは、アルゴリズムが直接エンコードされた再帰下降またはテーブル駆動のLL（k）であるかどうかは実際には問題ではありません。
興味深いことに、再帰下降の方法の後に直接エンコードされた解析アルゴリズムである再帰下降を調べることも価値がありますが、任意のLALR文法を処理できます。また、再帰下降パーサーを一緒に構成する機能的な方法であるパーサーコンビネーターについても掘り下げます。