Как определить ПЕРВЫЙ набор E в этой грамматике? - PullRequest
1 голос
/ 02 ноября 2009

Интересно, как определить FIRST набор E с грамматикой:

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

Кто-нибудь может дать мне какое-то направление?

Ответы [ 2 ]

3 голосов
/ 02 ноября 2009

Что ж, если вы начинаете с E , то либо первый терминал равен x через производство E & rarr; XYE (так как X всегда производит x), или это через производство E e. Итак, сначала ( E ) = {x, e}.

Это кажется довольно простым ...

0 голосов
/ 02 ноября 2009

Относитесь к правилам формы A -> ... x ... | ... у .... как два правила A -> ... x ... и B -> ... y ...

Форма множества S, изначально содержащая правила формы E-> ....

тогда

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 содержит токены, которые Первый (F).

Это не учитывает пустые производства.

...