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 可以是 epsilon，这意味着 FIRST(U) = FIRST(V) + FIRST(X)

X 可以是 epsilon。

这些 epsilons 有时会非常令人沮丧。

还有一点要说。只有一些规则： - 大写字母是非终结符 - 小写是终结符 - epsilon 用于空规则 - $ 用于记录输入的结尾。

  • 第一(a) = {a}
  • First(A,B) = First(A)，如果 epsilon 不在 First(A) 中
  • First(A,B) = First(A) + First(B)，如果 Epsilon 在 First(A)

  • 第一(A|B) = 第一(A) + 第一(B)

  • 如果 T 是开始符号，Follow(T) 包括 $

  • 如果存在带有 ..TA. 的规则，Follow(T) 包括 First(A)。
  • 如果存在规则 A -> ..T，Follow(T) 包括 Follow(A)
  • 如果存在规则 A -> ..TB 并且 B 可以是 epsilon，Follow(T) 包括 Follow(A)
  • Follow(T) 从不包含 epsilon

例子：

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 回答