《编译原理及实现技术：第四章 语法分析-自顶向下分析方法》由会员分享，可在线阅读，更多相关《编译原理及实现技术：第四章 语法分析-自顶向下分析方法（48页珍藏版）》请在金锄头文库上搜索。
1、第四章第四章 语法分析语法分析- -自顶向下分自顶向下分析方法析方法自顶向下分析概述自顶向下分析概述三个重要的集合三个重要的集合 递归下降语法分析递归下降语法分析LL(1)LL(1)语法分析语法分析1 1 自顶向下的语法分析简介自顶向下的语法分析简介21.11.1 自顶向下分析基本思想自顶向下分析基本思想从文法开始符出发试图推导出所给的终极从文法开始符出发试图推导出所给的终极符串。符串。例例 Gz :Gz :1Z 1Z aBdaBd2 B 2 B d d3 B 3 B c c4 B 4 B bBbBZ Za aB Bd db bB Bc c3 aBd # abcd # aBd # abcd #
2、 MatchMatch Bd # bcd # Bd # bcd # DerivationDerivation bBd # bcd # bBd # bcd # MatchMatch Bd # cd # Bd # cd # DerivationDerivation cd # cd # cd # cd # MatchMatch d # d # d # d # MatchMatch # # Success # # Success自顶向下的语法分析过程【自顶向下的语法分析过程【Sf,Rest,Action(D/M/S/E)】 Z # abcd # DerivationZ # abcd # Derivat
3、ion1.2 1.2 自顶向下分析实例自顶向下分析实例4思考思考使用自顶向下方法进行语法分析条件是？使用自顶向下方法进行语法分析条件是？52 2 三个重要集合三个重要集合FirstFirstFollowFollowPredictPredict62.12.1 FirstFirst集的定义集的定义定义：定义：设设G=(VG=(VT T，V VN N，S S，P)P)是是CFGCFG, , ( (V VT T V VN N)*)*，则字符串，则字符串 的的FirstFirst集集：First( )=a VT| * a |( * ) P P作用：作用：可以根据当前的输入符号是属于哪可以根据当前的输入符
4、号是属于哪个产生式右部的首符集而决定选择相应产个产生式右部的首符集而决定选择相应产生式进行推导。生式进行推导。 7文法文法G3S: S aA | d A bAS | 输入串输入串W=abd。自顶向下的推导过程为自顶向下的推导过程为: S aA abAS abS abd相应的语法树为：相应的语法树为：S Sa aA Ab bA AS S d d82.1.12.1.1 计算计算First(X)First(X)集集对一文法符号对一文法符号X X计算计算First(X)First(X)若若X X V VT T, ,First(X)=XFirst(X)=X若若X X V VN N, ,First(X)=
5、a| XFirst(X)=a| Xaa P,aP,a V VT T 若若X X V VN N, ,且有产生式且有产生式X X, ,则则 First(X)First(X)若若X X V VN N, ,有产生式有产生式X XY Y1 1Y Y2 2YYn n，对于所有前对于所有前k k个字符个字符Y Ym m都满足都满足Y Ym m V VN N，(m=1,k;1(m=1,k;1 kn)k可能使用此产生式规则的当前token集合不包括可包括#183 3 递归下降法递归下降法( (RECURSIVE-DESCENT PARSING)RECURSIVE-DESCENT PARSING)思想思想实例实例
6、算法算法193.13.1 递归下降法思想递归下降法思想对对每个非终极符每个非终极符按其产生式结构产生相应语按其产生式结构产生相应语法分析子程序。法分析子程序。遇到终极符执行匹配命令遇到终极符执行匹配命令( (读入下一读入下一token)token)；遇到非终极符则执行调用命令；遇到非终极符则执行调用命令；文法递归相应子程序也递归，文法递归相应子程序也递归，所以称这种方法为所以称这种方法为递归子程序方法递归子程序方法/ /递归下降法递归下降法203.2 3.2 递归下降法实例递归下降法实例规则：规则：StmStm whilewhile ExpExp dodo StmStm对应产生式右部的语法分析
7、程序部分如下：对应产生式右部的语法分析程序部分如下：begin Match($while)； Exp； Match($do)； Stm； end 21while xy do if xz then x:= x+y else x:= y Begin Match($while); Exp; Match($do); Stm End递归下降法实例续递归下降法实例续223.33.3 算法算法当产生式形如当产生式形如: :A A1 1| | 2 2| n n, ,则按下面的方法编写子程则按下面的方法编写子程序序A A： procedure A( ) begin if token Predict(A1) th
8、en ( 1) else if token Predict(A2) then ( 2) else if token Predict(An) then ( n) else err( ) end其中其中对对 i i=X=X1 1X X2 2XXn n， ( ( i i)=)= (X1); (X2); (Xn);如果如果X X V VN N， (X)= X(); 如果如果X X V VT T， (X)= Match(X); /if(token=X)ReadToken();/if(token=X)ReadToken();如果如果X= X= ， ( ( ) = skip() = skip(空空语语句句)
9、 ). .23假设有文法假设有文法Z a B aB b B | c则相应的递归子程序可如下：则相应的递归子程序可如下：void Z( ) if(token=a)Match(a); B( ); Match(a) ; else err( );void B ( )if(token=b)Match(b); B( );else if(token =c) Match(c); else err( );主程序：主程序： ReadToken(); Z( )244 4 LL(1)LL(1)分析方法分析方法概述概述LL(1)LL(1)分析器分析器LLLL驱动程序算法驱动程序算法LL(1)LL(1)算法执行实例算法执
10、行实例254.14.1 LLLL分析方法概述分析方法概述LL(1)LL(1)是是LL(k)LL(k)的特例的特例, ,其中的其中的k k则表示向前则表示向前看看k k个符号个符号。 LL(1)LL(1)方法和递归下降法属于同一级别的自方法和递归下降法属于同一级别的自顶向下分析法，但有一些顶向下分析法，但有一些区别区别。 递递归归下下降降法法对对每每个个非非终终极极符符产产生生子子程程序序，而而LL(1)LL(1)方法则产生方法则产生LLLL分析表；分析表；递递归归下下降降法法能能判判断断每每个个产产生生式式的的结结束束，而而LL(1)LL(1)方法则不能；方法则不能；递递归归下下降降法法分分析
11、析法法不不用用符符号号栈栈，而而LL(1)LL(1)方方法法则则用符号栈。用符号栈。264.1.14.1.1 LL(1)LL(1)分析法的适用条件分析法的适用条件对对于于任任一一非非终终极极符符A A，其其任任意意两两个个产产生生式式A A和和A A，都要满足下面条件：都要满足下面条件： Predict(APredict(A) ) Predict(APredict(A)=)= 满足这一条件的文法称为满足这一条件的文法称为LL(1)LL(1)文法。文法。可用可用LLLL（1 1）分析法进行语法分析。）分析法进行语法分析。 274.1.24.1.2 实例实例文法文法GA: GA: A A a B
12、c a B c11B B d d 22| b B| b B33输入串：输入串：abbdcabbdc分析过程：分析过程：( (A,abbdc)A,abbdc)1 1(aBc,abbdc) (aBc,abbdc) (Bc,bbdc) (Bc,bbdc) 3 3(bBc,bbdc) (bBc,bbdc) (Bc,bdc) (Bc,bdc) 3 3 (bBc,bdc) (bBc,bdc) (Bc,dc) (Bc,dc) 2 2 (dc,dc) (dc,dc) (c,c) (c,c) ( , )( , )284.1.34.1.3 LL(1)LL(1)分析的动作分析的动作替换：替换：当当X X1 1 V
13、VN N时选相应候选式时选相应候选式 去替换去替换X X1 1。匹配：匹配：当当X X1 1 V VT T时它与时它与Y Y1 1进行匹配，其结果进行匹配，其结果可能成功，也可能失败，如果成功则去掉可能成功，也可能失败，如果成功则去掉X X1 1和和Y Y1 1，否则报错。否则报错。接受：接受：当格局为（空，空）时报分析成功。当格局为（空，空）时报分析成功。报错：报错：出错后，停止分析。出错后，停止分析。294.24.2 LL(1)LL(1)分析器分析器组成组成LL(1)LL(1)语法分析表，即语法分析表，即LL(1)LL(1)矩阵矩阵LL(1)LL(1)语法分析驱动程序语法分析驱动程序304
14、.2.14.2.1 LL(1)LL(1)分析表的构造分析表的构造T T：V VN N V VT T P P Error Error A A若若t t Predict(APredict(A) )T(A,t)=T(A,t)=ErrorError否则否则 其中其中P P表示所有产生式的集合表示所有产生式的集合 314.2.24.2.2 LL(1)LL(1)分析的驱动器分析的驱动器32StackInputa栈为空情形的处理栈为空情形的处理X VT情形的处理情形的处理X VN情形的处理情形的处理XLL1分析表分析表4.34.3 LLLL驱动算法驱动算法1.1.初始化：初始化： Stack := #Sta
15、ck := #；Push(S)Push(S)；2.2.读下一个输入符：读下一个输入符： Read(a)Read(a)；3.3.若当前格局是若当前格局是( (#, # )#, # )，则成功结束；否则转下；则成功结束；否则转下；4.4.设当前格局为（设当前格局为（ X., a.)X., a.)，则则若若 X X V VT T & X=a& X=a则则 Pop(1)Pop(1)；Read(a)Read(a)；goto goto 3 3 若若 X X V VT T & X & X a a 则则 ErrorError； 若若 X X V VN N，则：则：if T(X,a)=XY1Y2 Ynthen
16、Pop(1)；Push(Yn,.,Y1)；goto 3else Error334.44.4 LLLL分析实例分析实例文法文法G:G: 34 E E T E T E11 E E + T E + T E22 | | 33 T T F T F T44 T T * F T * F T55 | | 66 F F id id77 | ( E ) | ( E )88符号串符号串 i + i * i # 的的LL(1)分析过程：分析过程：Predict(1Predict(1) = ) = first(TE)first(TE) = = id , ( id , ( Predict(2) = Predict(2)
17、= first(+TE)first(+TE) = = + + Predict(3) = Predict(3) = follow(E)follow(E) = = ) , # ) , # Predict(4) = Predict(4) = first(FT)first(FT) = = id , ( id , ( Predict(5) = Predict(5) = first(*FT)first(*FT) = = * * Predict(6) = Predict(6) = follow(T)follow(T) = = + , ) , # + , ) , # Predict(7) = Predict(
18、7) = first(id)first(id) = = id id Predict(8) = Predict(8) = first(E)first(E) = = ( ( 35分析栈分析栈S S 输入流输入流T T 矩阵元素矩阵元素 E # i + i * i # LL E ,i = 1 T E# i + i * i # LL T ,i = 4 F T E# i + i * i # LL F ,i = 7 i T E # i + i * i # Match T E# + i * i # LL T,+ = 6 E# +i * i # LL E,+ = 2 +T E# +i * i # Match
19、T E# i * i # LL T,i =4 F T E# i * i # LL F,i = 7 i T E# i * i # Match T E# * i # LL T,* = 5 *FT E# * i # Match FT E# i # LLF,i = 7 iT E# i # Match T E# # LLT,# = 6 E# # LLE, # = 3# # ok36非非LL(1)LL(1)文法的处理文法的处理BLBL语言语言 i i j j | i | i j j 0 0 不是不是LLLL文法文法条件语句的产生式是无法变换成条件语句的产生式是无法变换成LL(1)LL(1)型产型产生式的。
20、生式的。S Sif id then S ELSEif id then S ELSEELSEELSEelse S|else S| 处理方案：修改语法分析的驱动程序处理方案：修改语法分析的驱动程序指定优先级指定优先级指定产生式规则指定产生式规则37练习练习课后题课后题1 1：设有如下文法：设有如下文法GSGSS SaABbcdaABbcd1 1| | 2 2A AASdASd3 3| | 4 4B BSAhSAh5 5|eC|eC6 6| | 7 7C CSfSf8 8|Cg|Cg9 9| | 10101.1.求每个产生式的求每个产生式的PredictPredict集集2.2.该文法是否为该文法是
21、否为LL(1)LL(1)文法，为什么？文法，为什么？38FirstFirst集集串可能推导出的首个终串可能推导出的首个终极符极符( (可能为空串可能为空串) )First(S)=a,First(S)=a, First(A)=a,First(A)=a, ,d,dFirst(B)=a,First(B)=a, ,d,h,e,d,h,eFirst(C)=a,First(C)=a, ,f,g,f,gFirst(aABbcd)=aFirst(aABbcd)=aFirst(ASd)=a,dFirst(ASd)=a,dFirst(SAh)=a,d,hFirst(SAh)=a,d,hFirst(eC)=eFir
22、st(eC)=eFirst(Sf)=a,fFirst(Sf)=a,fFirst(Cg)=a,f,gFirst(Cg)=a,f,g39FollowFollow集集非终极符后可能出现的首个终极符非终极符后可能出现的首个终极符( (不为空不为空) )Follow(S)=a,d,f,#Follow(S)=a,d,f,#Follow(A)=a,d,hFollow(A)=a,d,hFollow(B)=bFollow(B)=bFollow(C)=g,bFollow(C)=g,b40PredictPredict集集产生式所推导出的句型产生式所推导出的句型首个终极符首个终极符( (不为空不为空) )Predic
23、t(1)=aPredict(1)=aPredict(2)=a,d,f,#Predict(2)=a,d,f,#Predict(3)=a,dPredict(3)=a,dPredict(4)=a,d,e,hPredict(4)=a,d,e,hPredict(5)=a,d,hPredict(5)=a,d,hPredict(6)=ePredict(6)=ePredict(7)=bPredict(7)=bPredict(8)=a,fPredict(8)=a,fPredict(9)=a,f,gPredict(9)=a,f,gPredict(10)=g,bPredict(10)=g,b(2)(2)由于不同产生
24、式规则由于不同产生式规则的的PredictPredict集有交集，集有交集，所以该文法不是所以该文法不是LL(1)LL(1)文法。文法。41课后题课后题2 2判断下列文法那些是判断下列文法那些是LL(1)LL(1)文法文法1.1.S S(SS|(SS| SS)|)| 2.2.S S(S)S|(S)S| 3.3.S SS(S)S|S(S)S| 4.4.S S(S|S(S|SS S(S)|(S)| Predict(SPredict(S(SS)=(SS)=(Predict(SPredict(S)=),#)=),#Predict(SPredict(S) )=)=)Predict(SPredict(S)
25、=),#)=),#Predict(SPredict(S(S)S)=(S)S)=(Predict(SPredict(S)=),#)=),#Predict(SPredict(SS S(S)S)=(S)S)=(Predict(SPredict(S)=),(,#)=),(,#Predict(SPredict(S(S)=(S)=(Predict(SPredict(SSS)=()=(Predict(SPredict(S(S)=(S)=(Predict(SPredict(S)=),#)=),#42课后题课后题3 3已知文法已知文法GEGEE EE+T|TE+T|TT TT*F|FT*F|FF Fi|(E)i
26、|(E)按递归下降法构造此文按递归下降法构造此文法的语法分析程序法的语法分析程序步骤：步骤：1.1.判断文法类型判断文法类型求求PredictPredict集集文法变换文法变换消除左递归消除左递归提取公共前缀提取公共前缀2.2.设计程序设计程序43文法变换文法变换消除左递归消除左递归对直接左递归形如：对直接左递归形如：A AA A | | 消除左递归：消除左递归：A AA A A AA A | | E EE+T|TE+T|TE ETETEE E+TE+TE| | T TT*F|FT*F|FT TFTFTT T*F*FT T| | 44文法变换文法变换(2)(2)提取公共前缀提取公共前缀对于产生
27、式：对于产生式：A A1 1| |2 2|n n| | ，其其中中 为为不不以以 开开头头的的字字符符串串，引引进进非非终终极极符符AA，使产生式替换为：，使产生式替换为：A A A A | | A A 1 1| | 2 2 | | n nEXPEXPEXP+EXP|EXP*EXP|EXP+EXP|EXP*EXP|(EXP)|number(EXP)|numberEXPEXPEX|(EXP)|numberEX|(EXP)|numberEXEX +EXP|*EXP+EXP|*EXP45课后题课后题4 4构造构造LL(1)LL(1)文法文法G G以识别以识别语言语言L L，其中，其中 =0,1=0,
28、1L=x|xL=x|x为不包括两个相为不包括两个相邻的邻的1 1的非空串的非空串 S S0A0A11|1B|1B22A A0A0A33|1B|1B44| | 55B B0A0A66| | 77P(1)=0=P(3)=P(6)P(1)=0=P(3)=P(6)P(2)=1=P(4)P(2)=1=P(4)P(5)=#=P(7)P(5)=#=P(7)46SAB11000AB课后题课后题5 5已知文法已知文法GAGAA AaABe|aaABe|aB BBb|dBb|d1.1.求求G G的的LL(1)LL(1)等价文法等价文法G GAA2.2.构造构造GAGA的的LL(1)LL(1)分析表并给出输入串分析
29、表并给出输入串aade#aade#的分析过程。的分析过程。A AaABe|aaABe|a消除公共前缀得消除公共前缀得A AaAaA11AAABeABe22| | 33B BBb|dBb|d消除左递归得消除左递归得B BdBdB44BBb bBB55| | 6647(A#,aade#)(A#,aade#)1 1( (aAaA#,aade#)#,aade#)m m(A(A#,ade#)#,ade#)2 2(ABe#,ade#)(ABe#,ade#)1 1(aA(aABe#,ade#)Be#,ade#)m m(A(ABe#,de#)Be#,de#)3 3(Be#,de#)(Be#,de#)4 4(dB(dBe#,de#)e#,de#)m m(B(Be#,e#)e#,e#)6 6(e#,e#)(e#,e#)m m(#,#)(#,#)! !课后题课后题5 5（2 2）P(1)=aP(1)=aP(2)=aP(2)=aP(3)=d,#P(3)=d,#P(4)=dP(4)=dP(5)=bP(5)=bP(6)=eP(6)=ea ab bd de e# #A A1 1A A2 23 33 3B B4 4B B5 56 648
