编译原理—清华大学—第2版_第5章自顶向下语法分析方法

1、第第5 5章章 自顶向下语法分析方法自顶向下语法分析方法 教学要求：教学要求：本章介绍编译程序的第二个本章介绍编译程序的第二个阶段语法分析的设计方法和实现原理，阶段语法分析的设计方法和实现原理，包括自上而下分析的无回朔的递归下降包括自上而下分析的无回朔的递归下降分析、分析、 LL(1)LL(1)分析法。要求理解递归下分析法。要求理解递归下降分析、降分析、LL(1)LL(1)文法的基本概念；掌握文法的基本概念；掌握LL(1)LL(1)分析表的构造与分析方法。分析表的构造与分析方法。 教学重点：教学重点：LL(1)LL(1)文法，预测分析表构造，文法，预测分析表构造，LLLL（1 1）分析法。）分

2、析法。 5.1 5.1 确定的自顶向下分析思想确定的自顶向下分析思想 文法文法G1S:SpASqBAcAdAaBdBBbW=pccadd自顶向下的推导过程：自顶向下的推导过程：S S pA pA pcAd pcAd pccAdd pccAdd pccadd pccadd语法树：语法树：SpAcA dcA da确定的自顶向下分析确定的自顶向下分析1 1、基本思想：、基本思想： 从识别符出发，不断建立直接推导，试图构造一从识别符出发，不断建立直接推导，试图构造一个推导序列，最终由它推导出与输入符号串相同个推导序列，最终由它推导出与输入符号串相同的符号串。的符号串。2 2、遇到问题、遇到问题: :

3、（1 1）回溯（出现若干个左部相同的产生式）回溯（出现若干个左部相同的产生式） （2 2）无限循环（文法出现左递归）无限循环（文法出现左递归）3 3、解决方法：、解决方法： （1 1）避免回溯）避免回溯 （2 2）消除左递归）消除左递归 为了避免回溯为了避免回溯, ,先研究三个定义：先研究三个定义： 符号串符号串开始符号开始符号FIRSTFIRST集集 非终结符非终结符A A后跟符号后跟符号FOLLOWFOLLOW集集 产生式的选择集合产生式的选择集合SELECTSELECT集集 定义：设定义：设 G = (VT ,VN , S , P) 是上下文无关是上下文无关文法，文法， = a|,a V

4、T,V*若若 ，则规定则规定FIRST()*1 1、符号串、符号串开始符号开始符号FIRSTFIRST集的定义：集的定义： FIRST(Ap)=a,c FIRST(Bq)=b,d 文法文法G2S:SApSBqAaAcABbBdB2 2、非终结符、非终结符A A后跟符号后跟符号FOLLOWFOLLOW集的定义：集的定义： 定义：设定义：设 G = (VT ,VN , S , P) 是上下文无关文是上下文无关文法，法，AVN , S是开始符号。是开始符号。 若若S A，则规定则规定 #FOLLOW(A)*# #作为输入串的结束符，或称为句子括号，作为输入串的结束符，或称为句子括号， 如：如：# #

5、输入串输入串# #3 3、产生式、产生式AA的选择集合的选择集合SELECTSELECT的定义：的定义：（确定选择那个产生式来推导）（确定选择那个产生式来推导） 定义：给定上下文无关文法的产生式定义：给定上下文无关文法的产生式A，AVN , V*，若若 ，则则=FIRST()如果如果 ，则则 =(FIRST()-)FOLLOW(A)*例：例： SaA Sd A AbASSELECT(SaA)=FIRST(aA)=aSELECT(Sd)=FIRST(d)=dSELECT(A)=FOLLOW(A)=a，d，#SELECT(AbAS)=FIRST(bAS)=b 定义：一个上下文无关文法是定义：一个上

6、下文无关文法是的的充要条件是：充要条件是： 对每个非终结符对每个非终结符A的的任两个任两个不同产生式不同产生式A和和A，满足满足SELECT(A)SELECT(A)=其中其中,不能同时不能同时 *LL(1)文法的含义：文法的含义： 第一个第一个 表示：自顶向下分析是表示：自顶向下分析是。 第二个第二个 表示：分析过程中将用表示：分析过程中将用。 表示：只需表示：只需便可决定如何便可决定如何推导（即选择哪个产生式进行推导）。推导（即选择哪个产生式进行推导）。 类似也可以有类似也可以有文法：需向前查看文法：需向前查看K个个符号才可确定选用哪个产生式。符号才可确定选用哪个产生式。 文法文法GS是否是

7、是否是LL(1)文法文法: :SaASdAbASA SELECT(SaA) =aSELECT(Sd)=dSELECT(AbAS)=bSELECT(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,bSELECT(SaAS)SELECT(Sb)=ab=SELECT(AbA)SELECT(A)=ba,b所以该文法

8、不是所以该文法不是LL(1)文法。文法。对输入串对输入串W=abW=ab进行推导：进行推导：SELECT(AbA)SELECT(A)=ba,bS Sa aA AS SabASabASabSabS出错出错S Sa aA AS SaSaSabab5.2 LL(1)文法的判别文法的判别求出能推出求出能推出的非终结符的非终结符计算计算FIRST集集计算计算FOLLOW集集计算计算SELECT集集判别是否是判别是否是LL(1)文法文法 例：设文法例：设文法GS 为为:SABSbCAAbBBaDCADCbDaSDc判断它是否是判断它是否是LL(1)文法。文法。1.1.求出能推出求出能推出 的非终结符的非终

9、结符SABSbCAAbBBaDCADCbDaSDc能推出能推出 的非终结符为：的非终结符为： A A，B B，S SSABSbCAAbBBaDCADCbDaSDcFIRST(S)=a,b,FIRST(A)=b, FIRST(B)=a, FIRST(C)=a,b,cFIRST(D)=a,cFIRST(AB)=a,b,FIRST(AD)=a,b,c2.2.计算计算FIRSTFIRST集集3.3.计算计算FOLLOWFOLLOW集集(1)(1)对于文法的开始符号对于文法的开始符号S, ,置置#于于FOLLOW(FOLLOW(S) )中中; ;(2)(2)若若B是一个产生式是一个产生式, , 则把则把

10、FIRST()-FIRST()- 加至加至FOLLOW(B)FOLLOW(B)中中; ; 若若 ( (即即 FIRST()FIRST()），），则把则把FOLLOW(A)FOLLOW(A)加至加至FOLLOW(B)FOLLOW(B)中中SABSbCAAbBBaDCADCbDaSDcFOLLOW(S)=#FOLLOW(D)FOLLOW(S)= #FOLLOW(A)= a,c,#FOLLOW(B)= #FOLLOW(C)= #FOLLOW(D)= #FOLLOW(A)=a FOLLOW(S) a,cFOLLOW(B)=FOLLOW(S)FOLLOW(C)=FOLLOW(S)FOLLOW(D)=FO

11、LLOW(B)FOLLOW(C) =FOLLOW(S)4.计算计算SELECT集集SABSbCAAbBBaDCADCbDaSDcFIRST(S)=a,b,FIRST(A)=b, FIRST(B)=a, FIRST(C)=a,b,cFIRST(D)=a,cFIRST(AB)=a,b,FIRST(AD)=a,b,cSELECT(SAB)=a,b,#SELECT(SbC)=bSELECT(A)=a,c,#,SELECT(Ab)=bSELECT(B)=#SELECT(BaD)=aSELECT(CAD)=a,b,cSELECT(Cb)=bSELECT(DaS)=aSELECT(Dc)=cFOLLOW(S

12、)= #FOLLOW(A)= a,c,#FOLLOW(B)= #FOLLOW(C)= #FOLLOW(D)= #该文法不是该文法不是LL(1)文法。文法。5.3 某些非某些非LL(1)文法到文法到LL(1)文法文法 的等价变换的等价变换LL(1)LL(1)文法的性质：文法的性质： LL(1)LL(1)文法不含左公共因子文法不含左公共因子 LL(1)LL(1)文法不含左递归文法不含左递归1、提取左公共因子提取左公共因子 产生式形如：产生式形如：A A1 1| |2 2|n n| | 表示不以表示不以 开头的字符串。开头的字符串。 2.2.引进非终极符引进非终极符A A ，使产生式替换使产生式替换

13、为：为： A AA A | | A A1 1| | 2 2| n n例例1 1：消除下面文法的左公共因子：消除下面文法的左公共因子Stm id := ExpStm id := ExpStm id (ExpL)Stm id (ExpL)ExpL Exp ExpL Exp ExpL Exp,ExpLExpL Exp,ExpL Stmid StmStmid Stm StmStm := Exp:= ExpStmStm ( ExpL )( ExpL )ExpLExp ExpLExpLExp ExpL ExpL ExpL ExpL ，ExpL ExpL 例例2 2：消除下面文法的左公共因子：消除下面文法的

14、左公共因子A AadadA ABcBcB BaAaAB BbBbB替换替换A AadadA AaAcaAcA AbBcbBcB BaAaAB BbBbB提因子提因子A Aa(d|Ac)a(d|Ac)A AbBcbBcB BaAaAB BbBbB引进引进AAA AaAaA A A d dA A AcAcA AbBcbBcB BaAaAB BbBbB说明：说明：（1）文法中不含左公共因子只是文法中不含左公共因子只是LL（1）文文法的必要条件。法的必要条件。 例如：例如：GS： S-aSb S-aS S- 变换后：变换后：G1SS-aSA A-bA- S- SELECT(S-aSA)=aSELECT

15、(S- )=FOLLOW(S)=#,bSELECT(A-b)=bSELECT(A- )= FOLLOW(S)=#,b化为：化为：SaS(b|)S结果仍然不是结果仍然不是LL(1)文法文法。（2 2）一个文法提取了左公共因子后，只解决）一个文法提取了左公共因子后，只解决了相同左部产生式右部的了相同左部产生式右部的FIRSTFIRST集不相交问集不相交问题，当改写后的文法不含空产生式，且无题，当改写后的文法不含空产生式，且无左递归时，则改写后的文法是左递归时，则改写后的文法是LL(1)LL(1)文法，文法，否则还需用否则还需用LL(1)LL(1)文法的判别方式进行判断文法的判别方式进行判断才能确定

16、是否为才能确定是否为LL(1)LL(1)文法。文法。2 2、消除左递归、消除左递归 直接左递归直接左递归：AA A VN, V* 间接左递归间接左递归：ABBA A,B VN, , V*（1 1）消除直接左递归）消除直接左递归 把直接左递归改写为右递归把直接左递归改写为右递归 如如G5:SSaSb(L=ban|n0) 改为改为：SbSSaS| 消除直接左递归的一般方法消除直接左递归的一般方法： AA1| A2| Am|1|2|n 其中其中： i 不等于不等于 ， j不以不以A开头开头。 改为改为： A 1A| 2A | nA A 1A | 2A | mA | 例例 文法文法G(E):G(E):

17、EEEET|TT|TTTTT* *F|FF|FF(E)|iF(E)|i经消去直接左递归后变成：经消去直接左递归后变成： ETEETE E E +TE+TE | | TFTTFT T T * *FTFT | | F(E)|i F(E)|iPP 1 | P 2 | | P m | 1 | 2| nP 1P | 2P | | nP P 1P | 2P | | mP | （2 2）消除间接左递归）消除间接左递归 将间接左递归变为直接左递归，然后消除将间接左递归变为直接左递归，然后消除直接左递归。直接左递归。AaBABbBAcBdAaBABbBaBcBBbcBdAaBABbBaBcB | dB BbcB

18、 |5.5 5.5 确定的自顶向下分析方法确定的自顶向下分析方法 1.1.递归子程序法递归子程序法 2.2.预测分析法预测分析法 1.1.递归子程序法递归子程序法 递归下降法递归下降法( (Recursive-Descent Parsing)Recursive-Descent Parsing) 对每个非终结符按其产生式结构产生相对每个非终结符按其产生式结构产生相应语法分析子程序应语法分析子程序. . 终结符产生匹配命令终结符产生匹配命令 非终结符则产生调用命令非终结符则产生调用命令 文法递归相应子程序也递归，所以称这文法递归相应子程序也递归，所以称这种方法为递归子程序方法或递归下降法。种方法为

19、递归子程序方法或递归下降法。假设有文法假设有文法ZaBaZaBaBbB|cBbB|c则相应的递归子程序可如下：则相应的递归子程序可如下：procedure Z( )procedure Z( )begin begin if token=a then Match(a) if token=a then Match(a)； B B； Match(a) Match(a) else error else errorend;end;procedure B ( )procedure B ( )beginbegin if token=b then Match(b); if token=b then Match(

20、b); B; B; else else if token=c if token=c then Match(c); then Match(c); else error else errorend;end;主程序：主程序：Begin readtoken Z endBegin readtoken Z endPROCEDURE match(t); BEGIN IF token=t THEN token:=nexttoken ELSE error END;2.2.预测分析法预测分析法一一. . 基本思想基本思想 预测分析是在每步推导中预测分析是在每步推导中, ,对被替换的非终对被替换的非终结符号结符号A

21、 A和当前向前看符号和当前向前看符号a a能选择能选择A A的某条产生式的某条产生式进行推导。进行推导。 非递归预测分析的基本思想是，根据文法非递归预测分析的基本思想是，根据文法G G，构造一张分析表构造一张分析表M M，表中元素表中元素MAMA，aa存放的，要存放的，要么是被选择的产生式（正确分析情况）；要么是么是被选择的产生式（正确分析情况）；要么是出错处理程序入口（分析出现错误）。整个分析出错处理程序入口（分析出现错误）。整个分析是在分析表是在分析表M M的驱动下完成的。的驱动下完成的。二、预测分析表的构造二、预测分析表的构造1 1对文法对文法G G的每个产生式的每个产生式A A执行第执

22、行第2 2步；步；2 2对每个终结符号对每个终结符号aSELECTaSELECT（A A），），把把 A A加至加至MA,aMA,a中；中； 3 3把所有无定义的把所有无定义的MA,aMA,a标上错误标记。标上错误标记。置置ipip指向指向w#w#的第一个符号的第一个符号,#,#进栈，进栈，S(S(开始符号开始符号) )进栈进栈 repeatrepeat 令令X X是栈顶符号，是栈顶符号，a a是是ipip所指向的符号；所指向的符号； if Xif X是一个终结符号或是一个终结符号或# #thenthen if X=a then if X=a then 把把X X从栈中弹出，并且更新从栈中弹出

23、，并且更新ipip else error() else error() else / else /* *X X是非终结符号是非终结符号* */ / if MX,aif MX,a XY XY1 1Y Y2 2YYk k then begin then begin 把把X X从栈中弹出；从栈中弹出； 把把Y Yk k，Y Yk-1k-1，, Y, Y1 1压入栈中，即压入栈中，即Y Y1 1在顶上；在顶上； 输出产生式输出产生式XYXY1 1Y Y2 2YYk k end end else error() else error() until X=# / until X=# /* *栈为空栈为空*

24、 */ /三、预测分析程序三、预测分析程序例例 G:E E+T | T T T*F | F F i | ( E )试分析输入串试分析输入串i+ii+i* *i i是否是句子是否是句子. . 1.1.将文法转换为将文法转换为LL(1)LL(1)文法文法E E+T | TT T*F | FF i | ( E )消除左递归消除左递归E TEE +TE | T FTT *FT | F i | ( E )可推出可推出的非终结符表：的非终结符表：E TEE +TE | T FTT *FT | F i | ( E )EETTF是是是是否否否否否否各非终结符的各非终结符的FIRSTFIRST集和集和FOLLOWFOLLOW集：集：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 ) , # ) , # + , ) , # + , ) , # * , + , ) , # 各产生式的各产生式的SELECTSELE