编译原理第05章自顶向下语法分析方法

1、编译原理编译原理(语法分析语法分析1)软件学院信息安全研究中心软件学院信息安全研究中心万仲保万仲保20201111年年3 3月月第第5章章 自顶向下语法分析方法自顶向下语法分析方法v确定的自顶向下分析思想vLL(1)文法v某些非LL(1)文法到LL(1)文法的等价变换v不确定的自顶向下分析思想v确定的自顶向下分析方法确定的自顶向下分析思想确定的自顶向下分析思想v确定的自顶向下分析方法，首先要解决从某文法的开始符号出发，对给定的输入符号串如何根据当前的输入符号(单词符号)唯一地确定选用哪个产生式替换相应非终结符往下推导，或构造一棵相应的语法树，若能够推导出给定的输入符号串，或能构造出语法树其末端

2、结点以从左向右的顺序连接正好为给定的输入符号串，则所给的输入符号串为该文法的句子。v示例v引起自顶向下分析不确定的原因例例5.1v文法G1S:SpA SqB AcAd Aa BdB Bbv对于输入串w=pccadd的分析w=pccadd自顶向下的推导过程：S pA pcAd pccAdd pccadd相应的语法树如下。SpA(1)SpAcA dcA d(3)SpAcA dcA da(4)SpAcA d(2)引起自顶向下分析不确定的原因引起自顶向下分析不确定的原因v由于相同左部的产生式的右部开始符号集合交集不为空而引起回溯。v由于相同左部非终结符的右部存在能 的情况且该非终结符的后跟符号的集合中

3、含有其它右部开始符号集合的元素。v由于文法含有左递归而引起回溯。LL(1)文法文法v定义文法符号串的开始符号集FIRST文法符号的后继符号集 FOLLOW选择集合SELECTLL(1)文法v判别FIRST的定义的定义v定义：定义：设 G = (VT ,VN, P , S ) 是上下文无关文法，FIRST() = a|=* a,a VT, V*若=*，则规定FIRST()FIRST()包含了对应的字的所有可能的首终结符号 (选择产生式的依据)v计算：根据定义计算文法符号的FIRST根据定义计算符号串的FIRST根据关系图计算根据定义计算文法符号的根据定义计算文法符号的FIRSTv1.若XV,则F

4、IRST(X)=X；v2.若XVN,且有产生式Xa ，则aFIRST(X);v3若XVN,X,则FIRST(X)；v4.若XVN，Y1,Y2, ,YiVN,12n是一个产生式,当Y1,Y2, ,Yi-1都=*时(1in)，则FIRST(j)-FIRST(X)，其中(1ji-1)FIRST(i)FIRST(X);.当4中的所有i=*(1in)，则FIRST(X)=FIRST(1)FIRST(2) FIRST(n);.反复使用25，直到每个符号的集合收敛。 v示例根据定义计算符号串的根据定义计算符号串的FIRSTv若符号串V*，=X1X2 Xn。v当X1 *，则置FIRST()=FIRST(X1)

5、。v若对任何j，FIRST(Xj)(1ji-1，2in)，则FIRST()=(FIRST(X1)-)(FIRST(X2)-) (FIRST(Xi-1)-)FIRST(Xi)v当所有FIRST(Xj)都含有时(1jn)，则FIRST()=FIRST(X1)FIRST(X2) (FIRST(Xn)v示例根据关系图计算根据关系图计算FIRSTv1、每个文法符号对应图中一个结点，对应终结符的结点时用符号本身标记，对应非终结符的结点用FIRST(A)标记。这里A表示非终结符。 v2、如果文法中有产生式A X，且=*，则从对应A的结点到对应X的结点连一条箭弧。 v3、凡是从FIRST(A)结点有路径可到达

6、的终结符结点所标记的终结符都为FIRST(A)的成员。 v4、由判别步骤1确定是否为某非终结符FIRST集的成员，若是则将加入该非终结符的FIRST集中。v示例示例：文法的定义示例：文法的定义v若文法GS为：SAB A B CAD DaSSbC Ab BaD Cb Dc返回定义计算FIRST返回计算符号串的FIRST返回关系图计算FIRST返回定义计算FOLLOW返回关系图计算FOLLOW返回SELECT计算能推出的非终结符示例根据定义计算符号的根据定义计算符号的FIRST示例示例v文法定义v计算非终结符的FIRST集FIRST(S)(FIRST(A)-)(FIRST(B)-)b=b,a,FI

7、RST(A)b=b,FIRST(B)a=a,FIRST(C)(FIRST(A)-)(FIRST(D)FIRST(b)=b,a,cFIRST(D)aca，cv所以最终求得：FIRST(S)=b,a,FIRST(A)=b,FIRST(B)=a,FIRST(C)=b,a,cFIRST(D)a,c根据定义计算符号串的根据定义计算符号串的FIRST示例示例v文法定义v每个产生式的右部符号串的 FIRST为：FIRST(AB) b,a, FIRST(bC) bFIRST() FIRST(b)bFIRST(aD)a FIRST(AD)a,b,cFIRST(b)bFIRST(aS)aFIRST(c)c 根据关

8、系图计算根据关系图计算FIRST示例示例v文法定义v作文法的FIRST集关系图v由关系图法求得文法非终结符的FIRST集结果如下：FIRST(S)b,a,FIRST(A)b,FIRST(B)a,FIRST(C)a,b,cFIRST(D)a,cFIRST(S)FIRST(A)FIRST(B)FIRST(C)FIRST(D)bacFOLLOW的定义的定义v定义：设G=(VT,VN,P,S)是上下文无关文法，AVN,S是开始符号，则FOLLOW(A)=a|S=* A 且且aVT,aFIRST( ), VT*, V+若S=*A,且=*，则规定#FOLLOW(A)。v或定义为：FOLLOW(A)=a|S

9、=* Aa ，aVT 若S=* A,则规定#FOLLOW(A)。vFOLLOW(A)表示了句型中可能紧跟在A后面的终结符号。v计算：根据定义计算根据关系图计算根据定义计算根据定义计算FOLLOW集集v1.设S为文法中开始符号，把#加入FOLLOW(S)中(这里“#”为句子括号)。v2.若AB是文法的一个产生式，则把FIRST()的非空元素加入FOLLOW(B)中。v如果=*,则把FOLLOW (A)也加入FOLLOW(B)中。因为当有形如：D1A1 AB的产生式时，A,B,DVN ， 1,1, V * 在推导过程中可能出现句型序列如：S =* 1A1 = 1B1 = 1B1 由定义可知：nFI

10、RST(1 ) FOLLOW (A) nFIRST(1 ) FOLLOW (B) 所以也就有FOLLOW(A)FOLLOW(B)v3.反复使用2,直到每个非终结符的FOLLOW 集不再增大为止。v示例根据关系图计算根据关系图计算FOLLOW集集v1.文法G中的每个符号和“#”对应图中的一个结点，对应终结符和“#”的结点用符号本身标记。对应非终结符的结点(如AVN)则用FOLLOW(A)或FIRST(A)标记。 v2.从开始符号S的FOLLOW(S) 结点到“#”号的结点连一条箭弧。 v3.如果文法中有产生式ABX，且=*，则从FOLLOW(B)结点到FIRST(X)结点连一条弧，当XVT时，则

11、与X相连。 v4.如果文法中有产生式AB，且=* ，则从FOLLOW(B)结点到FOLLOW(A)结点连一条箭弧。 v5.对每一FIRST(A)结点，如果有产生式AB，且=*，则从FIRST(A)到FIRST(B)连一条箭弧。 v凡是从FOLLOW(A)结点有路径可以到达的终结符或#”号的结点，其所标记的终结将或“#”号即为FOLLOW(A)的成员。 v示例根据定义计算根据定义计算FOLLOW集示例集示例v文法定义v各非终结符的FOLLOW集如下：FOLLOW(S)# FOLLOW(D) FOLLOW(A)(FIRST(B)-)FOLLOW(S)FIRST(D) FOLLOW(B) FOLLO

12、W(S)FOLLOW(C) FOLLOW(S)FOLLOW(D) FOLLOW(B) FOLLOW(C) v由以上最终计算结果得： FOLLOW(S) #FOLLOW(A)a,#,c FOLLOW(B) # FOLLOW(C) # FOLLOW(D) #根据关系图计算根据关系图计算FOLLOW集示例集示例v文法定义v作文法的FOLLOW集关系图v由关系图可得：FOLLOW(S) #FOLLOW(A)a,#,c FOLLOW(B) # FOLLOW(C) # FOLLOW(D) #FOLLOW(S)FOLLOW(A)FOLLOW(B)FOLLOW(C)FOLLOW(D)#acFIRST(D)FI

13、RST(B)SELECT的定义的定义v给定上下文无关文法G的产生式A，AVN,V*，v若 *，则SELECT(A)=FIRST()v如果=*，则SELECT(A)=(FIRST() -) FOLLOW(A)v计算算法v示例计算计算SELECT算法算法v若A ，则：1求FIRST()；2若FIRST() ，则令SELECT(A) FIRST() ；3若FIRST()，则先求FOLLOW(A)，并令SELECT(A) FIRST() FOLLOW(A)。计算计算SELECT的示例的示例v文法定义v确定文法的FIRST集和FOLLOW集v计算每一个产生式的SELECT集合SELECT(SAB )FI

14、RST(AB)FOLLOW(S)b,a,#SELECT(SbC ) FIRST(bC) bSELECT(A ) FIRST()FOLLOW(A) a,c,#SELECT(Ab ) FIRST(b) bSELECT(B ) FIRST()FOLLOW(B) #SELECT(BaD ) FIRST(aD) aSELECT(CAD ) FIRST(AD) a,b, cSELECT(Cb) FIRST(b) bSELECT(DaS) FIRST(aS) aSELECT(Dc) FIRST(c) c文法的文法的FIRST集和集和FOLLOW集表集表非终结符是否=*FIRST集FOLLOW集S是b,a,#

15、A是b,a,#,cB是a,#C否a,b,c#D否a,c#LL(1)文法的定义文法的定义v一个上下文无关文法是LL(1)文法的充要条件是对每个非终结符A的两个不同产生式A和A，满足：SELECT(A)SELECT(A)=其中，不能同时=*。vLL(1)的含义：第一个L表示：自顶向下分析是从左向右扫描输入串。第二个L表示：分析过程中将用最左推导。1表示：只需向右看一个符号便可决定如何推导（即选择哪个产生式进行推导）。类似也可以有LL(K)文法：需向前查看K个符号才可确定选用哪个产生式。v示例：例5.3例5.4例例5.3v文法G3S:SaA Sd AbAS Av文法的选择集为：SELECT(SaA)

16、 =aSELECT(Sd) =dSELECT(AbAS) =bSELECT(A) =a,d,#,v因为： SELECT(SaA) SELECT(Sd)=ad=SELECT(AbAS)SELECT(A)=ba,d,#, =v所以该文法为LL(1)文法。例例5.4v设文法GS 为:SaAS Sb AbA Av文法的选择集为： SELECT(SaAS)=aSELECT(Sb) =bSELECT(AbA) =bSELECT(A) =a,b,v因为：SELECT(SaAS) SELECT(Sb)=ab=SELECT(AbA)SELECT(A)=ba,b,v所以该文法不是LL(1)文法。LL(1)文法的判

17、别文法的判别v1、求出能推出的非终结符步骤示例v2、计算FIRST集v3、计算FOLLOW集v4、计算SELECT集v5、利用LL(1)的文法定义进行判断求能推出求能推出的非终结符步骤的非终结符步骤v首先建立一个以文法的非终结符个数为上界的一维数组，其数组元素为非终结符，对应每一非终结符有一标志位，用以记录能否推出 。其值有三种情况“未定”、“是”、“否”。v1、将数组X 中对应每一非终结符的标记置初值为“未定”。v2、扫描文法中的产生式。 (1)删除所有右部含有终结符的产生式，若这使得以某一非终结符为左部的所有产生式都被删除，则将数组中对应该非终结符的标记值改为否”，说明该非终结符不能推出

18、。 (2)若某一非终结符的某一产生式右部为 ，则将数组中对应该非终结符的标志置为“是”，并从文法中删除该非终结符的所有产生式。v3、扫描产生式有部的每一符号。(1)若所扫描到的非终结符号在数组中对应的标志是“是”，则删去该非终结符，若这使产生式右部为空，则对产生式左部的非终结符在数组中对应的标志改为“是”，并删除该非终结符为左部的所有产生式。(2)若所扫描到的非终结符号在数组中对应的标志是“否”，则删去该产生式，若这使产生式左部非终结符的有关产生式都被删去，则把在数组中该非终结符对应的标志改成“否”。v4、重复3，直到扫描完一遍文法的产生式，数组中非终结符对应的特征再没有改变为止。能推出能推出

19、的非终结符示例的非终结符示例v文法定义非终结符SABCD初值未定未定未定未定未定第一次扫描是是否第二次扫描是否非非LL(1)文法的等价变换文法的等价变换v提取左公共因子方法示例n例5.6n例5.7n例5.8n例5.9v消除左递归提取左公共因子提取左公共因子v若文法中含有形如：A|的产生式，这导致了对相同左部的产生式其右部的FIRST集相交，也就是SELECT(A)SELECT(A ) ，不满足LL(1)文法的充分必要条件。v现将产生式A| 进行等价变换为：A (|) 其中(，)为元符号，可进一步引进新非终结符A，去掉(，)使产生式变换为：AA A| v写成一般形式为：A 1| 2| n，提取左

20、公共因子后变为：A (1| 2| n），再引进非终结符A，变为：A A A1| 2| nv若在i、 j、 k (其中1i，j，kn)中仍含有左公共因子，这时可再次提取，这样反复进行提取直到引进新非终结符的有关产生式再无左公共因子为止。例例5.6v若文法G1的产生式为： (1) SaSb (2) SaS (3) S请提取文法中的左公因子。v解答：对产生式(1)、(2)提取左公因子后得：S aS(b|)S进一步变换为文法G1：SaSAAbAS例例5.7v若文法G2的产生式为：(1) Aad (2) ABc (3) BaA (4) BbBv请提取文法中的隐式左公因子。v产生式(2)的右部以非终结符开

21、始，因此左公共因子可能是隐式的，所以这种情况下对右部以非终结符开始的产生式，用其相同左部而右部以终结符开始的产生式进行相应替换，对文法G2分别用(3)、(4)的右部替换(2)中的B，可得： (1) Aad(2) AaAc(3) AbBc(4) BaA(5) BbBv提取产生式(1)、(2)的左公共因子得：Aa(d|Ac) AbBc BaA BbBv引进新非终结符A，去掉(，)后得G2为：(1) AaA (2) AbBc(3) Ad(4) AAc(5) BaA (6) BbB例例5.8v若有文法G3的产生式为：(1) SaSd(2) SAc(3) AaS(4) Abv用产生式(3)、(4)中右部

22、替换产生式(2)中右部的A，文法变为：(1) SaSd(2) SaSc(3) Sbc(4) AaS(5) Abv对(1)、(2)提取左公共因子得：SaS(d|c)v引入新非终结符A后变为：(1) SaSA(2) Sbc(3) Ad|c(4) AaS(5) Abv显然，原文法G3中非终结符A变成不可到达的符号，产生式(4)、(5)也就变为无用产生式，所以应删除。例例5.9v若有文法G4的产生式为：(1) SAp|Bq(2) AaAp|d(3) BaBq|ev用(2)、(3)产生式的右部替换(1)中产生式的A、B使文法变为：(1) SaApp|aBqq(2) Sdp|eq(3) AaAp|d(4)

23、 BaBq|ev对(1)提取左公共因子则得：Sa(App|Bqq)v再引入新非终符S结果得等价文法为：(1) SaS(2) Sdp|eq(3) SApp|Bqq(4) AaAp|d(5) BaBq|ev同样分别用(4)、(5)产生式的右部替换(3)中右部的A、B再提取左公共因子最后结果得：(1) SaS (2) Sdp|eq(3) SaS(4) Sdpp|eqq(5) SAppp|Bqqq(6) AaAp|d(7) BaBq|ev可以看出若对(5)中产生式A、B继续用(6)、(7)产生式的右部替换，只能使文法的产生式愈来愈多无限增加下去，但不能得到提取左公共因子的预期结果。消除左递归消除左递归

24、v设一个文法含有下列形式的产生式。1)AA AVN，V*2)AB BA A,BVN, ,V*v称含1)中产生式的文法为含有左递归的规则或称直接左递归的。v含2)中产生式的文法有A=+A 则称文法中含有左递归或间接左递归.v文法中只要含有1)或含有2)的产生式或二者皆有均认为文法是左递归的。v消除左递归的步骤v消除左递归的算法v示例：例5.10例5.11例5.12消除左递归的步骤消除左递归的步骤v1)把文法的所有非终结符按某一顺序排序；如A1，A2,Anv2)从A1开始消除左部为A1的产生式的直接左递归，然后把左部为A1的所有规则的右部逐个替换左部为A2右部以A1开始的产生式中的A1，并消除左部

25、为A2的产生式中的直接左递归。继而以同样方式把A1，A2的右部代入左部为A3右部以A1或A2开始的产生式中，消除左部为A3的产生式之直接左递归，直到把左部为A1，A2，,An-1的右部代入左部为An的产生式中，从An中消除直接左递归。v3)去掉无用产生式。v4)最后删除无用产生式。消除左递归的算法消除左递归的算法v若非终结符的排序为若非终结符的排序为A1，A2，An。vFOR i =1 TO N DOv BEGINv FOR j =1 TO i-1 DOv BEGINv 若若Aj的所有产生式为：的所有产生式为： Aj1|2|kv 替换形如替换形如AiAjr的产生式变为的产生式变为：Ai1r|2

26、r|krv ENDv 消除消除Ai中的一切直接左递归。中的一切直接左递归。v END例例5.10v文法G5含有直接左递归：SSaSbv可改写为：SbSSaS|v改写后的文法和原文法产生的语言都为：ban|n0。v可以验证改写后的文法为LL(1)文法。v一般情况下，假定关于A的全部产生式是：AA1|A2|Am|1|2|nv其中，i(1im)不等于,j(1jn)不以A开头，消除直接左递归后改写为：A1 A|2 A|n AA1 A|2 A|m A|例例5.11v文法G6含有间接左递归的文法：(1) AaB(2) ABb(3) BAc(4) Bdv用产生式(1)、(2)的右部代替产生式(3)中的非终结

27、符A得到左部为B的产生式为：(1) BaBc(2) BBbc(3) Bdv消除左递归后得：B(aBc|d)BBbcB|v再把原来其余的产生式AaB，ABb加入，最终文法为：(1) AaB(2) ABb(3) B(aBc|d)B(4) BbcB|v可以检验改写后的文法不是LL(1)文法。例例5.12v文法G的产生式为：(1) SQc|c(2) QRb|b(3) RSa|av该文法的每个非终结符为间接左递归。v若非终结符排序为S、Q、R, 左部为S的产生式(1)无直接左递归，(2)中右部不含S，所以把(1)右部代入(3)得：(4) RQca|ca|av再将(2)的右部代入(4)得：(5) RRbc

28、a|bca|ca|av对(5)消除直接左递归得：R(bca|ca|a)RRbcaR|v最终文法变为：SQc|cQRb|bR(bca|ca|a)RRbcaR|v若非终结符的排序为R、Q、S, 则把(3)代入(2)得：QSab|ab|bv再将此代入(1)得：SSabc|abc|bc|cv消除该产生式的左递归后，最终文法变为：vS(abc|bc|c)SSabcS|QRb|bRSa|av由于Q、R为不可到达的非终结符，所以以Q、R为左部及包含Q、R的产生式应删除。当非终结符的排序不同时，最后结果的产生式形式不同，但它们是等价的。不确定的自顶向下分析思想不确定的自顶向下分析思想v1.由于相同左部产生式的

29、右部FIRST集交集不为空引起回溯。v2.由于相同左部非终结符的右部能* 且该非终结符FOLLOW集中含有其右部FIRST集的元素。v3.由于文法含有左递归而引起回溯。v当文法不是LL(1)文法时，采用不确定的自顶向下分析方法，即带回溯的自顶向下分析方法。v示例：FIRST集交集不为空的示例能推出的示例左递归的实例FIRST集交集不为空的示例集交集不为空的示例v有文法SxAy Aab|av若当前输入串为xay，则可能的推导树为图(a)。进一步推导对A可选Aab替换，得语法树为图(b)。其中xa都已匹配，当前面临输入符为y与b不能匹配，所以将输入串指针退回到a，对A的替换重新选用下一个产生式Aa

30、进行试探，如图 (c)。输入串中当前符a得到匹配，指针向前移动到y，与语法树中y匹配，匹配成功。w=xaySx A ySx A ya bSx A ya(a)(b)(c)能推出能推出的示例的示例v设文法GS 为:(1)SaAS (2)Sb (3)AbAS (4) Av对输入串ab#的试探推导，试推过程在图 (a)，(b)，(c)中给出。当面临a时，用产生式(1)推导，a得到匹配，输入串指针移到b，语法树中可用A向下推导，而对A的产生式可选(3)或(4)，先试选用(3)推导。v这时b得到匹配，输入串指针向右移动，输入符已结束，但从语法树可以看出末端结点并非全是终结符，而且ab右部的非终结符ASS不

31、能推出 ，所以可知推导是失败的，需回溯使输入指针退回到b，对A的推导改为选用下一个产生式A ，对b用A的后跟符匹配。v继续用S的产生式和b匹配，s的两个产生式只能选用Sb则最终得到匹配，试推成功。w=ab#Sa A SSa A Sb A SSa A S b(a)(b)(c)左递归的实例左递归的实例v设文法设文法GS 为为:(1) SSa (2)Sbv若推导若推导baa#，开始由于输入当前符是开始由于输入当前符是b，所以试图用所以试图用(2)推导对应语法树为图推导对应语法树为图(a)。v这时推导树的末端结点都是终结符，输入串未分析完，所以应重新选用产生式这时推导树的末端结点都是终结符，输入串未分

32、析完，所以应重新选用产生式(1)来推导对应语法树为图来推导对应语法树为图(b)。v语法树末端结点最左符号为语法树末端结点最左符号为b与当前符号匹配，语法树下一符号与输入串的下与当前符号匹配，语法树下一符号与输入串的下一符号都为一符号都为a,所以匹配，但语法树的末结点只有两个终结符，而输入串还有剩所以匹配，但语法树的末结点只有两个终结符，而输入串还有剩余部分余部分a#，所以要把第二步的推导回溯，输入串指针也恢复到第一个符号，对所以要把第二步的推导回溯，输入串指针也恢复到第一个符号，对第二步推到的重新选择只有产生式第二步推到的重新选择只有产生式(2)，相应的语法树为图，相应的语法树为图(d)。v这

33、时语法树的最左末结点为非终结符这时语法树的最左末结点为非终结符S，当前输入符为当前输入符为b，所以试用产生式所以试用产生式(2)推导，得语法树如图推导，得语法树如图(e)。v当前输入符与语法树最左末结点匹配，剩余的输入符当前输入符与语法树最左末结点匹配，剩余的输入符aa与语法树其余的末结点与语法树其余的末结点也逐个相匹配，最后遇到输入串结束符，所以分析成功。也逐个相匹配，最后遇到输入串结束符，所以分析成功。w=baa#SbSS aSS abSS aS aSS aS ab(a)(b)(c)(d)(e)确定的自顶向下分析方法确定的自顶向下分析方法v递归子程序法实现思想：对文法中每个非终结符编写一个

34、递归过程，每个过程的功能是识别由该非终结符推出的串，当某非终结符的产生式有多个候选时能够按LL(1)形式可唯一地确定选择某个候选进行推导。缺点：对文法要求高，必须满足LL(1)文法，当然在某些语言中个别产生式的推导当不满足LL(1)而满足LL(2)时，也可以采用多向前扫描一个符号的办法；它的另一个缺点是由于递归调用多，所以速度慢占用空间多。v预测分析法预测分析器的组成n预测分析程序预测分析程序的框图n先进后出栈n预测分析表示例预测分析程序的框图预测分析程序的框图v图中符号说明如下：图中符号说明如下：v“#”句子括号即输入串的句子括号即输入串的括号括号v“S”文法的开始符号文法的开始符号v“X”存放当前栈顶符号的工存放当前栈顶符号的工作单元作单元va存放当前输入符号存放当前输入符号a的工的工作单元作单元#