第四章語法分析自上而下分析

第四章語法分析自上而下分析第1頁，共28頁，2023年，2月20日，星期三引言在詞法分析完成之后，進(jìn)入語法分析階段。語法分析是編譯過程的核心。其任務(wù)是：在詞法分析識別出的單詞符號串的基礎(chǔ)上，分析并判定程序的語法結(jié)構(gòu)是否符合語法規(guī)則。語法分析的基礎(chǔ)——上下文無關(guān)文法語法分析的輸入：單詞符號串輸出：程序的內(nèi)部中間表示形式。第2頁，共28頁，2023年，2月20日，星期三語法分析器——完成語法分析的程序，其工作的實(shí)質(zhì)是按文法產(chǎn)生式，識別輸入符號串是否為一個句子。具體來說，就是看能否從文法的開始符號出發(fā)，推導(dǎo)出輸入串（單詞符號組成的有限序列），即能否建立一個與輸入串相匹配的語法分析樹。以建立與輸入串相匹配的語法分析樹的不同，語法分析樹分為：自上而下的語法樹自下而上的語法樹4.1語法分析器的功能第3頁，共28頁，2023年，2月20日，星期三4.2自上而下分析面臨的問題自上而下分析的實(shí)質(zhì)：從推導(dǎo)的角度看，從文法的開始符號出發(fā)，自上而下，推出句子。（一般是最左推導(dǎo)）自上而下分析的主旨：對任何輸入串，試圖嘗試一切可能的辦法，文法的開始符號（根節(jié)點(diǎn)）出發(fā)，試圖自上而下建立一個語法樹，其末端節(jié)點(diǎn)正好與輸入符號串相同。第4頁，共28頁，2023年，2月20日，星期三例4.1（1）SxAy（2）A**|*SSxAy=x*y=x*y=x*ySxAySxAy**=x*y回溯*=x*y=x*y=x*y第5頁，共28頁，2023年，2月20日，星期三上述過程面臨的一些問題左遞歸問題回溯成功的暫時性不成功時找不到出錯的位置效率底、代價高（窮盡一切方法）解決方法：消除文法的左遞歸找出克服回溯的充分必要條件第6頁，共28頁，2023年，2月20日，星期三1.1消除直接左遞歸PP|

PP’P’

P’|例4.2P69PP1|P2…|Pm

|1|2|…|nP1P’|2P’|…|nP’P’

1P’|2P’|…|m

P’|第7頁，共28頁，2023年，2月20日，星期三1.2消除間接左遞歸間接左遞歸的含義P70消除間接左遞歸的算法——用代入的方法變間接左遞歸為直接左遞歸，然后用公式消除左遞歸第8頁，共28頁，2023年，2月20日，星期三例子4.3文法G4.2E::=E+T|T T::=T*F|F F::=(E)|i消左遞歸得到

E::=TE’ E’::=+TE’| T::=FT’ T’::=*FT’| F::=(E)|i第9頁，共28頁，2023年，2月20日，星期三2.1消除回溯為什么要消除回溯？

——無回溯就意味著不用做無謂的嘗試。如何消除回溯？對于任一非終結(jié)符號A的產(chǎn)生式的右部的后選式：

1|

2|…|

n，如果其對應(yīng)的第一個終結(jié)符號兩兩各不相同，那么A在匹配過程中就不用試探了，而是根據(jù)所面臨的輸入符號a唯一確定用哪個后選式匹配，即該后選式的成敗全權(quán)代表了A。第10頁，共28頁，2023年，2月20日，星期三

G是一個不帶左遞歸的文法，對于G的所有非終結(jié)符的每個后選定義其終結(jié)首符集：FIRST（）={a|a…，aVT

}FIRST(u)包含了u對應(yīng)的字的所有可能的首終結(jié)符號。First（X）的求法如下(書P78)：

1）若X是終結(jié)符或ε，則First（X）={X}。

2）若X是非終結(jié)符，則對于每個產(chǎn)生式X→X1X2…Xn,

a）First（X）包含F(xiàn)irst(X1)-{ε}。

b）若對于某個i<n，所有First(X1)...First(Xi)

都包括了ε，則First(X)包括First(Xi+1)-{ε}。

c）若所有集合First(X1)...First(Xn)包括ε，則First（X）包括ε。若→ε，則規(guī)定εFirst（）如果非終結(jié)符A的所有后選首符集兩兩不相交，則當(dāng)要求A匹配輸入串時，A就能根據(jù)它所面臨的第一個輸入符號a準(zhǔn)確指派某個后選去匹配。*第11頁，共28頁，2023年，2月20日，星期三FIRST（）求法示例文法G4.2E::=TE’ E’::=+TE’| T::=FT’ T’::=*FT’| F::=(E)|iFIRST（E）=First（T）=First（F）

=First（（）并First（i）={（，i}FIRST（E’）=First（+TE’

）并First（）

={+，

}FIRST（T’）=First（*FT’

）并First（）

={*，

}第12頁，共28頁，2023年，2月20日，星期三提取公因子——將文法改造成任何非終結(jié)符的所有首符集兩兩不相交的方法P1|2|…|n|1|2|

…

|m（每個不以開頭）PA|1|2|

…

|mA1|2|…|n第13頁，共28頁，2023年，2月20日，星期三自動匹配——文法不含左遞歸，也滿足任何非終結(jié)符的所有首符集兩兩不相交的要求，要進(jìn)行有效的自上而下的語法分析，還要考慮空字的自動匹配問題。例子：對文法4.2輸入串i+i自上而下的分析：=i+ii+ii+iT’FiT+E’ETE’iFT’由于E只有一個后選式TE’，iFirst（TE’），所以用ETE’進(jìn)行推導(dǎo)由于iFirst（i），所以用Fi推導(dǎo)由于iFirst（FT’），所以用TFT’進(jìn)行推導(dǎo)從T’出發(fā)繼續(xù)匹配，而輸入字符+不輸入First（T’），但有T’

，所以自動匹配第14頁，共28頁，2023年，2月20日，星期三自動匹配的條件：當(dāng)a是允許在文法的某個句型中跟在A后的終結(jié)符時，A才能自動匹配。FOLLOW(A)={a|S…Aa…,aVT}其中，如果S…A那么#FOLLOW(A)直觀地講：FOLLOW(A)表示了句型中可能緊跟再A后面的終結(jié)符號**第15頁，共28頁，2023年，2月20日，星期三FOLLOW(B)的算法（書P79）步驟1 文法的開始符號S，置#FOLLOW(B)步驟2 如果有規(guī)則A→B

，那么FIRST()中所有的非符號都在FOLLOW(B)中。步驟3 如果有規(guī)則A→B或則A→B且FIRST()，那么FOLLOW(A)中的一切符號都在FOLLOW(B)中。注意：步驟3需要重復(fù)執(zhí)行，直到?jīng)]有哪個非終結(jié)符號的FOLLOW集合增長為止。第16頁，共28頁，2023年，2月20日，星期三FOLLOW例子文法G4.3’[E]: E→TE’ E’→+TE’| T→FT’ T’→*FT’| F→

(E)|iFOLLOW(E)={#,)}FOLLOW(E’)=FOLLOW(E)={#,)}FOLLOW(T)=FIRST(E’)FOLLOW(E)-{}={+,#,)}FOLLOW(T’)=FOLLOW(T)={}={+,#,)}FOLLOW(F)=FIRST(T’)FOLLOW(T)={+,#,),*}第17頁，共28頁，2023年，2月20日，星期三LL(1)分析條件滿足構(gòu)造不帶回溯的自上而下分析的文法，即LL（1）文法的判定條件：(1)文法不含左遞歸。（2）對文法的每個非終結(jié)符號A的任何后選首符集兩兩不相交A→

1|2

|3

…

|n

滿足如下條件：

FIRST(i

)FIRST(j

)=（i不等于j）（3）如果某個非終結(jié)符號A，如果它的某個后選式首符集包含，那么FIRST(A)FOLLOW(A)=對于LL（1）文法，可以對其輸入串進(jìn)行有效的不帶回溯的自上而下分析：P73第18頁，共28頁，2023年，2月20日，星期三無回溯的自頂向下分析技術(shù)先決條件：無遞歸既沒有規(guī)則左遞歸，也沒有文法左遞歸。無回溯性對于任一非終結(jié)符號U的規(guī)則右部x1|x2|…|xn，其對應(yīng)的字的頭終結(jié)符號兩兩不相交。第19頁，共28頁，2023年，2月20日，星期三例子：判斷文法4.3是否是LL（1）文法？E→

E+T|T T→

T*F F→(E)|i（1）消左遞歸得到

E→

TE’E’→

+TE’|T→

FT’T’→

*FT’|F→(E)|i（滿足條件1）（2）對于該文法的每個非終結(jié)符，考察其后選式的FIRST（）

E和T只有一個后選式，所以不用考察其FIRST（）；對于E’：FIRST（+TE’

）FIRST（）={+}{}=對于T’：FIRST（*FT’）FIRST（）={*}{}=對于F：FIRST（(E)）FIRST（i）={（}{i}=（所以，該文法也滿足條件2）（3）對于含有的產(chǎn)生式E’::=+TE’|和T’::=*FT’|

因?yàn)镕IRST（E’

）FOLLOW（E’

）={+，

}{#,)}=FIRST（T’

）FOLLOW（T’

）={*，

}{+,#,)}=

（滿足條件3）第20頁，共28頁，2023年，2月20日，星期三遞歸下降分析技術(shù)（實(shí)現(xiàn)思想）實(shí)現(xiàn)思想：識別程序由一組過程組成。每個過程對應(yīng)于一個非終結(jié)符號。每一個過程的功能是：選擇正確的右部，掃描完相應(yīng)的字。在右部中有非終結(jié)符號時，調(diào)用該終結(jié)符號對應(yīng)的過程來完成。第21頁，共28頁，2023年，2月20日，星期三遞歸下降技術(shù)（實(shí)例）文法G4.3E→E+T|T T→T*F F→(E)|i消左遞歸得到

E→TE’ E’→+TE’| T→FT’ T’→*FT’| F→(E)|i第22頁，共28頁，2023年，2月20日，星期三遞歸分析程序的優(yōu)點(diǎn)實(shí)現(xiàn)思想簡單明了。程序結(jié)構(gòu)和語法規(guī)則有直接的對應(yīng)關(guān)系。因?yàn)槊總€過程表示一個非終結(jié)符號的處理，添加語義加工工作比較方便。需要書寫程序的語言支持遞歸調(diào)用。如果遞歸調(diào)用機(jī)制是高效的，那么分析程序也是高效的。第23頁，共28頁，2023年，2月20日，星期三預(yù)測分析表利用預(yù)測分析表進(jìn)行預(yù)測分析預(yù)測分析表的構(gòu)造當(dāng)我們需要將U選擇某個規(guī)則展開時，如果當(dāng)前的輸入為a，表示我們要將U展開為以a為首符號的字。如果有規(guī)則U::=u，且aFIRST(u)，那么表示這個規(guī)則是個好的選擇。第24頁，共28頁，2023年，2月20日，星期三分析表構(gòu)造算法對于每個規(guī)則U→u，執(zhí)行一下步驟對于每個終結(jié)符號aFIRST(u)，A[U,a]=‘U→u’.如果FIRST(y)，對于每個FOLLOW(U)中的每個終結(jié)符號b和#，讓A[U,b]=‘U→’。將其它為定義的分析表元素為ERROR。第25頁，共28頁，2023年，2月20日，星期三分析表的例子文法G4.3’[E]:E→