谁能向我解释在 LL(1) 语法中应该如何使用 FIRST 和 FOLLOW ？我知道它们用于语法表构建，但我不明白如何。
问问题
8086 次
1 回答
48
在 LL(1) 解析器中，解析器通过维护一个工作区来工作，该工作区最初播种到开始符号，后跟字符串结束标记（通常表示为 $）。在每个步骤中，它执行以下操作之一：
- 如果工作区的第一个符号是终端，它将与下一个输入标记匹配（如果不匹配则报告错误。）
- 如果工作区的第一个符号是非终结符，它会预测用什么产生式替换该非终结符。
预测步骤是 FIRST 和 FOLLOW 出现的地方。解析器需要能够猜测，完全基于当前的非终结符和输入的下一个标记，使用哪个产生式。问题是如何做到这一点。
假设当前非终结符是 A，输入的下一个标记是 t。如果你知道 A 的产生式，你会选择应用哪一个？有一个简单的情况需要考虑：如果有一个形式为 A → tω 的产生式，其中 ω 是一些任意字符串，那么您应该选择该产生式，因为您正在查看作为输入的 t 将与前面的 t 匹配生产。
还有一些复杂的情况需要考虑。假设你有一个 A → Bω 形式的产生式，其中 B 是非终结符，ω 是某个字符串。在什么情况下你想猜这个产生？好吧，如果你知道下一个终结符是 at，你就不会想猜测这个产生式，除非你知道 B 可以扩展为一个以终结符 t 开头的字符串（还有另一种情况，我们将在 a第二）。这就是 FIRST 集合的用武之地。在没有 ε 产生式的文法中，某些非终结符 X 的集合 FIRST(X) 是所有终结符的集合，这些终结符可能出现在从 X 派生的某个字符串的开头。如果你有形式 A → Bω 并且你看到非终结符 t，你猜想在 t ∈ FIRST(B) 时精确地使用该产生式；那是，B 可以导出一些以 t 开头的字符串。如果 B 没有导出任何以 t 开头的东西，那么就没有理由选择它，如果 B 确实导出了一些以 t 开头的东西，你会想要做出这个选择，以便最终可以将 t 与它匹配。
当引入 ε 产生式时，事情变得有点棘手。现在，假设您有一个形式为 A → BCω 的产生式，其中 B 和 C 是非终结符，而 ω 是一个字符串。我们还假设输入的下一个标记是 t。如果 t ∈ FIRST(B)，那么我们会选择这个产生式，如上所述。但是，如果 t ∉ FIRST(B) 会发生什么？如果语法中有 ε 产生式，如果 B 可以推导出 ε 和 t ∈ FIRST(C)，我们可能仍然希望选择这个产生式。为什么是这样？如果发生这种情况，这意味着我们可以通过产生 BCω 来匹配 t，然后从 B 产生 ε，留下 Cω 来匹配 t。这是我们可能必须“查看”非终结符的一种情况。幸运的是，这是由 FIRST 集处理的。如果一个非终结符 X 可以产生 ε，那么 ε ∈ FIRST(X)。所以，
到目前为止，我们还没有讨论 FOLLOW 集。他们从哪里进来？好吧，假设我们正在处理非终结符 A，我们看到终结符 t，但是 A 的所有产生式都不能真正消耗 t。那我们怎么办？事实证明，我们仍然有办法吃掉那个 t。请记住，LL(1) 解析器通过维护一个包含字符串的工作空间来工作。有可能我们正在查看的 t 根本不应该与当前的非终结符 A 匹配，而是我们应该让 A 产生 ε，然后让工作区中的一些后续非终结符与 t 匹配。这就是 FOLLOW 集的用武之地。非终结符 X 的 FOLLOW 集，表示为 FOLLOW(X)，是在某个推导中可以立即出现在 X 之后的所有终结符的集合。在选择 A 的生产时，我们添加一个最终规则——如果终结符号 t 在 A 的 FOLLOW 集中，我们选择一些最终会产生 ε 的产生式。这样，A 将“消失”，我们可以将 t 与出现在 A 非终结符之后的某个字符匹配。
这不是对 LL(1) 解析的完整介绍，但我希望它可以帮助您了解为什么我们需要 FIRST 和 FOLLOW 集。有关更多信息，请阅读有关解析的书籍（我推荐Grune 和 Jacobs 的Parsing Techniques: A Practical Guide）或学习编译器课程。作为一个完全无耻的插件，我在 2012-2013 年夏季教授了编译器课程，所有讲座幻灯片都可以在线获得。
希望这可以帮助！
于 2013-12-01T21:13:20.600 回答