LLパーサーはLRパーサーに比べてどのような利点があり、それが相対的に人気を博しているのでしょうか？今日のパーサージェネレーターツール?
によるとウィキペディアLR 構文解析は LL 構文解析よりも優れているようです。
LR 構文解析は LL 構文解析よりも広範囲の言語を処理でき、エラー報告も優れています。つまり、入力が文法に準拠していない場合に構文エラーをできるだけ早く検出します。これは、バックトラックによりエラー検出が文法の別のブランチに延期される可能性があり、長い共通接頭辞を持つ論理和全体でエラーを特定するのが難しくなることが多い LL(k) (またはさらに悪い場合は LL(*) 構文解析) とは対照的です。
注: これは宿題ではありません。 Antlr が LL パーサー ジェネレーターであることを知って驚いただけです (名前に「LR」が含まれているにもかかわらず)。
ベストアンサー1
GLRは、パースツリー/フォレストが必要で、ブラックボックスを気にしない場合に最適です。CFGLR/LALR の競合を静的に解決する代わりに、徹底的なテストによって解析時に曖昧さをチェックするというコストをかけて、望む結果が得られます。これは良いトレードオフだと言う人もいます。この種の問題には、Ira Baxter の DMS ツールや、無料の C++ 文法を備えた Elkhound が役立ちます。ANTLRは言語アプリケーションの大きなクラスにも役立ちますが、トップダウンアプローチを使用して、意味述語を許可するLL(*)と呼ばれる再帰下降パーサを生成します。ここでは、述語を使用すると、CFGを超えて文脈依存言語を解析できることを証明なしで述べます。プログラマーは、文法にアクションを挿入したり、適切なエラー処理をしたり、シングルステップデバッグをしたりすることを好みます。LLはこれら3つすべてに優れています。LLは手作業で行うため、理解しやすいです。LR がエラー処理に優れているというウィキペディアのナンセンスとはいえ、ANTLR でバックトラックを頻繁に行う場合、LL(*) ではエラーがさらに悪化します (PEG にはこの問題があります)。
バックトラックについて。GLR も、PEG、ANTLR、その他の非決定論的戦略と同様に推測 (つまりバックトラック) します。非決定論的 LR 状態では、GLR はサブパーサーを「フォーク」して、実行可能なパスを試します。とにかく、LL にはエラー処理に適したコンテキストがあります。LR は、それが式に一致していることを認識している場合、それが代入式または -条件式であることを認識します。LR は、IFそれがどちらにもある可能性があることを認識していますが、確信はありません。そして、その不確実性こそが、その威力を発揮するところです。
GLR はO(n^3)最悪のケースです。packrat/PEG はO(n)最悪のケースです。ANTLR はO(n^2)巡回先読み DFA によるものですが、O(n)実際には問題ではありません。GLR は十分に高速です。
ANTLRはAN他のTオル用らアンR反LRではないが、これも好き ;)
率直に言って、80 年代の多くの若いプログラマーと同様に、私は LALR を理解しておらず、ブラック ボックスが好きではありませんでした (今では GLR エンジンの素晴らしさに魅力を感じていますが、それでも LL の方が好きです)。私は商用の LL(k) ベースのコンパイラーを構築し、手作業で構築したものを生成するツールを構築することにしました。ANTLR はすべての人に適しているわけではなく、C++ などのエッジ ケースは GLR で処理した方がよいかもしれませんが、ANTLR が自分の得意分野に合っていると感じる人もたくさんいます。2008 年 1 月以来、ANTLR のバイナリ jar は ANTLRWorks 内で 134,000 回ダウンロードされ、ソース zip は合計で 134,000 回ダウンロードされています (Google Analytics による)。私たちの論文LL(*) に関する多くの実証データ。