Comment déterminer le PREMIER ensemble de E dans cette grammaire?

Question

Je me demande comment déterminer le FIRST ensemble de E avec la grammaire:

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

Quelqu'un peut-il me donner une certaine direction?

Answer 1

Eh bien, en supposant que vous êtes en commençant par E , alors soit la première borne est x via le E → Xye production (depuis X produit toujours x) ou il est e via le E → e production. Donc d'abord (E) = {x, e}.

Cela semble assez simple ...

Answer 2

règles Traiter de la forme A -> ... x ... | ... y .... comme deux règles A -> ... x ... et B -> ... y ...

Former un ensemble S contenant initialement des règles de forme E->. ...

puis

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 

lorsque la boucle se termine, F contient les jetons qui sont les premières (F).

Ceci ne prend pas en compte les productions vides.