LLパーサーとLRパーサーの基本的な違いを知っています。また、GLR、SLR、およびLALRはすべてLRパーサーの拡張機能であることも知っています。だから私の質問はもっと詳しく...
LL（*）パーサーとLRパーサーのバリエーションを考えると、一方で記述でき、他方で記述できない言語はありますか？それとももっと簡単に言えば、どちらでも表現できない特徴や特性はありますか？
具体的な例として。LL（*）パーサーを使用して言語を作成する場合、LRパーサーでのみ可能になる（またはその逆の）言語に追加したい機能/プロパティに遭遇することはありますか？
ここにいくつかの意見があります、あなたはそれらをポイントとカウンターポイントと考えることができます：
もちろん。LLパーサーは、左再帰の文法を処理できません。固定kのL（AL）R（k）パーサーは、k <*であるため、LL（ * ）パーサーが処理できるいくつかのことを解析できません。
ウィキペディアでこの段落が興味深いと思うかもしれません。LL（*）文法はLR（k）文法のサブセットです：http： //en.wikipedia.org/wiki/Context-free_grammar#Restrictions したがって、より多くの言語を解析できますLR解析メソッドを使用します。
LRパーサーで解析できるLLパーサーで解析するために「書き換え」できない文法がいくつかあります。一例：減算を使用して用語を構成する単純な文法を考えます。
S -> S - S | num
ここには明らかに左再帰がありますが、これはLLパーサーでは処理できません。この文法をLLで構文解析できるようにするには、左再帰を排除する必要があります。
S -> num S'
S' -> - num S' | epsilon
これで、LLパーサーがこの文法を処理できるようになりました。ただし、4 --2 -1のような用語の構文ツリーを構築する場合、ツリーを操作する深さ優先探索では、（4 --2）-1 = 3ではなく4-（2-1）=3が得られます。あなたが期待するように。
これは、左結合演算子（減算など）を処理するために、文法で左再帰規則を使用する必要があるためです。ただし、左再帰ルールはLLパーサーでは処理できません。
したがって、ここには、LLでは処理できない言語のクラスがあります。
LRパーサーは、LLよりも大きなクラスの言語を受け入れることができます。LL（k）およびLR（k）で、kは、適切な生産/削減を適用できるように知る必要のある先読みシンボルの数を意味します。k getが大きいほど、解析テーブルは大きくなります。したがって、kはLRパーサーだけを制限するのではなく、LLパーサーも制限します。LRパーサーがより大きなクラスの言語を受け入れることができる理由は、LLパーサーを操作するときに問題となる左再帰のためです。しかし、これは完全には当てはまりません。直接再帰は解決可能であり、つまり、文法をLL文法に書き直すことができるからです。直接再帰は、A->Abcのようなものです。間接再帰があり、それがどのように見えるかがわかっている場合は、問題が発生します。LRパーサーは、ツリーをボトムアップ方式で解析するため、この問題を解決できます。なぜそれが正確であるかを確認するには、LR解析をもう少し深く調べる必要があります。しかし、LRパーサーはすべてが強力というわけではなく、制限もあります。一部の文法は消化が非常に難しく、kファクターは役に立ちません。この種の文法にはGLRパーサーが必要です。これは、実際にはLR（k）パーサーをシミュレートしますが、生成/削減のあいまいさが発生した場合は、バックトラッキングを使用して解析空間全体を分析します。
LR（1）パーサーは、左再帰と一般的な要因を削除するために文法を書き直す必要がないため、LL（1）よりも多くの文法を認識します。
ただし、明確な文法があれば、左再帰と共通の要因をいつでも削除できるため、最終的には両方とも同じ言語を解析できます。
誰かがこれについて疑問を持っているなら、私はあなたに、LL（1）は解析できず、LR（1）はできる、つまり、左再帰と一般的な要因を取り除くために書き直すことができないという明確な文法を与えるように挑戦します。
LL解析は、理論的にはO（n ^ 4）であるか、かなり遅いです。LR解析は高速、O（n ^ 3）、またはかなり低速です。 https://en.wikipedia.org/wiki/Top-down_parsing
私はこれの証拠を見たいのですが。