【教学课件】第5章自顶向下的语法分析方法.ppt

第5章 自顶向下的语法分析方法,语法分析的作用是识别由词法分析给出的单词符号序列是否是给定文法的正确句子(程序)。目前语法分析常用的方法有:1、自顶向下（自上而下）分析2、自底向上（自下而上）分析,自顶向下分析法也就是从文法的开始符号出发企图推导出与输入的单词串完全相匹配的句子，若输入串是给定文法的句子，则必能推出，反之必然出错。,回顾在“文法和语言”一章中介绍的关于句子、句型和语言的定义及什么叫最左推导、最右推导和规范推导的基本概念。,句型、句子、语言的定义 句型:有文法G S，若S x，且x V*则称x是文法G S的句型。符号 表示经过0步或若干步的推导。句子:有文法GS，若S x，且xVT*，则称x是文法G S的句子。例：GS：S0S1，S01可有推导 S 0S1 00S11 000S111 00001111说明00001111是GS的句子。,句型的分析 句型分析就是识别一个符号串是否为某文法的句型，是某个推导的构造过程。,最左（最右）推导：在推导的任何一步，都是对中的最左（右）非终结符进行替换。最右推导被称为规范推导。由规范推导所得的句型称为规范句型。,句型分析的有关问题 如何选择使用哪个产生式进行推导？假定要被替换的最左非终结符号是V，且左部为V的规则有n条：VA1|A2|An，那么如何确定用哪个右部去替换V呢？如何识别可归约的串？在自下而上的分析方法中，在分析程序工作的每一步，都是从当前串中寻找一个子串，看它是否能归约到文法的某个非终结符号，该子串称为“可归约串”。,5.1 确定的自顶向下分析思想,确定的自顶向下分析方法:首先要解决从某文法的开始符号出发，对给定的输入符号串如何根据当前的输入符号(单词符号)唯一地确定选用哪个产生式替换相应非终结符往下推导.,这个文法有以下两个特点：每个产生式的右部都由终结符号开始。如果两个产生式有相同的左部，那么它们的右部由不同的终 结符开始。即每个产生式的右部的开始终结符不同。对于这样的文法显然在推导过程中完全可以根据当前的输入符号决定选择哪个产生式往下推导，因此分析过程是唯一确定的。,文法的特点是：产生式的右部不全是由终结符开始。如果两个产生式有相同的左部，它们的右部是由不同的 终结 符或非终结符开始。文法中无空产生式。,对于产生式中相同左部含有非终结符开始的产生式时，在推导过程中选用哪个产生式不像例5.1文法那样直观，对于 W=ccap 为输入串时，其第一个符号是c，这时从S出发选择 SAp 还是选择 SBq，需要知道，Ap或Bq它们的开始终结符号集合是什么？因为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,d因此有 FIRST(Ap)(FIRST(Bq)=这样文法G中，两个产生式有相同的左部，它们的右部是由不同的终结 符或非终结符开始。但它们右部的符号串可能推导出的First集不相交，因而可以根据当前的输入符号是属于哪个产生式的FIRST集而决定选择相应产生式进行推导，因此仍能构造确定的自顶向下分析。,G2：S Ap|BqA a|cA B b|dB,文法的特点是：文法中含有空产生式。从以上推导过程中我们可以看到在第2步到第3步的推导中，因当前面临输入符号为d，而最左非终结符A的产生式右部的开始符号集合都不包含d，但有，因此对于d 的匹配自然认为只能依赖于在可能的推导过程中A的后面的符号，所以这时选用产生式A往下推导，而当前A后面的符号为S，S产生式右部的开始的终结符号集合包含了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 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),是否所有的文法都能采用确定的自上而下的分析,该文法的特点是：关于A的产生式的不同右部开始符号集合都含有a，因此要替换非终结符A时，对当前输入符为a的情况，不能确定用产生式Aab 的右部还是用Aa的右部去替换。所以导致必须用带回溯的自顶向下分析，,这是一个不确定的分析,文法含有左递归，可见一个文法含有左递归时不能用确定的自顶向下分析,文法含有左递归，一个文法含有左递归时不能用确定的自顶向下分析。由以上例子可以看出，例5.4例5.6的文法不能用确定的自顶向下分析,可用带回溯的自顶向下分析。,5.2 LL(1)文法的定义和判别,由5.1的例1例6可知，一个文法能否用确定的自顶向下分析与文法中相同左部的每个产生式右部的开始符号集合有关，当某个非终结符能推出 时则与该非终结符的后跟符号集合也有关。综合以上两点，即一个文法能否用确定的自顶向下分析与产生式的Select集有关。此外在产生式中不存在左递归。,定义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(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)文法，因而也就不可能用确定的自顶向下分析。,LL(1)文法的判别,当我们需选用自顶向下分析技术时，首先必须判别所给文法是否是LL(1)文法。因而我们对任给文法需计算FIRST、FOLLOW、SELECT集合，进而判别文法是否为LL(1)文法。,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)中所有Yi,(i=1,2,n)，则FIRST(X)=(FIRST(Y1)）（FIRST(Y2)）（FIRST(Yn)）,反复使用上述(2)(5)步直到每个符号的FIRST集合不再增大为止。,例,求每个终结符的First集。,例,文法G S为：SABSbCAAb,BBaDCADCbDaSDc,FIRST(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表示非终结符。(b)如果文法中有产生式AX，且,则从对应A的结点到对应X的结点连一条箭弧。(c)凡是从FIRST(A)结点有路径可到达的终结符结点所标记的终结符都为FIRST(A)的成员。(d)由是否为某非终结符FIRST集的成员，若是则将加入该非终结符的FIRST集中。,FIRST(S)=b,a,FIRST(A)=b,FIRST(B)=a,FIRST(C)=a,b,cFIRST(D)=a,c,计算FOLLOW集 根据定义计算 对文法中每一 AVN 计算 FOLLOW(A)(a)设S为文法中开始符号，把#加入FOLLOW(S)中(这里“#”为句子括号)。(b)若AB是一个产生式，则把FIRST()的非空元素加入 FOLLOW(B)中。如果 则把FOLLOW(A)也加入FOLLOW(B)中。(c)反复使用(b)直到每个非终结符的FOLLOW集不再增大为止。,求每个非终结符的Follow集。,解：FOLLOW(S)=#FOLLOW(D)#FOLLOW(A)=(FIRST(B)FOLLOW(S)FIRST(D)a,#,cFOLLOW(B)=FOLLOW(S)=#FOLLOW(C)=FOLLOW(S)=#FOLLOW(D)=#,判断它是否是LL(1)文法,每个产生式的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)=(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,文法G S为：SABSbCAAb,BBaDCADCbDaSDc,由以上计算结果可得相同左部产生式的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,a,cbb SELECT(DaS)SELECT(Dc)=ac 由LL(1)文法定义知该文法不是LL(1)文法，因为关于S和C的相同左部其产生式的SELECT集的交集不为空。,非LL(1)文法到LL(1)文法的等价转换,由前面可知：确定的自顶向下分析要求对给定语言的文法必须是LL(1)形式。然而，不一定每个语言都有LL(1)文法。对一个语言的非LL(1)文法是否能变换为等价的LL(1)形式以及如何变换是本节讨论的主要问题。,若文法中含有直接或间接左递归，或含有左公共因子则该文法肯定不是LL(1)文法。因而，我们设法消除文法中的左递归，提取左公共因子对文法进行等价变换，在某些特殊情况下可能使其变为LL(1)文法。,1提取左公共因子若文法中含有形如：A|的产生式，这导致了对相同左部的产生式其右部的FIRST集相交，也就是SELECT(A)SELECT(A)，不满足LL(1)文法的充分必要条件。,现将产生式A|进行等价变换为：A（|）,使产生式变换为：AAA|,写成一般形式为：A1|2|n，提取左公共因子后变为：A（1|2|n），再引进非终结符A，变为：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)的右部以非终结符开始，因此左公共因子可能是隐式的，所以这种情况下对右部以非终结符开始的产生式，用其相同左部而右部以终结符开始的产生式进行相应替换，对文法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)文法，因此文法中不含左公共因子只是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)引入新非终结符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)再引入新非终符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)产生式的右部替换，只能使文法的产生式愈来愈多无限增加下去，但不能得到提取左公共因子的预期结果。,由上面所举例子可以说明以下问题：不一定每个文法的左公共因子都能在有限的步骤内 替换成无左公共因子的文法，上面文法G4就是如 此。一个文法提取了左公共因子后，只解决了相同左部 产生式右部的FIRST集不相交问题，当改写后的文 法不含空产生式，且无左递归时，则改写后的文法 是LL(1)文法，否则还需用LL(1)文法的判别方式进 行判断才能确定是否为LL(1)文法。,2.消除左递归,设一个文法含有下列形式的产生式。1)AA AVN，V*2)AB BA A,BVN,V*可称含1)中产生式的文法为含有直接左递归。含2)中产生式的文法有A A 则称文法中含有间接左递归，文法中只要含有1)或含有2)的产生式或二者皆有，均认为文法是左递归的，然而，一个文法是左递归时不能采用自顶向下分析法。,为了使某些含有左递归的文法经过等价变换消除左递归后可能变为LL(1)文法，可采取下列变换公式：a)消除直接左递归，把直接左递归改写为右递归，如对文法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)BAc(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)|i,c)消除文法中一切左递归的算法。,步骤(P83 P84 算法步骤）1)把文法的所有非终结符按某一顺序排序；如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/则：替换产生式变为：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|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|a,例：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 End,Procedure F Begin if symi then Begin if sym=(then Begin getsym;E;if sym=)then getsym;else Error End else Error End End,F(E)|i,（见附录）,递归子程序要求文法必须是LL(1)文法。,预测分析方法 预测分析方法是自顶向下分析的另一种方法，一个预测分析器是由三个部分组成。预测分析程序(总控程序)先进后出栈(stack)预测分析表,表驱动予测分析程序模型,Input,#,总控程序,预测分析表,stack,其中只有预测分析表与文法有关，而分析表又可用一个矩阵M(或称二维数组)表示。矩阵的元素MA，a中的下标A表示非终结符，a为终结符或句子括号“#”，矩阵元素MA,a中的内容为存放着一条关于A的产生式，表明当用非终结符A向下推导时，面临输入符a时，所应采取的候选产生式，当元素内容无产生式时，则表明用A为左部向下推导时遇到了不该出现的符号，因此元素内容为转向出错处理的信息,A,a,A,A遇到输入符a，选用哪个产生式，如果A，a Frist()。如果A，a Follow(A),即如果a select(A)则把A 加入到M(A,a)中。,解：(1)判断它是否是LL（1）文法因为该文法含有左递归，所以不是LL（1）文法，必须改写成LL(1)文法：G E:(1)E TE(2)E+TE(3)E(4)T FT(5)T*FT(6)T(7)F(E)(8)F a,例：为文法G(E):E E+T|T T T*F|F F a|(E)构造预测分析表。,Select(E TE)=First(T)=First(F)=a,(Select(E+TE)=+Select(E)=Follow(E)=Follow(E)=(#,)Select(T FT)=First(F)=(,aSelect(T*FT)=*Select(T)=Follow(T)=Follow(T)=(First（E)-)Follow(E)=(First（E)-)Follow(E)=+,#,)Select(F(E)=(Select(F a)=a,G E:(1)E TE(2)E+TE(3)E(4)T FT(5)T*FT(6)T(7)F(E)(8)F a,G E:(1)E TE(2)E+TE(3)E(4)T FT(5)T*FT(6)T(7)F(E)(8)F a,分析输入串#a+a#,栈内容 栈顶符号 当前输入 余留串 MX,b 1#E E a+a#E TE2#ET T a+a#T FT3#ETF F a+a#F a4#ETa a a+a#匹配a5#ET T+a#T 6#E E+a#E+TE7#ET+a#匹配+8#ET T a#T FT 9#ETF F a#F a10#ETa a a#匹配a11#ET T#T 12#E E#E 13#,分析算法,BEGIN 首先把#然后把文法开始符号推入栈；把第一个输入符号读进a;FLAG：=TRUE；WHILE FLAG DO BEGIN 把栈顶符号上托出去并放在中；IF X Vt THEN IF X=a THEN 把下一个输入符号读进a ELSE ERROR ELSE IF X=#THEN IF X=a THEN FLAG:=FALSE ELSE ERROR ELSE IF X,b=X X1X2.XK THEN 把XK，X K-1,.,X1一一推进栈 ELSEERROR END OF WHILE;STOP/*分析成功，过程完毕*END,LL(1)文法的性质：LL(1)文法是无二义的 LL(1)文法不含左递归非LL(1)文法的改造消除左递归提左公因子 将产生式|变换为：B B|,