編譯原理編譯第九章課件

1、二. 語法分析方法的分類語法分析: 自上而下(自頂而下) 自下而上(自底而上)自上而下語法分析法:或從開始符號(hào)出發(fā),找最左推導(dǎo);或從根開始,構(gòu)造推導(dǎo)樹。自下而上語法分析法:從輸入串開始,歸約,直至文法開始符。 牛牛文庫文檔分享第1頁，共49頁。第二節(jié) 回溯分析法一.一個(gè)實(shí)例 SxAy Aaba輸入串為xay,說明分析過程 牛牛文庫文檔分享第2頁，共49頁。Sx A ySx A ya bSx A ya 牛牛文庫文檔分享第3頁，共49頁。 二. 存在的問題(1)回溯公共左因子的存在 A1| 2(2)左遞歸 AA 或 AA (3)產(chǎn)生式也會(huì)引起回溯 SaAS Sb AbAS A + 牛牛文庫文檔分享

2、第4頁，共49頁。第三節(jié) 遞歸下降分析法一. 提取公共左因子 A1| 2| . |n| 改寫為:AB| B 1| 2| . |n 牛牛文庫文檔分享第5頁，共49頁。例： SxAy Aaba 改寫為： SxAy AaB Bb 牛牛文庫文檔分享第6頁，共49頁。二. 左遞歸的消除(1)直接左遞歸的消除 PP改寫為:PP PP一般地 AA1|A2|Am|1|2|n （i，j不以A開頭）改寫為:A1P 2P. . . nP P 1P2P. . .mP 牛牛文庫文檔分享第7頁，共49頁。(2)間接左遞歸的消除 PP(a)將文法G的所有非終結(jié)符按任一給定的順序排列,設(shè)為A1,A2,An;+ 牛牛文庫文檔分

3、享第8頁，共49頁。(b)消除可能的左遞歸; for i:=1 to n do begin for j:=1 to i-1 do 把一個(gè)形如AiAj的產(chǎn)生式改寫為 Ai1|2|k 其中Aj1|2|k是Aj的所有產(chǎn)生式; 消除Ai產(chǎn)生式的直接左遞歸 end(c)化簡 牛牛文庫文檔分享第9頁，共49頁。以 SQcc QRbb RSaa為例,按S,Q,R排列,或R,Q,S排列 牛牛文庫文檔分享第10頁，共49頁。按S、Q、R排列, 代入后 SQcc QRbb R RbcabcacaaSQccQRbbRSaa消除R中的直接左遞歸 R bcaRcaRaR R bcaR文法產(chǎn)生的語言:(bca|ca|a)

4、(bca)*bc|bc|c 牛牛文庫文檔分享第11頁，共49頁。按R、Q、S排列, 代入后 RSaa QSababb SSabcabc bcc SQccQRbbRSaa消除S中的直接左遞歸 SabcSbcScS SabcS文法產(chǎn)生的語言:(abc|bc|c)(abc)* 牛牛文庫文檔分享第12頁，共49頁。三. 遞歸下降分析器的構(gòu)造 當(dāng)改造文法為無公共左因子,無左遞歸時(shí),讓每個(gè)非終結(jié)符對(duì)應(yīng)一個(gè)過程;該過程對(duì)相應(yīng)的非終結(jié)符產(chǎn)生式的右部短語進(jìn)行語法分析 牛牛文庫文檔分享第13頁，共49頁。例: G(E) EE+TT TT*FF F(E) i消除左遞歸:ETEE+TETFTT*FTF(E)i 牛牛文

5、庫文檔分享第14頁，共49頁。過程match:匹配單詞符號(hào),并讀入下一符號(hào)變量lookahead:即將處理但尚未處理的符號(hào)procedure match(t:token);begin if lookahead=t then lookahead=nexttoken else errorend; 牛牛文庫文檔分享第15頁，共49頁。procedure E;begin T; Eend;procedure T;begin F; Tend;ETETFT 牛牛文庫文檔分享第16頁，共49頁。procedure E; if lookahead=+ then begin match(+); T; E end;

6、procedure T; if lookahead=* then begin match(*); F; T end;E+TET*FT 牛牛文庫文檔分享第17頁，共49頁。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 牛牛文庫文檔分享第18頁，共49頁。ETFiiM(i)ETFiiM(i)i+i*i#的遞歸下降分析過程+M(+)*#*TM(*)iF#TEM

7、()#M(i)M()ETEE+TETFTT*FTF(E)iT+M() 牛牛文庫文檔分享第19頁，共49頁。四. 擴(kuò)充的BNF(1)表示形式:用花括號(hào)表示閉包運(yùn)算* ;用 表示可任意重復(fù)0次至n次 =0=;用方括號(hào)表示 ,即表示的出現(xiàn)可有可無(等價(jià)于)n00010 牛牛文庫文檔分享第20頁，共49頁。例: 實(shí)數(shù)可定義為 decimal signinteger.digitexponent exponentEsigninteger integerdigitdigit sign+- 牛牛文庫文檔分享第21頁，共49頁。(2)左遞歸的消除 pxy. .zpv改寫成: p(xy. . .z)v 牛牛文庫文

8、檔分享第22頁，共49頁。(3)文法的轉(zhuǎn)換圖表示產(chǎn)生式右端可用轉(zhuǎn)換圖表示。如: ET+T 表示成012T+ 牛牛文庫文檔分享第23頁，共49頁。(4)遞歸下降分析器的改進(jìn)procedure E;begin T; while lookahead=+ do begin match(+); T end end; 牛牛文庫文檔分享第24頁，共49頁。procedure T;begin F; while lookahead=* do begin match(*); F end end; 牛牛文庫文檔分享第25頁，共49頁。procedure F; if lookahead=i then match(i)

9、 else if lookahead=( then begin match(); E; if lookahead=) then match() else error end else error； 牛牛文庫文檔分享第26頁，共49頁。i+i*i#的遞歸下降分析過程ETFiiM(i)TFiM(i)+iM(+)*FM(i)i#M(*)ET+TTF*FF(E)i 牛牛文庫文檔分享第27頁，共49頁。第四節(jié) 預(yù)測分析法 一. 預(yù)測分析過程1. 預(yù)測分析表 形式:MA,a矩陣, AVN,a VT# 內(nèi)容:A或出錯(cuò)標(biāo)志(空白) 牛牛文庫文檔分享第28頁，共49頁。預(yù)測分析表EETTFi+*()#ETEET

10、EE+TETFTTFTT*FTFiF(E)EETTT 牛牛文庫文檔分享第29頁，共49頁。2. 分析方法 初始時(shí),#和開始符入棧,輸入指針指向第一個(gè)符號(hào),然后根據(jù)下推棧棧頂符x和當(dāng)前輸入符a進(jìn)行工作:x=a=#, 成功x=a#, 匹配 xVN, 查表 牛牛文庫文檔分享第30頁，共49頁。例: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 牛牛文庫文檔分享第31頁，共49頁。#ETF i*i#ETi#ET#ETF*#ETi#ETF

11、#ET#E *i# i# *i# i# # # #T*FT結(jié)束FiT i*i#FiE 牛牛文庫文檔分享第32頁，共49頁。二. FIRST集和FOLLOW集1FIRST集(1)定義:對(duì)(VTVN)*,有 FIRST（）a|a. . . , aVT 若,則FIRST()(2)對(duì)文法符號(hào)XVTVN(3)當(dāng)=X1X2Xn時(shí)* 牛牛文庫文檔分享第33頁，共49頁。XVT, 則FIRST(X)=X;XVN, 分三種情形: Xa XY XY1Y2Yk 牛牛文庫文檔分享第34頁，共49頁。例子：X Y1Y2A Y1 y1 Y2 y2 A aFIRST(Y1)=y1, FIRST(Y2)=y2, FIRST(

12、A)=a FIRST(X)=y1, y2, a 牛牛文庫文檔分享第35頁，共49頁。 2. FOLLOW集(1)定義:對(duì)AVN ,有 FOLLOW(A)=aS . . .Aa. . . ,aVT 若S .A, 則#FOLLOW(A),其中S為開始符號(hào)* 牛牛文庫文檔分享第36頁，共49頁。(2)求法# FOLLOW(S)AB: 將FIRST()-加入FOLLOW(B)AB或者AB且: 將FOLLOW(A)加入FOLLOW(B)注意: 求FOLLOW(B)實(shí)際上是考察B在產(chǎn)生式右端的每一次出現(xiàn)* 牛牛文庫文檔分享第37頁，共49頁。例: G(E) ETE E+TE TFT T*FT F(E)i

13、牛牛文庫文檔分享第38頁，共49頁。EETTFFIRSTFOLLOW( i( i( i+ * ) #) #+ ) #+ ) #* + ) #ETEE+TETFTT*FT F(E)i 牛牛文庫文檔分享第39頁，共49頁。三. 預(yù)測分析表的構(gòu)造1. 構(gòu)造算法 對(duì)每個(gè)產(chǎn)生式A對(duì)aFIRST(),將A記入MA,a中;若FIRST(),對(duì)bFOLLOW(A), 將A記入MA,b中;凡未被定義的MA,a項(xiàng)中標(biāo)以出錯(cuò)標(biāo)志。 牛牛文庫文檔分享第40頁，共49頁。如: G(E) ETE E+TE TFT T*FT F(E)iEETTFFIRSTFOLLOW( i( i( i+ * ) #) #+ ) #+ )

14、#* + ) # 牛牛文庫文檔分享第41頁，共49頁。預(yù)測分析表EETTFi+*()#ETEETEE+TETFTTFTT*FTFiF(E)EETTTG(E) ETE E+TE TFT T*FT F(E)i 牛牛文庫文檔分享第42頁，共49頁。2. 預(yù)測分析表的改進(jìn)MA,a中只記產(chǎn)生式右部;對(duì)=x1x2. . .xn, 在M,a中記xn xn-1. x1;當(dāng)xn xn-1. x1的x1VT時(shí), x1必為a, x1無須入棧,只移動(dòng)輸入指針。 牛牛文庫文檔分享第43頁，共49頁。四. LL(1)文法 設(shè)上下文無關(guān)文法G的產(chǎn)生式形如A1|2|n, 當(dāng)G滿足下述條件時(shí)則稱為LL(1)文法:FIRST(i

15、) FIRST(j)=, ij,i,j=1,2,. . .,n若i,則FIRST(j) FOLLOW(A)=, j=1,2,. . .,n且ji。 于是,在自頂向下分析時(shí),可根據(jù)當(dāng)前輸入符號(hào)a選擇aFIRST(i)的Ai。* 牛牛文庫文檔分享第44頁，共49頁。五. 非LL(1)文法的處理（1）并非任何文法G都可以改寫成LL(1)文法；（2）對(duì)非LL(1)文法可以根據(jù)語義進(jìn)行處理。 牛牛文庫文檔分享第45頁，共49頁。例：下述文法具有二義性 S i C t Si C t S e Sa C b提取公共左因子后： S i C t S Sa S e S C b 牛牛文庫文檔分享第46頁，共49頁。FIRST(S)=i, aFIRST(S)=e, FIRST(C)=bFOLLOW(S)=FOL