1

この文法のために作成した FIRST と FOLLOW のセットが正しいかどうかを知りたい

S -> TS'
S' -> +TS' | -TS' | epsilon
T -> UT'
T' -> *UT' | /UT' | epsilon
U -> VX
X -> ^U | epsilon
V -> (W) | -W | W | epsilon
W -> S | number 

FIRST(S) = FIRST(T) = FIRST(U) = FIRST(V) = FIRST(W) = { ( , - , + , number ,     epsilon } 
FIRST(T') = { *, / , epsilon} 
FIRST(S') = { + , - , epsilon}
FIRST(X) = { ^ , epsilon}

FOLLOW(S) = FOLLOW(S') = FOLLOW(V) = {$}
FOLLOW(T) = {+ , - , $ }
FOLLOW(T')= {+, - , $ }
FOLLOW(U) = FOLLOW(X) = { * , / , + , - ,$ }
FOLLOW(W) = { ) , $ }
4

1 に答える 1

5

ただの発言：

あなたが言った：

FIRST(U) = FIRST(V)

これは正しいですが、V はイプシロンにすることができます。これは、FIRST(U) = FIRST(V) + FIRST(X) を意味します。

そして、X はイプシロンにできます。

これらのイプシロンは、非常にイライラすることがあります。

もう少し言いたいことがあります。いくつかのルール: - 大文字は非終端記号です - 小文字は終端記号です - イプシロンは空の規則に使用されます - $ は入力の終わりを示すために使用されます。

  • 最初(a) = {a}
  • First(A,B) = First(A)、イプシロンが First(A) にない場合
  • First(A,B) = First(A) + First(B)、First(A) のイプシロンの場合

  • 最初(A|B) = 最初(A) + 最初(B)

  • T が開始記号の場合、Follow(T) には $ が含まれます

  • ..TA. のルールがある場合、Follow(T) には First(A) が含まれます。
  • ルール A -> ..T がある場合、Follow(T) には Follow(A) が含まれます。
  • Follow(T) には、ルール A -> ..TB があり、B がイプシロンである場合、Follow(A) が含まれます。
  • Follow(T) にはイプシロンは含まれません

例：

E  = TE'
E' = +TE'|epsilon
T  = FT'
T' = *FT' | epsilon
F = (E) | id

First(E)   = First(T) = First(F) = {(, id}
First(E')  = {+, epsilon}
First(T)   = First(F) = {(, id}
First(T')  = {*, epsilon}
First(F)   = {(, id}

Follow(E)  = {$, )}
Follow(E') = Follow(E) = {$, )}
Follow(T)  = First(E') + Follow(E') = {$, ), +}
Follow(T') = Follow(T) = {$, ), +}
Follow(F)  = First(T') + Follow(T') + Follow(T) = {*, $, ), +}

あなたの文法ははるかに複雑で、少し奇妙です (文法に誤りがないことを確信していますか?) が、規則に従うことはできます。

于 2009-03-14T12:46:31.323 に答える