关于文法的跟随集

Question

这里定义了http://slkpg.byethost7.com/llkparse.html _k-Sets

“文法中符号串的FOLLOWk集合是文法中一组k长的末端符号串，它们可以跟随在文法中可派生的某种句子形式的符号串之后”

首先，我有一个关于链接下面的例子的方程式，那里是语法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 }？

Answer 1

对于任何k，FOLLOWk(S)都是空的，因为S后面根本不能跟任何东西。我不知道你所说的‘因为这些字符串是可派生的’是什么意思，但是因为它们不能跟在S后面，所以这是无关紧要的。