parsing - 关于 FOLLOW 语法集

Question

“语法中符号串的 FOLLOWk 集是语法中的一组 k 长度终端符号串，它可能遵循语法中可导出的某种句子形式的符号串”

首先，我对链接下的示例有一个疑问，那里是 Grammar 4.2

     A  -->  a <Baa> a a              
     A  -->  b <Bba> b a
 <Baa>  -->  b
 <Baa>  -->
 <Bba>  -->  b
 <Bba>  -->

据说：

FIRST2 ( A ) = { aa, ab, bb }
FIRST2 ( <Baa> ) = { epsilon }
FIRST2 ( <Bba> ) = { epsilon }

FOLLOW2 ( <Baa> ) = { aa }
FOLLOW2 ( <Bba> ) = { ba }

但我问自己为什么不

FIRST2 ( <Baa> ) = { epsilon, b }
FIRST2 ( <Bba> ) = { epsilon, b }

因为从例如也可以导出单个 b 。

此外对于语法

S -> X 
X -> aX
X -> aY
Y -> epsilon

我不确定这个集合

FOLLOW2(S)

它是空的，{ epsilon } 还是 { a, aa } 因为这些字符串是可推导的，还是因为 S 之后的内容很重要，并且因为 S 是起始符号，所以它后面什么都没有，但是我应该写 FOLLOW2(S) = \empyset 或 FOLLOW2(S) = { epsilon }？

score 0 · Accepted Answer

对于任何 k，FOLLOWk(S) 都是空的，因为根本没有任何东西可以跟随 S。我不知道您所说的“因为这些字符串是可推导的”是什么意思，但是由于它们不能遵循 S ，因此无论如何都无关紧要。

1 回答 1