FIRST集合
$ \mathrm{FIRST}(\gamma)は$ \gammaから導出される文字列の先頭になり得る、全ての終端記号の集合 $ \epsilonも含まれることがある
引数は非終端記号を考えることが多い
$ Xが終端記号なら$ \mathrm{FIRST}(X)は$ \{X\}なので秒でわかるから
規則の下側から求めていくと良い
定義
$ \mathrm{FIRST}(a)=\{a|a\in T,a\xRightarrow{\ast}a\cdots\}
ただし、$ a\xRightarrow{\ast}\epsilonなら$ \mathrm{FIRST}(a)に$ \epsilonを追加する
記号の意味
$ \xRightarrow{\ast} は0回以上ステップの導出 $ a\cdotsは$ aから始まる記号列
ex. $ abc
例えば以下のような文法規則を考える(この規則をこのノート内で「規則1」と呼ぶ)
$ Z → d -- ①
$ Z → X Y Z -- ②
$ Y → c -- ③
$ X → Y -- ④
$ X → a -- ⑤
このとき、$ \gammaを$ X * Yとすると
③④⑤より$ X → c | a
③⑤より$ Y → c
が導かれるので$ \mathrm{FIRST}(X\times Y)=\{a, c\}となる
試す
code:grammar
Z -> d
Z -> X Y Z
Y -> c
X -> Y
X -> a
FIRST集合を求めるアルゴリズム
『(環境)5 プログラミング言語処理系』.icon p.151-参考
FIRSTを手で計算するときは、(略)、開始記号より遠い方から計算するとよい. 『(環境)5 プログラミング言語処理系』.icon p.152
以下のような生成規則がある時
$ X\rightarrow\gamma_1
$ X\rightarrow\gamma_2
ここである終端記号$ Iが、FIRST($ \gamma_1)にも、FIRST($ \gamma_2)にも入っているとすると、関数$ Xは$ Iを入力されたときに、どちらの規則に従えば良いのか判断ができない
複雑になる例
nullableが絡んでくるとFIRST集合は複雑になる
上述した規則1に以下の規則を足したものを考える
$ Y \rightarrow \epsilon
$ \epsilonは空文字を表す
この時、これと規則1の④よりXも空文字を生成できる
ので、$ \gamma=XYZを考えた時
$ \mathrm{FIRST}(Z)\subset \mathrm{FIRST}(XYZ)になることがわかる
なので、FIRST集合を計算する際は、どの記号がnullableを生成することができるかを覚えておかないといけない
書いてて意味わからんくなったので再度復習したい！！！！！！！！！！！！！！mrsekut.icon
参考