5

チューターから提供された例の 1 つがわかりません。

例

S ::= aBA | BB | Bc
A ::= Ad | d
B ::= ε

我々は持っています

FIRST(B) = FIRST(ε)
         = {ε}

FIRST(A) = FIRST(Ad) ∪ FIRST(d)
         = FIRST(A) ∪ {d}
         = {d}

FIRST(S) = FIRST(aBA) ∪ FIRST(BB) ∪ FIRST(Bc)
         = FIRST(a) ∪ (FIRST(B)\{ε}) ∪ FIRST(B) ∪ (FIRST(B)\{ε) ∪ FIRST(c)
         = {a, ε, c}

FIRST(S) の計算に FIRST(B) があるのはなぜですか? そうじゃないかな

(FIRST(B)\{ε)?

FIRST(S) の計算で A が欠落しているのはなぜですか?

4

1 に答える 1

11

このページでは、FIRST (および FOLLOW) セットを導出するための機械的なルールを示します。これらのルールの背後にあるロジックと、それらがあなたの例にどのように適用されるかを説明しようとします.

最初のセット

FIRST(u)は、 の完全な派生で最初に出現する端末のセットですu。ここuで、 は端末と非端末のシーケンスです。言い換えると、FIRST(u)セットを計算するとき、 から派生できる文字列の最初の端末である可能性がある端末のみを探しますu。

FIRST(アバ)

定義を考えると、 がに、次に にFIRST(aBA)還元されることがわかります。これは、およびプロダクションが何であれ、がターミナルであるため、から派生したものでは常にターミナルが最初に発生し、そのシーケンスの先頭から削除できないためです。FIRST(a)aABaaBAa

ファースト(紀元前)

ここではスキップFIRST(BB)して に進みFIRST(Bc)ます。は非終端なので、ここでは状況が異なりますB。FIRST(B)最初に、 にあるものは にもあると言いFIRST(S)ます。残念ながら、シナリオが発生する可能性があるため、問題を引き起こすものがFIRST(B)含まれていますε

   FIRST(Bc)
-> FIRST(εc)
=  FIRST(c)
=  c

ここで、矢印は可能な派生/還元です。FIRST(Xu)したがって、一般に、εは にありFIRST(X)、 は に等しいと言い(FIRST(X)\{ε}) ∪ FIRST(u)ます。これにより、計算の最後の 2 つの項が説明されます。

ファースト(BB)

上記の規則を使用して、FIRST(BB)として導出できるようになりまし(FIRST(B)\{ε}) ∪ FIRST(B)た。同様に、計算FIRST(BBB)していた場合、次のように削減します。

  FIRST(BBB)
= (FIRST(B)\{ε}) ∪ FIRST(BB)
= (FIRST(B)\{ε}) ∪ (FIRST(B)\{ε}) ∪ FIRST(B)

注目すべきは、FIRST セットの計算中、一連のシンボルの最後のシンボルから空の文字列が削除されることは決してないということです。これは、この時点で空の文字列が正当な可能性であるためです。これは、あなたの例で考えられる派生で見ることができます:

   S
-> BB
-> εε
-> ε

うまくいけば、上記のすべてからFIRST(B)、計算に表示されない理由がわかるでしょうFIRST(A)。

于 2013-10-28T15:13:23.270 に答える