grammar - First & Follow Sets 检查简单语法

Question

这是我在课堂测验中遇到的几个问题，只是想验证它们的正确性。语法：

S -> ABC
A -> df | epsilon
B -> f | epsilon
C -> g | epsilon

1.) B 的跟随集包含 g 和 epsilon (T/F)？Ans: F. Follow 集合中没有 epsilon，对吗？（只有 $ aka 输入结束）

2.) 第一组 S 包含 d、f、g 和 epsilon (T/F)？Ans: T. 我说错了，因为我认为 First(S) = First(A)，g 不是其中的一部分。谁是正确的？

Answer 1

1. 你是对的。如果涉及到 epsilon，它将被计入 First 集合，而不是 Follow 集合。如果生产可以结束字符串，则 $ 进入 Follow 集合，而不是 epsilon。
2. 测验是正确的。产生式 S 确实可以以 d、f 和 g 中的任何一个开头，也可以以空字符串开头。考虑输入字符串 g。它匹配S，对吗？A满足空串，B满足空串，C满足g。由于 A、B 和 C 都满足，因此 S 满足。S消耗的第一个字符是g，所以g必须在First(S)中。