构造规则:
FIRST集:
(1)A-->αβ𝛼𝛽,若α𝛼是终结符,那么FIRST(A)=α𝛼,若α𝛼是非终结符,那么FIRST(A)=FIRST(α𝛼)
(2)若A-->ε𝜀,那么FIRST(A)=ε
举个例子:
1.First(E)
E->TE′𝐸′,最左边为T,又因为T->FT′𝑇′,最左边为F,F->(E)|i,则最左边为{(,i }
2.First(T):只需要看符号串最左边的符号,即=First(T)
T->FT′𝑇′,最左边为F,F->(E)|i,则最左边为{(,i }
3.First((E)):也只需要看最左边的
First((E))={ ( }
4.First(i):终结符的first集就是它本身
First(i)={i}
以此类推:
再举一个例子:
最后得到:
LARST集:
(1)# Follow (S),S为识别符号,即 ”#“要放在开始符号"S"的 Follow集中
(2)若存在规则U->xWy,First(y)-{}(空串) Follow(W)
(3)若存在规则U->xW或U->xWy,其中y能广义推导出(空串),则Follow(U)Follow(W)
举个例子:
Follow(E)
首先E是开始符号,Follow(E)={#}
在"->"右边找E,看E后面跟的所有终结符号,这里F->(E)| i,E的右边为")",终结符的First集就是它本身(对应第二条规则)
所以Follow(E)={#,)}
Follow(T)
首先找”->“的右边,看T后面跟的所有终结符号
E->TE′ 𝐸′->+TE′|ε
T后面跟的是E′ E′的First集是{+,ε},将ε去掉,最后得到{+},又因为E′可以推导出ε空串(对应第三条规则),就要把E->TE′ E′->+TE′|ε ”->“左边的E和E′的follow集写上
Follow(T)={+,#,)}
Follow(E')
首先找”->“的右边,看E’后面跟的所有终结符号
E->TE′ E′->+TE′|ε
E′后面没有符号,E′的follow集就是”->“左边E和E′的follow集
Follow(E′)={#,)}
以此类推:
构造规则:
FIRSTVT集:
(1)若有T->a...或T->Ra...,则aFIRSTVT(T)
(2)若有aFIRSTVT(R),且有产生式T->R...,则aFIRSTVT(T)
LASTVT集:
(1)若有T->...a或T->...aR,则aLASTVT(T)
(2)若aLASTVT(R),且产生式T->...R,则aLASTVT(T)
举个例子:
FIRSTVT集合:
(1)首先根据E->E+T|T的E->E+T,可得(注:行代表终结符,列代表非终结符)
(2)再看E->E+T|T 的E->T,需要把T的FIRSTVT元素放到E中,但是此时T中没有✔元素,所以
(3)T->T*F|F中的T->T*F
(4)T->T*F|F中的T->F,而F没有✔项
(5)F->(E)|i 中的F->(E)
(6)F->(E)|i 中的F->i
这是第一遍遍历式子,因为表有变化,所以要继续进行遍历,直到表不变
(1)首先根据E->E+T|T的E->E+T,可得
(2)再看E->E+T|T 的E->T,需要把T的FIRSTVT元素放到E中
(3)T->T*F|F中的T->T*F
(4)T->T*F|F中的T->F,将F中的✔项放到T中
表依旧有改变,继续遍历,直到没有出现新的内容
所以得出结论:
E(FIRSTVT)={+,*,{,},i}
T(FIRSTVT)={*,(,i}
F(FIRSTVT)={(,i}
LASTVT的操作步骤同理,得到:
再来一个例子:
(1) S’→#S#
(2) S→bAb
(3) A→(B
(4) A→a
(5) B→Aa)
FIRSTVT集合:
FIRSTVT(S’)={#}
FIRSTVT(S)={b}
FIRSTVT(A)={(,a)
FIRSTVT(B)=FIRSTVT(A)={(,a)
LASTVT集合:
LASTVT(S’)={#}
LASTVT(S)={b}
LASTVT(B)={ )}
LASTVT(A)={a,(,)}
这里注意:LASTVT(A)={a,(,)}
对于A-->(B,其中 "(" ϵLASTVT(A),LASTVT(B)= {)} ϵ LASTVT(A)
对于A-->a,其中"a"ϵ𝜖LASTVT(A)
所以LASTVT(A)={a,(,)}