LL解析器和递归下降解析器的区别是什么？

Question

LL解析器和递归下降解析器的区别是什么？

parsinggrammarcontext-free-grammarrecursive-descentll-grammar

93

我最近试图自学语言/无上下文语法解析器，大部分内容似乎都很清晰易懂，只有一点不太理解。我特别关注 LL(k) 文法，其中两个主要算法似乎是 LL 解析器（使用堆栈/解析表）和 递归下降解析器（只需使用递归）。

据我所知，递归下降算法可用于所有 LL(k) 文法，可能还有更多，而 LL 解析器可用于所有 LL(k) 文法。明显，递归下降解析器比 LL 解析器容易实现，就像 LL 解析器比 LR 解析器容易实现一样。

因此，我的问题是，使用任何算法时可能会遇到什么优缺点？既然它们可以在相同的文法集上运行并且难以实现，为什么会选择 LL 而不是递归下降呢？

- Noldorin

嘿，你能解释一下吗？你写的似乎是使用堆栈/解析表的LL分析器和仅使用递归的递归下降分析器。这个答案指出所有自顶向下的分析器都是LL分析器。我感到困惑。 - Max Koretskyi

2

@MaximKoretskyi 这绝对不是真的。LL解析器是自顶向下解析器的子集。 - Noldorin

谢谢，你可以把你的答案发到我的问题里吗？ - Max Koretskyi

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Daniel Spiewak · Accepted Answer

LL通常比递归下降更有效的解析技术。事实上，天真的递归下降解析器在最坏情况下实际上是O(k^n)（其中n是输入大小）。一些技术，如备忘录（产生Packrat解析器），可以改善此问题，并扩展解析器接受的语法类别，但总会有一些空间折衷。LL解析器始终是线性时间（据我所知）。

另一方面，您的直觉是正确的，递归下降解析器可以处理比LL更广泛的语法类别。递归下降可以处理任何LL(*)文法（也就是说，无限先见之后和一个小的二义性文法集合）。这是因为递归下降实际上是PEGs或解析器表达式语法的直接编码实现。具体来说，分支运算符（a | b）不是交换的，意味着a | b不等于b | a。递归下降解析器将按顺序尝试每个替代。因此，如果a匹配输入，即使b将匹配输入，它也将成功。这样，可处理经典的“最长匹配”歧义，例如悬空的else问题只需要正确排序分支。

尽管如此，可以使用递归下降实现LL(k)解析器以在线性时间内运行。这是通过基本上内联预测集来实现的，这样每个解析例程就能在常数时间内确定给定输入的适当产生式。不幸的是，这种技术消除了一个可以处理的语法类别。一旦涉及到预测解析，像悬挂的else这样的问题就不再容易解决了。

关于为什么选择LL算法而不是递归下降算法，主要是考虑效率和可维护性。递归下降解析器的实现相对容易，但通常难以维护，因为它们表示的语法在任何声明形式中都不存在。大多数非平凡的解析器用例都使用解析器生成器，例如ANTLR或Bison。对于这样的工具，无论算法是直接编码的递归下降还是表驱动的LL(k)，都不会有太大区别。

值得一提的是，还可以研究递归上升，它是按照递归下降方式直接编码的解析算法，但能够处理任何LALR语法。此外，还有解析器组合子，它是一种将递归下降解析器以函数式方式组合在一起的方法。