LL(1)解析器中FIRST和FOLLOW集的目的是什么？

Question

LL(1)解析器中FIRST和FOLLOW集的目的是什么？

parsingcontext-free-grammarll-grammar

28

有人能解释一下在LL(1)文法中如何使用FIRST和FOLLOW吗？我知道它们被用于语法表的构建，但我不明白具体应该怎么做。

- Kobe-Wan Kenobi

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- templatetypedef · Accepted Answer

在LL(1)解析器中，解析器通过维护一个工作区来工作，最初由开始符号和字符串结束标记（通常表示为$）组成。在每个步骤中，它会执行以下操作之一：

如果工作区的第一个符号是终端符号，则将其与输入的下一个标记进行匹配（或者如果不匹配则报告错误）。
如果工作区的第一个符号是非终端符号，则预测要用哪个产生式替换该非终端符号。

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

假设当前的非终端符号是A，下一个输入标记是t。如果您知道A的产生式，您会选择应用哪个？有一个简单的情况要考虑：如果有一个形式为A→tω的产生式，其中ω是任意字符串，则应选择该产生式，因为您正在查看的输入中的t将与产生式前面的t匹配。

还有一些复杂的情况需要考虑。假设你有一个形式为A→Bω的产生式，其中B是一个非终结符，ω是某个字符串。在什么情况下您想要猜测这个产生式呢？如果您知道下一个终结符号是t，除非您知道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)。为什么会这样呢？如果发生这种情况，这意味着我们可能能够通过从B中产生ε来匹配t，然后留下Cω来匹配t。这是一种需要“查看”非终结符的情况。幸运的是，这可以通过FIRST集处理。如果一个非终结符X可以产生ε，则ε∈FIRST(X)。因此，我们可以使用FIRST集来检查是否需要通过查看FIRST集中是否包含ε来“查看”非终结符。

到目前为止，我们还没有讨论 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的《解析技术：实用指南》）或参加编译器课程。作为一个非常无耻的广告，我在2012-2013年夏季教授了一门编译器课程，所有讲座幻灯片都可以在线获取。

希望这可以帮助您！