parsing - この文法で E の最初のセットを決定する方法は?

Question

FIRST文法で Eのセットを決定する方法を知りたい:

E -> XYE | e
X -> x
Y -> y

誰かが私に指示を与えることができますか？

Answer 1

Eで開始すると仮定すると、最初の端末はE → XYE生成による x ( Xは常に x を生成するため) であるか、E →e 生成による e です。したがって、First( E ) = {x,e} です。

それはかなり簡単に思えます...

Answer 2

A -> ...x... | 形式の規則を扱います。...y .... 2 つのルールとして A -> ...x... および B -> ...y...

最初にフォーム E-> .... のルールを含むセット S を形成します。

それから

Set a set P to empty.
Set a set F to empty.
Repeat until S is empty 
  Choose element of S, and call it R
  If R is in P, remove R from S
  Elsif R is of the form  A -> b ... 
    then { add b to F,
           add R to P,
           remove R from S}
  Else (R is the form A -> B ...)
     then  { place all rules of form B -> ... into S
             remove R from S}
End

ループが終了すると、F には First(F) であるトークンが含まれます。

これは、空のプロダクションを考慮していません。