\mathrm{FIRST}(\gamma)は\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を追加する

記号の意味

Tは終端記号

\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\}となる

試す

下にも書いたが、ここで試せる

FIRST集合を求めるアルゴリズム

p.151-参考

再帰下降構文解析が出来ない例

以下のような生成規則がある時

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を生成することができるかを覚えておかないといけない

書いてて意味わからんくなったので再度復習したい！！！！！！！！！！！！！！

文法規則からFIRST集合とFOLLOW集合を求めるやつ

参考