かなり長い間悩まされてきた小さな問題があり、オンラインで適切な答えを見つけることができませんでした.
与えられた文法:
S = Sc | Eab | Db | b
D = EDcD | ca | ɛ
E = dE | DY
Y = Ed | Dad | ɛ
たとえば Y の FIRST セット、つまり FIRST(Y) を見つけるには、次のようになると仮定して正しいでしょうか。
FIRST(Y)
= FIRST(Ed) ∪ FIRST(Dad) ∪ FIRST(ɛ)
= FIRST(E) ∪ (FIRST(D)\{ɛ}) ∪ FIRST(ad) ∪ {ɛ}
= FIRST(E) ∪ (FIRST(D)\{ɛ}) ∪ {a, ɛ}
ここで問題は、FIRST(E) と FIRST(D) をどのように見つけるかです。
したがって、FIRST(E) と FIRST(D) の問題は、E と D が互いに参照し合うことです。そして、解決策は、一種の「最小不動点」が必要な場合の通常の方法です。すべてを空にして開始し、安定するまで繰り返します。
つまり、まず最初に、すべての FIRST セットを空のセットに初期化します。ここで、繰り返し、各プロダクションを検討し、非ターミナルの FIRST セットの現在の見積もりが真実であると仮定します。(実際には、それらは通常「過小評価」されます。) LHS の FIRST セットについてプロダクションが何を伝えているかを調べ、それに応じてその非ターミナルの FIRST セットの推定を更新します。これを続けて、すべてのプロダクションを順番に処理し、すべてのプロダクションを調べて見積もりが変わらなくなるまで続けます。その時点で、完了です。
この場合は、次のようになります (もちろん、私が間抜けしていないと仮定して)。最初のパスでは、S: {b}、D: {c,ɛ}、E: {c,d}、Y: {c,d,ɛ} が連続して生成されます。2 番目は、S: {b,c,d}、D: {c,d,ɛ}、E: {c,d,ɛ}、Y: {c,d,ɛ} を連続して生成します。3番目はそれらのいずれも変更しないため、これらが最終的な答えです。