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

编译原理第四章 语法分析,2022/12/2,1,第四章 语法分析,编译原理第四章 语法分析,2022/12/2,2,第四章 语法分析1、概述一. 语法分析器的功能,编译原理第四章 语法分析,2022/12/2,3,语法分析：在词法分析的基础上，根据语法规则，从单词符号串中识别出各种语法成分，同时进行语法检查，检查各种语法成分在语法结构上的正确性。,编译原理第四章 语法分析,2022/12/2,4,二.语法分析方法,自上向下分析法：从文法的开始符号出发，以给定的符号串为目标，根据文法规则，正向推导出给定符号串的一种方法。自下向上分析法：从给定的符号串出发，反复使用文法中有关产生式的左部去替换当前符号串中的相应子串，逐步归约成文法开始符号的一种方法。自上向下分析法：递归下降、LL(1)分析法自下向上分析法：算符优先、LR分析法,编译原理第四章 语法分析,2022/12/2,5,2、自上而下分析方法一、带回溯的自上而下分析法,基本思想：对任何输入串，试图用一切可能的方法，从文法的开始符号出发，采用最左推导，自上而下为输入串建立一棵语法树。例如：设有文法：SxAyA* | *输入串：x*y看匹配过程,S,A,x,y,S,A,x,y,S,A,x,y,*,*,*,编译原理第四章 语法分析,2022/12/2,6,二、存在的问题以及解决的方法1.左递归：,当文法为左递归时，会使分析程序进入无限循环之中。若文法中有非终结符P=P(文法左递归)输入某输入串w=a1a2an 就有P= P= P 如此循环，不会终止,+,编译原理第四章 语法分析,2022/12/2,7,消除直接左递归,方法一：引进新的非终结符，改写文法规则式。PP | P PP P | （将文法中的左递归结构变成等价的右递归结构）例如：算术表达式文法左递归EE+T | TETETT*F | FE+TE| F(E) | iTFTT*FT | F(E) | i,编译原理第四章 语法分析,2022/12/2,8,一般情况：有多个直接左递归：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 | ,编译原理第四章 语法分析,2022/12/2,9,方法二：采用扩充的BNF表示法改写文法规则式用花括号表示符号串出现0次或多次。即*标识符：Il l | d 或Il l | d 7 即将AA | 改写成A 中括号表示是可供选择的符号串。if B then else 使用圆括号，可以在规则中提因子。UXY|XW|XZUX(Y|W|Z)例如：算术表达式文法左递归EE+T | TET+TTT*F | FTF*FF(E) | i F(E) | i,编译原理第四章 语法分析,2022/12/2,10,消除所有左递归的算法,(1)把文法G的所有非终结符按任一顺序排列成P1 , P2 , Pn ; (2)执行循环语句：for i:=1 to n do将规则 PiPj 改写；改写方法：Pj1 | 2 | n 则 Pi1 | 2 | n 消除关于Pi的直接左递归end(3)化简由(2)得到的文法。,编译原理第四章 语法分析,2022/12/2,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的直接左递归，得下面文法： Sabc S| bc S | c S Sabc S| (3)Sabc S| bc S | c S QSab | ab | b Sabc S| RSa | a若排列方法不同，得到的文法也可能不同，但等价,编译原理第四章 语法分析,2022/12/2,12,2.回溯问题,问题：如果对同一个非终结符号，有若干个产生式右部 A 1 | 2 | | n , 选择哪一个产生式匹配呢？ 匹配不好就产生回溯。回溯使语法分析器的动作不确定。分析：要消除回溯，必须使文法具有一定的特性。例如：ScAdAad | a 输入符号w=cad分析：要求各规则式右部1 | 2 | | n 所推出的终结首符号的集合两两不相交。定义：符号串i 终结首符号的集合：FIRST(i )= | i =a , VT ,*,编译原理第四章 语法分析,2022/12/2,13,条件一：对文法中每一个非终结符A，如有规则： A 1 | 2 | | n 则下面条件成立 FIRST(i ) FIRST(j )= (ij)上例中：FIRST(ab) FIRST(a)=a a=a 改写方法：提取公共左因子A 1 | 2 | | n | 1 | 2 | m则：AA | 1 | 2 | mA 1 | 2 | | n 例如：if E then S1 else S2 | if E then S1 改写为： if E then S1 BB else S2 | ,编译原理第四章 语法分析,2022/12/2,14,问题：若满足条件 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 产生回溯,*,*,编译原理第四章 语法分析,2022/12/2,15,小结：构造不带回溯的自上而下分析的条件是：1.文法不含左递归2.对文法中每一个非终结符A，如有规则： A 1 | 2 | | n 则下面条件成立 FIRST(i ) FIRST(j )= (ij)3.对文法中每一个非终结符A，若它的某个产生式首符集包含 时 ，则： FIRST(A) FOLLOW(A) = 满足以上条件的文法称为LL(1)文法。对于一个LL(1）文法，可以构造无回溯的自上而下分析。,编译原理第四章 语法分析,2022/12/2,16,FIRST()的求法：(A 是文法G的产生式）,若=a ，且a是终结符，则FIRST()=a。若=X，且X是非终结符，且X=b，则把终结符b加入到FIRST()中。若=X1X2Xk，且X1 , X2 , Xk 都是非终结符，而X1X2Xi=，则把 FIRST(Xi+1Xi+2Xk)加入到FIRST()中。,编译原理第四章 语法分析,2022/12/2,17,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)中。,编译原理第四章 语法分析,2022/12/2,18,例：已知文法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)文法,编译原理第四章 语法分析,2022/12/2,19,例：将文法改写成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)文法。,编译原理第四章 语法分析,2022/12/2,20,已知文法：GS：SAB | PQxAxy | mBbCCbC | PpP | Qq如果要保持文法为LL(1)文法，下列哪几个产生式不能加入到该文法中？为什么？（1）SbC（2）AbC（3）B （4）Q,编译原理第四章 语法分析,2022/12/2,21,解：(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)文法。,编译原理第四章 语法分析,2022/12/2,22,(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)文法。,编译原理第四章 语法分析,2022/12/2,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,m p,q,x =x 加入Q 后文法不是LL(1)文法。,编译原理第四章 语法分析,2022/12/2,24,定义规则的选择集合SELECT，设 A 是文法G的任一条规则，其中 AVN , (VNVT)* ，定义,SELECT(A ) =,FIRST(),FIRST()FOLLOW (A),定义SELECT集合,编译原理第四章 语法分析,2022/12/2,25,例 设有文法GA:,AaB | d,BbBA | ,SELECT(AaB ) =,FIRST(aB) =, a ,SELECT(Ad ) =,FIRST(d) =, d ,编译原理第四章 语法分析,2022/12/2,26, b ,SELECT(BbBA ) =,FIRST(bBA) =,= , $, d, a ,FOLLOW(B),SELECT(B) =,FIRST(),AaB | d,BbBA | ,编译原理第四章 语法分析,2022/12/2,27,LL(1)文法的判断条件,LL(1)文法定义,一个上下文无关文法 G是LL(1)文法, 当且仅当对 G 中每个非终结符A的任何两个不同的规则 A | ，满足,SELECT(A )SELECT(A) = ,其中 、中至多只有一个能推出串。,编译原理第四章 语法分析,2022/12/2,28,例1 设有文法GS:,S aAbA de | d,SELECT(Ade)= FIRST(de)=d,SELECT(Ad)= FIRST(d)=d,SELECT(Ade)SELECT(Ad),由LL(1)文法定义可知，该文法不是LL(1)文法，因此对输入串不能进行确定的自上而下分析。,编译原理第四章 语法分析,2022/12/2,29,例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, $ ,编译原理第四章 语法分析,2022/12/2,30,所以 SELECT(AaB)SELECT(Ad)=,SELECT(BbBA)SELECT(B)=,由定义可知，GA是LL(1)文法，对任何输入串W可进行确定的分析。,编译原理第四章 语法分析,2022/12/2,31,例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)文法。,编译原理第四章 语法分析,2022/12/2,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)=,S aABA bB | dA | B a | e, 该文法为LL(1)文法,编译原理第四章 语法分析,2022/12/2,33,三、递归下降分析法,条件：要求文法为LL(1)文法1基本思想：对每一个非终结符，构造相应的递归子程序，以完成该非终结符所对应语法成分的分析和识别任务。,编译原理第四章 语法分析,2022/12/2,34,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 ;,编译原理第四章 语法分析,2022/12/2,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)文法,编译原理第四章 语法分析,2022/12/2,36,构造递归下降分析程序。定义：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;,编译原理第四章 语法分析,2022/12/2,37,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;,编译原理第四章 语法分析,2022/12/2,38,若改写文法用BNF范式表示：ET+TTF*FF(E) | i则编程如下：,Procedure E;BeginT;while sym=+ do beginadvance;T;endend,Procedure T;BeginF;while sym=* do beginadvance;F;endend,编译原理第四章 语法分析,2022/12/2,39,例如：,编译原理第四章 语法分析,2022/12/2,40,编译原理第四章 语法分析,2022/12/2,41,编译原理第四章 语法分析,2022/12/2,42,PROCEDURE BEGIN IF SYM=iTHEN READWORD ELSE ERROREND;,编译原理第四章 语法分析,2022/12/2,43,PROCEDURE BEGIN,编译原理第四章 语法分析,2022/12/2,44,编译原理第四章 语法分析,2022/12/2,45,四、LL(1)分析法（预测分析法）,条件：要求文法为LL(1)文法L从左到右进行分析L每次进行最左推导(1)向前查看一个符号,编译原理第四章 语法分析,2022/12/2,46,1.LL(1)分析器的逻辑结构,总控程序,LL(1)分析表,Tj,Sk,j,分析栈,编译原理第四章 语法分析,2022/12/2,47,2.分析表的构造方法,输入：文法G输出：分析表M方法：对文法中每一个产生式A，按照下述规则确定M中各个元素。对于FIRST()中的每一个终结符a置为 MA , a=A 若空串 FIRST()，则对Follow(A)中的每一个终结符b置为 MA , b=A 把M中未定义的元素置为error。,编译原理第四章 语法分析,2022/12/2,48,例如：已知文法GE: 试构造分析表。ETEE+TE| TFTT*FT | F(E) | i对ETE产生式：First(TE)=( , i 置 ME , ( = ETEME , i = ETE,编译原理第四章 语法分析,2022/12/2,49,对产生式E+TE| First(+TE )=+置ME , + = E+TEFollow(E)= ) , #置ME , ) =E ME , # =E 对产生式TFTFirst(FT)= ( , i 置MT , ( = TFT MT , i = TFT对产生式T*FT | First(*FT)=* 置MT,*= T*FT Follow(T)= + , ) , # 置MT,+= T MT,)= T MT,#= T 对产生式F(E) | i First( (E) )= ( 置MF , ( = F(E) First( i )= i 置MF , i = Fi,编译原理第四章 语法分析,2022/12/2,50,3.总控程序框图,J:=1;k:=1;sk:= #;k:=k+1;Z =sk,Sk VT?,Sk =Tj?,Sk =# ?,查M Sk , 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,编译原理第四章 语法分析,2022/12/2,51,4.分析过程,例如：已知文法G，请利用LL(1)分析表给出输入串i1*i2+i3的分析过程。GE:ETEE+TE| TFTT*FT | F(E) | i,编译原理第四章 语法分析,2022/12/2,52,E,编译原理第四章 语法分析,2022/12/2,53,例2：已知文法GA：AaAa | 该文法是LL(1)文法吗？为什么？若采用LL(1)方法进行语法分析，请构造该文法的LL(1)分析表？若输入符号串为“aaaa”，请给出语法分析 过程。请给出该文法的递归下降分析子程序。,编译原理第四章 语法分析,2022/12/2,54,解：Follow(A)=# First(a)=a , # 有: First(A) Follow(A)=a , a , # 该文法不是LL(1)文法。修改文法 GA : AaaA | 由于：First(A) Follow(A)= a , # = GA 是LL(1)文法该文法的分析表为：,编译原理第四章 语法分析,2022/12/2,55,若输入符号串为“aaaa”，则分析过程如下。,编译原理第四章 语法分析,2022/12/2,56,编译原理第四章 语法分析,2022/12/2,57,例3：已知文法GP:Pbegin d ; X endXd ; X | sYY ; sY | 作出该文法的LL(1)分析表。解：Follow(Y)=Follow(X) Follow(Y)=end该文法的LL(1)分析表为：,编译原理第四章 语法分析,2022/12/2,58,课堂练习,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)文法。,编译原理第四章 语法分析,2022/12/2,59,3.已知文法GS:SBAABS | dBaA | bS | c求：每一个非终结符的First集和Follow集。证明文法G是LL(1)的。构造LL(1)分析表。写出句子adccd的分析过程,