13

我知道 LL 与 LR 解析器的基本区别。我也知道 GLR、SLR 和 LALR 都是 LR 解析器的扩展。所以我更详细的问题是......

给定一个 LL(*) 解析器和 LR 解析器的任何变体，是否有任何语言可以用一种语言来描述，而不能用另一种语言来描述？或者更简单地说，是否有任何特性或属性都无法表达？

作为一个具体的例子。如果我要使用 LL(*) 解析器创建一种语言，我是否会遇到想要添加到我的语言中的所需功能/属性，而这只有通过 LR 解析器才能实现（反之亦然）？

4

7 回答 7

11

以下是一些观点，您可以将它们视为点和对位：

于 2011-03-29T02:39:09.897 回答
6

有一些语法不能被“重写”以被 LL 解析器解析，而这些语法可以被 LR 解析器解析。一个例子：给定一个用减法构造术语的简单语法：

S -> S - S | num

您显然在这里有左递归，这是 LL 解析器无法处理的。为了使这个语法可以被 LL 解析，你必须消除左递归：

S -> num S'

S' -> - num S' | epsilon

现在你的 LL 解析器可以处理这个语法了。但是当为像 4 - 2 -1 这样的术语构建语法树时，在树上操作的深度优先搜索会给你 4 - (2 - 1) = 3 而不是 (4 - 2) - 1 = 3如您所料。

这样做的原因是，您必须在语法中使用左递归规则来处理左关联运算符（如减法）。但是左递归规则不能被 LL 解析器处理。

所以在这里你有一类语言不能被 LL 处理。

于 2011-05-04T12:16:55.390 回答
6

当然。LL 解析器不能处理任何带有左递归的文法。固定 k 的 L(AL)R(k) 解析器将无法解析 LL( * ) 解析器可以处理的某些内容，因为 k<*.

于 2011-03-29T02:33:49.803 回答
6

您可能会在 Wikipedia 中发现这一段很有趣，其中说 LL(*) 语法是 LR(k) 语法的子集： http ://en.wikipedia.org/wiki/Context-free_grammar#Restrictions 所以您可以解析更多语言使用LR解析方法。

于 2011-04-02T04:58:36.813 回答
2

LR 解析器可以接受比 LL 更大的语言类别。在 LL(k) 和 LR(k) 中，k 表示它需要知道的前瞻符号的数量，以便它可以应用适当的产生/减少。k 越大，解析表越大。所以 k 不仅限制了 LR 解析器，它也限制了 LL 解析器。LR 解析器可以接受更大类语言的原因是因为左递归在使用 LL 解析器时会出现问题。但这并不完全正确，因为直接递归是可解的，这意味着您可以将文法重写为 LL 文法。直接递归类似于 A -> Abc。当你有间接递归时，你现在可能知道它的样子，那么你就有问题了。LR 解析器可以解决这个问题，因为它们以自下而上的方式生成解析树。您将不得不更深入地研究 LR 解析，以了解为什么会这样。但是，LR 解析器也不是很强大，它们也有局限性。有些语法很难消化，k 因子也无济于事。对于这种语法，需要 GLR 解析器，它实际上模拟 LR(k) 解析器，但在产生/归约歧义发生时使用回溯来分析整个解析空间。

于 2011-09-21T05:21:35.117 回答
0

LR (1) 解析器比 LL (1) 识别更多的文法，因为它不需要我们重写文法来去除左递归和公因子。

但是，给定一个明确的语法，我们总是可以去除左递归和公因数，因此最终它们都可以解析相同的语言。

如果有人对此有疑问，我挑战你给出一个明确的语法，LL(1) 无法解析而 LR(1) 可以，也就是说，不能重写以删除左递归和常见因素

于 2021-04-19T09:11:31.163 回答
-1

LL 解析理论上是 O(n^4)，或者非常慢。LR 解析更快，O(n^3)，或者相当慢。 https://en.wikipedia.org/wiki/Top-down_parsing

虽然我很想看到这一点的证据。

于 2018-02-14T23:24:38.267 回答