编译原理(第二版)第5章 自顶向下语法分析方法.ppt

1、第5章 自顶向下语法分析方法,教学要求：本章介绍编译程序的第二个阶段语法分析的设计方法和实现原理，包括自上而下分析的无回朔的递归下降分析、 LL(1)分析法。要求理解递归下降分析、LL(1)文法的基本概念；掌握LL(1)分析表的构造与分析方法。 教学重点：预测分析表构造，LL(1)文法。,5.1 确定的自顶向下分析思想,文法G1S:SpASqBAcAdAaBdBBb,W=pccadd自顶向下的推导过程： S pA pcAd pccAdd pccadd,语法树：,确定的自顶向下分析,1、基本思想： 从识别符出发，不断建立直接推导，试图构造一个推导序列，最终由它推导出与输入符号串相同的符号串。 2

2、、遇到问题: （1）回溯（出现若干个左部相同的产生式） （2）无限循环（文法出现左递归） 3、解决方法： （1）避免回溯 （2）消除左递归,为了避免回溯,先研究三个定义： 符号串的开始符号FIRST集 非终结符A后跟符号FOLLOW集 产生式的选择集合SELECT集,定义：设 G = (VT ,VN , S , P) 是上下文无关文法，FIRST() = a| a,a VT,V*若 ，则规定FIRST(),* ,* ,1、符号串的开始符号FIRST集的定义：,FIRST(Ap)=a,c FIRST(Bq)=b,d,文法G2S:SApSBqAaAcABbBdB,2、非终结符A后跟符号FOLLOW

3、集的定义： 定义：设 G = (VT ,VN , S , P) 是上下文无关文法，AVN , S是开始符号。 FOLLOW(A)=a|S Aa ,aVT 若S A，则规定 #FOLLOW(A),* ,* ,#作为输入串的结束符，或称为句子括号， 如：#输入串#,3、产生式A的选择集合SELECT的定义： （确定选择那个产生式来推导） 定义：给定上下文无关文法的产生式A，AVN , V*，若 ，则 SELECT(A)=FIRST()如果 ，则 SELECT(A)=(FIRST()-)FOLLOW(A),* ,例： SaA Sd A AbAS SELECT(SaA)=FIRST(aA)=a SEL

4、ECT(Sd)=FIRST(d)=d SELECT(A)=FOLLOW(A)=a，d，# SELECT(AbAS)=FIRST(bAS)=b,定义：一个上下文无关文法是LL(1)文法的充要条件是： 对每个非终结符A的任两个不同产生式A和A，满足SELECT(A)SELECT(A)=其中,不能同时 ,* ,LL(1)文法的含义：,第一个L表示：自顶向下分析是从左向右扫描输入串。 第二个L表示：分析过程中将用最左推导。 1表示：只需向右看一个符号便可决定如何推导（即选择哪个产生式进行推导）。 类似也可以有LL(K)文法：需向前查看K个符号才可确定选用哪个产生式。,文法GS是否是LL(1)文法:Sa

5、ASdAbASA,SELECT(SaA) =a SELECT(Sd)=d SELECT(AbAS)=b SELECT(A)=a,d,#,SELECT(SaA)SELECT(Sd)=ad= SELECT(AbAS)SELECT(A)=ba,d,#=,所以该文法是LL(1)文法。,例：文法GS 为:SaASSbAbAA,则：SELECT(SaAS)=a SELECT(Sb)=b SELECT(AbA)=b SELECT(A)=a,b,SELECT(SaAS)SELECT(Sb)=ab= SELECT(AbA)SELECT(A)=ba,b,所以该文法不是LL(1)文法。,5.2 LL(1)文法的判别

6、,求出能推出的非终结符 计算FIRST集 计算FOLLOW集 计算SELECT集 判别是否是LL(1)文法,例：设文法GS 为:SABSbCAAbBBaDCADCbDaSDc判断它是否是LL(1)文法。,1.求出能推出的非终结符,SABSbCAAbBBaDCADCbDaSDc,能推出的非终结符为： A，B，S,SABSbCAAbBBaDCADCbDaSDc,FIRST(S)=a,b, FIRST(A)=b, FIRST(B)=a, FIRST(C)=a,b,c FIRST(D)=a,c,FIRST(AB)=a,b, FIRST(AD)=a,b,c,2.计算FIRST集,3.计算FOLLOW集,

7、(1)对于文法的开始符号S,置#于FOLLOW(S)中; (2)若B是一个产生式, 则把FIRST()-加至FOLLOW(B)中;,SABSbCAAbBBaDCADCbDaSDc,FOLLOW(S)=#FOLLOW(D),FOLLOW(S)= # FOLLOW(A)= a,c,# FOLLOW(B)= # FOLLOW(C)= # FOLLOW(D)= #,FOLLOW(A)=a FOLLOW(S) a,c,FOLLOW(B)=FOLLOW(S),FOLLOW(C)=FOLLOW(S),FOLLOW(D)=FOLLOW(B)FOLLOW(C) =FOLLOW(S),4.计算SELECT集,SA

8、BSbCAAbBBaDCADCbDaSDc,FIRST(S)=a,b, FIRST(A)=b, FIRST(B)=a, FIRST(C)=a,b,c FIRST(D)=a,c FIRST(AB)=a,b, FIRST(AD)=a,b,c,SELECT(SAB)=a,b,# SELECT(SbC)=b SELECT(A)=a,c,#, SELECT(Ab)=b SELECT(B)=# SELECT(BaD)=a SELECT(CAD)=a,b,c SELECT(Cb)=b SELECT(DaS)=a SELECT(Dc)=c,FOLLOW(S)= # FOLLOW(A)= a,c,# FOLLO

9、W(B)= # FOLLOW(C)= # FOLLOW(D)= #,该文法不是LL(1)文法。,5.3 某些非LL(1)文法到LL(1)文法 的等价变换,LL(1)文法的性质： LL(1)文法不含左公共因子 LL(1)文法不含左递归,1、提取左公共因子,产生式形如：A1|2|n| 表示不以开头的字符串。 2.引进非终极符A ，使产生式替换为： AA| A1|2|n,例1：消除下面文法的左公共因子,Stm id := Exp Stm id (ExpL) ExpL Exp ExpL Exp,ExpL,Stmid Stm Stm:= Exp Stm( ExpL ) ExpLExp ExpL ExpL

10、 ExpL，ExpL,例2：消除下面文法的左公共因子,Aad ABc BaA BbB,Aad AaAc AbBc BaA BbB,Aa(d|Ac) AbBc BaA BbB,AaA Ad AAc,AbBc BaA BbB,说明：,（1）文法中不含左公共因子只是LL（1）文法的必要条件。 例如：GS： S-aSb S-aS S- ,变换后：G1S S-aSA A-b A- S- ,SELECT(S-aSA)=a SELECT(S- )=FOLLOW(S)=#,b SELECT(A-b)=b SELECT(A- )= FOLLOW(S)=#,b,化为： SaS(b|) S,结果仍然不是LL(1)文

11、法。,（2）一个文法提取了左公共因子后，只解决了相同左部产生式右部的FIRST集不相交问题，当改写后的文法不含空产生式，且无左递归时，则改写后的文法是LL(1)文法，否则还需用LL(1)文法的判别方式进行判断才能确定是否为LL(1)文法。,2、消除左递归,直接左递归：AA AVN, V* 间接左递归：ABBA A,BVN, ,V*,（1）消除直接左递归,把直接左递归改写为右递归 如G5:SSaSb(L=ban|n0) 改为：SbSSaS|,消除直接左递归的一般方法： AA1| A2| Am|1|2|n 其中： i 不等于 ， j不以A开头。 改为： A 1A| 2A | nA A 1A | 2

12、A | mA |,（2）消除间接左递归,将间接左递归变为直接左递归，然后消除直接左递归。AaBABbBAcBd,AaBABb BaBcBBbcBd,AaBABb BaBcB | dB BbcB |,5.5 确定的自顶向下分析方法,1.递归子程序法 2.预测分析法,1.递归子程序法,递归下降法(Recursive-Descent Parsing) 对每个非终结符按其产生式结构产生相应语法分析子程序. 终结符产生匹配命令 非终结符则产生调用命令 文法递归相应子程序也递归，所以称这种方法为递归子程序方法或递归下降法。,假设有文法 ZaBa BbB|c 则相应的递归子程序可如下： procedure

13、Z( ) begin if token=a then Match(a)； B； Match(a) else error end;,procedure B ( ) begin if token=b then Match(b); B; else if token=c then Match(c); else error end;,主程序：Begin readtoken Z end,PROCEDURE match(t); BEGIN IF token=t THEN token:=nexttoken ELSE error END;,2.预测分析法,一. 基本思想 预测分析是在每步推导中,对被替换的非终结

14、符号A和当前向前看符号a能选择A的某条产生式进行推导。 非递归预测分析的基本思想是，根据文法G，构造一张分析表M，表中元素MA，a存放的，要么是被选择的产生式（正确分析情况）；要么是出错处理程序入口（分析出现错误）。整个分析是在分析表M的驱动下完成的。,二、预测分析表的构造,1对文法G的每个产生式A执行第2步； 2对每个终结符号aSELECT（A），把 A加至MA,a中； 3把所有无定义的MA,a标上错误标记。,置ip指向w#的第一个符号,#进栈，S(开始符号)进栈 repeat 令X是栈顶符号，a是ip所指向的符号； if X是一个终结符号或#then if X=a then 把X从栈中弹出

15、，并且更新ip else error() else /*X是非终结符号*/ if MX,a XY1Y2Yk then begin 把X从栈中弹出； 把Yk，Yk-1，, Y1压入栈中，即Y1在顶上； 输出产生式XY1Y2Yk end else error() until X=# /*栈为空*/,三、预测分析程序,例 G:E E+T | T T T*F | F F i | ( E )试分析输入串i+i*i是否是句子.,1.将文法转换为LL(1)文法,E E+T | T T T*F | F F i | ( E ),消除左递归,E TE,E +TE | ,T FT,T *FT | ,F i | (

16、E ),可推出的非终结符表：,E TEE +TE | T FTT *FT | F i | ( E ),是,是,否,否,否,各非终结符的FIRST集和FOLLOW集：,FIRST(E)= FIRST(E)= FIRST(T)= FIRST(T)= FIRST(F)= FOLLOW(E)= FOLLOW(E)= FOLLOW(T)= FOLLOW(T)= FOLLOW(F)=,ETEE+TE| TFTT*FT| Fi|( E ), ( , i , + , , ( , i , * , , ( , i , ) , # , ) , # , + , ) , # , + , ) , # , * , + ,

17、) , # ,各产生式的SELECT集：,E TEE +TE | T FTT *FT | F i | ( E ),SELECT(E TE) = SELECT(E +TE ) = SELECT(E ) = SELECT(T FT) = SELECT(T *FT ) = SELECT(T ) = SELECT(F ( E ) = SELECT(F i) =,是LL(1)文法。,FIRST(E)= ( , i FIRST(E)= + , FIRST(T)= ( , i FIRST(T)= * , FIRST(F)= ( , i ,FOLLOW(E)= ) , # FOLLOW(E)= ) , # F

18、OLLOW(T)= + , ) , # FOLLOW(T)= + , ) , # FOLLOW(F)= * , + , ) , # , ( , i , + , ) , # , ( , i , * , + , ) , # , ( , i ,2.构造预测分析表,SELECT(E TE)= ( , i SELECT(E +TE )= + SELECT(E )= ) , # SELECT(T FT)= ( , i SELECT(T *FT )= * SELECT(T )= + , ) , # SELECT(F ( E )= ( SELECT(F i)= i ,ETE,ETE,E+TE,E ,E ,TFT