编译原理(王晓斌)编译第九章

第九章自上而下的语法分析,第一节引言一.语法分析的功能,符号串,（二元式流）,正确句子的语法树,报告语法错误,语法分析程序,二.语法分析方法的分类语法分析:自上而下(自顶而下)自下而上(自底而上)自上而下语法分析法:或从开始符号出发,找最左推导;或从根开始,构造推导树。自下而上语法分析法:从输入串开始,归约,直至文法开始符。,第二节回溯分析法一.一个实例SxAyAaba输入串为xay,说明分析过程,二.存在的问题(1)回溯公共左因子的存在A1|2(2)左递归AA或AA(3)产生式也会引起回溯SaASSbAbASA,+,第三节递归下降分析法一.提取公共左因子A1|2|.|n|改写为:AB|B1|2|.|n,例：SxAyAaba改写为：,SxAyAaBBb,二.左递归的消除(1)直接左递归的消除PP改写为:PPPP一般地AA1|A2|Am|1|2|n（i，j不以A开头）改写为:A1P2P.nPP1P2P.mP,(2)间接左递归的消除PP(a)将文法G的所有非终结符按任一给定的顺序排列,设为A1,A2,An;,+,(b)消除可能的左递归;fori:=1tondobeginforj:=1toi-1do把一个形如AiAj的产生式改写为Ai1|2|k其中Aj1|2|k是Aj的所有产生式;消除Ai产生式的直接左递归end(c)化简,以SQccQRbbRSaa为例,按S,Q,R排列,或R,Q,S排列,按S、Q、R排列,代入后SQccQRbbRRbcabcacaa,SQccQRbbRSaa,消除R中的直接左递归RbcaRcaRaRRbcaR,文法产生的语言:(bca|ca|a)(bca)*bc|bc|c,按R、Q、S排列,代入后RSaaQSababbSSabcabcbcc,SQccQRbbRSaa,消除S中的直接左递归SabcSbcScSSabcS,文法产生的语言:(abc|bc|c)(abc)*,三.递归下降分析器的构造当改造文法为无公共左因子,无左递归时,让每个非终结符对应一个过程;该过程对相应的非终结符产生式的右部短语进行语法分析,例:G(E)EE+TTTT*FFF(E)i,消除左递归:,ETEE+TE,TFTT*FT,F(E)i,过程match:匹配单词符号,并读入下一符号变量lookahead:即将处理但尚未处理的符号procedurematch(t:token);beginiflookahead=tthenlookahead=nexttokenelseerrorend;,procedureE;beginT;Eend;procedureT;beginF;Tend;,ETETFT,procedureE;iflookahead=+thenbeginmatch(+);T;Eend;procedureT;iflookahead=*thenbeginmatch(*);F;Tend;,E+TET*FT,procedureF;iflookahead=ithenmatch(i)elseiflookahead=(thenbeginmatch();E;iflookahead=)thenmatch()elseerrorendelseerror;,F(E)i,E,T,F,i,i,M(i),E,T,F,i,i,M(i),i+i*i#的递归下降分析过程,+,+,+,M(+),*,#,*,T,M(*),i,F,#,#,#,T,E,M(),#,#,#,#,M(i),M(),ETEE+TETFTT*FTF(E)i,T,+,+,M(),四.扩充的BNF(1)表示形式:用花括号表示闭包运算*;用表示可任意重复0次至n次=0=;用方括号表示,即表示的出现可有可无(等价于),n0,00,10,例:实数可定义为decimalsigninteger.digitexponentexponentEsignintegerintegerdigitdigitsign+-,(2)左递归的消除pxy.zpv改写成:p(xy.z)v,(3)文法的转换图表示产生式右端可用转换图表示。如:ET+T表示成,0,1,2,T,+,(4)递归下降分析器的改进procedureE;beginT;whilelookahead=+dobeginmatch(+);Tendend;,procedureT;beginF;whilelookahead=*dobeginmatch(*);Fendend;,procedureF;iflookahead=ithenmatch(i)elseiflookahead=(thenbeginmatch();E;iflookahead=)thenmatch()elseerrorendelseerror；,i+i*i#的递归下降分析过程,E,T,F,i,i,M(i),T,F,i,M(i),+,+,i,M(+),*,F,M(i),i,#,#,M(*),ET+TTF*FF(E)i,第四节预测分析法一.预测分析过程1.预测分析表形式:MA,a矩阵,AVN,aVT#内容:A或出错标志(空白),预测分析表,E,E,T,T,F,i,+,*,(,),#,ETE,ETE,E+TE,TFT,TFT,T*FT,Fi,F(E),E,E,T,T,T,2.分析方法初始时,#和开始符入栈,输入指针指向第一个符号,然后根据下推栈栈顶符x和当前输入符a进行工作:x=a=#,成功x=a#,匹配xVN,查表,例:i+i*i的分析过程,下推栈,输入串,查分析表,i+i*i#,#E,#ET,#ETF,#ET,#ETi,#E,#ET,#ET+,i+i*i#,+i*i#,i+i*i#,i+i*i#,+i*i#,+i*i#,i*i#,ETE,TFT,TFT,Fi,T,E+TE,#ETF,i*i#,#ETi,#ET,#ETF*,#ETi,#ETF,#ET,#,#E,*i#,i#,*i#,i#,#,#,#,T*FT,结束,Fi,T,i*i#,Fi,E,二.FIRST集和FOLLOW集1FIRST集(1)定义:对(VTVN)*,有FIRST（）a|a.,aVT若,则FIRST()(2)对文法符号XVTVN(3)当=X1X2Xn时,*,*,XVT,则FIRST(X)=X;XVN,分三种情形:XaXYXY1Y2Yk,例子：XY1Y2AY1y1Y2y2AaFIRST(Y1)=y1,FIRST(Y2)=y2,FIRST(A)=aFIRST(X)=y1,y2,a,2.FOLLOW集(1)定义:对AVN,有FOLLOW(A)=aS.Aa.,aVT若S.A,则#FOLLOW(A),其中S为开始符号,*,*,(2)求法#FOLLOW(S)AB:将FIRST()-加入FOLLOW(B)AB或者AB且:将FOLLOW(A)加入FOLLOW(B)注意:求FOLLOW(B)实际上是考察B在产生式右端的每一次出现,*,例:G(E)ETEE+TETFTT*FTF(E)i,E,E,T,T,F,FIRST,FOLLOW,(i,(i,(i,+,*,)#,)#,+)#,+)#,*+)#,ETEE+TETFTT*FTF(E)i,三.预测分析表的构造1.构造算法对每个产生式A对aFIRST(),将A记入MA,a中;若FIRST(),对bFOLLOW(A),将A记入MA,b中;凡未被定义的MA,a项中标以出错标志。,如:G(E)ETEE+TETFTT*FTF(E)i,E,E,T,T,F,FIRST,FOLLOW,(i,(i,(i,+,*,)#,)#,+)#,+)#,*+)#,预测分析表,E,E,T,T,F,i,+,*,(,),#,ETE,ETE,E+TE,TFT,TFT,T*FT,Fi,F(E),E,E,T,T,T,G(E)ETEE+TETFTT*FTF(E)i,2.预测分析表的改进MA,a中只记产生式右部;对=x1x2.xn,在M,a中记xnxn-1.x1;当xnxn-1.x1的x1VT时,x1必为a,x1无须入栈,只移动输入指针。,四.LL(1)文法设上下文无关文法G的产生式形如A1|2|n,当G满足下述条件时则称为LL(1)文法:FIRST(i)FIRST(j)=,ij,i,j=1,2,.,n若i,则FIRST(j)FOLLOW(A)=,j=1,2,.,n且ji。于是,在自顶向下分析时,可根据当前输入符号a选择aFIRST(i)的Ai。,*,五.非LL(1)文法的处理（1）并非任何文法G都可以改写成LL(1)文法；（2）对非LL(1)文法可以根据语义进行处理。,例：下述文法具有二义性SiCtSiCtSeSaCb,提取公共左因子后：SiCtSSaSeSCb,FIRST(S)=i,aFIRST(S)=e,FIRST(C