FIRST集、FOLLOW集 和 SELECT集
一、FIRST集
FIRST(A)为A的开始符或者首符号集。
1、定义:
设G=(VT,VN,S,P)是上下文无关文法 ,FIRST(α)={a|α能推导出aβ,a∈VT,α,β∈V*}
特别的,若α能推导出ε,则规定ε∈FIRST(α).
2、根据定义求解FIRST集(对每一文法符号X∈V计算FIRST(X)):
①.若X∈VT,则FIRST(X)={X}。(简单讲,终结符的FIRST集就是它本身)
②.若X∈VN,且有产生式X→a…,a∈VT,则a∈FIRST(X)X→ε,则ε∈FIRST(X)。 (简单讲,若是非终结符X,能推导出以终结符a开头的串,那么这个终结符a属于FIRST(X),若X能够推导出空符号串ε,那么空符号串ε也属于X的FIRST集)
③.X→Y…是一个产生式且Y∈VN则把FIRST(Y)中的所有非空符号串ε元素都加入到FIRST(X)中。(这个可以理解吧)
④.若X∈VN;Y1,Y2,…,Yi∈VN,且有产生式X→Y1Y2…Yn;当Y1Y2…Yn-1都能推导出ε时,则FIRST(Y1)、FIRST(Y2)、…、FIRST(Yn-1)的所有非空元素和FIRST(Yn)包含在FIRST(X)中。
即:FIRST(X)=(FIRST(Y1)-{ε})∪(FIRST(Y2)-{ε})∪…∪(FIRST(Yn-1)-{ε})∪{FIRST(Yn)}
⑤.当(4)中所有Yi能够推导出ε,(i=1,2,…n),则
FIRST(X)=(FIRST(Y1)-{ε})∪(FIRST(Y2)-{ε}∪…∪(FIRST(Yn)-{ε})∪{ε}
反复使用上述②~⑤步直到每个符号的FIRST集合不再增大为止。
1、文法G[S]为:
S→AB
S→bC
A→ε
A→b
B→ε
B→aD
C→AD
C→b
D→aS
D→c
求每个非终结符的First集?
解:对于非终结符S,S的开始符有终结符b和非终结符A,根据上面定义②把b加入FIRST(S),由上面的定义③把FIRST(A)中的所有非空符号串ε元素都加入到FIRST(S)中,而且因为S→AB符合上面的定义④和⑤,所以FIRST(S)=(FIRST(A)-{ε})∪(FIRST(B)-{ε})∪{ε}那么先求FIRST(A)和FIRST(B),A的开始符有终结符b和空符号串ε,由定义①和定义②全部加入FIRST(A),也就是FIRST(A)={ε,b},同理,FIRST(B)={a,ε},这样FIRST(S)也就求出来了,FIRST(S)={b,a,ε},其实回过头来看之所以要反复调用定义②~⑤,是因为开始符中A可能为空字符串ε,所以要考虑A后面的情况。
再求,FIRST(C),由定义①,把b加入FIRST(C),再由定义④,FIRST(C)=(FIRST(A)-{ε})∪{FIRST(D)},先求FIRST(D),易知,FIRST(D)={a,c},所以FIRST(C)={b,a,c}
4、小结:
1、对于终结符而言,FIRST集中的元素只有它本身
2、对于非终结符而言,如果开始符是终结符或者空符号串ε,则加入其FIRST集中;若开始符是非终结符,则要加入它的不含ε的FIRST集,并考虑其为ε时的情况。
二、FOLLOW集
FOLLOW(A)={a|S能推导出μAβ,且a∈VT,a∈FIRST(β),μ∈VT*
,β∈V+},若S能推导出μAβ,且β能推导出ε, 则#∈FOLLOW(A)。 也可定义为:FOLLOW(A)={a|S能推导出…Aa…,a ∈VT} ,若有S能推导出…A,则规定#∈FOLLOW(A) ,这里我们用‘#’作为输入串的结束符,或称为句子括号,
如: #输入串#。
FOLLOW(A)为非终结符A的后跟符号集合。
1、定义:
设G=(VT,VN,S,P)是上下文无关文法,A∈VN,S是开始符号
需要注意的是,FOLLOW(A)集是针对非终结符A的,集合中的元素是终结符,是A的全部后跟符号的集合,当A是文法G的开始符(识别符)时,把‘#也加入其中’
2、根据定义求解FOLLOW集(对每一文法符号S∈VN计算FOLLOW(S)):
①.设S为文法中开始符号,把{#}加入FOLLOW(S)中(这里“#” 为句子括号)。
②.若A→αBβ是一个产生式,则把FIRST(β)的非空元素加入
FOLLOW(B)中。如果β能够推导出ε则把FOLLOW(A)也加入FOLLOW(B)中。
③.反复使用(b)直到每个非终结符的FOLLOW集不再增大为止。
3、求解示例:
1、文法G[E]为:
E → TE'
E' → +TE' |ε
T → FT'
T' → *FT' |ε
F → (E) | i
求每个非终结符的FOLLOW集?
解:先给出它们的FIRST集:(求解方法见上面FIRST集的求解)
FIRST(F)={ (,i }
FIRST(T’)={ *,ε }
FIRST(T) ={ (,i }
FIRST(E’)={ +,ε }
FIRST(E)={ (,i }
FOLLOW集的求解:因为E是文法的识别符所以把#加入FOLLOW(E),又由规则F → (E) | i 得E的后跟符号),所以,FOLLOW(E)={ #,) };
FOLLOW(E’)={ #,) } ∵E → TE’ ∴FOLLOW(E)加入 FOLLOW(E’)
FOLLOW(T)={+,),#} ∵E'→ +TE’ ∴FIRST(E’)-{ε}加入FOLLOW(T);又E’→ε, ∴ FOLLOW(E’)加入FOLLOW(T)
FOLLOW(T’)= FOLLOW(T)= {+,),#} ∵T → FT’ ∴ FOLLOW(T)加入FOLLOW(T’)
FOLLOW(F)={*,+,),#}
∵T → FT’ ∴ FOLLOW(F)=FIRST(T’)-{ε} ;又T’→ε ∴ FOLLOW(T)加入FOLLOW(F)
4、小结:
1、FOLLOW集对于非终结符而言,是非终结符的全部后跟符号的集合,如果后跟终结符则加入,如果后跟非终结符,则加入该非终结符的不含空符号串的FIRST集,特别地,文法的识别符的FOLLOW集需要额外的加入‘#’。
三、SELECT集
1、定义:
给定上下文无关文法的产生式A→α, A∈VN,α∈V*, 若α不能推导出ε,则SELECT(A→α)=FIRST(α)
如果α能推导出ε则:SELECT(A→α)=(FIRST(α) –{ε})∪FOLLOW(A)
需要注意的是,SELECT集是针对产生式而言的。
2、LL(1)文法:
① 一个上下文无关文法是LL(1)文法的充分必要条件是:对每个非终结符A的两个不同产生式,A→α, A→β,满足SELECT(A→α)∩SELECT(A→β)=空集 其中α,β不同时能推导出ε。
② LL(1)文法的含义:
第一个L 从左到右扫描输入串
第二个L 生成的是最左推导
1 向右看一个输入符号便可决定选择哪个产生式。
③LL(1)文法的判别:当我们需选用自顶向下分析技术时,首先必须判别所给文法是否是LL(1)文法。因而我们对任给文法需计算FIRST、FOLLOW、SELECT集合,进而判别文法是否为LL(1)文法。
3、求解示例:
1、文法G[S]为:
S→AB
S→bC
A→ε
A→b
B→ε
B→aD
C→AD
C→b
D→aS
D→c
求每个产生式的SELECT集,并判断文法G是否为LL(1)文法?
解:SELECT(S→AB)=(FIRST(AB)-{ε})∪FOLLOW(S)={b,a,#}
SELECT(S→bC)=FIRST(bC)={b}
SELECT(A→ε)=(FIRST(ε) -{ε})∪FOLLOW(A)={a,c,#}
SELECT(A→b)=FIRST(b)={b}
SELECT(B→ε)=(FIRST(ε) -{ε})∪FOLLOW(B)={#}
SELECT(B→aD)=FIRST(aD)={a}
SELECT(C→AD)=FIRST(AD)={a,b,c}
SELECT(C→b)=FIRST(b)={b}
SELECT(D→aS)=FIRST(aS)={a}
SELECT(D→c)=FIRST(c)={c}
由以上计算结果可得相同左部产生式的SELECT交集为:
SELECT(S→AB)∩SELECT(S→bC)={b,a,#}∩{b}={b}≠ф
SELECT(A→ε)∩SELECT(A→b)={a,c,#}∩{b}=ф
SELECT(B→ε)∩SELECT(B→aD)={#}∩{a}=ф
SELECT(C→AD)∩SELECT(C→b)={b,a,c}∩{b}={b}≠ф
SELECT(D→aS)∩SELECT(D→c)={a}∩{c}=ф
由LL(1)文法定义知该文法不是LL(1)文法,因为具有相同左部其产生式的SELECT集的交集不为空。
4、小结:
1、Select集的作用是将first集和follow集进行合并,如果两个文法的左端都是A,若他们的select集交集为空,表明他们是两个无关的,不会产生不确定性的文法,反之,则表明文法不是LL(1)文法。
分享到:
相关推荐
编译实验中求一文法的first集和follow集
编译原理用C语言求first集sellect集follow集,最后,判断给出的文法是否是LL(1)文
C语音代码。实现功能:1....2.求每个非终结符FIRST 集FOLLOW集和SELECT集模块。3.预测分析表的构建模块。4.文法的检验及消除左公因子和左递归模块。5.对输入终结符串的判断,是否为LL1文法,并进一步分析。
该分析器主要包括三大部分:求FIRST集,求FOLLOW集,求SELECT集。下面主要介绍计算FIRST集和FOLLOW集算法思想。 求FIRST集的算法思想:主要有三个函数 First(), First_getvn(), First_getvt。函数 First()调用First_...
java 编译原理 ll1 文法分析 first follow select 集的 求解
C语言实现的LL1文法判别,及first、follow、select集合计算,编译原理实验要求,自己实现的,可能会有不完善的地方,欢迎讨论~~~
1.求出每个非终结符的FIRST集合 2.求出每个产生式右部的FIRST集合 3.求出每个非终结符的Follow集合
东华大学计算机学院姚砺原创,简明、幽默、诙谐讲解。
C和C++混合编写的编译原理实验,包括求first/follow/select,进行词法分析 构造预测分析表及判断是否为LL1文法
文法分析 first follow select 集的 求解
覆盖知识点:FIRST 集、FOLLOW 集、SELECT 集、预测分析表的构建、消除左递归、 消除左公共因子。 求first集、FOLLOW集、select集、LL(1)文法判别、构造预测分析表、非LL(1)文法转换为LL(1) C++版
编译原理实验 first、follow、select集合的求解,经测试正确,c语言编写
编译原理Java实现完整自顶向下语法分析——First、Follow、Select、判断LL(1)、提取公因子、消除左递归、自顶向下分析输入串
需要创建一个名字叫project.txt的文件来存储要识别的文法
里面是编译原理课上所讲的求first的集合的源代码,使用C++编写的
Python代码,求First集合Follow集合Select集合以及预测分析表以及驱动分析程序
2021年编译原理课程设计求follow集、first集、predict集 可运行,简洁,有详细注释
输入文法,分别求出每一个非终结符FIRST 集FOLLOW集和SELECT集,画出预测分析表,判定读入的文法是否是LL(1)文法,给定的任意符号串判定是否是文法中的句子,将分析过程用计算机打印出来,查出文法中是否含有左递归...
LL1文法分析器 模拟LL1文法分析过程 ...2.求每个非终结符FIRST 集FOLLOW集和SELECT集模块。3.预测分析表的构建模块。4.文法的检验及消除左公因子和左递归模块。5.对输入终结符串的判断,是否为LL1文法,并进一步分析。