parsing - LL(1) 解析器中 FIRST 和 FOLLOW 集的目的？

Question

谁能向我解释在 LL(1) 语法中应该如何使用 FIRST 和 FOLLOW？我知道它们用于语法表构造，但我不明白如何。

Answer 1

在 LL(1) 解析器中，解析器通过维护一个工作区来工作，该工作区最初被播种到开始符号，然后是字符串结束标记(通常表示为 $)。在每一步，它执行以下操作之一:

如果工作区的第一个符号是终端，则 匹配 它针对输入的下一个标记(如果不匹配则报告错误。)

如果工作区的第一个符号是非终结符，则 预测 用什么生产代替那个非终结符。

预测步骤是 FIRST 和 FOLLOW 出现的地方。解析器需要能够纯粹基于当前非终结符和输入的下一个标记来猜测要使用的产生式。问题是如何做到这一点。

让我们假设当前的非终结符是 A，输入的下一个标记是 t。如果你知道A的作品，你会选择申请哪一个？有一个简单的情况需要考虑:如果存在形式 A → tω 的产生式，其中 ω 是某个任意字符串，那么您应该选择该产生式，因为您作为输入查看的 t 将匹配前面的 t生产。

还有一些复杂的情况需要考虑。假设你有一个 A → Bω 形式的产生式，其中 B 是一个非终结符，ω 是一些字符串。在什么情况下你想猜这个生产？好吧，如果您知道下一个终结符是 at，您就不会想猜测这个产生式，除非您知道 B 可以扩展为以终结符 t 开头的字符串(还有另一种情况，我们将在第二)。这就是 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)。因此，我们可以使用 FIRST 集通过查看 ε ∈ 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 集。有关更多信息，请阅读有关解析的书(我推荐 Parsing Techniques: A Practical Guide by Grune 和 Jacobs)或参加有关编译器的类(class)。作为一个完全无耻的插件，我在2012-2013年夏季和 all of the lecture slides are available online教了一门编译器类(class)。 .

希望这可以帮助!