编译原理第5章

1、第第5 5章章 自顶向下的语法分析方法自顶向下的语法分析方法n回顾“文法和语言”一章中所介绍的有关概念5.1 确定的自顶向下分析思想5.2 LL(1)文法的判别5.3 非LL(1)文法到LL(1)文法的等价变换5.4 不确定的自顶向下分析思想5.5 确定的自顶向下分析方法 语法分析的作用是识别由词法分析给出语法分析的作用是识别由词法分析给出的单词符号序列是否是给定文法的正确句的单词符号序列是否是给定文法的正确句子子(程序程序)。目前语法分析常用的方法有目前语法分析常用的方法有:1、自顶向下（自上而下）分析、自顶向下（自上而下）分析2、自底向上（自下而上）分析、自底向上（自下而上）分析自顶向下分

2、析法也就是从文法的开始符号出自顶向下分析法也就是从文法的开始符号出发企图推导出与输入的单词串完全相匹配的发企图推导出与输入的单词串完全相匹配的句子，若输入串是给定文法的句子，则必能句子，若输入串是给定文法的句子，则必能推出，反之必然出错。推出，反之必然出错。回顾在“文法和语言”一章中介绍的关于句子、句型和语言的定义及什么叫最左推导、最右推导和规范推导的基本概念。句型、句子、语言的定义句型、句子、语言的定义 句型:有文法GS，若S x，且xV*则称x是文法GS的句型。符号 表示经过0步或若干步的推导。 句子:有文法GS，S x，且xVT*，则称x是文法G S的句子。例：GS： S0S1， S01

3、可有推导 S 0S1 00S11 000S111 00001111说明00001111是GS的句子。句型的分析句型的分析 句型分析句型分析就是识别一个符号串是否为某文法的句型，是某个推导的构造过程。最左（最右）推导最左（最右）推导：在推导的任何一步 ，都是对中的最左（右）非终结符进行替换。最右推导被称为规范推导。最右推导被称为规范推导。由规范推导所得的句型称为规范句型。由规范推导所得的句型称为规范句型。 句型分析的有关问题句型分析的有关问题 如何选择使用哪个产生式进行推导？如何选择使用哪个产生式进行推导？假定要被替换的最左非终结符号是V，且左部为V的规则有n条：VA1|A2|An，那么如何确定

4、用哪个右部去替换V呢？ 如何识别可归约的串？如何识别可归约的串？在自下而上的分析方法中，在分析程序工作的每一步，都是从当前串中寻找一个子串，看它是否能归约到文法的某个非终结符号，该子串称为“可归约串”。5.1 确定的自顶向下分析思想确定的自顶向下分析思想 确定的自顶向下分析方法:首先要解决从某文法的开始符号出发，对给定的输入符号串如何根据当前的输入符号(单词符号)唯一地确定选用哪个产生式替换相应非终结符往下推导. 例 5.1若有文法G1S:S pA |qBA cAd|aB d B |c识别输入串w= pccadd是否是G1S的句子试探推导过程：S pA pcAd pccAdd pccadd试探

5、成功。这个文法有以下两个特点这个文法有以下两个特点： 每个产生式的右部都由终结符号开始。 如果两个产生式有相同的左部，那么它们的右部由不同的终右部由不同的终 结符开始。即每个产生式的右部的开始终结符不同。结符开始。即每个产生式的右部的开始终结符不同。对于这样的文法显然在推导过程中完全可以根据当前的输入符对于这样的文法显然在推导过程中完全可以根据当前的输入符号决定选择哪个产生式往下推导，因此分析过程是唯一确定的。号决定选择哪个产生式往下推导，因此分析过程是唯一确定的。 例 5.2若有文法G2S:S Ap |BqA a|cA B b|dB识别输入串w=ccap是否是G2S的句子，那么试探推出输入串

6、的推导过程为 ：S Ap cAp ccAp ccap试探推导成功。文法的特点是：文法的特点是： 产生式的右部不全是由终结符开始。 如果两个产生式有相同的左部，它们的右部是由不同的 终结 符或非终结符开始。 文法中无空产生式。对于产生式中相同左部含有非终结符开始的产生式时，在推导对于产生式中相同左部含有非终结符开始的产生式时，在推导过程中选用哪个产生式不像例过程中选用哪个产生式不像例5.1文法那样直观，对于文法那样直观，对于 W=ccap 为输入串时，其第一个符号是为输入串时，其第一个符号是c，这时从，这时从S出发选择出发选择 SAp 还是还是选择选择 SBq，需要知道，需要知道，Ap或或Bq它

7、们的它们的开始终结符号集合开始终结符号集合是什么？是什么？因为因为c是包含在是包含在Ap的的开始终结符号集合中开始终结符号集合中，且不包含在，且不包含在Bq的的开开始终结符号集合中始终结符号集合中，则选择，则选择 SAp 往下进行推导。往下进行推导。S Ap |BqA a|cA B b|dB一个文法一个文法符号串符号串的终结符的首符集定义如下的终结符的首符集定义如下： 定义定义5.1 设设G=(VT，VN，S，P)是是上下文无关文法上下文无关文法FIRST()=a| a,aVT，,V*若若 ,则规定则规定FIRST()不难求出在例5.2文法G2中FIRST(Ap)=a,cFIRST(Bq)=b

8、,d因此有因此有 FIRST(Ap)(FIRST(Bq)= 这样文法这样文法G中，中，两个产生式有相同的左部，它们的右部是由不同的终结 符或非终结符开始。但它们右部的符号串可能推导出的但它们右部的符号串可能推导出的First集不相交，因而可以根据当前的输入符号是属于哪个产生式的集不相交，因而可以根据当前的输入符号是属于哪个产生式的FIRST集而决定选择相应产生式进行推导，因此仍能构造确定的自集而决定选择相应产生式进行推导，因此仍能构造确定的自顶向下分析。顶向下分析。G2：S Ap |BqA a|cA B b|dB例 5.3若有文法G3S:S aA|dA bAS|识别输入串w=abd是否是G3S

9、的句子试探推导出abd的推导过程为：S aA abAS abS abd试探推导成功。 文法的特点是：文法的特点是：文法中含有空产生式。从以上推导过程中我们可以看到在第2步到第3步的推导中，因当前面临输入符号为因当前面临输入符号为d，而最左非终结符，而最左非终结符A的产生式右部的开始符号集合都不包含的产生式右部的开始符号集合都不包含d，但有，但有，因此对于因此对于d 的匹的匹配自然认为配自然认为只能依赖于在可能的推导过程中只能依赖于在可能的推导过程中A的后面的符号，所以的后面的符号，所以这时选用产生式这时选用产生式A往下推导，而往下推导，而当前当前A后面的符号为后面的符号为S，S产生式产生式右部

10、的开始的终结符号集合包含了右部的开始的终结符号集合包含了d，所以可匹配。，所以可匹配。当一个文法中相同左部非终结符的右部存在能 的情况则必须知道该非终结符的后跟符号的集合中的符号是该非终结符的后跟符号的集合中的符号是否可以唯一地确定选择哪个产生式。否可以唯一地确定选择哪个产生式。为此，我们定义一个文法非终结符的后跟符号的集合如下： 定义定义5.2： 设 G=(VT，VN，S，P)是上下文无关 文法，AVN，S是开始符号FOLLOW(A)=a|S A,且aVT，aFIRST(),VT* ,V+若S A,且 , 则#FOLLOW(A)。也可定义为：FOLLOW(A)=a|S Aa,a VT若有S

11、A，则规定#FOLLOW(A)这里我们用#作为输入串的结束符，或称为句子括号，如：#输入串#。因此当文法中含有形如：AA的产生式时，其中AVN，,V*，当,不同时推导出空时，设 , ,则当FIRST()( FIRST()FOLLOW(A)= 时，对于非终结符A的替换仍可唯一地确定候选。综合以上情况可定义综合以上情况可定义选择集合选择集合SELECT如下：如下： 定义定义5.3 给定上下文无关文法的产生式A, AVN,V*, 若 ,则SELECT(A)=FIRST()如果 则： SELECT(A)=（FIRST() ）FOLLOW(A)是否所有的文法都能采用确定的自上而下的分析是否所有的文法都能

12、采用确定的自上而下的分析例 5.15.3都是确定的自上而下语法分析 ，由当前的输入符号能唯一确定选择哪个产生式进行推导。但并非任意一个文法都能用确定的自顶向下分析法。引起自顶向下分析不确定的原因有以下三种情况： 由于相同左部的产生式的右部开始符号集由于相同左部的产生式的右部开始符号集合交集不为空而引起回溯。合交集不为空而引起回溯。 该文法的特点是：该文法的特点是：关于关于A的产生式的不同右部开始符号集合都含有的产生式的不同右部开始符号集合都含有a，因此要替，因此要替换非终结符换非终结符A时，对当前输入符为时，对当前输入符为a的情况，不能确定用产生式的情况，不能确定用产生式Aab 的右部还是用的

13、右部还是用Aa的右部去替换。所以导致必须用带回溯的右部去替换。所以导致必须用带回溯的自顶向下分析的自顶向下分析， 由于相同左部非终结符的右部存在能 的情况且该非终结符的后跟符号的集合中含有其它右部开始符号集合的元素。这是一个不确定的语法分析这是一个不确定的语法分析文法含有左递归，可见一个文法含有左递归时不能用确定的自顶向文法含有左递归，可见一个文法含有左递归时不能用确定的自顶向下分析下分析 由于文法含有左递归而引起回溯。文法含有左递归，一个文法含有左递归时不能用确定的自顶向文法含有左递归，一个文法含有左递归时不能用确定的自顶向下分析。由以上例子可以看出，例下分析。由以上例子可以看出，例5.4例

14、例5.6的文法不能用确定的文法不能用确定的自顶向下分析的自顶向下分析, 可用带回溯的自顶向下分析。可用带回溯的自顶向下分析。5.2 LL(1) 文法的定义和判别文法的定义和判别由5.1的例1例6可知，一个文法能否用确一个文法能否用确定的自顶向下分析与文法中相同左部的每定的自顶向下分析与文法中相同左部的每个产生式右部的开始符号集合有关，当某个产生式右部的开始符号集合有关，当某个非终结符能推出个非终结符能推出 时则与该非终结符时则与该非终结符的后跟符号集合也有关。综合以上两点，的后跟符号集合也有关。综合以上两点，即一个文法能否用确定的自顶向下分析与即一个文法能否用确定的自顶向下分析与产生式的产生式

15、的SelectSelect集有关。此外在产生式中集有关。此外在产生式中不存在左递归。不存在左递归。n定义定义5.4 一个上下文无关文法是LL(1)文法的充分必要条件是：对每个非终结符A的两个不同产生式，A, A,满足SELECT(A)SELECT(A)= 其中，不同时能 LL(1) 文法的定义文法的定义LL(1)文法的含义： 第一个L 从左到右扫描输入串 第二个L 生成的是最左推导 1 向右看一个输入符号便可 决定选择哪个产生式。例：判断下列文法是否是LL(1)文法G：SaA Sd AbAS A解： select(SaA)=a select(S d)=d select (SaA) select

16、(S d)= select(AbAS)=b select(A) =First()-Follow(A) =Follow(A)=a,d,#select (AbAS) select(A )=所以，该文法是LL（1）文法。例：判断下列文法是否是LL(1)文法 文法G S为：SaASSbAbAA例 文法G S为：SaASSbAbAA则 SELECT(SaAS)=aSELECT(Sb)=bSELECT(AbA)=bSELECT(A)=a,b所以 SELECT(SaAS)SELECT(Sb)=ab= SELECT(AbA)SELECT(A)=ba,b 因此，该文法不是LL(1)文法，因而也就不可能用确定的自

17、顶向下分析。LL(1)文法的判别文法的判别 当我们需选用自顶向下分析技术时，首先必须判别所给文法是否是LL(1)文法。因而我们对任给文法需计算FIRST、FOLLOW、SELECT集合，进而判别文法是否为LL(1)文法。在下面的讨论中我们假定所给文法是经过压缩的。 所谓文法是经过压缩的是指：文法中不得含有有害规则和多余规则有害规则有害规则：形如UU的产生式。会引起文法的二义性多余规则多余规则：指文法中任何句子的推导都不会用到的规则 文法中某些非终结符不在任何规则的右部出现，该非终结符称为不可到达。 文法中某些非终结符，由它不能推出终结符号串，该非终结符称为不可终止。含有、情况非终结符的产生式都

18、为多余规则。 例：GS 为： 1) SBe 2) BCe 3) BAf 4) AAe 5) Ae6) CCf7) Df经对每个产生式进行分析可发现非终结符D为不可到达，C为不可终止含D 、C的产生式 2)，6)，7)为多余规则应去掉。判别步骤：判别步骤：1. 求出能推出的非终结符首先建立一个以文法的非终结符个数为上界的一维数组，其数组元素为非终结符，对应每一非终结符有一标志位，用以记录能否推出。其值有三种情况：未定、是、否。 计算能推出的非终结符步骤如下： 将数组X 中对应每一非终结符的标记置初值为“未定”。 扫描文法中的产生式。(a) 删除所有右部含有终结符的产生式，若这使得以某一非终结符为

19、左部的所有产生式都被删除，则将数组中对应该非终结符的标记值改为“否”，说明该非终结符不能推出。(b) 若某一非终结符的某一产生式右部为，则将数组中对应该非终结符的标志置为“是”，并从文法中删除该非终结符的所有产生式。例中对应非终结符A、B的标志改为“是”。 扫描产生式右部的每一符号。(a) 若所扫描到的非终结符号在数组中对应的标志是“是”，则删去该非终结符，若这使产生式右部为空，则对产生式左部的非终结符在数组中对应的标志改“是”，并删除该非终结符为左部的所有产生式。(b) 若所扫描到的非终结符号在数组中对应的标志是“否”，则删去该产生式，若这使产生式左部非终结符的有关产生式都被删去，则把在数组

20、中该非终结符对应的标志改成“否”。 重复，直到扫描完一遍文法的产生式，数组中非终结符对应的特征再没有改变为止例5.7若文法G7S为： SABSbCAAbBBaDCADCbDaSDc例5.5所对应数组X 的内容如表5.1。 表5.1非终结符能否推出空的表 非终结符SABCD初值第一次扫描第二次扫描未定是未定是未定是未定否未定否2)计算FIRST集4、若XVN；Y1，Y2，YiVN，且有产生式XY1 Y2 Yn；当Y1 Y2 Yi-1都 时，(其中1in)，则FIRST(Y1)、FIRST(Y2)、FIRST(Yi-1)的所有非空元素和FIRST(Yi)都包含在FIRST(X)中。5、当(4)中所

21、有Yi ,(i=1,2,n)，则FIRST(X)=(FIRST(Y1) ） （FIRST(Y2) ） （FIRST(Yn) ） 反复使用上述反复使用上述(2)(5)步直到每个符号的步直到每个符号的FIRST集合不再增大为止。集合不再增大为止。求出每个文法符号的FIRST集合后也就不难求出一个符号串的FIRST集合。n若符号串V*，=X1 X2 Xn,当X1 ,则置FIRST()= FIRST(X1)。n若对任何j(1ji-1，2in), FIRST(Xj), 则FIRST()= (FIRST(Xj)-)FIRST(Xi)当所有FIRST(Xj)(1jn)都含有时，则FIRST()= (FIRS

22、T(Xj)i-1j=1nj=1例文法G S为：SABSbCAAbBBaDCADCbDaSDc求每个终结符的First集。例文法G S为：SABSbCAAbBBaDCADCbDaSDcFIRST(S)=FIRST(A)FIRST(B)b =b,a,FIRST(A)=b= b,FIRST(B)aa,FIRST(C)=FIRST(A) FIRST(D)FIRST(b)=b,a,cFIRST(D)=ac=a,c也可以由关系图法求文法符号的FIRST集，可作为一种验证。其方法为：(a) 每个文法符号对应图中一个结点，对应终结符的结点时用符号本身标记，对应非终结符的结点用FIRST(A)标记。这里A表示非

23、终结符。(b) 如果文法中有产生式AX，且 ,则从对应A的结点到对应X的结点连一条箭弧。(c) 凡是从FIRST(A)结点有路径可到达的终结符结点所标记的终结符都为FIRST(A)的成员。(d) 由是否为某非终结符FIRST集的成员，若是则将加入该非终结符的FIRST集中。 文法G S为：SABSbCAAbBBaDCADCbDaSDc FIRST(S)=b,a,FIRST(A)=b,FIRST(B)=a,FIRST(C)=a,b,cFIRST(D)=a,c3）计算）计算FOLLOW集集 根据定义计算根据定义计算 对文法中每一 AVN 计算 FOLLOW(A)(a) 设S为文法中开始符号，把#加

24、入FOLLOW(S)中(这里“#” 为句子括号)。(b) 若AB是一个产生式，则把FIRST()的非空元素加入 FOLLOW(B)中。如果 则把FOLLOW(A)也加入FOLLOW(B)中。(c) 反复使用(b)直到每个非终结符的FOLLOW集不再增大为止。对(b)中 时，则把FOLLOW(A)也加入FOLLOW(B)中的解释：因为当有形如：D1A1AB的产生式时，A，B，DVN，1,1,V*，在推导过程中可能出现句型序列如：S 1A1 1B1 1B1 ；（因有 ）由定义5.2可知FIRST(1) FOLLOW(A)和FIRST(1)FOLLOW(B)，所以也就有FOLLOW(A) FOLLO

25、W(B)。例：文法G S为：SABSbCAAbBBaDCADCbDaSDc求每个非终结符的Follow集。文法G S为：SABSbCAAbBBaDCADCbDaSDc解： FOLLOW(S)=# FOLLOW(D) #FOLLOW(A)=(FIRST(B) ) FOLLOW(S) FIRST(D) a,#,cFOLLOW(B)=FOLLOW(S)=#FOLLOW(C)=FOLLOW(S)=#FOLLOW(D)=#也可用关系图法求非终结符的FOLLOW集。(a) 文法G中的每个符号和“#”对应图中的一个结点，对应终结符和“#”的结点用符号本身标记。对应非终结符的结点(如AVN)则用FOLLOW(

26、A)或FIRST(A)标记。(b) 从开始符号S的FOLLOW(S)结点到“#”号的结点连一条箭弧。(c) 如果文法中有产生式ABX, 且 ,则从FOLLOW(B)结点到FIRST(X)结点连一条弧，当XVT时，则与X相连。(d) 如果文法中有产生式AB, 且 ，则从FOLLOW(B)结点到FOLLOW(A)结点连一条箭弧。(e) 对每一FIRST(A)结点如果有产生式AX, 且 , 则从FIRST(A)到FIRST(X)连一条箭弧。 (f) 凡是从FOLLOW(A)结点有路径可以到达的终结符或#号的结点，其所标记的终结符或#号即为FOLLOW(A)的成员。对例5.5文法用关系图法计算FOLL

27、OW集，如图所示, 则得FOLLOW(S)=#FOLLOW(A)=a,c,#FOLLOW(B)=#FOLLOW(C)=#FOLLOW(D)=#与根据定义计算结果相同。4） 计算SELECT集对例5.5文法的FIRST集和FOLLOW集计算结果如表。文法的FIRST集和FOLLOW集表非终结符名是否T*FIRST集FOLLOW集S是b,a,#A是b,a,c,#B是a,#C否a,b,c#D否a,c#每个产生式的SELECT集合计算为：SELECT(SAB)=FIRST(AB) FOLLOW(S)=b,a,#SELECT(SbC)=FIRST(bC)=bSELECT(A)=FIRST()FOLLOW

28、(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由以上计算结果可得相同左部产生式的SELECT交集为：SELECT(SAB)SELECT(SbC)=b,a,#b=b SELECT(A)SELECT(Ab)=a,c,#b= SELECT(B)SELECT(BaD)=#a= SELECT(CAD)SELE

29、CT(Cb)b,a,cbb SELECT(DaS)SELECT(Dc)=ac 由LL(1)文法定义知该文法不是LL(1)文法，因为关于S和C的相同左部其产生式的SELECT集的交集不为空。 判断它是否是判断它是否是LL(1)文法文法文法G S为：SABSbCAAbBBaDCADCbDaSDc每个产生式的SELECT集合计算为：SELECT(SAB)=（FIRST(AB)- ) FOLLOW(S)=b,a,#SELECT(SbC)=FIRST(bC)=bSELECT(A)=(FIRST() - ) FOLLOW(A)=a,c,#SELECT(Ab)=FIRST(b)=bSELECT(B)=(FI

30、RST() - ) 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文法G S为：SABSbCAAbBBaDCADCbDaSDc由以上计算结果可得相同左部产生式的SELECT交集为：SELECT(SAB)SELECT(SbC)=b,a,#b=b SELECT(A)SELECT(Ab)=a,c,#b= SELECT(B)SELECT(BaD)=#a= SELECT(CAD)SELECT(Cb)b

31、,a,cbb SELECT(DaS)SELECT(Dc)=ac 由LL(1)文法定义知该文法不是LL(1)文法，因为关于S和C的相同左部其产生式的SELECT集的交集不为空。5.3非LL(1)文法到LL(1)文法的等价转换由前面可知：确定的自顶向下分析要求对给定语言的文法必须是LL(1)形式。然而，不一定每个语言都有LL(1)文法。对一个语言的非LL(1)文法是否能变换为等价的LL(1)形式以及如何变换是本节讨论的主要问题。若文法中含有直接或间接左递归，或含有左公共因子则若文法中含有直接或间接左递归，或含有左公共因子则该文法肯定不是该文法肯定不是LL(1)文法。因而，我们设法消除文法文法。因而

32、，我们设法消除文法中的左递归，提取左公共因子对文法进行等价变换，在中的左递归，提取左公共因子对文法进行等价变换，在某些特殊情况下可能使其变为某些特殊情况下可能使其变为LL(1)文法。文法。1提取左公共因子提取左公共因子若文法中含有形如：A|的产生式，这导致了对相同左部的产生式其右部的FIRST集相交，也就是SELECT(A)SELECT(A) ，不满足LL(1)文法的充分必要条件。现将产生式A|进行等价变换为：A（|）使产生式变换为：AAA|写成一般形式为：写成一般形式为：A1|2|n，提取左公共因子后变为：，提取左公共因子后变为：A（1|2|n），再引进非终结符），再引进非终结符A，变为：，

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

34、终结符开始，因此左公共因子可能是隐左公共因子可能是隐式的式的，所以这种情况下对右部以非终结符开始的产生式，用其相同左部而右部以终结符开始的产生式进行相应替换进行相应替换，对文法G2分别用(3)、(4)的右部替换(2)中的B，可得： (1) Aad(2) AaAc(3) AbBc(4) BaA(5) BbB提取产生式(1)、(2)的左公共因子得：Aa(d|Ac)AbBcBaABbB引进新非终结符A，去掉(，)后得G为：(1) AaA(2) AbBc(3) Ad(4) AAc(5) BaA(6) BbB不难验证经提取左公共因子后文法例1中的G仍不是LL(1)文法。而文法例2中的G变成LL(1)文法

35、，因此文法中不含左公共因子只是因此文法中不含左公共因子只是LL(1)文法的必要文法的必要条件。条件。值得注意的是对文法进行提取左公共因子变换后，有时会使值得注意的是对文法进行提取左公共因子变换后，有时会使某些产生式变成某些产生式变成无用产生式无用产生式，在这种情况下必须对文法重新，在这种情况下必须对文法重新压缩压缩(或化简或化简例3：若有文法G的产生式为：(1) SaSd(2) SAc(3) AaS(4) Ab用产生式(3)、(4)中右部替换产生式(2)中右部的A，文法变为：(1) SaSd(2) SaSc(3) Sbc(4) AaS(5) Ab对(1)、(2)提取左公共因子得：SaS(d|c

36、)引入新非终结符A后变为：(1) SaSA(2) Sbc(3) Ad|c(4) AaS(5) Ab显然，原文法G3中非终结符A变成不可到达的符号，产生式(4)、(5)也就变为无用产生式，所以应删除。此外也存在某些文法此外也存在某些文法不能在有限步骤内提取完不能在有限步骤内提取完左公共因子。左公共因子。例：若有文法G4的产生式为：(1) SAp|Bq(2) AaAp|d(3) BaBq|e用(2)、(3)产生式的右部替换(1)中产生式的A、B使文法变为：(1) SaApp|aBqq(2) Sdp|eq(3) AaAp|d(4) BaBq|e对(1)提取左公共因子则得：Sa(App|Bqq)再引入

37、新非终符S结果得等价文法为：(1) SaS(2) Sdp|eq(3) SApp|Bqq(4) AaAp|d(5) BaBq|e同样分别用(4)、(5)产生式的右部替换(3)中右部的A、B再提取左公共因子最后结果得：(1) SaS(2) Sdp|eq(3) SaS(4) Sdpp|eqq(5) SAppp|Bqqq(6) AaAp|d(7) BaBq|e可以看出若对(5)中产生式A、B继续用(6)、(7)产生式的右部替换，只能使文法的产生式愈来愈多无限增加下去，但不能得到提取左公共因子的预期结果。由上面所举例子可以说明以下问题：由上面所举例子可以说明以下问题： 不一定每个文法的左公共因子都能在有

38、限的步骤内不一定每个文法的左公共因子都能在有限的步骤内 替换成无左公共因子的文法，上面文法替换成无左公共因子的文法，上面文法G4就是如就是如 此。此。 一个文法提取了左公共因子后，一个文法提取了左公共因子后，只解决了相同左部只解决了相同左部 产生式右部的产生式右部的FIRST集不相交问题集不相交问题，当改写后的文，当改写后的文 法不含空产生式，且无左递归时，则改写后的文法法不含空产生式，且无左递归时，则改写后的文法 是是LL(1)文法，否则还需用文法，否则还需用LL(1)文法的判别方式进文法的判别方式进 行判断才能确定是否为行判断才能确定是否为LL(1)文法。文法。2. 消除左递归消除左递归设

39、一个文法含有下列形式的产生式。1)AA AVN，V* 2)AB BA A,BVN, ,V*可称含1)中产生式的文法为含有直接左递归直接左递归。含2)中产生式的文法有A A 则称文法中含有间接左递归间接左递归，文法中只要含有1)或含有2)的产生式或二者皆有，均认为文法是左递归的，然而，一个文法是左递归时不能采用自顶向下分析一个文法是左递归时不能采用自顶向下分析法。法。为了使某些含有左递归的文法经过等价变换消除左递为了使某些含有左递归的文法经过等价变换消除左递归后可能变为归后可能变为LL(1)文法，可采取下列变换公式：文法，可采取下列变换公式：a) 消除直接左递归，消除直接左递归，把直接左递归改写

40、为右递归把直接左递归改写为右递归，如对文法如对文法G：SSaSb可改写为：可改写为：SbSSaS|一般情况下，假定关于一般情况下，假定关于A的全部产生式是：的全部产生式是：AA1|A2|Am|1|2|n其中，i (1im)不等于,j(1jn)不以A开头， 消除直接左递归后改写为：消除直接左递归后改写为：A1 A|2 A|n AA1 A|2 A|m A|b) 消除间接左递归。消除间接左递归。对于间接左递归的消除需对于间接左递归的消除需先将间接左递归变为直接左先将间接左递归变为直接左递归，然后再按递归，然后再按a)消除直接左递归消除直接左递归。例：文法G为例：(1) AaB(2) ABb(3) B

41、Ac(4) Bd用产生式(1)、(2)的右部代替产生式(3)中的非终结符A得到左部为B的产生式为：(1) BaBc(2) BBbc(3) Bd消除左递归后得：B(aBc|d)BBbcB|再把原来其余的产生式AaB， ABb加入，最终文法为：(1) AaB(2) ABb(3) B(aBc|d)B(4) BbcB|可以检验改写后的文法不 是LL(1)文法。例：文法：E E+T|T T T*F|F F (E)|i 试消除它的左递归E TEE +TE|T FTT *FT| F (E)|ic) 消除文法中一切左递归的算法。消除文法中一切左递归的算法。步骤步骤(P89 P90 算法步骤）算法步骤）1) 把

42、文法的所有非终结符按某一顺序排序；把文法的所有非终结符按某一顺序排序；如如A1，A2,An 2) A1产生式右部用产生式右部用A2，,An表示，表示， A2产生式右部用产生式右部用A3，,An表示，表示， A3产生式右部用产生式右部用A4，,An表示，表示， , An产生式右部用产生式右部用An表示。消除表示。消除An中的直接中的直接左递归。左递归。 3) 去掉无用产生式。去掉无用产生式。把上述算法归结为：把上述算法归结为：若非终结符的排序为A1，A2，An。 for (i=1; i=n ; i+) for (j=1; j=i-1; j+) 将规则Ai Ajr改写： /若Aj 1|2|k /则

43、 ：替换产生式变为：Ai1r|2r|kr 消除规则中的直接左递归 例如，有文法的产生式为：(1) SQc|c(2) QRb|b(3) RSa|a该文法为间接左递归，按上述方法消除该文法的一切左递归。若非终结符排序为若非终结符排序为S、Q、R, （1）式左部为S的产生式是用后面的符号表示，不用修改 (2)号产生式中右部是用后面的符号表示，不用修改， (3)式中R是用前面的S表示， 所以把(1)右部代入(3)得： (4) RQca|ca|a 再将(2)的右部代入(4)得：(5) RRbca|bca|ca|a对(5)消除直接左递归得：R(bca|ca|a)RRbcaR|最终文法变为：SQc|cQRb

44、|bR(bca|ca|a)RRbcaR|若非终结符的排序为若非终结符的排序为R、Q、S, 则把(3)代入(2)得：QSab|ab|b再将此代入(1)得：SSabc|abc|bc|c消除该产生式的左递归后，最终文法变为：S(abc|bc|c)SSabcS|QRb|bRSa|a由于Q、R为不可到达的非终结符，所以以Q、R为左部及包含Q、R的产生式应删除。当非终结符的排序不同时，最后结果的产生式形式不同，但它们是等价的。(1) SQc|c(2) QRb|b(3) RSa|a5.5 确定的自顶向下分析方法确定的自顶向下分析方法 n递归子程序法n预测分析法递归子程序法也称也称为递归子程序法也称也称为递归

45、下降分析器递归下降分析器（ recursive-descent parser ） 例：G：E TE E +TE| T FT T *FT| F (E)|i 写出它的递归子程序。Procedure E Begin T; E End;Procedure T Begin F; T End;Procedure E Begin if sym=+ then Begin getsym T; E; End End; Procedure T Begin if sym=* then Begin getsym; F;T; End EndProcedure F Begin if symi then Begin if s

46、ym=( then Begin getsym; E; if sym=) then getsym; else Error End else Error End EndF (E)|i 递归子程序法的程序实现可以参照第2章PL/0编译程序的实现。递归子程序要求文法必须是递归子程序要求文法必须是LL(1)文法。文法。预测分析方法预测分析方法 预测分析方法是自顶向下分析的另一种方法，一个预测分析方法是自顶向下分析的另一种方法，一个预测分析器是由三个部分组成。预测分析器是由三个部分组成。 预测分析程序预测分析程序(总控程序总控程序) 先进后出栈先进后出栈(stack) 预测分析表预测分析表表驱动预测分析程

47、序模型表驱动预测分析程序模型a1a2aian#分析表M控制程序输入串：栈顶#x1xj输出分析栈 对上图所示的对上图所示的预测分析器预测分析器说明如下：说明如下： (1) (1) 输入串是待分析的符号串，它以界符输入串是待分析的符号串，它以界符“#”#”作为结束作为结束标志。标志。( (注：注：# #不是文法符号，是由分析程序自动添加的。不是文法符号，是由分析程序自动添加的。) ) (2) (2) 分析栈中存放分析过程中的文法符号。分析开始时栈分析栈中存放分析过程中的文法符号。分析开始时栈底先放入一个底先放入一个“#”#”，然后再压入文法的开始符号；当分，然后再压入文法的开始符号；当分析栈中仅剩

48、析栈中仅剩“#”#”，输入串指针也指向串尾的，输入串指针也指向串尾的“#”#”时，分时，分析成功。析成功。 (3) (3) 分析表用一个矩阵分析表用一个矩阵( (或二维数组或二维数组)M)M表示，它概括了相表示，它概括了相应文法的全部信息。矩阵的每一行与文法的一个非终结符应文法的全部信息。矩阵的每一行与文法的一个非终结符相关联，而每一列与文法的一个终结符或界符相关联，而每一列与文法的一个终结符或界符“#”#”相关相关联。对联。对MA,aMA,a来说，来说，A A为非终结符，而为非终结符，而a a为终结符或为终结符或“#”#”。分析表元素分析表元素MA,aMA,a中的内容为一条关于中的内容为一条

49、关于A A的产生式，表明的产生式，表明当当A A面临输入符号面临输入符号a a时当前推导所应采用的候选式；当元素时当前推导所应采用的候选式；当元素内容为空白内容为空白( (空白表示空白表示“出错标志出错标志”) )时，则表明时，则表明A A不应该不应该面临这个输入符号面临这个输入符号a a，即输入串含有语法错误。，即输入串含有语法错误。 (4) (4) 控制程序根据分析栈顶符号控制程序根据分析栈顶符号x x和当前输入符号和当前输入符号a a来决来决定分析器的动作：定分析器的动作： 若若x xa a“#”#”，则分析成功，分析器停止工作。，则分析成功，分析器停止工作。 若若x xa“#”a“#”

50、，即栈顶符号，即栈顶符号x x与当前扫描的输入与当前扫描的输入符号符号a a匹配；则将匹配；则将x x从栈顶弹出，输入指针指向下一个输从栈顶弹出，输入指针指向下一个输入符号，继续对下一个字符进行分析。入符号，继续对下一个字符进行分析。 若若x x为一非终结符为一非终结符A A，则查，则查MA,aMA,a： i i若若MA,aMA,a中为一个中为一个A A的产生式，则将的产生式，则将A A自栈顶弹自栈顶弹出，并将出，并将MA,aMA,a中的产生式右部符号串按逆序逐一中的产生式右部符号串按逆序逐一压入栈中；如果压入栈中；如果MA,aMA,a中的产生式为中的产生式为AA，则只将，则只将A A自栈顶弹

51、出。自栈顶弹出。 iiii若若MA,aMA,a中为空，则发现语法错误，调用出错中为空，则发现语法错误，调用出错处理程序进行处理。处理程序进行处理。预测分析程序的框图 分析算法分析算法 BEGINBEGIN 首先把首先把#然后把文法开始符号推入栈；把第一个输入符号读进然后把文法开始符号推入栈；把第一个输入符号读进a; a; FLAGFLAG：=TRUE=TRUE；WHILE FLAG DOWHILE FLAG DO BEGIN BEGIN 把栈顶符号上托出去并放在把栈顶符号上托出去并放在中；中； IF X IF X Vt Vt THEN IF X=a THEN THEN IF X=a THEN

52、把下一把下一个输入符号读进个输入符号读进a a ELSE ERRORELSE ERROR ELSE IF X=# THEN ELSE IF X=# THEN IF X=a THEN FLAG:=FALSE IF X=a THEN FLAG:=FALSE ELSE ERROR ELSE ERROR ELSE IF ELSE IF X,b=X X,b=X X X1 1X X2 2.X.XK K THEN THEN 把把X XK K，X X K-1K-1,.,X,.,X1 1一一推进栈一一推进栈 ELSE ELSEERRORERROR END OF WHILE; END OF WHILE;STOP/

53、STOP/* *分析成功，过程完毕分析成功，过程完毕* *ENDEND将将“#”#”和文法开始符依次压入栈中；和文法开始符依次压入栈中； 把第一个输入符号读入把第一个输入符号读入a a；dodo 把栈顶符号弹出并放入把栈顶符号弹出并放入x x中；中； if (xVif (xVT T) ) if (x if (xa) a) 将下一输入符号读入将下一输入符号读入a;a; else error( else error();); else else if (Mx,a if (Mx,a “xyxy1 1y y2 2yyk k”) ”) 按逆序依次把按逆序依次把y yk k、y yk k1 1、y y1 1压入栈中压入栈中; ; 输出输出“xyxy1 1y y2 2yyk k”;”; else error( else error();); while(x while(x!=“#”) !=“#”) 构造分析表构造分析表M 对文法对文法GS的每个产生式的每个产生式A执行以下执行以下、步。步。 对每个终结符对每个终结符aFIRST(A)，把，把A加入到加入到MA,a中，其中中，其中为含有首字符为含有首字符a的候选式或为惟一的候选式。的候选式或为惟一的候选式。 若若FIRST(A),则对任何属于则对任