LL(0)解析器是否存在？

Question

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

我在某处看到有人提出了关于LL（0）和LR（0）解析器差异的问题。是否存在LL（0）解析器？如果存在，它们是如何在不查看任何标记的情况下进行解析的呢？

- Can't Tell

---

LL(0)和LL(1)语言应该是相同的。语言定义是集合论，但解析在计算理论和算法学中进行。在集合论中，你可以以几乎任何方式定义一种语言，但知道是否可能构建一台机器，在合理的时间内确定一个序列是否属于该语言，这是计算理论的核心。 - Apalala

@Apalala- 一个LL(0)语言可能有一个非LL(0)的语法。 - templatetypedef

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) 语言中，没有选择，所以输入序列要么被接受并解析，要么被拒绝。

- Apalala

---

这样的语法只有一个解析器规则吗？所有其他规则都是词法分析器规则吗？这就是为什么它不需要检查应用哪个产生式的原因吗？ - Can't Tell

@不能确定。不是那么复杂的语法问题。对于 ASCII 中的固定列、固定格式表的语法将是 LL(0)，但语法将有更多推导式。请参阅修改。 - Apalala

你的示例语法由于使用了正闭包而不是LL(0)。为了说明操作在预先词法分析的标记上进行，需要将语言限制为固定长度的标识符和字符串，或者需要将“词法分析器”规则分离到一个单独的语法中，该语法不是LL(0)。 - Sam Harwell

@280Z28 / Sam。已修改！ - Apalala

Answer 2

LR(k)中的k指的是前瞻标记（lookahead tokens）的数量。您总是至少使用一个标记以确定要执行的操作。维基百科页面提供了更多关于此的信息。链接 直观地说，额外的前瞻符号使您能够更多地使用信息进行约简选择，因此它们允许表达较大的语法类别而不会产生冲突。

- MikeP

---

不，你并不总是需要向前查看。如果要应用的生产规则已知，则只需解析当前标记。 - Apalala

我并没有说你需要一个向前看，但你确实需要消耗至少一个标记，否则你永远无法在标记流中前进。 - MikeP

我的讲座笔记上写着：“它们（LR（0））不使用当前标记来执行规约。”这意味着根本没有令牌，而不仅仅是向前看？ - Jonathan.

这个问题是关于LL解析器的，而你在回答中提到了LR解析器。 - Diwakar Moturu

Answer 3

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

一个LL(0)解析器意味着解析器可以在不知道流中下一个标记的情况下做出决策。如果具有该属性的语言存在，我会认为它们非常罕见。

- ngephart

---

一个LL(0)解析器适用于没有决策的语法。 - Apalala

有道理。我想到了更大的情况，但你的例子很好地展示了出来，我认为。 - ngephart

一个带有回溯的自顶向下解析器可以是LL(0)的，对吧？它不需要看到向前看符号，可以逐个扩展产生式以匹配当前终结符，并在失败时进行回溯，非常类似于暴力搜索。 - rsonx

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的FIRST集合没有进行优化，则当尝试S -> A时只知道这些信息，用户的上下文信息就少得多，必须在这时报告错误。

- David Spector