编译原理消除回溯.ppt

单击此处编辑母版标题样式,*,编译原理,主讲教师,：,于永彦,计算机科学与技术专业最重要的学科基础课程,淮阴工学院,,信箱,FIRST集合,引入FIRST集概念是为了在当前输入的条件下，观察哪个产生式的右部能够导出输入符号，进而决定采用哪个产生式来进行推导显然，我们关心的是,产生式右部符号串的FIRST集,，即文法符号串的FIRST这个符号串可以是任意的终结符和非终结符的组合2,FIRST集合,【定义】,假定,是文法G的任一符号串，即,(V,N,V,T,)*，则,的首符号集定义为：,可见，所谓符号串,的FIRST，就是指,的所有可能推导的开头终结符或,的集合由定义，不难得出下面的结论：,若,，则,；,若,=aA,，其中,A,代表非终结符,，则,；,若,=Aa,，则,；,若,，则,3,FIRST集合,一、关系图法求解FIRST,【,例,】,已知文法GS如下：,SAB|bC,Ab|,BaD|,CAD|b,DaS|c,求所有非终结符的FIRST解】,关系图法求解FIRST集，分为三步进行1）,求出能推出的非终结符,首先建立一个以文法非终结符为元素的一维数组X，对应每个非终结符设置一个标志位，以记录能否推出。

其值有三种情况：“未定”、“是”、“否”其次，按下述步骤逐步更新标志位：,4,FIRST集合,依次扫描文法,每一条产生式,I删除所有右部含终结符的产生式若使得以某非终结符为左部的所有产生式都被删除，则置该非终结符的标记为“否”，例“D”II若某非终结符存在一条右部为的产生式，则置该非终结符的标志为“是”，并删除该非终结符的所有产生式，如“A”、“B”见表的第2行扫描产生式,右部的每一符号,I若某非终结符标志为“是”，则删去该非终结符，若进而使得某产生式右部为空，则置该式左部的非终结符标志为“是”，并删除该非终结符为左部的所有产生式，如“S”II若某非终结符标志为“否”，则删去该产生式，若使得左部为该非终结符的产生式都被删去，则置该非终结符标志为“否”，例如“C”重复上述步骤，直到扫描完一遍文法的产生式，非终结符标志位不再改变为止5,FIRST集合,结合本例，由中(I)、(II)得知例中对应非终结符D的标志改为“否”，对应非终结符A、B的标志改为“是”经过中(I)、(II)两步后文法中的产生式只剩下：SAB和CAD，也就是只剩下右部全是非终结符串的产生式再由中的(I)步扫描到产生式SAB时，在数组中A、B对应的标志都为“是”，删去后S的右部变为空，所以S对应标志置为“是”。

最后由中的(II)扫描到产生式CAD时，其中A对应的标志为“是”，D对应的标志是“否”，删去该产生式后，再无左部为C的产生式，所以C的对应标志改为“否”结果如下表S,A,B,C,D,初值,未定,未定,未定,未定,未定,扫描产生式,是,是,否,扫描文法符号,是,否,6,FIRST集合,（2）,绘制文法关系图,按下述步骤绘制文法关系图每个文法符号对应图中一个结点，对应终结符的结点时用符号本身标记，对应非终结符A的结点用其FIRST(A)标记若有产生式AX，且 ，则从对应A的结点到对应X的结点连一条箭弧7,FIRST集合,（3）,求解FIRST,按下述步骤从关系图求解FIRST凡是从FIRST(A)结点有路径可到达的终结符点所标记的终结符为FIRST(A)的成员若某非终结符能够 ，则将加入该非终结符的FIRST集中至此，可以求得本例的结果：,FIRST(S)=b,a,FIRST(A)=b,FIRST(B)=a,FIRST(C)=a,b,c,FIRST(D)=a,c,8,FIRST集合,二、根据通用算法构造FIRST,（1）文法符号的FIRST,对于文法中的每一个符号X,（V,N,V,T,），构造FIRST（X）时，只要连续使用下列步骤，直至FIRST集不再扩大为止。

步骤1,若X,V,T,，则FIRST（X）X；,步骤2,若X,V,N,，则考查,以X为左部的每一条产生式,：,若X,是一条产生式，则,FIRST（X）；,若XY,1,Y,2,Y,n,是产生式：,(I),若Y,1,Y,i-1,都,V,N,且都能,（其中1in），则FIRST(Y,1,)-,，FIRST(Y,2,)-,，FIRST(Y,i-1,)-,和FIRST(Y,i,)都包含在FIRST(X)中；,(II),若所有的FIRST(Y,i,)均能,，i1,2,k，则把,加到FIRST(X)中9,FIRST集合,10,FIRST集合,【例】,已知文法GS如下：,SaAd,ABC,Bb|,Cc|,求各个非终结符的FIRST集解】,由上述算法，容易求各个FIRST集：,FIRST(S)=a,FIRST(B)=b,FIRST(C)=c,FIRST(A)=b,c,11,FIRST集合,（2）文法符号串的FIRST,对文法G的任一符号串,，可按下图所示的步骤构造FIRST(,)再看上例GS，求产生式右部的符号串的FIRST集解】,由上图，容易求各个FIRST集：,FIRST(aAd)=aFIRST(BC)=b,c,FIRST(b)=bFIRST(c)=c,12,FIRST集合,注意：,在使用通用算法法求解FIRST的时候，如果求解过程中存在递归循环现象，将使求解过程陷入无限循环中。

例】,若文法GS为：,SBCc|gDB,B|bCDE,CDSB|cS,D|dD,EgSf|c,容易看出：,FIRST(S)=（FIRST(B)-）FIRST(C)g,=（FIRST(B)-）（FIRST(D)-）FIRST(S)cg,很明显，存在循环求解过程，求FIRST(S)时，需要先求FIRST(C)，而若求解FIRST(C)又需要先求FIRST(S)所以，此文法不适宜应用通用算法13,FIRST集合,【结论】,对于所有形如A,1,2,n,的产生式，若存在,FIRST(,i,)FIRST(,j,),（i,j）,则能够根据不同输入符号唯一确定候选式,i,，即不存在回溯此时，当要求使用A去匹配输入串时，能够根据输入符号a准确指派某一个候选式前去执行任务，这个候选式就是FIRST中含a的那个,i,14,实例分析,【例】,已知文法GS定义如下：,SAp|Bq,Aa|cA,Bb|dB,考查输入串w=ccap是否合法解】,所谓考查输入串ccap是否合法，就是看能否由文法开始符号导出符号串首先，可由上面介绍的方法求得文法的各个符号（串的）FIRST文法符号的FIRST：,FIRST(S)=a,c,b,dFIRST(A)=a,c,FIRST(B)=b,dFIRST(p)=p,FIRST(q)=qFIRST(a)=a,FIRST(c)=cFIRST(b)=b,FIRST(d)=d,15,FIRST集合,文法符号串的FIRST：,FIRST(Ap)=a,cFIRST(Bq)=b,d,FIRST(a)=aFIRST(cA)=c,FIRST(b)=bFIRST(dB)=d,显然，,各个候选式的FIRST互不相交,，符合要求：,FIRST(Ap)FIRST(Bq)=a,cb,d=,FIRST(a)FIRST(cA)=ac=,FIRST(b)FIRST(dB)=bd=,因此，可以很容易得到符号串w=ccap的推导过程：,S,Ap,cAp,ccAp,ccap,不存在回溯现象！,16,提取左公共因子,不过，有时候一个文法并不一定能满足“候选式的首符号集并非两两不相交。

譬如下面的例子例】,已知文法GA定义如下：,Aad,ABc,BaA,BbB,17,提取左公共因子,【解】,利用上述算法，不难求得各个符号串的FIRST：,FIRST(ad)=a,FIRST(Bc)=a,b,FIRST(aA)=a,FIRST(bB)=b,不难看出，存在候选式的FIRST相交的情况：,FIRST(ad)FIRST(Bc)=aa,b=a,所以，本文法存在回溯现象，不适于应用确定的自顶向下分析法那么，有没有什么办法能够对文法进行一定的,预处理,，从而达到所有候选式的FIRST集两两不相交呢？答案是肯定的，通过提取左公共因子即能实现此目的！,18,提取左公共因子,所谓,左公共因子,，是指形如A,B和A,C的产生式假定关于A的规则是：,A,1,|,2,|,n,那么，可以把上述规则改写为下面的形式，以提取左公共因子：,A,A,A,1,|,2,|,n,经过反复提取左公共因子，就能够把每个非终结符的所有候选式的FIRST变成两两不相交的19,提取左公共因子,例如，对于上例中的文法GA，将、代入，就可得,A,a,d|,a,Ac存在左公共因子a,AbBc,BaA|bB,因此，提取左公共因子后的文法GA消除了回溯：,AaA,Ad|Ac,AbBc,BaA|bB,20,。