遵循设定的程序

Question

我知道有很多关于此的问题，但我仍然无法找到我要找的东西。

至于为给定语法查找 Follow 集的过程，我已经看过很多版本，但让我们坚持给定的那个 here，因为它是我见过的那个见得最多。我会把它复制到这里，这样你就不必打开它了：

First put $ (the end of input marker) in Follow(S) (S is the start symbol)

If there is a production A → aBb, (where a can be a whole string) then everything in FIRST(b) except for ε is placed in FOLLOW(B).

If there is a production A → aB, then everything in FOLLOW(A) is in FOLLOW(B)

If there is a production A → aBb, where FIRST(b) contains ε, then everything in FOLLOW(A) is in FOLLOW(B)

问题 1: 规则 2 和 4 是相互排斥的还是它们可以同时应用 "iteration"（这样写是因为这实际上会成为我的问题之一）？我在这里的意思是它们在第一部分中匹配，也就是说它们都应用了 "If there is a production A -> aBb".

这是否意味着如果我遇到产生式 A -> aBb 使得 ε 在 First(b) 中，我应该应用第二条和第四条规则，还是只应用第四条？

问题2：'a'和'b'到底是什么？除了规则 2 中的部分内容外，它没有在其他任何地方正式指定，它表示 "a can be a whole string"。规则 3 和 4 呢？实际上，让我进一步概括这个问题。如果我有以下形式的作品： A -> abcd....efgBxyzw..... 可以应用这些规则吗？也就是说，这些规则是否要求产生式的右侧仅包含三个元素？或者可以这样解读：

A -> abcd...ef [gBx] yzw.... ，其中 gBx 部分现在对应于规则 2 和 4 中的 aBb 部分。或者这是否仅适用于规则 2 和只有 'a' 部分，如：

A -> abcd....ef[gBx] , 左边可以是一整串而右边必须是一个符号?

注意：方括号不是语法的一部分，我只是用它们来分隔内容，以便解释我的意思。

问题 3：这个过程是确定性的吗？问题是，他们没有提到我们应该这样做多长时间以及以何种顺序进行。好吧，实际上，我看到一些消息来源说 'as long as there is anything left to add'。我们应该按什么顺序来做这件事？我想我们只是随机制作并尽可能长时间地应用它们。我们是否应该尝试从现有的语法规则中推导出更多的产品？或者程序是为 'catch' 间接设计的？这里还有一件非常令人困惑的事情。让我们看看以下场景：

我正在看一部作品，通过应用规则，我确定 Follow(A) 中的所有内容都应该进入 Follow(B)。让我们非正式地将其写为：

关注(B) += 关注(A)

让 Follow(A) 现在（根据我的最新计算）包含一些元素，例如 {x, y, z}。我应该立即写 Follow(B) = {..., x, y, z} 还是应该等到最后？为什么？好吧，如果在几个作品之后，我遇到一个以任何方式修改 Follow(A) 的作品，假设它添加了 'w'，那么现在 Follow(A) = {x, y, z , w}。这是否意味着，假设我已经立即编写 Follow(B) = {..., x, y, z} 而不是等待，我现在需要返回那里并向其添加 'w'，或者该过程是否应该 'catch' 在一些后来的迭代中 'w'？

提前致谢。

Answer 1

问题 1: 不，它们不能在同一次迭代中应用。那是因为里面的except for ε部分的意思就是如果有没有ε.

问题 2： 'a' 和 'b' 是 α (alpha) 和 β (beta)。它们都代表多个符号。（比如 A → Z b B n m 可以是 A → α B β；Z b 可以缩短为 α，n m 可以缩短为 β）。所以不，它不仅限于 rhs 上的 3 个符号。

问题 3: 是的，这是确定性的。你所做的是，你有一个地图（比如 std::unordered_map 来存储跟随集），然后你开始一个 while 循环——条件是在当前迭代期间对跟随集进行了更改。在循环体内，您放置了规则。一个例子：

follow_sets = {} # map
changes = True
while changes:
    changes = False
    # follow set rules
    # once a rule is applied, and things are added to the follow sets map, set changes to True

现在，您的规则集不错，但描述性不够。这是我用来构建跟随集的规则集：

Follow(START) has $

If A → α B β (Provided β ≠ ε):
Follow(B) → First(β)

If A → α B:
Follow(B) → Follow(A)

If A → α B β (provided β → ε):
Follow(B) → { First(β) - ε } ∪ First(A)

遵循设定的程序

The follow set procedure

compiler-construction

parsing