自顶向下语法分析方法课件.ppt

1、自顶向下语法分析方法自顶向下语法分析方法4.1 确定的自顶向下分析思想确定的自顶向下分析思想n确定的自顶向下分析方法，首先要解决从文法确定的自顶向下分析方法，首先要解决从文法的开始符号出发，如何的开始符号出发，如何根据当前的输入符号（根据当前的输入符号（单词符号）唯一地确定选用哪个产生式单词符号）唯一地确定选用哪个产生式替换相替换相应非终结符往下推导，或构造一棵相应的语法应非终结符往下推导，或构造一棵相应的语法树。树。n例例4.1设文法设文法G1S：S pA|qBA cAd|aB dB|b考虑对输入串考虑对输入串w=pccadd的分析。的分析。n这个文法有以下两个特点：这个文法有以下两个特点：

2、q每个产生式的右部都由终结符号开始。每个产生式的右部都由终结符号开始。q如果两个产生式有相同的左部，那么它们的右部由如果两个产生式有相同的左部，那么它们的右部由不同的终结符开始。不同的终结符开始。n例例4.2设文法设文法G2S：S ApS BqA aA cAB bB db考虑对输入串考虑对输入串w=ccap的分析。的分析。n这个文法有以下两个特点：这个文法有以下两个特点：q产生式的右部不全是由终结符开始产生式的右部不全是由终结符开始q如果两个产生式有相同的左部，它们的右部是由不如果两个产生式有相同的左部，它们的右部是由不同的终结符或非终结符开始。同的终结符或非终结符开始。q文法中无空产生式文法

3、中无空产生式n定义定义4.1设设G=(VT,VN,P，S)是上下文无关文法是上下文无关文法FIRST()=a|a,aVT,V*若若 ，则规定，则规定FRIST()。如：如：FIRST(Ap)=a,cFIRST(Bq)=b,d*n例例4.3设文法设文法GS：SaASdAbASA考虑对输入串考虑对输入串w=abd的分析。的分析。n结论结论q当某一非终结符的产生式中含有空产生式时，它的当某一非终结符的产生式中含有空产生式时，它的非空产生式右部的首符号集两两不相交，并与在推非空产生式右部的首符号集两两不相交，并与在推导过程中紧跟该非终结符右边可能出现的终结符集导过程中紧跟该非终结符右边可能出现的终结符

4、集也不相交则仍可构造确定的自顶向下分析。也不相交则仍可构造确定的自顶向下分析。n定义定义4.2设设G=(VT,VN,P,S)是上下文无关文法是上下文无关文法,对对AVN定义定义FOLLOW(A)=a S A 且且aVT，aFRIST()，V*，V+若若S uA，且且 ，则规定，则规定#FOLLOW(A)如：如：FOLLOW(A)=FIRST(S)#=a,d,#*n定义定义4.3给定上下文无关文法的产生式给定上下文无关文法的产生式A，A VN，V*,若若 ，则，则SELECT(A)=FIRST()若如果若如果 ，则，则SELECT(A)=(FIRST()-)FOLLOW(A)*n定义定义4.4一

5、个上下文无关文法是一个上下文无关文法是LL(1)文法的充分必要文法的充分必要条件是，对每个非终结符条件是，对每个非终结符A的两个不同产生式的两个不同产生式，A，A，满足，满足SELECT(A)SELECT(A )=其中其中、不能同时不能同时 。*nLL(1)文法的含义文法的含义q第第1个个“L”指的是由左向右地处理输入。指的是由左向右地处理输入。q第第2个个“L”指的是它为输入串描绘出一个最左推导。指的是它为输入串描绘出一个最左推导。q括号中的数字括号中的数字1意味着它只需向右看意味着它只需向右看1个符号便可决个符号便可决定如何推导即选择哪个产生式（规则）进行推导。定如何推导即选择哪个产生式（

6、规则）进行推导。4.2 LL(1)文法的判别文法的判别n求出能推出求出能推出的非终结符的非终结符n计算计算FIRST集集n计算计算FOLLOW集集n计算计算SELECT集集n判别是否是判别是否是LL(1)文法文法n例：设文法例：设文法GS 为为:SABSbCAAbBBaDCADCbDaSDc判断它是否是判断它是否是LL(1)文法。文法。1.求出能推出求出能推出的非终结符的非终结符SABSbCAAbBBaDCADCbDaSDc非终结符非终结符SABCD初值初值未定未定未定未定未定未定未定未定未定未定第一次扫描第一次扫描是是是是否否第二次扫描第二次扫描是是否否2.计算计算FIRST集集n根据定义计

7、算根据定义计算1.若若X V,则则FIRST(X)=X2.若若X VN,且有产生式且有产生式Xa，a V,则则aFIRST(X);若若X也是一条产生式也是一条产生式,则则 FIRST(X).3.若若XY是一个产生式且是一个产生式且Y VN,则把则把FIRST(Y)中的所有非中的所有非 元元素都加到素都加到FIRST(X)中中;若若X Y1Y2YK 是一个产生式是一个产生式,Y1,Y2,Yi-1都是非终结都是非终结符符,而且对于任何而且对于任何j,1j i-1,FIRST(Yj)都含有都含有(即即Y1.Yi-1 ),则把则把FIRST(Yj)中的所有非中的所有非 元素都加元素都加到到FIRST(

8、X)中中;特别是特别是,若所有的若所有的FIRST(Yj,j=1,2,K)均含有均含有,则把则把 加到加到FRIST(X)中中.*n用关系图法求文法符号的用关系图法求文法符号的FIRST集集(自学自学)3.计算计算FOLLOW集集n根据定义计算根据定义计算1.对于文法的开始符号对于文法的开始符号S,置置#于于FOLLOW(S)中中;2.若若B是一个产生式是一个产生式,则把则把 FIRST()-加至加至FOLLOW(B)中中;3.若若B是一个产生式是一个产生式,或或B是一个产是一个产生式而生式而 ，则把，则把FOLLOW(A)加至加至FOLLOW(B)中中*n用关系图法求非终结符的用关系图法求非

9、终结符的FOLLOW集集(自学自学)4.计算计算SELECT集集SELECT(SAB)=a,b,#SELECT(SbC)=bSELECT(A)=a,c,#SELECT(Ab)=bSELECT(B)=#SELECT(BaD)=aSELECT(CAD)=a,b,cSELECT(Cb)=bSELECT(DaS)=aSELECT(Dc)=c5.判别是否是判别是否是LL(1)文法文法 所以文法所以文法GS 不是不是LL(1)文法。文法。4.3 某些非某些非LL(1)文法到文法到LL(1)文法的等价变换文法的等价变换n提取左公共因子提取左公共因子n消除左递归消除左递归1.提取左公共因子提取左公共因子n例例

10、4.6文法文法G1S:SaSbSaSS化为：化为：SaS(b|)S进一步化为：进一步化为：SaSAAbAS结果仍然不是结果仍然不是LL(1)文法。因此，文法中不含左公共文法。因此，文法中不含左公共因子只是因子只是LL(1)文法的必要条件。文法的必要条件。A1|2|n 变换为变换为A(1|2|n)，即，即AAA 1|2|nn例例4.7文法文法G2A:AadABcBaABbB1.化为：化为：AadAaAcAbBcBaABbB2.化为：化为：Aa(d|Ac)AbBcBaABbB3.化为：化为：AaA AbBcAdAAcBaABbBn例例4.8文法文法G3S:SaSdSAcAaSAb1.化为：化为：S

11、aSdSaScSbc AaSAb2.化为：化为：SaS(d|c)Sbc AaSAb3.化为：化为：SaSA SbcAdAcAaSAb结果中结果中A是不可达到的符号。是不可达到的符号。n例例4.9文法文法G4S:SAp|BqAaAp|dBaBq|e1.化为：化为：SaApp|aBqq|dp|eqAaAp|dBaBq|e2.化为：化为：Sa(App|Bqq)Sdp|eqAaAp|dBaBq|e3.化为：化为：SaS Sdq|eqSApp|BqqAaAp|dBaBq|e4.化为：化为：SaS Sdp|eqS aAppp|aBqqq|dpp|eqqAaAp|dBaBq|en结论结论q不一定每个文法的左

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

13、n间接左递归间接左递归ABBA A,BVN,V*n例例4.10G5S:SSaSb考虑对输入串考虑对输入串baaaa#的分析的分析n例例4.11G6A：AaBABbBAcBd考虑对输入串考虑对输入串adbcbcbc#的分析的分析SbSSaS|BaBcBBbcBdBaBcB|dB BbcB|消除直接左递归消除直接左递归nAA1|A2|Am|1|2|n其中：其中：i 不等于不等于，j不以不以A开头。开头。改为：改为：A 1A|2A|nA A 1A|2A|mA|消除间接左递归消除间接左递归n将间接左递归变为直接左递归，然后消除直接将间接左递归变为直接左递归，然后消除直接左递归。左递归。消除文法中一切左

14、递归的算法消除文法中一切左递归的算法1.以某种顺序将文法非终结符排列以某种顺序将文法非终结符排列A1,A2 An2.for i:=1 to n do begin for j:=1 to i-1 do 用用Aj-1|2|k关于关于Aj的全部产生式替代的全部产生式替代 形如形如Ai-Ajr的的产生式为产生式为:Ai-1r|2r|kr;end;消除消除Ai的直接左递归的直接左递归;3.化简由化简由2得到的文法得到的文法n例例文法文法GS:SQc|cQRb|bRSa|aR Qca|ca|aR Rbca|bca|ca|aR(bca|ca|a)RR bcaR|将非终结符排序为将非终结符排序为S、Q、R4.

15、5 LL(1)分析的实现分析的实现n递归下降递归下降LL(1)分析程序分析程序n表驱动表驱动LL(1)分析程序分析程序4.5.2表驱动表驱动LL(1)分析程序分析程序n一个预测分析器是由三个部分组成一个预测分析器是由三个部分组成q预测分析程序预测分析程序q符号栈符号栈q预测分析表预测分析表预测分析程序预测分析表输入单词流符号栈iptop输出预测分析表预测分析表n预测分析表可用一个矩阵预测分析表可用一个矩阵M表示。矩阵的元素表示。矩阵的元素MA,a中的内容为一条关于中的内容为一条关于A的产生式，表明当的产生式，表明当用非终结符用非终结符A向下推导且面临输入符向下推导且面临输入符a时，所应采时，所

16、应采取的候选产生式，当元素内容无产生式时，则出取的候选产生式，当元素内容无产生式时，则出错。错。n一个文法的预测分析表不含有多重入口，当且仅一个文法的预测分析表不含有多重入口，当且仅当该文法是当该文法是LL(1)的。的。n预测分析表的构造算法预测分析表的构造算法q若若a SELECT(A)，则把，则把A放入放入MA,a中。中。q把所有无定义的把所有无定义的MA，a标上出错标记。标上出错标记。n例例文法文法GE：E TEE+TE|T FTT*FT|F i|(E)构造过程：构造过程：1.判断文法是否为判断文法是否为LL(1)文法文法 2.构造预测分析表构造预测分析表(E)FT TE()#*+i T

17、E E i F *FT T FT T +TE E 预测分析程序算法预测分析程序算法#S进 栈，当 前 终 结 符 送 a上 托 栈 顶 符 号 放 入 XXVT?是X=a?是读 入下 一符 号否X=#?是X=a?是结 束出 错否MX,a是 产 生 式 吗？否出 错是将 产 生 式 右 部 逆 序 入 栈分析栈分析栈#E#ET#ETF#ETi#ET#E#ET+#ET#ETF#ETi#ET#ETF*#ETF#ETi#ET#E#剩余串剩余串i+i*i#i+i*i#i+i*i#i+i*i#+i*i#+i*i#+i*i#i*i#i*i#i*i#*i#*i#i#i#产生式产生式ETETFTF iT E +

18、TET FTF iT *FTF iT E n例例对输入串对输入串 i+i*i的分析的分析(E)FT TE()#*+i TE E i F *FT T FT T +TE E 4.5.1递归下降递归下降LL(1)分析程序（自学）分析程序（自学）n实现思想实现思想q对文法中每个非终结符编写一个递归过程，每个过对文法中每个非终结符编写一个递归过程，每个过程的功能是识别由该非终结符推出的串，当某非终程的功能是识别由该非终结符推出的串，当某非终结符的产生式有多个候选时能够按结符的产生式有多个候选时能够按LL(1)形式可唯形式可唯一地确定选择某个候选进行推导。一地确定选择某个候选进行推导。n限制限制q对文法要求高，必须满足对文法要求高，必须满足LL(1)文法；文法；q速度慢，占用空间多。速度慢，占用空间多。