parsing - LALR vs LL パーサー

Question

これまで lex/yacc を使用していましたが、ANTLR に切り替えようとしています。主な懸念事項は、LALR である yacc とは異なり、ANTLR が LL(*) パーサーであることです。私はボトムアップで考えることに慣れていて、LL 文法の利点が正確にはわかりません。最近は LL 文法の方が理解しやすく、人気が高いと言われています。しかし、LR パーサーの方が強力なようです。たとえば、LL パーサーは左再帰を処理できませんが、いくつかの回避策があるようです。

では、問題は、LALR に対する LL 文法の利点は何ですか? 誰かが私にいくつかの例を教えていただければ幸いです。役に立つ記事へのリンクも素晴らしいでしょう。

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

(これは素晴らしいリソースだと思います: LL パーサーは LR パーサーに対してどのような利点がありますか? ですが、いくつかの例があればもっと良かったでしょう。)

Answer 1

LR パーサーは LL パーサーより厳密に強力であり、さらに、LALR パーサーは LL パーサーのように O(n) で実行できます。したがって、LR よりも LL の機能的な利点は見られません。

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

Answer 2

LL パーサーの最大の利点は、理解と実装が非常に簡単なことです。文法に厳密に一致するコードを使用して、再帰降下パーサーを手動で作成できます。

LR は一般に、より強力で、はるかに高速であると考えられていますが、私が知っているいくつかのトレードオフがあります。

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

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