FOLLOW集合
\epsilonは含まれることはない
規則の根の方(上側の方)から求めていくと良い
定義
\mathrm{FOLLOW}(A)=\{a|a\in T\cap\{\$\}, S\$\xRightarrow{\ast}\cdots Aa\cdots\}
記号の意味
Sは開始記号
Tは終端記号
\$は文末を表す
\xRightarrow{\ast} は0回以上ステップの導出
a\cdotsはaから始まる記号列
ex. abc
具体例
以下のような生成規則で\mathrm{FOLLOW}(Y)を考える
bnfZ -> d
Z -> X Y Z
Y -> c
X -> Y
X -> aZ\$から始めて、以下のように導出が出来る
Z\$\Rightarrow XYZ\$ \Rightarrow XYd\$
Z\$\Rightarrow XYZ\$ \Rightarrow YYd\$ \Rightarrow Ycd\$
Z\$\Rightarrow XYZ\$ \Rightarrow XYXYZ\$ \Rightarrow XYaYZ\$
となるので、Yの直後に出てくるものを見てみると、d,c,aの3つ
なので、\mathrm{FOLLOW}(Y)=\{d,c,a\}
FOLLOWを求めるアルゴリズム
参考