編譯原理語法分析從上至下.ppt_第1頁
編譯原理語法分析從上至下.ppt_第2頁
編譯原理語法分析從上至下.ppt_第3頁
編譯原理語法分析從上至下.ppt_第4頁
編譯原理語法分析從上至下.ppt_第5頁
已閱讀5頁,還剩27頁未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡介

1、1,編譯方法,中國人民大學(xué)信息學(xué)院 陳文萍,2,第四章 語法分析自上而下分析,4.1 語法分析器的功能 4.2 自上而下分析面臨的問題 4.3 LL(1) 分析法 4.4 遞歸下降分析程序構(gòu)造 4.5 預(yù)測分析程序 4.6 LL(1) 分析中的錯(cuò)誤處理,3,4.1 語法分析器的功能,語法分析器的地位 分類 自上而下分析 自下而上分析,詞法分析器,語法分析器,編譯程序后續(xù)部分,符號表,源程序,單詞符號,取下一個(gè)單詞符號,語法分析樹,4,4.2 自上而下分析,定義:也稱面向目標(biāo)的分析方法,從文法的開始符號出發(fā)企圖推導(dǎo)出與輸入的單詞串完全相匹配的句子。 主旨:對任何輸入串,試圖用一切可能的辦法,從文

2、法開始符號著手,自上而下地為輸入串構(gòu)造一棵語法樹。本質(zhì)上是一個(gè)試探過程,反復(fù)使用不同的產(chǎn)生式謀求匹配輸入串的過程。,5,自上而下分析的問題(1),左遞歸 例:例文法G0S: (1) SSa (2) Sb 分析baa是不是文法的句子 按照自上而下的分析思想,選用產(chǎn)生式(1)來推導(dǎo)SSa, 語法樹末端結(jié)點(diǎn)最左符號為非終結(jié)符,所以選用(1)繼續(xù) 推導(dǎo)SSaSaa 此時(shí)語法樹末端結(jié)點(diǎn)最左符號為非終結(jié)符,所以選用(1) 繼續(xù)推導(dǎo)SSaSSa SSSa 試圖用S匹配輸入串時(shí),出現(xiàn):在沒有識別任何輸入符號的情況下,又得重新要求S去進(jìn)行新的匹配,分析過程陷入無限循環(huán),6,自上而下分析的問題(2),回溯 例:G

3、S: SxAy, Aaba 若當(dāng)前輸入串為xay,首先構(gòu)造的推導(dǎo)SxAy 匹配 進(jìn)一步推導(dǎo)對A可選擇Aab替換,得SxAy xaby xay xaby 匹配 xa都已匹配,當(dāng)前面臨輸入符為y與b不能匹配,所以將輸入串指針退回到a,對A的替換重新選用下一個(gè)產(chǎn)生式Aa進(jìn)行試探, SxAy xay輸入串中當(dāng)前符a得到匹配,指針向前移動(dòng)到y(tǒng),與語法樹中y匹配,匹配成功。 由于相同左部的產(chǎn)生式的右部開始符號相同而引起回溯。,7,自上而下分析的問題(3),分析過程中,匹配成功可能是暫時(shí)的。 最終分析不成功,很難知道輸入串中出錯(cuò)的確切位置。 帶回溯,效率低,代價(jià)高,8,4.3 LL(1) 分析法,左遞歸的消

4、除 消除回溯 LL(1) 分析條件,9,直接左遞歸的消除,左遞歸:一個(gè)文法是含有左遞歸的,如果存在非終結(jié)符P, P = P 形如:P P|,其中不為 ,不以P打頭 消除直接左遞歸改寫為:P P,PP| 一般來說,若P P1|P2|Pm|1|2|n,i不為 ,i不以P打頭,消除直接左遞歸就把規(guī)則改寫為: P 1P|2P|nP P 1P|2P|mP| 例:E E+T|T,T T*F|F,F(xiàn) (E)| i 消除直接左遞歸后變?yōu)椋?E TEE +TE| T FTT *FT| F (E)|i,10,文法左遞歸的消除,消除一個(gè)文法左遞歸:對文法的要求 無回路( ) 不含以為右部的產(chǎn)生式 消除左遞歸算法:

5、(1)以某種順序?qū)⑽姆ǚ墙K結(jié)符排列P1 ,P2 Pn (2) for i:=1 to n do begin for j:=1 to i-1 do 用Pi-1r| 2r| k r替代形如Pi- Pjr的規(guī)則 其中Pj- 1| 2| k是關(guān)于Pj的全部產(chǎn)生式; 消除Pi規(guī)則的直接左遞歸; end (3)化簡由2得到的文法,11,左遞歸的消除,例,文法S Qc|c,QRb|b, RSa|a 1,非終結(jié)符排序?yàn)椋篠,Q,R 2,替換規(guī)則 對于S,無需替換,S Qc|c 對于Q,無需替換,Q Rb|b 關(guān)于R,替換為,R Rbca|bca|ca|a,消除直接左遞歸為 R bcaR|caR|aR,R bc

6、aR| 非終結(jié)符的順序不同,文法的形式可能不同,但都是等價(jià)的,12,消除回溯,不回溯,對文法的要求 設(shè)G是一個(gè)不含左遞歸的文法,對G的所有非終結(jié)符的每個(gè)候選,它的終結(jié)首符集FIRST()為 FIRST()=a| =* a,aVT,若 =* 則規(guī)定FIRST() 若非終結(jié)符A的所有候選首符集兩兩不相交,即A的任何兩個(gè)不同候選和,F(xiàn)IRST()FIRST()=,則可消除回溯 改造文法的方法:提左公因子 將產(chǎn)生式 1|n|1|m 變換為: B|1|m B 1|n,13,LL(1) 分析條件,例如:文法:E TE,E +TE| , T FT,T *FT| ,F(xiàn) (E)|i 輸入串i+i,語法分析樹 F

7、IRST(TE)=(,i FIRST(+TE)=+ FIRST(FT)=(,i FIRST(*FT)=* FIRST(E)=( FIRST(i)=i,E,T,E,i,T,E,+,T,F,F,T,i,14,LL(1) 分析條件,S是文法G的開始符號,對G的任何非終結(jié),定義 FOLLOW(A)=aS =* Aa且a VT , 若S =* A , 則#FOLLOW(A) 一個(gè)文法G是LL(1)的,當(dāng)且僅當(dāng)對于G的每一個(gè)非終結(jié)符的任何兩個(gè)不同產(chǎn)生式 ,下面的條件成立: 1.文法不含左遞歸。 2.FIRST()FIRST()=,也就是和推導(dǎo)不出以同一個(gè)終結(jié)符a為首的符號串;它們不應(yīng)該都能推出空字。 3.

8、假若 =* ,那么,F(xiàn)IRST()FOLLOW(A). 也就是, 若 =* .則所能推出的串的首符號不應(yīng)在FOLLOW(A)中。,15,LL(1) 分析條件,文法是LL(1)的 第一個(gè)L 從左到右掃描輸入串 第二個(gè)L 生成的是最左推導(dǎo) 1 向前看一個(gè)輸入符號,16,4.4 遞歸下降分析程序構(gòu)造,遞歸分析器:不帶回溯的自上而下的分析程序 例:文法:E TE,E +TE| , T FT,T *FT| ,F(xiàn) (E)|i 遞歸子程序?yàn)椋?PROCEDURE E; BEGIN T;E END;,PROCEDURE E; IF SYM=+ THEN BEGIN ADVANCE; T;E END;,17,4

9、.4 遞歸下降分析程序構(gòu)造,PROCEDURE T; BEGIN F;T END; PROCEDURE T; IF SYM=* THEN BEGIN ADVANCE; F;T END;,PROCEDURE F; IF SYM=i THEN ADVANCE ELSE IF SYM=( THEN BEGIN ADVANCE; E; IF SYM=) THEN ADVANCE ELSE ERROR END ELSE ERROR;,18,4.4 遞歸下降分析程序構(gòu)造,擴(kuò)充的巴科斯范式 用a表示閉包運(yùn)算a* 用 表示a可任意重復(fù)0次到n次, 用a表示 ,即a的出現(xiàn)可有可無 例如,文法 E T|E+T,T

10、 F|T*F,F(xiàn) (E)|I 可以表示成 E T+T,T F*F,F(xiàn) (E)|I PROCEDURE E; BEGIN T; WHILE SYM=+ DO BEGIN ADVANCE; T END END;,19,4.4 遞歸下降分析程序構(gòu)造,PROCEDURE F; IF SYM=* THEN ADVANCE ELSE IF SYM=( THEN BEGIN ADVANCE; E; IF SYM=) THEN ADVANCE ELSE ERROR END ELSE ERROR;,PROCEDURE T; BEGIN F; WHILE SYM=* DO BEGIN ADVANCE; F; EN

11、D END;,20,4.4 LL(1)分析器,LL(1)分析器的模型, a + b #,X Y Z . . #,LL(1)分析算法,LL(1)分析表M,輸入緩沖區(qū),分析棧,輸出,21,LL(1)分析器,分析要件 輸入緩沖區(qū):存放要分析的符號串,在串的末尾加符號#表示輸入結(jié)束。 預(yù)測分析表:看作矩陣,存放文法中非終結(jié)符A和終結(jié)符a的關(guān)系。矩陣元素MA,a 表示A對于輸入符號a所采用的候選。結(jié)束標(biāo)記符#作為一個(gè)終結(jié)符號。 棧:分析過程中,存放當(dāng)前句型中尚待分析的文法符號,包括終結(jié)符號和非終結(jié)符號。棧底用#標(biāo)記結(jié)束。初始化時(shí),把#和文法的開始符號放在棧頂。,22,LL(1)預(yù)測分析表,例:G E:

12、(1) E TE (2) E +TE (3) E T FT (5) T *FT (6) T (7) F (E) (8) F i,23,預(yù)測分析表的構(gòu)造,計(jì)算FIRST集合的方法 1.若XV,則FIRST(X)=X 2.若XVN,且有產(chǎn)生式Xa,則把a(bǔ)加入到FIRST(X)中;若X也是一條產(chǎn)生式,則把也加到FIRST(X)中. 3.若XY是一個(gè)產(chǎn)生式且YVN,則把FIRST(Y)中的所有非元素都加到FIRST(X)中;若X Y1Y2YK 是一個(gè)產(chǎn)生式,Y1,Y2,Y(i-1)都是非終結(jié)符,而且,對于任何j,1j i-1, FIRST(Yj)都含有 (即Y1.Y(i-1) =* ),則把FIRST

13、(Yj)中的所有非元素都加到FIRST(X)中;特別是,若所有的FIRST(Yj , j=1,2,K)均含有,則把加到FRIST(X)中.,24,預(yù)測分析表的構(gòu)造,計(jì)算FOLLOW集 1.對于文法的開始符號S,置#于FOLLOW(S) 中; 2.若 B是一個(gè)產(chǎn)生式,則把 FIRST()加至FOLLOW(B)中; 3.若 B是一個(gè)產(chǎn)生式,或B是一個(gè)產(chǎn)生式而 =* (即FIRST()),則把FOLLOW(A)加至FOLLOW(B)中,25,預(yù)測分析表的構(gòu)造,例:文法G E: (1) E TE (2) E +TE (3) E (4) T FT (5) T *FT (6) T (7) F (E) (8

14、) F a,非終結(jié)符的FIRST集合: FIRST(E)=(,a FIRST(E)=+, FIRST(T)=(,a FIRST(T)=*, FIRST(F)=(,a,非終結(jié)符的FOLLOW集合: FOLLOW(E)=), FOLLOW(E)=), FOLLOW(T)=,), FOLLOW(T)=,),# FOLLOW(F)=*,,),#,26,預(yù)測分析表構(gòu)造算法,1.對文法G的每個(gè)產(chǎn)生式 執(zhí)行第二步和第三步; 2.對每個(gè)終結(jié)符aFIRST(),把 加至A,a中, 3.若 FIRST(),則對任何bFOLLOW(A)把 加至A,b中, 4.把所有無定義的A,a標(biāo)上“出錯(cuò)標(biāo)志”。 可以證明,一個(gè)文

15、法G的預(yù)測分析表不含多重入口,當(dāng)且僅當(dāng)該文法是LL(1)的,27,預(yù)測分析程序,預(yù)測分析程序算法: 首先把#然后把文法開始符號推入棧;把第一個(gè)輸入符號讀進(jìn)a; FLAG:=TRUE; WHILE FLAG DO BEGIN 把棧頂符號上托出去并放在中; IF X Vt THEN IF X=a THEN 把下一個(gè)輸入符號讀進(jìn)b ELSE ERROR ELSE IF X=# THEN IF X=a THEN FLAG:=FALSE ELSE ERROR ELSE IF X,b=X X1X2.XK THEN 把XK,X K-1,.,X1一一推進(jìn)棧 ELSEERROR END OF WHILE; ST

16、OP/*分析成功,過程完畢*,28,預(yù)測分析程序,分析步驟 棧內(nèi)容 棧頂符號 當(dāng)前輸入 余留串 MX,a 1 #E E i +i# E TE 2 #ET T i +i# T FT 3 #ETF F i +i# F i 4 #ETi i i +i# 5 # ET T + i# T 6 #E E + i# E +TE 7 #ET+ + + i# 8 # ET T i # T FT 9 #ETF F i # F i 10 #ETi i i # 11 #ET T # T 12 #E E # E 13 # # #,29,4.6 LL(1)分析中的錯(cuò)誤處理,發(fā)現(xiàn)錯(cuò)誤 棧頂?shù)慕K結(jié)符與當(dāng)前輸入符不匹配 非終結(jié)符A于棧頂,面臨的輸入符為a,但分析表M的MA,a為空 應(yīng)急恢復(fù)策略 跳過輸入串中的一些符號直至遇到“同步符號”為止。,30,4.6 LL(1)分析中的錯(cuò)誤處理,同步符號集的選擇 把FOLLOW(A)中的所有符號作為A的同步符號。跳過輸入串中的一些符號直至遇到這些“同步符號”,把A從棧中彈出,可使分析繼續(xù) 錯(cuò)誤處理 若MA,a為空,跳過輸入符號a 若MA,

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

最新文檔

評論

0/150

提交評論