计算 FOLLOW 集合

Question

我的任务是为以下语法计算 FIRST 和 FOLLOW 集：

P ::= S CS .
S ::= ( int , int )
CS ::= C CS | epsilon
C ::= left int | right int | low C

我得到了以下第一组：

FIRST(S) = {'('}
FIRST(C) = {left,right,low}
FIRST(CS) = {left,right,low,epsilon}
FIRST(P) = FIRST(S) = {'('}

我计算了以下集合：

FOLLOW(P) = $ (or empty)
FOLLOW(C) = {left,right,low,'.'}
FOLLOW(CS) = {'.'}
FOLLOW(S) = {left,right,low}

我使用 first 和 follow 集生成器尝试了我的解决方案，我使用 FOLLOW(S) 得到的结果是：FOLLOW(S) = {'.', left, right, low}。生成器的解决方案是否正确，为什么？我使用公式计算了我的解决方案：FOLLOW(S) = FIRST({left,right,low} concat FOLLOW(P)) = {left, right, low}。有人能解释一下为什么我的/生成器的解决方案不正确并检查我是否做对了其他一切吗？我还想知道为什么我没有 int 在任何 first 或 follow 集合中，以及这是否可以在以后构建解析器时使用。谢谢

Answer 1

当你计算 FOLLOW 集合时，你必须小心空产生式。

在这种情况下，CS 有一个空产生式，这意味着 S 后面可能跟在 P → S CS . 中的 .。类似地，C CS 中的 C 可能在生产结束时，因此 C 也可以跟随 .

int 只能出现在 left 或 right 标记之后。它永远不会出现在名义终端的开头，也不会紧跟在非终端之后。因此完全可以预期它不会出现在任何 FIRST 或 FOLLOW 集合中。