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

1/30/20231编译原理第四章 语法分析第四章 语法分析1、概述一.语法分析器的功能1/30/20232编译原理第四章 语法分析语法分析：语法分析：在词法分析的基础上，根据语法规则，从单词符号串中识别出识别出各种语法成分，同时进行语法检查，检查各种语法成分在语法结构上的正确性。1/30/20233编译原理第四章 语法分析二.语法分析方法自上向下分析法：自上向下分析法：从文法的开始符号出发，以从文法的开始符号出发，以给定的符号串为目标，根据文法规则，正向推给定的符号串为目标，根据文法规则，正向推导出给定符号串的一种方法。导出给定符号串的一种方法。自下向上分析法：自下向上分析法：从给定的符号串出发，反复使从给定的符号串出发，反复使用文法中有关产生式的左部去替换当前符号串用文法中有关产生式的左部去替换当前符号串中的相应子串，逐步归约成文法开始符号的一中的相应子串，逐步归约成文法开始符号的一种方法。种方法。自上向下分析法：递归下降、自上向下分析法：递归下降、LL(1)分析法分析法自下向上分析法：算符优先、自下向上分析法：算符优先、LR分析法分析法1/30/20234编译原理第四章 语法分析2、自上而下分析方法一、带回溯的自上而下分析法基本思想：基本思想：对任何输入串，试图用一切可能的方法，从文法的开始符号出发，采用最左推导，自上而下为输入串建立一棵语法树。例如：例如：设有文法：SxAyA*|*输入串：x*y看匹配过程S SA Ax xy yS SA Ax xy yS SA Ax xy y*1/30/20235编译原理第四章 语法分析二、存在的问题以及解决的方法1.左递归：当文法为左递归时，会使分析程序进入无限循环之中。若文法中有非终结符P=P(文法左递归)输入某输入串w=a1a2an 就有P=P=P 如此循环，不会终止+1/30/20236编译原理第四章 语法分析消除直接左递归方法一：方法一：引进新的非终结符，改写文法规则式。PP|P PP P|（将文法中的左递归结构变成等价的右递归结构）将文法中的左递归结构变成等价的右递归结构）例如：算术表达式文法左递归EE+T|TETETT*F|FE+TE|F(E)|iTFTT*FT|F(E)|i1/30/20237编译原理第四章 语法分析一般情况：有多个直接左递归：PP1|P2|Pm|1|2|n 其中，每个都不等于，而每个都不以P开头，则上式改写为 P1 P|2 P|n P P1 P|2 P|m P|例如：AAc|Aad|bd|e改写为：A bd A|e A A c A|ad A|1/30/20238编译原理第四章 语法分析方法二：方法二：方法二：方法二：采用扩充的BNF表示法改写文法规则式l用花括号表示符号串出现0次或多次。即*标识符：Il l|d 或Il l|d 7 即将即将即将即将AA AA|改写成改写成改写成改写成AA l中括号表示是可供选择的符号串。if B then else l使用圆括号，可以在规则中提因子。UXY|XW|XZUX(Y|W|Z)例如：算术表达式文法左递归EE+T|TET+TTT*F|FTF*FF(E)|i F(E)|i1/30/20239编译原理第四章 语法分析消除所有左递归的算法(1)把文法G的所有非终结符按任一顺序排列成P1,P2,Pn;(2)执行循环语句：for i:=1 to n do将规则 PiPj 改写；改写方法：Pj1|2|n 则 Pi1|2|n 消除关于Pi的直接左递归end(3)化简由(2)得到的文法。1/30/202310编译原理第四章 语法分析例如：消除下面文法的左递归。文法：SQc|cQRb|bRSa|a(1)排列：R,Q,S(2)对对R：没有直接左递归，不执行内循环 对对Q：将R代入Q变为 QSab|ab|b ，也没有直接左递归，不执行内循环。对对S：将Q代入S变为 SSabc|abc|bc|c消除S的直接左递归，得下面文法：Sabc S|bc S|c S Sabc S|(3)Sabc S|bc S|c S QSab|ab|b Sabc S|RSa|a若排列方法不同，得到的文法也可能不同，但等价1/30/202311编译原理第四章 语法分析2.回溯问题问题：问题：如果对同一个非终结符号，有若干个产生式右部 A 1|2|n,选择哪一个产生式匹配呢？匹配不好就产生回溯。回溯使语法分析器的动作不确定。分析：分析：要消除回溯，必须使文法具有一定的特性。例如：ScAdAad|a 输入符号w=cad分析：分析：要求各规则式右部1|2|n 所推出的终结首符号的集合两两不相交。定义：定义：符号串符号串i 终结首符号的集合：终结首符号的集合：FIRST(i)=|i=a,VT*1/30/202312编译原理第四章 语法分析条件一：条件一：条件一：条件一：对文法中每一个非终结符A，如有规则：AA 1 1|2 2|n n 则下面条件成立 FIRST(FIRST(i i)FIRST(FIRST(j j)=(ij)=(ij)上例中：FIRST(ab)FIRST(a)=a a=a 改写方法：改写方法：改写方法：改写方法：提取公共左因子提取公共左因子AA 1 1|2 2|n n|1 1|2 2|mm则：则：则：则：AAAA|1 1|2 2|mmA A 1 1|2 2|n n 例如：if E then S1 else S2|if E then S1 改写为：if E then S1 BB else S2|1/30/202313编译原理第四章 语法分析问题：问题：若满足条件 FIRST(i)FIRST(j)=是否完全避免回溯呢？上例中：ScAdAad|a改写为：ScAdA aA Ad|输入符号w=cad 匹配d可能失败，差条件定义：定义：非终结符号A的后继符号的集合：FOLLOW(A)=a|S=Aa,VT 当当S=A，则则规定规定#FOLLOW(A)（#为为为为界符）界符）界符）界符）条件二：条件二：若若i=时时，FIRST(i)FOLLOW(A)=上例中：FIRST(d)FOLLOW(A)=d 产生回溯*1/30/202314编译原理第四章 语法分析小结：小结：构造不带回溯的自上而下分析的条件是：1.文法不含左递归2.对文法中每一个非终结符A，如有规则：A 1|2|n 则下面条件成立 FIRST(i)FIRST(j)=(ij)3.对文法中每一个非终结符A，若它的某个产生式首符集包含 时，则：FIRST(A)FOLLOW(A)=满足以上条件的文法称为LL(1)文法。对于一个LL(1）文法，可以构造无回溯的自上而下分析。1/30/202315编译原理第四章 语法分析FIRST()的求法：的求法：(A 是文法是文法G的产生式）的产生式）若=a，且a是终结符，则FIRST()=a。若=X，且X是非终结符，且X=b，则把终结符b加入到FIRST()中。若=X1X2Xk，且X1,X2,Xk 都是非终结符，而X1X2Xi=，则把 FIRST(Xi+1Xi+2Xk)加入到FIRST()中。1/30/202316编译原理第四章 语法分析FOLLOW(A)的求法：的求法：（其中（其中A是任一非终结符）是任一非终结符）若有产生式B Aa,且a是终结符，则把a加入到FOLLOW(A)中。若有产生式B AX,且X是非终结符,则把FIRST(X)加入到FOLLOW(A)中。若有产生式B A，或B A，但=，则把FOLLOW(B)加入到FOLLOW(A)中。若A是文法的开始符号，则把结束符#加入到FOLLOW(A)中。1/30/202317编译原理第四章 语法分析例：已知文法例：已知文法GS:SaSb|PPbPc|bQcQQa|a消除文法左递归后是不是消除文法左递归后是不是LL(1)文法？文法？解：消除文法左递归得到：解：消除文法左递归得到：SaSb|PPbPc|bQcQaQQaQ|提取公共左因子后得文法：提取公共左因子后得文法：SaSb|PPbP P Pc|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)=c Follow(Q)=c 是是LL(1)文法文法1/30/202318编译原理第四章 语法分析例：将文法改写成例：将文法改写成LL(1)文法。文法。SS*aP|aP|*aPP+aP|+a解：消除文法左递归、提取公共左因子得到：解：消除文法左递归、提取公共左因子得到：SaPS|*aPS S*aPS|P+aP PP|计算每个非终结符的计算每个非终结符的FIRST和和FOLLOW集合：集合：FIRST(S)=a,*Follow(S)=#FIRST(S)=*,Follow(S)=#FIRST(P)=+Follow(P)=*,#FIRST(P)=+,Follow(P)=*,#以上文法是以上文法是LL(1)文法。文法。1/30/202319编译原理第四章 语法分析已知文法：GS：SAB|PQxAxy|mBbCCbC|PpP|Qq如果要保持文法为LL(1)文法，下列哪几个产生式不能加入到该文法中？为什么？（1）SbC（2）AbC（3）B（4）Q1/30/202320编译原理第四章 语法分析解：解：(1)加入加入SbC后文法为：后文法为：SAB|PQx|bCAxy|mBbCCbC|PpP|Qq对对S:First(AB)First(PQx)First(bC)=x,m p,q b=对对A:First(xy)First(m)=x m=对对C:First(bC)Follow(C)=b#=对对P:First(pP)Follow(P)=p q=加入加入SbC后文法是后文法是LL(1)文法。文法。1/30/202321编译原理第四章 语法分析(2)加入加入AbC后文法为：后文法为：SAB|PQxAxy|m|bCBbCCbC|PpP|Qq对对A:First(xy)First(m)First(bC)=x m b=对对C:first(bC)follow(C)=b b,#=b不是不是LL(1)文法。文法。(3)加入加入B 后文法为：后文法为：SAB|PQxAxy|mBbC|CbC|PpP|Qq对对B:First(bC)Follow(B)=b#=是是LL(1)文法。文法。1/30/202322编译原理第四章 语法分析(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,m p,q,x=x 加入加入Q 后文法不是后文法不是LL(1)文法。文法。1/30/202323编译原理第四章 语法分析定义规则的选择集合SELECT，设 A 是文法G的任一条规则，其中 AVN,(VNVT)*，定义 SELECT(A)=FIRST()FIRST()FOLLOW(A)*/若 *若 定义SELECT集合1/30/202324编译原理第四章 语法分析例 设有文法GA:AaB|dBbBA|SELECT(AaB)=FIRST(aB)=a SELECT(Ad)=FIRST(d)=d 1/30/202325编译原理第四章 语法分析 b SELECT(BbBA)=FIRST(bBA)=,$,d,a FOLLOW(B)SELECT(B)=FIRST()FOLLOW(B)=$,d,a AaB|dBbBA|1/30/202326编译原理第四章 语法分析LL(1)文法的判断条件LL(1)文法定义一个上下文无关文法 G是LL(1)文法,当且仅当对 G 中每个非终结符A的任何两个不同的规则 A|，满足 SELECT(A)SELECT(A)=其中、中至多只有一个能推出串。1/30/202327编译原理第四章 语法分析例1 设有文法GS:S aAbA de|dSELECT(Ade)=FIRST(de)=dSELECT(Ad)=FIRST(d)=dSELECT(Ade)SELECT(Ad)由LL(1)文法定义可知，该文法不是LL(1)文法，因此对输入串不能进行确定的自上而下分析。1/30/202328编译原理第四章 语法分析例2 设有文法GA A aB|dB bBA|则 SELECT(AaB)=FIRST(aB)=a SELECT(Ad)=FIRST(d)=d SELECT(BbBA)=FIRST(bBA)=b SELECT(B)=FIRST()FOLLOW(B)=a,d,$=,a,d,$1/30/202329编译原理第四章 语法分析所以 SELECT(AaB)SELECT(Ad)=SELECT(BbBA)SELECT(B)=由定义可知，GA是LL(1)文法，对任何输入串W可进行确定的分析。1/30/202330编译原理第四章 语法分析例3 设有文法GS:S aABA bB|dA|B a|e SELECT(AbB)=FIRST(bB)=b SELECT(AdA)=FIRST(dA)=d SELECT(A)=FIRST()FOLLOW(A)=a,e=,a,e 试判断该文法是否LL(1)文法。1/30/202331编译原理第四章 语法分析 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)=S aABA bB|dA|B a|e 该文法为LL(1)文法1/30/202332编译原理第四章 语法分析三、递归下降分析法条件：要求文法为LL(1)文法1 基本思想：对每一个非终结符，构造相应的递归子程序，以完成该非终结符所对应语法成分的分析和识别任务。1/30/202333编译原理第四章 语法分析2 方法：方法：为每一个非终结符，构造相应的递归过程，过程的名为每一个非终结符，构造相应的递归过程，过程的名字表示规则左部的非终结符；过程体按规则右部符号字表示规则左部的非终结符；过程体按规则右部符号串的顺序编写。串的顺序编写。对于产生式对于产生式：Ux1|x2|xn 则编写则编写if ch in FIRST(x1)then p(x1)else if ch in FIRST(x2)then p(x2)else error;对于符号串对于符号串x=y1 y2yn;p(x)的含义为：的含义为：begin p(y1);p(y2);p(yn)end 如果如果yiVT 则则if ch=yi then read(ch)else error 对于对于U;则则 if chFollow(U)then returnelse error;1/30/202334编译原理第四章 语法分析举例：设有文法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)文法1/30/202335编译原理第四章 语法分析构造递归下降分析程序。定义：advance:读下一个单词并放入全程变量sym中 error：错误诊断处理程序编程如下：主:advance;E;procedure E;begin T;Eend;procedure E;beginif sym=+thenbegin advance;T;Eend;else if symfollow(E)then return else errorEnd;1/30/202336编译原理第四章 语法分析 Procedure T;BeginF;TEnd;Procedure TBegin if sym=*thenbegin advance;F;T;end else if sym not in+,),#then error else returnEnd;Procedure FBegin if sym=i then advance;else if sym=(then beginadvance;E;if sym=)thenadvance;else error;end else error;End;1/30/202337编译原理第四章 语法分析若改写文法用BNF范式表示：ET+TTF*FF(E)|i则编程如下：Procedure E;BeginT;while sym=+do beginadvance;T;endendProcedure T;BeginF;while sym=*do beginadvance;F;endend1/30/202338编译原理第四章 语法分析 例如：1/30/202339编译原理第四章 语法分析 1/30/202340编译原理第四章 语法分析 1/30/202341编译原理第四章 语法分析 PROCEDURE BEGIN IF SYM=iTHEN READWORD ELSE ERROREND;1/30/202342编译原理第四章 语法分析 PROCEDURE BEGIN1/30/202343编译原理第四章 语法分析 1/30/202344编译原理第四章 语法分析四、LL(1)分析法（预测分析法）条件：要求文法为LL(1)文法L从左到右进行分析L每次进行最左推导(1)向前查看一个符号1/30/202345编译原理第四章 语法分析1.LL(1)分析器的逻辑结构a1a2aian#总控程序LL(1)分析表x Z1#TjSkj分析栈分析栈分析栈分析栈1/30/202346编译原理第四章 语法分析2.分析表的构造方法输入：输入：文法G输出：输出：分析表M方法：方法：对文法中每一个产生式A，按照下述规 则确定M中各个元素。对于FIRST()中的每一个终结符a置为 MA,a=A 若空串 FIRST()，则对Follow(A)中的每一个终结符b置为 MA,b=A 把M中未定义的元素置为error。1/30/202347编译原理第四章 语法分析例如：已知文法GE:试构造分析表。ETEE+TE|TFTT*FT|F(E)|i对ETE产生式：First(TE)=(,i 置 ME,(=ETEME,i=ETE1/30/202348编译原理第四章 语法分析对对对对产生式产生式产生式产生式E E+TE+TE|First(First(+TE+TE )=+)=+置置置置MEME ,+=E,+=E+TE+TE Follow(EFollow(E)=),#)=),#置置置置MEME ,)=E,)=E MEME ,#=E,#=E 对产生式对产生式对产生式对产生式TFTTFT First(FT)=(,i First(FT)=(,i 置置置置MT,(=TFTMT,(=TFT MT,i=TFT MT,i=TFT 对产生式对产生式对产生式对产生式T T*FT*FT|First(First(*FT*FT)=*)=*置置置置MTMT,*=T,*=T*FT*FT Follow(TFollow(T)=+,),#)=+,),#置置置置MTMT,+=T,+=T MTMT,)=T,)=T MTMT,#=T,#=T 对产生式对产生式对产生式对产生式F(E)|i F(E)|i First(E)=(First(E)=(置置置置MF,(=MF,(=F(E)F(E)First(i)=i First(i)=i 置置置置MF,i =MF,i =Fi Fi 1/30/202349编译原理第四章 语法分析3.总控程序框图J:=1;J:=1;k:=1;k:=1;sk:=#;sk:=#;k:=k+1;k:=k+1;Z=skZ=skSk Sk V VT T?Sk=Tj?Sk=Tj?Sk=#?Sk=#?查查查查M Sk,Tj=XyM Sk,Tj=Xy1 1y y2 2y yn nSk=Tj?Sk=Tj?K:=k-1;K:=k-1;J:=j+1;J:=j+1;errorerrorN NN NN Ny yy yy yerrorerrorstopstopy yN N将将将将y y1 1y y2 2y yn n逆序推进栈中逆序推进栈中逆序推进栈中逆序推进栈中若若若若y y1 1y y2 2y yn n=则则则则k=k-1k=k-1errorerrorN Ny y1/30/202350编译原理第四章 语法分析4.分析过程例如：已知文法G，请利用LL(1)分析表给出输入串i1*i2+i3的分析过程。GE:ETEE+TE|TFTT*FT|F(E)|i1/30/202351编译原理第四章 语法分析 E E1/30/202352编译原理第四章 语法分析例2：已知文法GA：AaAa|该文法是LL(1)文法吗？为什么？若采用LL(1)方法进行语法分析，请构造该文法的LL(1)分析表？若输入符号串为“aaaa”，请给出语法分析 过程。请给出该文法的递归下降分析子程序。1/30/202353编译原理第四章 语法分析解：Follow(A)=#First(a)=a,#有:First(A)Follow(A)=a,a,#该文法不是LL(1)文法。修改文法 GA:AaaA|由于：First(A)Follow(A)=a,#=GA 是LL(1)文法该文法的分析表为：1/30/202354编译原理第四章 语法分析若输入符号串为“aaaa”，则分析过程如下。1/30/202355编译原理第四章 语法分析1/30/202356编译原理第四章 语法分析例3：已知文法GP:Pbegin d;X endXd;X|sYY;sY|作出该文法的LL(1)分析表。解：Follow(Y)=Follow(X)Follow(Y)=end该文法的LL(1)分析表为：beginbegind d;endends s#P PPBegin d;X endPBegin d;X endX XXd;XXd;XXXsYsYY YY;Y;sYsYYY 1/30/202357编译原理第四章 语法分析课堂练习1.设字母表=a,b，给出上的正规式R=(a|ba)*求最小化的DFA M，使得L(M)=L(R)。求右线性文法G，使得L(G)=L(M)。2.已知文法GM为：MTBTBa|BDb|eT|Dd|首先计算每个非终结符的First集和Follow集，然后判断该文法是不是LL(1)文法。1/30/202358编译原理第四章 语法分析3.已知文法GS:SBAABS|dBaA|bS|c求：每一个非终结符的First集和Follow集。证明文法G是LL(1)的。构造LL(1)分析表。写出句子adccd的分析过程1/30/202359编译原理第四章 语法分析