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

1、编译原理第四章 语法分析,2020/6/20,1,第四章 语法分析,编译原理第四章 语法分析,2020/6/20,2,第四章 语法分析 1、概述 一. 语法分析器的功能,编译原理第四章 语法分析,2020/6/20,3,语法分析：在词法分析的基础上，根据语法规则，从单词符号串中识别出各种语法成分，同时进行语法检查，检查各种语法成分在语法结构上的正确性。,编译原理第四章 语法分析,2020/6/20,4,二.语法分析方法,自上向下分析法： 从文法的开始符号出发，以给定的符号串为目标，根据文法规则，正向推导出给定符号串的一种方法。 自下向上分析法：从给定的符号串出发，反复使用文法中有关产生式的左部

2、去替换当前符号串中的相应子串，逐步归约成文法开始符号的一种方法。 自上向下分析法：递归下降、LL(1)分析法 自下向上分析法：算符优先、LR分析法,编译原理第四章 语法分析,2020/6/20,5,2、自上而下分析方法 一、带回溯的自上而下分析法,基本思想：对任何输入串，试图用一切可能的方法，从文法的开始符号出发，采用最左推导，自上而下为输入串建立一棵语法树。 例如：设有文法：SxAy A* | * 输入串：x*y 看匹配过程,S,A,x,y,S,A,x,y,S,A,x,y,*,*,*,编译原理第四章 语法分析,2020/6/20,6,二、存在的问题以及解决的方法 1.左递归：,当文法为左递归

3、时，会使分析程序进入无限循环之中。 若文法中有非终结符P=P (文法左递归) 输入某输入串w=a1a2an 就有P= P= P 如此循环，不会终止,+,编译原理第四章 语法分析,2020/6/20,7,消除直接左递归,方法一：引进新的非终结符，改写文法规则式。 PP | P P P P | （将文法中的左递归结构变成等价的右递归结构） 例如：算术表达式文法左递归 EE+T | T ETE TT*F | F E+TE| F(E) | i TFT T*FT | F(E) | i,编译原理第四章 语法分析,2020/6/20,8,一般情况：有多个直接左递归： PP1 | P2 | | Pm | 1

4、| 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 | ,编译原理第四章 语法分析,2020/6/20,9,方法二：采用扩充的BNF表示法改写文法规则式 用花括号表示符号串出现0次或多次。即* 标识符：Il l | d 或 Il l | d 7 即将 AA | 改写成 A 中括号表示是可供选择的符号串。 if B then else 使用圆括号，可以在规则中提因子。 UXY|XW|XZ U

5、X(Y|W|Z) 例如：算术表达式文法左递归 EE+T | T ET+T TT*F | F TF*F F(E) | i F(E) | i,编译原理第四章 语法分析,2020/6/20,10,消除所有左递归的算法,(1)把文法G的所有非终结符按任一顺序排列成 P1 , P2 , Pn ; (2)执行循环语句： for i:=1 to n do 将规则 PiPj 改写； 改写方法： Pj1 | 2 | n 则 Pi1 | 2 | n 消除关于Pi的直接左递归 end (3)化简由(2)得到的文法。,编译原理第四章 语法分析,2020/6/20,11,例如：消除下面文法的左递归。 文法：SQc |

6、c QRb | b RSa | 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 若排列方法不同，得到的文法也可能不同，但等价,编译原理第四章 语法分析,2020/6/20,12,2.回溯问题,问题：如果对同一个非终结符号

7、，有若干个产生式右部 A 1 | 2 | | n , 选择哪一个产生式匹配呢？ 匹配不好就产生回溯。回溯使语法分析器的动作不确定。分析：要消除回溯，必须使文法具有一定的特性。 例如：ScAd Aad | a 输入符号w=cad 分析：要求各规则式右部1 | 2 | | n 所推出的终结首符号的集合两两不相交。 定义：符号串i 终结首符号的集合： FIRST(i )= | i =a , VT ,*,编译原理第四章 语法分析,2020/6/20,13,条件一：对文法中每一个非终结符A，如有规则： A 1 | 2 | | n 则下面条件成立 FIRST(i ) FIRST(j )= (ij) 上例中

8、： FIRST(ab) FIRST(a)=a a=a 改写方法：提取公共左因子 A 1 | 2 | | n | 1 | 2 | m 则： AA | 1 | 2 | m A 1 | 2 | | n 例如：if E then S1 else S2 | if E then S1 改写为： if E then S1 B B else S2 | ,编译原理第四章 语法分析,2020/6/20,14,问题：若满足条件 FIRST(i ) FIRST(j )= 是否完全避免回溯呢？ 上例中： ScAd Aad | a 改写为： ScAd A aA Ad | 输入符号w=cad 匹配d可能失败，差条件 定义：

9、非终结符号A的后继符号的集合： FOLLOW(A)=a | S=Aa , VT 当S=A，则规定 # FOLLOW(A) （#为界符） 条件二：若i = 时 ， FIRST(i ) FOLLOW(A) = 上例中：FIRST(d) FOLLOW(A)=d 产生回溯,*,*,编译原理第四章 语法分析,2020/6/20,15,小结：构造不带回溯的自上而下分析的条件是： 1.文法不含左递归 2.对文法中每一个非终结符A，如有规则： A 1 | 2 | | n 则下面条件成立 FIRST(i ) FIRST(j )= (ij) 3.对文法中每一个非终结符A，若它的某个产生式首符集包含 时 ，则： F

10、IRST(A) FOLLOW(A) = 满足以上条件的文法称为LL(1)文法。 对于一个LL(1）文法，可以构造无回溯的自上而下分析。,编译原理第四章 语法分析,2020/6/20,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/6/20,17,FOLLOW(A)的求法： （其中A是任一非终

11、结符）,若有产生式B Aa ,且a是终结符，则把a加入到FOLLOW(A)中。 若有产生式B AX ,且X是非终结符 , 则把FIRST(X)加入到FOLLOW(A)中。 若有产生式B A，或B A，但=，则把FOLLOW(B)加入到FOLLOW(A)中。 若A是文法的开始符号，则把结束符#加入到FOLLOW(A)中。,编译原理第四章 语法分析,2020/6/20,18,例：已知文法GS: SaSb | P PbPc | bQc QQa | a 消除文法左递归后是不是LL(1)文法？ 解：消除文法左递归得到： SaSb | P PbPc | bQc QaQ QaQ| 提取公共左因子后得文法：

12、SaSb | P PbP P Pc | Qc QaQ QaQ| 计算FIRST和FOLLOW集合： FIRST(S)=a,b FIRST(P)=b FIRST(P)=a,b FIRST(Q)=a FIRST(Q)=a, Follow(S)=b,# Follow(P)=b,c,# Follow(P)=b,c,# Follow(Q)=c Follow(Q)=c 是LL(1)文法,编译原理第四章 语法分析,2020/6/20,19,例：将文法改写成LL(1)文法。 SS*aP | aP | *aP P+aP | +a 解：消除文法左递归、提取公共左因子得到： SaPS | *aPS S *aPS |

13、 P+aP PP | 计算每个非终结符的FIRST和FOLLOW集合： FIRST(S)=a,* Follow(S)=# FIRST(S)=*, Follow(S)=# FIRST(P)=+ Follow(P)=*, # FIRST(P)=+, Follow(P)=*,# 以上文法是LL(1)文法。,编译原理第四章 语法分析,2020/6/20,20,已知文法：GS： SAB | PQx Axy | m BbC CbC | PpP | Qq 如果要保持文法为LL(1)文法，下列哪几个产生式不能加入到该文法中？为什么？ （1）SbC （2）AbC （3）B （4）Q,编译原理第四章 语法分析,2

14、020/6/20,21,解：(1) 加入SbC后文法为： SAB | PQx | bC Axy | m BbC CbC | 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)文法。,编译原理第四章 语法分析,2020/6/20,22,(2) 加入AbC后文法为： SAB | PQx Axy | m | bC BbC CbC

15、 | 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 | PQx Axy | m BbC | CbC | PpP | Qq 对B: First(bC) Follow(B) =b # = 是LL(1)文法。,编译原理第四章 语法分析,2020/6/20,23,(4) 加入Q 后文法为： SAB | PQx Axy | m BbC CbC | PpP | Qq | First(S)=x,m,p,q Follow(S)=# F

16、irst(A)=x,m Follow(A)=b First(B)=b Follow(B)=# First(C)=b, Follow(C)=# First(P)=p, Follow(P)=q,x First(Q)=q , Follow(Q)=x 对S: First(AB) First(PQx) = x,m p,q,x =x 加入Q 后文法不是LL(1)文法。,编译原理第四章 语法分析,2020/6/20,24,定义规则的选择集合SELECT，设 A 是文法G的任一条规则，其中 AVN , (VNVT)* ，定义,SELECT(A ) =,FIRST(),FIRST()FOLLOW (A),定义S

17、ELECT集合,编译原理第四章 语法分析,2020/6/20,25,例 设有文法GA:,AaB | d,BbBA | ,SELECT(AaB ) =,FIRST(aB) =, a ,SELECT(Ad ) =,FIRST(d) =, d ,编译原理第四章 语法分析,2020/6/20,26, b ,SELECT(BbBA ) =,FIRST(bBA) =,= , $, d, a ,FOLLOW(B),SELECT(B) =,FIRST(),AaB | d,BbBA | ,编译原理第四章 语法分析,2020/6/20,27,LL(1)文法的判断条件,LL(1)文法定义,一个上下文无关文法 G是L

18、L(1)文法, 当且仅当对 G 中每个非终结符A的任何两个不同的规则 A | ，满足,SELECT(A )SELECT(A) = ,其中 、中至多只有一个能推出串。,编译原理第四章 语法分析,2020/6/20,28,例1 设有文法GS:,S aAb A de | d,SELECT(Ade)= FIRST(de)=d,SELECT(Ad)= FIRST(d)=d,SELECT(Ade)SELECT(Ad),由LL(1)文法定义可知，该文法不是LL(1)文法，因此对输入串不能进行确 定的自上而下分析。,编译原理第四章 语法分析,2020/6/20,29,例2 设有文法GA,A aB | d B

19、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, $ ,编译原理第四章 语法分析,2020/6/20,30,所以 SELECT(AaB)SELECT(Ad)=,SELECT(BbBA)SELECT(B)=,由定义可知，GA是LL(1)文法，对任何输入串W可进行确定的分析。,编译原理第四章 语法分析,2020/6/20,31,例3 设有文法GS:,S aAB A bB | dA | B a |

20、e, SELECT(AbB)=FIRST(bB)= b,SELECT(AdA)=FIRST(dA)= d,SELECT(A)=FIRST()FOLLOW(A),= a, e = , a, e ,试判断该文法是否LL(1)文法。,编译原理第四章 语法分析,2020/6/20,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 aAB A bB | dA | B a |

21、e, 该文法为LL(1)文法,编译原理第四章 语法分析,2020/6/20,33,三、递归下降分析法,条件：要求文法为LL(1)文法 1 基本思想：对每一个非终结符，构造相应的递归子程序，以完成该非终结符所对应语法成分的分析和识别任务。,编译原理第四章 语法分析,2020/6/20,34,2 方法： 为每一个非终结符，构造相应的递归过程，过程的名字表示规则左部的非终结符；过程体按规则右部符号串的顺序编写。 对于产生式：Ux1 | x2 | xn 则编写 if ch in FIRST(x1) then p(x1) else if ch in FIRST(x2) then p(x2) else e

22、rror ; 对于符号串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 return else error ;,编译原理第四章 语法分析,2020/6/20,35,举例：设有文法G： EE+T | T TT*F | F F(E) | i 试构造一个识别该文法句子的递归下降分析程序。 消除文法左递归 ETE E+TE| TFT T*FT | F(E) | i 改写后的文法是否为LL(1)文法： 对E：F

23、irst(+TE) Follow(E)=+ #, )= 对T：First(*FT) Follow(T)=* +,#, )= 对F： First(i) First( (E) )=i ( = 是LL(1)文法,编译原理第四章 语法分析,2020/6/20,36,构造递归下降分析程序。 定义：advance:读下一个单词并放入全程变量sym中 error：错误诊断处理程序 编程如下：,主: advance; E ;,procedure E; begin T; E end;,procedure E; begin if sym=+ then begin advance; T; E end; else i

24、f symfollow(E) then return else error End;,编译原理第四章 语法分析,2020/6/20,37,Procedure T ; Begin F ; T End;,Procedure T Begin if sym=* then begin advance; F ; T; end else if sym not in +,),# then error else return End;,Procedure F Begin if sym=i then advance; else if sym=( then begin advance; E; if sym=) th

25、en advance; else error; end else error; End;,编译原理第四章 语法分析,2020/6/20,38,若改写文法用BNF范式表示： ET+T TF*F F(E) | i 则编程如下：,Procedure E; Begin T; while sym=+ do begin advance; T; end end,Procedure T; Begin F; while sym=* do begin advance; F; end end,编译原理第四章 语法分析,2020/6/20,39,例如：,编译原理第四章 语法分析,2020/6/20,40,编译原理第四

26、章 语法分析,2020/6/20,41,编译原理第四章 语法分析,2020/6/20,42,PROCEDURE BEGIN IF SYM=i THEN READWORD ELSE ERROR END;,编译原理第四章 语法分析,2020/6/20,43,PROCEDURE BEGIN,编译原理第四章 语法分析,2020/6/20,44,编译原理第四章 语法分析,2020/6/20,45,四、LL(1)分析法（预测分析法）,条件：要求文法为LL(1)文法 L从左到右进行分析 L每次进行最左推导 (1)向前查看一个符号,编译原理第四章 语法分析,2020/6/20,46,1.LL(1)分析器的逻辑

27、结构,总控程序,LL(1)分析表,Tj,Sk,j,分析栈,编译原理第四章 语法分析,2020/6/20,47,2.分析表的构造方法,输入：文法G 输出：分析表M 方法：对文法中每一个产生式A，按照下述规 则确定M中各个元素。 对于FIRST()中的每一个终结符a置为 MA , a=A 若空串 FIRST()，则对Follow(A)中的每一个终结符b置为 MA , b=A 把M中未定义的元素置为error。,编译原理第四章 语法分析,2020/6/20,48,例如：已知文法GE: 试构造分析表。 ETE E+TE| TFT T*FT | F(E) | i 对ETE产生式： First(TE)=(

28、 , i 置 ME , ( = ETE ME , i = ETE,编译原理第四章 语法分析,2020/6/20,49,对产生式 E+TE| First(+TE )=+ 置 ME , + = E+TE Follow(E)= ) , # 置 ME , ) =E ME , # =E 对产生式 TFT First(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,编译原理第四章 语法分析,2020/6/20,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,编译原理第四章 语法分析,2020