今日のパーサー生成ツールで LL パーサーが相対的に人気を博しているのは、LR パーサーよりも LL パーサーが優れている点は何ですか?
Wikipediaによると、LR 解析は LL よりも優れているようです。
LR 構文解析は LL 構文解析よりも広い範囲の言語を処理でき、エラー報告にも優れています。つまり、入力が文法に準拠していない場合に構文エラーをできるだけ早く検出します。これは、バックトラッキングのために文法の別のブランチにエラー検出を延期する可能性のある LL(k) (またはさらに悪い場合は LL(*) パーサー) とは対照的であり、多くの場合、長い共通の接頭辞を使用した選言全体でエラーをローカライズするのが難しくなります。 .
注: これは宿題ではありません。Antlr が LL パーサー ジェネレーターであることを知ったときは驚きました (名前に「LR」が含まれているにもかかわらず!)。
GLR は、パース ツリー/フォレストが必要で、ブラック ボックスを気にしない場合に最適です。LR/LALR 競合を静的に解決するのではなく、徹底的なテストを介して解析時にあいまいさをチェックすることを犠牲にして、必要なCFGを入力できます。それは良いトレードオフだと言う人もいます。無料の C++ 文法を持つ Ira Baxter の DMS ツールまたは Elkhound は、このクラスの問題に役立ちます。ANTLR言語アプリケーションの大規模なクラスにも役立ちますが、トップダウン アプローチを使用して、セマンティック述語を許可する LL(*) と呼ばれる再帰的降下パーサーを生成します。ここでは、述語を使用すると、CFG を超えて状況依存言語を解析できることを証明なしで述べます。プログラマーは、優れたエラー処理などのアクションを文法に挿入したり、シングルステップ デバッグを好みます。LLは3つとも得意です。LLは手作業なので分かりやすいです。ウィキペディアが LR の方がエラー処理に優れているというナンセンスを信じないでください。とはいえ、ANTLR で多くのバックトラックを行うと、LL(*) ではエラーが実際に悪化します (PEG にはこの問題があります)。
後戻りし直します。PEG、ANTLR、およびその他の非決定論的戦略と同様に、GLR も投機 (バックトラック) を行います。非決定論的な LR 状態では、GLR はサブパーサーを「フォーク」して実行可能なパスを試します。とにかく、LL にはエラー処理のための適切なコンテキストがあります。LR が式に一致していることを認識している場合、LL は代入または条件付きの式であることを認識していIFます。LR は、どちらかになる可能性があることを知っていますが、確かではありません。
GLR はO(n^3)最悪のケースです。packrat/PEG はO(n)最悪のケースです。ANTLR はO(n^2)循環先読み DFA によるものですがO(n)、実際にはそうです。本当に関係ありません。GLRは十分に高速です。
ANTLRはアンチLRではなく、言語認識のためのもう 1 つのツールですが、私はそれも気に入っています; )
率直に言って、80 年代の多くの若いプログラマーと同じように、私は LALR を理解していませんでしたし、ブラック ボックスも好きではありませんでした (今では GLR エンジンの美しさを掘り下げていますが、それでも LL の方が好きです)。私は市販の LL(k) ベースのコンパイラを構築し、手動で構築したものを生成するツールを構築することにしました。ANTLR は万人向けではなく、C++ のようなエッジ ケースは GLR でより適切に処理される可能性がありますが、多くの人は ANTLR が自分のコンフォート ゾーンに収まると感じています。2008 年 1 月以降、ANTLRWorks 内で ANTLR のバイナリ jar とソース zip の合計が 134,000 回ダウンロードされました (Google Analytics による)。多くの経験的データを含む LL(*)に関する論文を参照してください。
手作業でコードを作成する必要がある場合は、再帰的降下 (LL) を使用すると現実的に実行できます。人々は L(AL)R パーサーを実際に手作業で構築することはできません。
最新のパーサー ジェネレーターがすべてのパーサー構成を処理し、そのスペースがそれほど問題にならないことを考えると、特定のパーサー ジェネレーターに対して文法を有効にするために文法と戦う必要がないため、LR パーサーを好みます。 （「すべての左再帰を削除する」という愚かさはありません）。
実際、私はGLR パーサーを好みます。これは、文脈自由文法でほとんどすべてを解析します。左再帰の心配はありません。シフトなし/コンフリクトの心配を減らします。先読み制限なし。
1 つのGLR 構文解析エンジンで処理できる言語の範囲 (LL/LALR を使用した構文解析が難しいことで有名な C++ を含む)を知りたい場合は、こちらを参照してください。
私の個人的な経験から (私はさまざまな状況で両方を使用しました)、最も実際的な違いは、LL(k) を使用すると、多くの可能な reduce- LR パーサーでよく発生する競合の削減またはシフト削減。気にしなければならないのは、右再帰に変換する必要がある左再帰だけです。
もう 1 つのことは、トップダウン アプローチは通常、解析中にツリー全体を格納する必要があり、あいまいさが解決されるまで大きく成長する可能性があるため、(空間または時間に関して) より複雑になることを意味します。
私が知っている唯一の利点は、LL パーサーを手作業で簡単にコーディングできることです。LR パーサーを手動でコーディングするのは非常に困難です (通常はパーサー ジェネレーターを使用します)。
LL 解析の最悪の場合の複雑さは O(n^4) ですが、LR 解析の最悪の場合の複雑さは O(n^3) です。
(しかし、誰も O(n^4) 文法を書くことはありません。)
頭に浮かぶ理由の1つは、LLパラダイムで任意のバックトラック（咳C ++）を必要とする言語を実行する方がはるかに簡単であるということです。