grammar - 构建跟随集

Question

在为给定语法创建第一组时，我注意到在我的算法参考中没有描述的场景。

即，如何使用这样的规则计算非终结符的跟随集。

<exp-list_tail> --> COMMA <exp> <exp-list_tail>

<..> 包围的表达式是非终结符，COMMA 是终结符。
我最好的猜测是我应该将空字符串添加到后续集合中，但我不确定。

通常，对于非终结符位于生产规则末尾的情况，您只需计算左侧非终结符的跟随列表，但您可以看到这将是一个问题。

Answer 1

要正确回答这个问题，了解你的整个语法会很有帮助。但是，这是一个一般性答案的尝试：

以下是计算跟随组的算法：

初始化所有跟随组到 {}，除了初始化到 {$} 的 S。
虽然有变化，但对于每个 A∈V 做：
  对于每个 Y → αAβ 做：
    follow(A) = follow(A) ∪ first(β)
    如果 β ⇒* ε，也做：follow(A) = follow(A ) ∪ 跟随(Y)

请注意，这是一个确定性算法，它会给您一个答案，仅取决于您的（整个）语法。

具体来说，我不认为这个特定的规则会影响<exp-list_tail>' 跟随集（它可以，但可能不会）。