N 0 thing:有LL(0)解析器吗(ll0)-边看边学

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

LL（0）解析器确实会查看令牌，但它们不会决定要在其上应用哪些产品。他们只是确定序列是否属于该语言。这意味着每个非终端符号必须具有单个右侧，并且可能没有递归。

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

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

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

如果在解析了给定输入序列的一部分之后可以应用多个产品，则需要进行确定性预测。

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

在解析编程语言时，前瞻是了解下一步使用哪种语法产品所需的信息。

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

LR (k) 中的 k 指的是lookahead令牌的数量。您总是使用至少一个令牌来确定要执行的操作。Wikipedia page页面有关于此的更多信息。

直观上，额外的前瞻符号让您可以使用更多信息进行缩减选择，因此它们允许在没有冲突的情况下表达更大的语法类。

当我使用编译器时，我们从未谈论过它们，尽管我们确实谈论过 LL（1）。Wikipedia上没有提到它们。

LL（0）解析器意味着解析器可以在不知道流中的下一个令牌的情况下做出决定。我希望如果具有该属性的语言存在，它们非常罕见。

您通常不会听说 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-& gt;A 和 A-& gt;B 产品是 LL（0）子语法。因此，优化是忽略这两个非终端的 FIRST 集。

为了明确这一点，假设输入是字符串 'b'。然后解析器可以自动在查看输入之前生成自上而下的派生 S-& gt;A a 和 A-& gt;B（这称为自动机）。然后，对于最内层的派生，对于 B，它必须查看输入以决定使用哪个 B 生产来完成树。

这种优化的一个优点是，错误检测（没有发现输入，或者除了 'a' 或 'b' 之外的输入）可以在检查输入的点上完成，而不是在解析其他产品时完成。如果需要，则错误消息不仅可以引用 B 产品，还可以引用 A 和 S 产品，因为它们已经被生成。如果在没有优化的情况下对所有 S 进行了检查，则将对 S 进行第一次设置

本站系公益性非盈利分享网址，本文来自用户投稿，不代表边看边学立场，如若转载，请注明出处