parsing - LL(1) Parsing -- First(A) with Recursive First Alternatives

Question

我如何将 FIRST() 规则应用于生产，例如：

A -> AAb | 抗体 | s

其中 A 是非终结符，b,s 是终结符。

备选方案 1 和 2 的 FIRST(A) 将再次成为 A，但这会以 FIRST 的无限应用而告终，因为我需要一个终端来获取 FIRST 集？

Answer 1

要计算 FIRST 集，您通常执行定点迭代。也就是说，您从一小组值开始，然后迭代地重新计算第一个集合，直到集合收敛。

在这种情况下，您首先要注意产生式 A → s 意味着 FIRST(A) 必须包含 {s}。所以最初你设置 FIRST(A) = {s}。

现在，您遍历 A 的每个产生式并根据迄今为止计算的 FIRST 集的知识更新 FIRST。例如，规则

A→AAb

意味着您应该更新 FIRST(A) 以包含 FIRST(AAb) 的所有元素。这不会导致 FIRST(A) 发生变化。然后你访问

A → 抗体

您再次更新 FIRST(A) 以包括 FIRST(Ab)，这又是一个无操作。最后，您访问

A → s

并且由于 FIRST(A) 已经包含 s，这不会导致任何变化。

由于在此迭代中没有任何变化，因此您最终会得到 FIRST(A) = {s}，这确实是正确的，因为从 A 开始的任何推导最终都会产生一个s作为其第一个字符。

有关更多信息，您可能会发现这些讲座幻灯片很有用（这里是第二部分）。他们详细描述了自顶向下解析的工作原理以及如何迭代计算 FIRST 集。

希望这可以帮助！

Answer 2

Answer 3

正如您已经意识到的那样，您的语法规则已经左递归，并且 LL 解析器无法使用左递归解析语法。

所以你需要首先摆脱左递归，然后你应该能够计算规则的第一组。