編譯原理編譯第九章

1、精選ppt第九章 自上而下的語法分析第一節(jié) 引言一. 語法分析的功能符號串（二元式流）正確句子的語法樹報告語法錯誤語法分析程序精選ppt二. 語法分析方法的分類u語法分析: 自上而下(自頂而下) 自下而上(自底而上)u自上而下語法分析法:或從開始符號出發(fā),找最左推導(dǎo);或從根開始,構(gòu)造推導(dǎo)樹。u自下而上語法分析法:從輸入串開始,歸約,直至文法開始符。精選ppt第二節(jié) 回溯分析法一.一個實例 SxAy Aaba輸入串為xay,說明分析過程精選pptSx A ySx A ya bSx A ya精選ppt 二. 存在的問題(1)回溯公共左因子的存在 A1| 2(2)左遞歸 AA 或 AA (3)產(chǎn)生式

2、也會引起回溯 SaAS Sb AbAS A +精選ppt第三節(jié) 遞歸下降分析法一. 提取公共左因子 A1| 2| . |n| 改寫為:AB| B 1| 2| . |n 精選ppt例： SxAy Aaba 改寫為： SxAy AaB Bb精選ppt二. 左遞歸的消除(1)直接左遞歸的消除 PP改寫為:PP PP一般地 AA1|A2|Am|1|2|n （i，j不以A開頭）改寫為:A1P 2P. . . nP P 1P2P. . .mP精選ppt(2)間接左遞歸的消除 PP(a)將文法G的所有非終結(jié)符按任一給定的順序排列,設(shè)為A1,A2,An;+精選ppt(b)消除可能的左遞歸; for i:=1

3、to n do begin for j:=1 to i-1 do 把一個形如AiAj的產(chǎn)生式改寫為 Ai1|2|k 其中Aj1|2|k是Aj的所有產(chǎn)生式; 消除Ai產(chǎn)生式的直接左遞歸 end(c)化簡精選ppt以 SQcc QRbb RSaa為例,按S,Q,R排列,或R,Q,S排列精選pptu按S、Q、R排列, 代入后 SQcc QRbb R RbcabcacaaSQccQRbbRSaau消除R中的直接左遞歸 R bcaRcaRaR R bcaRu文法產(chǎn)生的語言:(bca|ca|a)(bca)*bc|bc|c精選pptu按R、Q、S排列, 代入后 RSaa QSababb SSabcabc b

4、cc SQccQRbbRSaau消除S中的直接左遞歸 SabcSbcScS SabcSu文法產(chǎn)生的語言:(abc|bc|c)(abc)*精選ppt三. 遞歸下降分析器的構(gòu)造 當改造文法為無公共左因子,無左遞歸時,讓每個非終結(jié)符對應(yīng)一個過程;該過程對相應(yīng)的非終結(jié)符產(chǎn)生式的右部短語進行語法分析精選ppt例: G(E) EE+TT TT*FF F(E) i消除左遞歸:ETEE+TETFTT*FTF(E)i精選pptu過程match:匹配單詞符號,并讀入下一符號u變量lookahead:即將處理但尚未處理的符號procedure match(t:token);begin if lookahead=t

5、then lookahead=nexttoken else errorend;精選pptprocedure E;begin T; Eend;procedure T;begin F; Tend;ETETFT精選pptprocedure E; if lookahead=+ then begin match(+); T; E end;procedure T; if lookahead=* then begin match(*); F; T end;E+TET*FT精選pptprocedure F; if lookahead=i then match(i) else if lookahead=( th

6、en begin match(); E; if lookahead=) then match() else error end else error;F(E)i精選pptETFiiM(i)ETFiiM(i)i+i*i#的遞歸下降分析過程+M(+)*#*TM(*)iF#TEM()#M(i)M()ETEE+TETFTT*FTF(E)iT+M()精選ppt四. 擴充的BNF(1)表示形式:u用花括號表示閉包運算* ;u用 表示可任意重復(fù)0次至n次 =0=;u用方括號表示 ,即表示的出現(xiàn)可有可無(等價于)n00010精選ppt例: 實數(shù)可定義為 decimal signinteger.digitexp

7、onent exponentEsigninteger integerdigitdigit sign+-精選ppt(2)左遞歸的消除 pxy. .zpv改寫成: p(xy. . .z)v精選ppt(3)文法的轉(zhuǎn)換圖表示產(chǎn)生式右端可用轉(zhuǎn)換圖表示。如: ET+T 表示成012T+精選ppt(4)遞歸下降分析器的改進procedure E;begin T; while lookahead=+ do begin match(+); T end end;精選pptprocedure T;begin F; while lookahead=* do begin match(*); F end end;精選pp

8、tprocedure F; if lookahead=i then match(i) else if lookahead=( then begin match(); E; if lookahead=) then match() else error end else error；精選ppti+i*i#的遞歸下降分析過程ETFiiM(i)TFiM(i)+iM(+)*FM(i)i#M(*)ET+TTF*FF(E)i精選ppt第四節(jié) 預(yù)測分析法 一. 預(yù)測分析過程1. 預(yù)測分析表 形式:MA,a矩陣, AVN,a VT# 內(nèi)容:A或出錯標志(空白)精選ppt預(yù)測分析表EETTFi+*()#ETEET

9、EE+TETFTTFTT*FTFiF(E)EETTT精選ppt2. 分析方法 初始時,#和開始符入棧,輸入指針指向第一個符號,然后根據(jù)下推棧棧頂符x和當前輸入符a進行工作:x=a=#, 成功x=a#, 匹配 xVN, 查表精選ppt例: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#ETETFTTFTFiTE+TE精選ppt#ETF i*i#ETi#ET#ETF*#ETi#ETF#ET#E *i# i# *i# i# # # #T*FT結(jié)束FiT i*i#FiE

10、精選ppt二. FIRST集和FOLLOW集1FIRST集(1)定義:對(VTVN)*,有 FIRST（）a|a. . . , aVT 若,則FIRST()(2)對文法符號XVTVN(3)當=X1X2Xn時*精選pptuXVT, 則FIRST(X)=X;uXVN, 分三種情形: Xa XY XY1Y2Yk精選ppt例子：X Y1Y2A Y1 y1 Y2 y2 A aFIRST(Y1)=y1, FIRST(Y2)=y2, FIRST(A)=a FIRST(X)=y1, y2, a精選ppt 2. FOLLOW集(1)定義:對AVN ,有 FOLLOW(A)=aS . . .Aa. . . ,aV

11、T 若S .A, 則#FOLLOW(A),其中S為開始符號*精選ppt(2)求法u# FOLLOW(S)uAB: 將FIRST()-加入FOLLOW(B)uAB或者AB且: 將FOLLOW(A)加入FOLLOW(B)注意: 求FOLLOW(B)實際上是考察B在產(chǎn)生式右端的每一次出現(xiàn)*精選ppt例: G(E) ETE E+TE TFT T*FT F(E)i精選pptEETTFFIRSTFOLLOW( i( i( i+ * ) #) #+ ) #+ ) #* + ) #ETEE+TETFTT*FT F(E)i精選ppt三. 預(yù)測分析表的構(gòu)造1. 構(gòu)造算法 對每個產(chǎn)生式A對aFIRST(),將A記入

12、MA,a中;若FIRST(),對bFOLLOW(A), 將A記入MA,b中;凡未被定義的MA,a項中標以出錯標志。精選ppt如: G(E) ETE E+TE TFT T*FT F(E)iEETTFFIRSTFOLLOW( i( i( i+ * ) #) #+ ) #+ ) #* + ) #精選ppt預(yù)測分析表EETTFi+*()#ETEETEE+TETFTTFTT*FTFiF(E)EETTTG(E) ETE E+TE TFT T*FT F(E)i精選ppt2. 預(yù)測分析表的改進MA,a中只記產(chǎn)生式右部;對=x1x2. . .xn, 在M,a中記xn xn-1. x1;當xn xn-1. x1的

13、x1VT時, x1必為a, x1無須入棧,只移動輸入指針。精選ppt四. LL(1)文法 設(shè) 上 下 文 無 關(guān) 文 法 G 的 產(chǎn) 生 式 形 如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。 于是,在自頂向下分析時,可根據(jù)當前輸入符號a選擇aFIRST(i)的Ai。*精選ppt五. 非LL(1)文法的處理（1）并非任何文法G都可以改寫成LL(1)文法；（2）對非LL(1)文法可以根據(jù)語義進行處理。精選ppt例：下述文法具有二義性 S i C t Si C t S e Sa C b提取公共左因子后： S i C t S Sa S e S C b精選pptFIRST(S)=i, aFIRST(S)=e, FIRST