grammar - 遵循自递归规则集

Question

好吧，我试图理解跟随集，我想我明白了，除了一件事：

X -> a X
X -> b X
X -> epsilon

按照本页的规则，FOLLOW(X) 应包含 $，即文件结尾字符（规则 1）。然后，按照规则 3，FOLLOW(X) 包含 FOLLOW(X) 的所有内容，这让我的大脑融化了。

对我来说，直觉上，FOLLOW(X) 应该是 {a,b,$}，但是在kfg Edit中尝试这个例子只给了我 {$}。为什么？

Answer 1

FOLLOW(X) 通常是其自身的一个子集，因此规则 3 在应用于右递归产生式时没有任何贡献。

虽然这很容易通过描述来解决，但您的困难可能源于考虑计算算法。为了计算 FOLLOW 集，您可以根据规则迭代地填充它们直到饱和。那么你也不需要为琐碎的情况做任何事情。

然而，没有任何规则可以将 a 或 b 放入 FOLLOW(X)，而且我看不出有任何理由期望它们出现在 FOLLOW(X) 中。语法很简单，可以想象它可以生成的完整语法树集：

                                                                  X
                                                                 /|
                                                 X              / X
                                                /|             / /|
                                  X            / X            / / X
                                 /|           / /|           / / /|
                     X          / X          / / X          / / / X
                    /|         / /|         / / /|         / / / /|
          X        / X        / / X        / / / X        / / / / X
         /|       / /|       / / /|       / / / /|       / / / / /|
 X      / X      / / X      / / / X      / / / / X      / / / / / X
 |     /  |     / /  |     / / /  |     / / / /  |     / / / / /  |
 ε    α   ε    α α   ε    α α α   ε    α α α α   ε    α α α α α   ε    ...

( for α ∊ {a, b} )

他们只允许 X 在最右边，所以没有办法让 X 后跟 a 或 b。