FOLLOW集合
$ \mathrm{FOLLOW}(X)は$ Xの直後に続くことができる終端記号の集合 $ \epsilonは含まれることはない
規則の根の方(上側の方)から求めていくと良い
定義
$ \mathrm{FOLLOW}(A)=\{a|a\in T\cap\{\$\}, S\$\xRightarrow{\ast}\cdots Aa\cdots\}
記号の意味
$ \$は文末を表す
$ \xRightarrow{\ast} は0回以上ステップの導出 $ a\cdotsは$ aから始まる記号列
ex. $ abc
具体例
以下のような生成規則で$ \mathrm{FOLLOW}(Y)を考える
code:bnf
Z -> d
Z -> X Y Z
Y -> c
X -> Y
X -> a
$ Z\$から始めて、以下のように導出が出来る
$ 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を求めるアルゴリズム
『(環境)5 プログラミング言語処理系』.icon p.153-参考
参考