编译原理第4章 语法分析.ppt

编译原理第四章语法分析,2020/5/30,1,第四章语法分析,编译原理第四章语法分析,2020/5/30,2,第四章语法分析1、概述一.语法分析器的功能,编译原理第四章语法分析,2020/5/30,3,语法分析：在词法分析的基础上，根据语法规则，从单词符号串中识别出各种语法成分，同时进行语法检查，检查各种语法成分在语法结构上的正确性。,编译原理第四章语法分析,2020/5/30,4,二.语法分析方法,自上向下分析法：从文法的开始符号出发，以给定的符号串为目标，根据文法规则，正向推导出给定符号串的一种方法。自下向上分析法：从给定的符号串出发，反复使用文法中有关产生式的左部去替换当前符号串中的相应子串，逐步归约成文法开始符号的一种方法。自上向下分析法：递归下降、LL(1)分析法自下向上分析法：算符优先、LR分析法,编译原理第四章语法分析,2020/5/30,5,2、自上而下分析方法一、带回溯的自上而下分析法,基本思想：对任何输入串，试图用一切可能的方法，从文法的开始符号出发，采用最左推导，自上而下为输入串建立一棵语法树。例如：设有文法：SxAyA*|*输入串：x*y看匹配过程,S,A,x,y,S,A,x,y,S,A,x,y,*,*,*,编译原理第四章语法分析,2020/5/30,6,二、存在的问题以及解决的方法1.左递归：,当文法为左递归时，会使分析程序进入无限循环之中。若文法中有非终结符P=P(文法左递归)输入某输入串w=a1a2an就有P=P=P如此循环，不会终止,+,编译原理第四章语法分析,2020/5/30,7,消除直接左递归,方法一：引进新的非终结符，改写文法规则式。PP|PPPP|（将文法中的左递归结构变成等价的右递归结构）例如：算术表达式文法左递归EE+T|TETETT*F|FE+TE|F(E)|iTFTT*FT|F(E)|i,编译原理第四章语法分析,2020/5/30,8,一般情况：有多个直接左递归：PP1|P2|Pm|1|2|n其中，每个都不等于，而每个都不以P开头，则上式改写为P1P|2P|nPP1P|2P|mP|例如：AAc|Aad|bd|e改写为：AbdA|eAAcA|adA|,编译原理第四章语法分析,2020/5/30,9,方法二：采用扩充的BNF表示法改写文法规则式用花括号表示符号串出现0次或多次。即*标识符：Ill|d或Ill|d7即将AA|改写成A中括号表示是可供选择的符号串。ifBthenelse使用圆括号，可以在规则中提因子。UXY|XW|XZUX(Y|W|Z)例如：算术表达式文法左递归EE+T|TET+TTT*F|FTF*FF(E)|iF(E)|i,编译原理第四章语法分析,2020/5/30,10,消除所有左递归的算法,(1)把文法G的所有非终结符按任一顺序排列成P1,P2,Pn;(2)执行循环语句：fori:=1tondo将规则PiPj改写；改写方法：Pj1|2|n则Pi1|2|n消除关于Pi的直接左递归end(3)化简由(2)得到的文法。,编译原理第四章语法分析,2020/5/30,11,例如：消除下面文法的左递归。文法：SQc|cQRb|bRSa|a(1)排列：R,Q,S(2)对R：没有直接左递归，不执行内循环对Q：将R代入Q变为QSab|ab|b，也没有直接左递归，不执行内循环。对S：将Q代入S变为SSabc|abc|bc|c消除S的直接左递归，得下面文法：SabcS|bcS|cSSabcS|(3)SabcS|bcS|cSQSab|ab|bSabcS|RSa|a若排列方法不同，得到的文法也可能不同，但等价,编译原理第四章语法分析,2020/5/30,12,2.回溯问题,问题：如果对同一个非终结符号，有若干个产生式右部A1|2|n,选择哪一个产生式匹配呢？匹配不好就产生回溯。回溯使语法分析器的动作不确定。分析：要消除回溯，必须使文法具有一定的特性。例如：ScAdAad|a输入符号w=cad分析：要求各规则式右部1|2|n所推出的终结首符号的集合两两不相交。定义：符号串i终结首符号的集合：FIRST(i)=|i=a,VT,*,编译原理第四章语法分析,2020/5/30,13,条件一：对文法中每一个非终结符A，如有规则：A1|2|n则下面条件成立FIRST(i)FIRST(j)=(ij)上例中：FIRST(ab)FIRST(a)=aa=a改写方法：提取公共左因子A1|2|n|1|2|m则：AA|1|2|mA1|2|n例如：ifEthenS1elseS2|ifEthenS1改写为：ifEthenS1BBelseS2|,编译原理第四章语法分析,2020/5/30,14,问题：若满足条件FIRST(i)FIRST(j)=是否完全避免回溯呢？上例中：ScAdAad|a改写为：ScAdAaAAd|输入符号w=cad匹配d可能失败，差条件定义：非终结符号A的后继符号的集合：FOLLOW(A)=a|S=Aa,VT当S=A，则规定#FOLLOW(A)（#为界符）条件二：若i=时，FIRST(i)FOLLOW(A)=上例中：FIRST(d)FOLLOW(A)=d产生回溯,*,*,编译原理第四章语法分析,2020/5/30,15,小结：构造不带回溯的自上而下分析的条件是：1.文法不含左递归2.对文法中每一个非终结符A，如有规则：A1|2|n则下面条件成立FIRST(i)FIRST(j)=(ij)3.对文法中每一个非终结符A，若它的某个产生式首符集包含时，则：FIRST(A)FOLLOW(A)=满足以上条件的文法称为LL(1)文法。对于一个LL(1）文法，可以构造无回溯的自上而下分析。,编译原理第四章语法分析,2020/5/30,16,FIRST()的求法：(A是文法G的产生式）,若=a，且a是终结符，则FIRST()=a。若=X，且X是非终结符，且X=b，则把终结符b加入到FIRST()中。若=X1X2Xk，且X1,X2,Xk都是非终结符，而X1X2Xi=，则把FIRST(Xi+1Xi+2Xk)加入到FIRST()中。,编译原理第四章语法分析,2020/5/30,17,FOLLOW(A)的求法：（其中A是任一非终结符）,若有产生式BAa,且a是终结符，则把a加入到FOLLOW(A)中。若有产生式BAX,且X是非终结符,则把FIRST(X)加入到FOLLOW(A)中。若有产生式BA，或BA，但=，则把FOLLOW(B)加入到FOLLOW(A)中。若A是文法的开始符号，则把结束符#加入到FOLLOW(A)中。,编译原理第四章语法分析,2020/5/30,18,例：已知文法GS:SaSb|PPbPc|bQcQQa|a消除文法左递归后是不是LL(1)文法？解：消除文法左递归得到：SaSb|PPbPc|bQcQaQQaQ|提取公共左因子后得文法：SaSb|PPbPPPc|QcQaQQaQ|计算FIRST和FOLLOW集合：FIRST(S)=a,bFIRST(P)=bFIRST(P)=a,bFIRST(Q)=aFIRST(Q)=a,Follow(S)=b,#Follow(P)=b,c,#Follow(P)=b,c,#Follow(Q)=cFollow(Q)=c是LL(1)文法,编译原理第四章语法分析,2020/5/30,19,例：将文法改写成LL(1)文法。SS*aP|aP|*aPP+aP|+a解：消除文法左递归、提取公共左因子得到：SaPS|*aPSS*aPS|P+aPPP|计算每个非终结符的FIRST和FOLLOW集合：FIRST(S)=a,*Follow(S)=#FIRST(S)=*,Follow(S)=#FIRST(P)=+Follow(P)=*,#FIRST(P)=+,Follow(P)=*,#以上文法是LL(1)文法。,编译原理第四章语法分析,2020/5/30,20,已知文法：GS：SAB|PQxAxy|mBbCCbC|PpP|Qq如果要保持文法为LL(1)文法，下列哪几个产生式不能加入到该文法中？为什么？（1）SbC（2）AbC（3）B（4）Q,编译原理第四章语法分析,2020/5/30,21,解：(1)加入SbC后文法为：SAB|PQx|bCAxy|mBbCCbC|PpP|Qq对S:First(AB)First(PQx)First(bC)=x,mp,qb=对A:First(xy)First(m)=xm=对C:First(bC)Follow(C)=b#=对P:First(pP)Follow(P)=pq=加入SbC后文法是LL(1)文法。,编译原理第四章语法分析,2020/5/30,22,(2)加入AbC后文法为：SAB|PQxAxy|m|bCBbCCbC|PpP|Qq对A:First(xy)First(m)First(bC)=xmb=对C:first(bC)follow(C)=bb,#=b不是LL(1)文法。,(3)加入B后文法为：SAB|PQxAxy|mBbC|CbC|PpP|Qq对B:First(bC)Follow(B)=b#=是LL(1)文法。,编译原理第四章语法分析,2020/5/30,23,(4)加入Q后文法为：SAB|PQxAxy|mBbCCbC|PpP|Qq|First(S)=x,m,p,qFollow(S)=#First(A)=x,mFollow(A)=bFirst(B)=bFollow(B)=#First(C)=b,Follow(C)=#First(P)=p,Follow(P)=q,xFirst(Q)=q,Follow(Q)=x对S:First(AB)First(PQx)=x,mp,q,x=x加入Q后文法不是LL(1)文法。,编译原理第四章语法分析,2020/5/30,24,定义规则的选择集合SELECT，设A是文法G的任一条规则，其中AVN,(VNVT)*，定义,SELECT(A)=,FIRST(),FIRST()FOLLOW(A),定义SELECT集合,编译原理第四章语法分析,2020/5/30,25,例设有文法GA:,AaB|d,BbBA|,SELECT(AaB)=,FIRST(aB)=,a,SELECT(Ad)=,FIRST(d)=,d,编译原理第四章语法分析,2020/5/30,26,b,SELECT(BbBA)=,FIRST(bBA)=,=,$,d,a,FOLLOW(B),SELECT(B)=,FIRST(),AaB|d,BbBA|,编译原理第四章语法分析,2020/5/30,27,LL(1)文法的判断条件,LL(1)文法定义,一个上下文无关文法G是LL(1)文法,当且仅当对G中每个非终结符A的任何两个不同的规则A|，满足,SELECT(A)SELECT(A)=,其中、中至多只有一个能推出串。,编译原理第四章语法分析,2020/5/30,28,例1设有文法GS:,SaAbAde|d,SELECT(Ade)=FIRST(de)=d,SELECT(Ad)=FIRST(d)=d,SELECT(Ade)SELECT(Ad),由LL(1)文法定义可知，该文法不是LL(1)文法，因此对输入串不能进行确定的自上而下分析。,编译原理第四章语法分析,2020/5/30,29,例2设有文法GA,AaB|dBbBA|,则SELECT(AaB)=FIRST(aB)=a,SELECT(Ad)=FIRST(d)=d,SELECT(BbBA)=FIRST(bBA)=b,SELECT(B)=FIRST()FOLLOW(B),=a,d,$=,a,d,$,编译原理第四章语法分析,2020/5/30,30,所以SELECT(AaB)SELECT(Ad)=,SELECT(BbBA)SELECT(B)=,由定义可知，GA是LL(1)文法，对任何输入串W可进行确定的分析。,编译原理第四章语法分析,2020/5/30,31,例3设有文法GS:,SaABAbB|dA|Ba|e,SELECT(AbB)=FIRST(bB)=b,SELECT(AdA)=FIRST(dA)=d,SELECT(A)=FIRST()FOLLOW(A),=a,e=,a,e,试判断该文法是否LL(1)文法。,编译原理第四章语法分析,2020/5/30,32,SELECT(Ba)=FIRST(a)=a,SELECT(Be)=FIRST(e)=e,SELECT(AbB)SELECT(AdA)=,SELECT(AbB)SELECT(A)=,SELECT(AdA)SELECT(A)=,SELECT(Ba)SELECT(Be)=,SaABAbB|dA|Ba|e,该文法为LL(1)文法,编译原理第四章语法分析,2020/5/30,33,三、递归下降分析法,条件：要求文法为LL(1)文法1基本思想：对每一个非终结符，构造相应的递归子程序，以完成该非终结符所对应语法成分的分析和识别任务。,编译原理第四章语法分析,2020/5/30,34,2方法：为每一个非终结符，构造相应的递归过程，过程的名字表示规则左部的非终结符；过程体按规则右部符号串的顺序编写。对于产生式：Ux1|x2|xn则编写ifchinFIRST(x1)thenp(x1)elseifchinFIRST(x2)thenp(x2)elseerror;对于符号串x=y1y2yn;p(x)的含义为：beginp(y1);p(y2);p(yn)end如果yiVT则ifch=yithenread(ch)elseerror对于U;则ifchFollow(U)thenreturnelseerror;,编译原理第四章语法分析,2020/5/30,35,举例：设有文法G：EE+T|TTT*F|FF(E)|i试构造一个识别该文法句子的递归下降分析程序。消除文法左递归ETEE+TE|TFTT*FT|F(E)|i改写后的文法是否为LL(1)文法：对E：First(+TE)Follow(E)=+#,)=对T：First(*FT)Follow(T)=*+,#,)=对F：First(i)First(E)=i(=是LL(1)文法,编译原理第四章语法分析,2020/5/30,36,构造递归下降分析程序。定义：advance:读下一个单词并放入全程变量sym中error：错误诊断处理程序编程如下：,主:advance;E;,procedureE;beginT;Eend;,procedureE;beginifsym=+thenbeginadvance;T;Eend;elseifsymfollow(E)thenreturnelseerrorEnd;,编译原理第四章语法分析,2020/5/30,37,ProcedureT;BeginF;TEnd;,ProcedureTBeginifsym=*thenbeginadvance;F;T;endelseifsymnotin+,),#thenerrorelsereturnEnd;,ProcedureFBeginifsym=ithenadvance;elseifsym=(thenbeginadvance;E;ifsym=)thenadvance;elseerror;endelseerror;End;,编译原理第四章语法分析,2020/5/30,38,若改写文法用BNF范式表示：ET+TTF*FF(E)|i则编程如下：,ProcedureE;BeginT;whilesym=+dobeginadvance;T;endend,ProcedureT;BeginF;whilesym=*dobeginadvance;F;endend,编译原理第四章语法分析,2020/5/30,39,例如：,编译原理第四章语法分析,2020/5/30,40,编译原理第四章语法分析,2020/5/30,41,编译原理第四章语法分析,2020/5/30,42,PROCEDUREBEGINIFSYM=iTHENREADWORDELSEERROREND;,编译原理第四章语法分析,2020/5/30,43,PROCEDUREBEGIN,编译原理第四章语法分析,2020/5/30,44,编译原理第四章语法分析,2020/5/30,45,四、LL(1)分析法（预测分析法）,条件：要求文法为LL(1)文法L从左到右进行分析L每次进行最左推导(1)向前查看一个符号,编译原理第四章语法分析,2020/5/30,46,1.LL(1)分析器的逻辑结构,总控程序,LL(1)分析表,Tj,Sk,j,分析栈,编译原理第四章语法分析,2020/5/30,47,2.分析表的构造方法,输入：文法G输出：分析表M方法：对文法中每一个产生式A，按照下述规则确定M中各个元素。对于FIRST()中的每一个终结符a置为MA,a=A若空串FIRST()，则对Follow(A)中的每一个终结符b置为MA,b=A把M中未定义的元素置为error。,编译原理第四章语法分析,2020/5/30,48,例如：已知文法GE:试构造分析表。ETEE+TE|TFTT*FT|F(E)|i对ETE产生式：First(TE)=(,i置ME,(=ETEME,i=ETE,编译原理第四章语法分析,2020/5/30,49,对产生式E+TE|First(+TE)=+置ME,+=E+TEFollow(E)=),#置ME,)=EME,#=E对产生式TFTFirst(FT)=(,i置MT,(=TFTMT,i=TFT对产生式T*FT|First(*FT)=*置MT,*=T*FTFollow(T)=+,),#置MT,+=TMT,)=TMT,#=T对产生式F(E)|iFirst(E)=(置MF,(=F(E)First(i)=i置MF,i=Fi,编译原理第四章语法分析,2020/5/30,50,3.总控程序框图,J:=1;k:=1;sk:=#;k:=k+1;Z=sk,SkVT?,Sk=Tj?,Sk=#?,查MSk,Tj=Xy1y2yn,Sk=Tj?,K:=k-1;J:=j+1;,error,N,N,N,y,y,y,error,stop,y,N,将y1y2yn逆序推进栈中若y1y2yn=则k=k-1,error,N,y,编译原理第四章语法分析,2020/5/30,51,4.分析过程,例如：已知文法G，请利用