是否有 LL(0) 解析器之类的东西？

Question

我在某处看到一个问题询问 LL(0) 和 LR(0) 解析器之间的区别。是否有 LL(0) 解析器之类的东西？如果是这样，他们如何在不查看任何标记的情况下进行解析？

Answer 1

LL(0) 解析器确实会查看标记，但它们不会决定对它们应用哪些产生式。他们只是确定序列是否属于该语言。这意味着每个非终结符必须有一个右侧，并且可能没有递归。

G == ID name lastname
name == STRING
lastname == STRING

# lexer rules
# -----------
ID == [0-9]+
STRING == <unicode>+

请注意，正如@280Z28所提到的，需要一个单独的词法分析器来处理可变长度部分（ID和STRING），否则语法将不是LL(0)。

用于解析具有该语法的输入的产生式序列需要零前瞻。

当解析部分给定输入序列后可以应用多个产生式时，确定性需要先行。

从理论上讲，语法生成一种语言，因此，歧义（有多种方法来导出给定短语）是可以的。在解析中，只有一种方式是语义（意义）方式，这就是我们想要的。

在编程语言的解析中，前瞻是了解接下来要使用哪种语法产生式所需的信息。

在 LL(0) 语言中，没有选择，因此输入序列要么被接受并解析，要么被拒绝。

Answer 2

LR(k) 中的 k 指的是先行标记的数量。您始终至少使用一个令牌来确定要执行的操作。 维基百科页面页面提供了有关此内容的更多信息。

直观上，额外的前瞻符号让您可以使用更多信息做出简化选择，因此它们允许表达更大的语法类而不会发生冲突。

Answer 3

当我学习编译器时，我们从未谈论过它们，尽管我们确实谈论了 LL(1)。 维基百科上没有提及它们。

LL(0) 解析器意味着解析器可以在不知道流中的下一个标记的情况下做出决定。我预计，如果存在具有这种特性的语言，那么它们也是非常罕见的。

Answer 4

您通常不会听说 LL(0) 解析，因为其他答案中给出的原因：非平凡的解析需要查看一些输入。但是，LL(1) 解析器的某些部分确实可以作为 LL(0) 解析器运行。

例如，下面是一个简单的 BNF 语法，只需要在一个产生式中进行前瞻：

S -> A
A -> B
B -> 'a' | 'b'

B 产生式有两个右侧，对应于输入中的两个单独的字符串“a”和“b”。因此解析器必须查看输入才能选择正确的 RHS。

然而，S 和 A 生产都没有任何选择。因此，虽然它们实际上具有关联的 FIRST 集（包含“a”和“b”），但不需要它们的 FIRST 集来做出解析决策，这意味着 S -> 。 A和A-> B 产品是 LL(0) 子语法。因此，优化是忽略这两个非终结符的 FIRST 集。

为了清楚起见，假设输入是字符串“b”。然后解析器可以自动生成自上而下的推导S -> 。 A a 和A-> B 在查看输入之前（这称为自动机）。然后，对于最内层的推导，对于 B，它必须查看输入来决定使用哪个 B 产生式来完成解析树。

这种优化的优点是可以在检查输入时进行错误检测（没有找到输入，或者找不到“a”或“b”以外的输入），而不是在解析其他产生式时进行。如果需要，错误消息不仅可以引用 B 产生式，还可以引用 A 和 S 产生式，因为它们已经生成了。如果在没有优化的情况下检查 S 的第一组，则当已知的全部是 S → S 时，必须报告错误。 A 正在尝试，这对于用户来说上下文信息要少得多。