编译原理(王晓斌)编译第九章.ppt
第九章 自上而下的语法分析,第一节 引言一.语法分析的功能,符号串,（二元式流）,正确句子的语法树,报告语法错误,语法分析程序,二.语法分析方法的分类语法分析:自上而下(自顶而下)自下而上(自底而上)自上而下语法分析法:或从开始符号出发,找最左推导;或从根开始,构造推导树。自下而上语法分析法:从输入串开始,归约,直至文法开始符。,第二节 回溯分析法一.一个实例 SxAy Aaba输入串为xay,说明分析过程,二.存在的问题(1)回溯公共左因子的存在 A1|2(2)左递归 AA 或 AA(3)产生式也会引起回溯 SaAS Sb AbAS A,+,第三节 递归下降分析法一.提取公共左因子 A1|2|.|n|改写为:AB|B 1|2|.|n,例：SxAy Aaba 改写为：,SxAy AaB Bb,二.左递归的消除(1)直接左递归的消除 PP改写为:PP PP一般地 AA1|A2|Am|1|2|n（i，j不以A开头）改写为:A1P 2P.nP P 1P2P.mP,(2)间接左递归的消除 PP(a)将文法G的所有非终结符按任一给定的顺序排列,设为A1,A2,An;,+,(b)消除可能的左递归;for i:=1 to n do begin for j:=1 to i-1 do 把一个形如AiAj的产生式改写为 Ai1|2|k 其中Aj1|2|k是Aj的所有产生式;消除Ai产生式的直接左递归 end(c)化简,以 SQcc QRbb RSaa为例,按S,Q,R排列,或R,Q,S排列,按S、Q、R排列,代入后 SQcc QRbb R Rbcabcacaa,SQccQRbbRSaa,消除R中的直接左递归 R bcaRcaRaR R bcaR,文法产生的语言:(bca|ca|a)(bca)*bc|bc|c,按R、Q、S排列,代入后 RSaa QSababb SSabcabc bcc,SQccQRbbRSaa,消除S中的直接左递归 SabcSbcScS SabcS,文法产生的语言:(abc|bc|c)(abc)*,三.递归下降分析器的构造 当改造文法为无公共左因子,无左递归时,让每个非终结符对应一个过程;该过程对相应的非终结符产生式的右部短语进行语法分析,例:G(E)EE+TT TT*FF F(E)i,消除左递归:,ETEE+TE,TFTT*FT,F(E)i,过程match:匹配单词符号,并读入下一符号变量lookahead:即将处理但尚未处理的符号procedure match(t:token);begin if lookahead=t then lookahead=nexttoken else errorend;,procedure E;begin T;Eend;procedure T;begin F;Tend;,ETETFT,procedure E;if lookahead=+then begin match(+);T;E end;procedure T;if lookahead=*then begin match(*);F;T end;,E+TET*FT,procedure F;if lookahead=i then match(i)else if lookahead=(then begin match();E;if lookahead=)then match()else error end else error;,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,例:实数可定义为 decimal signinteger.digitexponent exponentEsigninteger integerdigitdigit sign+-,(2)左递归的消除 pxy.zpv改写成:p(xy.z)v,(3)文法的转换图表示产生式右端可用转换图表示。如:ET+T 表示成,0,1,2,T,+,(4)递归下降分析器的改进procedure E;begin T;while lookahead=+do begin match(+);T end end;,procedure T;begin F;while lookahead=*do begin match(*);F end end;,procedure F;if lookahead=i then match(i)else if lookahead=(then begin match();E;if lookahead=)then match()else error end else error；,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,a VT#内容: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,分三种情形:Xa XY XY1Y2Yk,例子：X Y1Y2A Y1 y1 Y2 y2 A aFIRST(Y1)=y1,FIRST(Y2)=y2,FIRST(A)=a FIRST(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)ETE E+TE TFT T*FT F(E)i,E,E,T,T,F,FIRST,FOLLOW,(i,(i,(i,+,*,)#,)#,+)#,+)#,*+)#,ETEE+TETFTT*FT F(E)i,三.预测分析表的构造1.构造算法 对每个产生式A对aFIRST(),将A记入MA,a中;若FIRST(),对bFOLLOW(A),将A记入MA,b中;凡未被定义的MA,a项中标以出错标志。,如:G(E)ETE E+TE TFT T*FT F(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)ETE E+TE TFT T*FT F(E)i,2.预测分析表的改进MA,a中只记产生式右部;对=x1x2.xn,在M,a中记xn xn-1.x1;当xn xn-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)文法可以根据语义进行处理。,例：下述文法具有二义性 S i C t Si C t S e Sa C b,提取公共左因子后：S i C t S Sa S e S C b,FIRST(S)=i,aFIRST(S)=e,FIRST(C)=bFOLLOW(S)=FOLLOW(S)=FIRST(S)-#=e,#FOLLOW(C)=t,S i C t S Sa S e S C b,FIRST(eS)FOLLOW(S)=e,预测分析表,S,S,C,a,b,e,i,t,#,Sa,Si C t S S,Se SS,S,Cb,最近匹配原则令MS,e仅含一个产生式Se S,S i C t S Sa S e S C b,第九章习题(必做题):9-2、9-3、9-5、9-6,
