LALR対LLパーサー

Question

私はlex/yaccを使用していましたが、今ではANTLRに切り替えようとしています。主な関心事は、ANTLRはLALRであるyaccとは違って、LL（*）パーサーであるということです。私はボトムアップを考えるのに慣れており、LL文法の利点が何であるか正確には分かりません。 LL文法は理解しやすく、最近普及していると言われています。しかし、LRパーサはより強力であると思われる。 LLパーザは左回帰を扱うことができませんが、いくつかの回避策があるようです。

LALRよりLL文法の利点は何ですか？誰かが私にいくつかの例を教えていただければ幸いです。有用な記事へのリンクも素晴らしいでしょう。

ご協力いただきありがとうございます。

（私はこれは素晴らしいリソースです参照してください。What advantages do LL parsers have over LR parsers?、それはいくつかの例で、より良いてきたでしょう）

Answer 1

私はパーサをLLするために見る最大の利点は、彼らが理解し、実装するのは簡単であるということです！ recursive descentパーサーに文法によく似たコードを書くことができます。

LRは、一般的に、より強力とみなされ、また、非常に高速ですが、私が知っているいくつかのトレードオフが存在しています

• LRパーサはのみ合成された属性を使用することができます。継承された属性を渡すことはできません。
• LR文法でのアクションは、文法非決定性を引き起こしますが、LLでは起こりません。

ただし、LL（*）も非常に強力であることがわかります。

Answer 2

LRパーサーは、LLパーサーよりも厳密に強力です。さらに、LALRパーサーは、LLパーサーのようにO（n）で実行できます。だからあなたはLRに比べてLLの機能上の利点を見つけることはできません。

したがって、LLの唯一の利点は、LR状態マシンがかなり複雑で理解しにくいことです.LRパーサー自体は特に直感的ではありません。一方、自動的に生成されるLLパーサーコードは、非常に理解しやすくデバッグすることができます。