編譯原理語法分析從上至下.ppt

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,