我在某处看到一个问题，询问 LL(0) 和 LR(0) 解析器之间的区别。有没有像 LL(0) 解析器这样的东西？如果是这样，他们如何在不查看任何令牌的情况下进行解析？
问问题
23181 次
4 回答
26
LL(0) 解析器确实会查看令牌，但他们不决定对它们应用哪些产生式。他们只是确定序列是否属于该语言。这意味着每个非终结符号都必须有一个右手边，并且可能没有递归。
G == ID name lastname
name == STRING
lastname == STRING
# lexer rules
# -----------
ID == [0-9]+
STRING == <unicode>+
请注意，正如@280Z28 所提到的，需要一个单独的词法分析器来处理可变长度部分（ID和STRING），否则语法将不是LL(0)。
用于使用该语法解析输入的产生式序列需要零前瞻。
当在解析给定输入序列的一部分后可以应用多个产生式时，确定性需要前瞻。
从理论上讲，语法会产生一种语言，并且，在这方面，歧义（有不止一种方法来导出给定的短语）是可以的。在解析中，只有一种方式是语义（意义）方式，这是我们想要的。
在解析编程语言时，前瞻是知道接下来要使用哪种语法产生所需的信息。
在 LL(0) 语言中，没有选择，因此输入序列要么被接受和解析，要么被拒绝。
于 2011-03-09T23:58:02.327 回答
3
LR(k) 中的 k 指的是前瞻令牌的数量。您始终使用至少一个标记来确定要执行的操作。维基百科页面页面对此有更多信息。
直观地说，额外的前瞻符号让您可以使用更多信息做出归约选择，因此它们允许表达更大类的语法而不会发生冲突。
于 2011-03-09T23:57:29.823 回答
2
当我学习编译器时，我们从未谈论过它们，尽管我们确实谈论过 LL(1)。维基百科上没有提到它们。
LL(0) 解析器意味着解析器可以在不知道流中的下一个标记的情况下做出决定。我希望如果存在具有该属性的语言，它们将非常罕见。
于 2011-03-09T23:57:29.387 回答
1
您通常不会听说 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 -> A 正在尝试时，必须报告错误，这对于用户来说是更少的上下文信息。
于 2020-07-23T16:12:15.367 回答