编译原理----FIRST集,LARST集,FIRSTVT集,LASTVT集

简介: 编译原理----FIRST集,LARST集,FIRSTVT集,LASTVT集

构造规则:


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,(,)}


目录
相关文章
|
程序员 C语言 Windows
C语言技巧 ----------调试----------程序员必备技能
C语言技巧 ----------调试----------程序员必备技能
|
3月前
|
C语言
C语言------程设设计入门
这篇文章是C语言程序设计的入门教程,涵盖了C程序的实现过程、VC集成开发环境的使用、基本数据类型的使用、格式控制字符的作用,以及通过示例代码演示了如何使用printf()函数输出不同类型的数据。
C语言------程设设计入门
|
5月前
|
程序员 编译器 C语言
c语言常见概念----
c语言常见概念----
|
存储 编译器 C语言
初识C语言----完结篇(二)
初识C语言----完结篇(二)
70 0
|
存储 缓存 编译器
初识C语言----完结篇(一)
初识C语言----完结篇(一)
76 0
|
存储 C语言
C语言进阶第二课-----------指针的进阶----------升级版
C语言进阶第二课-----------指针的进阶----------升级版
|
存储 搜索推荐 编译器
C语言进阶第三课-----------指针的进阶----------后续版
C语言进阶第三课-----------指针的进阶----------后续版
|
存储 编译器 C语言
C语言第十一课--------操作符的使用与分类-------基本操作
C语言第十一课--------操作符的使用与分类-------基本操作
|
存储 编译器 C语言
C语言第十三课--------初阶指针的认识--------重要部分
C语言第十三课--------初阶指针的认识--------重要部分
|
编译器 C语言 C++
C语言第十二课---------操作符的介绍与使用(下)
C语言第十二课---------操作符的介绍与使用(下)