《自上而下的語(yǔ)法分析.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《自上而下的語(yǔ)法分析.ppt（32頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、1,第4章 自上而下的語(yǔ)法分析,4.1 帶回溯的自上而下分析法概述 4.2 直接左遞歸的消除 4.3 不帶回溯的自上而下分析法的基本原理 4.4 提取左因子 4.5 first集和follow集 4.6 遞歸下降分析法 4.7 預(yù)測(cè)分析法,從文法的開(kāi)始符號(hào)出發(fā)進(jìn)行推導(dǎo)，最終推出確定的輸入串（由單詞種別構(gòu)成的源程序）。,2,4.1 帶回溯的自上而下分析法概述,從根結(jié)點(diǎn)出發(fā)，試圖用一切可能的辦法，自上而下地為輸入串建立一棵語(yǔ)法樹(shù)?；蛘哒f(shuō)，為輸入串尋找一個(gè)最左推導(dǎo)。 分析過(guò)程概述 例已知文法G： SxAy A**|* 和輸入串=x*y。 初始時(shí)，指示器P指向的第一個(gè)符號(hào)x。 從S推導(dǎo)，因最左子

2、結(jié)和輸入串第1個(gè)符號(hào)相匹配，故P指向下一符號(hào)*。 因第二個(gè)子結(jié)是非終結(jié)符A，從A采用第一個(gè)候選進(jìn)行推導(dǎo)。從A推導(dǎo)出的左子結(jié)和指示器P所指的符號(hào)一致，故P指向下一個(gè)符號(hào)y。 因A的第二個(gè)子結(jié)*和指示器P所指的符號(hào)不一致，這意味著A的第一個(gè)候選不適用于構(gòu)造的語(yǔ)法樹(shù)，應(yīng)該回溯。將A的子樹(shù)注銷(xiāo)，P恢復(fù)進(jìn)入A時(shí)的值。 用A的第二個(gè)候選進(jìn)行推導(dǎo)，因子樹(shù)A的子結(jié)和指示器P所指的符號(hào)*一致，則P指向下一個(gè)符號(hào)y。 因S的第三個(gè)子結(jié)和指示器P所指的符號(hào)一致，故是一個(gè)句子。,3,顯然上述分析過(guò)程本質(zhì)上是一個(gè)試探過(guò)程，是反復(fù)使用不同產(chǎn)生式謀求匹配輸入串的過(guò)程。,問(wèn)題和困難 對(duì)于左遞歸文法定義的語(yǔ)言，不能采用自上而下

3、的語(yǔ)法分析法。 存在虛假匹配，回溯不可避免。 編譯程序的語(yǔ)法分析和語(yǔ)義分析通常是同時(shí)進(jìn)行的。由于回溯，編譯程序所做的一大堆語(yǔ)義分析工作必須推倒重來(lái)。 當(dāng)選用所有的不同候選組合，都不能為輸入串建立一棵語(yǔ)法樹(shù)，那么輸入串存在語(yǔ)法錯(cuò)誤。這種分析法最終只能告知輸入串不是文法的一個(gè)句子，而無(wú)法告知輸入串錯(cuò)在何處。 帶回溯的自上而下分析法實(shí)際上是一種窮盡一切可能的試探法，因此效率很低，這種分析法幾乎沒(méi)有實(shí)用價(jià)值。 總上所述，必須消除分析過(guò)程中的回溯，只有不帶回溯的分析方法才是實(shí)際可使用的。,4,4.2 直接左遞歸的消除,程序設(shè)計(jì)語(yǔ)言文法的左遞歸性通常是由左遞歸規(guī)則直接引起的，由規(guī)則推導(dǎo)所產(chǎn)生的間接左遞歸

4、的情況較少見(jiàn)。 實(shí)例引入 例：已知左遞歸文法G：SSa|b，構(gòu)造文法G的等價(jià)文法G，G不含左遞歸。 解：文法G如下所示 SbS SaS| SSaSaaban 或 Sb L(G)= bann0 SbSbaSban 或 SbSb L(G)= bann0 L(G)= L(G) 文法G和G等價(jià)，而文法G不含左遞歸。,5,直接左遞歸消除方法 假定關(guān)于非終結(jié)符P的規(guī)則為 PP| 其中，不以P開(kāi)頭?？梢园殃P(guān)于P的規(guī)則變換為如下形式： PP PP| 由于二者推導(dǎo)出的句型均為n(n0)，故上述變換是等價(jià)的。 例文法G： EE+T|T TT*F|F F(E)|i|x|y 經(jīng)消除直接左遞歸后變成 ETE E+T

5、E| TFT T*FT| F(E)|i|x|y,6,直接左遞歸消除一般規(guī)則及等價(jià)性證明 設(shè)非終結(jié)符P的產(chǎn)生式如下 PP1|P2||Pm|1|2||n 其中，i（1in）不以P開(kāi)頭?？蓪的規(guī)則改成如下等價(jià)形式，即可消除左遞歸。 P1P|2P||nP P1P|2 P||m P | 證： PP1| P2|| Pm|1|2||n 等價(jià)于 PP（1|2||m）|（1|2||n） 令=1|2||m、=1|2||n，則上式為： PP|。 消除直接左遞歸后變成 PP PP|,7,證： PP1| P2|| Pm|1|2||n 等價(jià)于 PP（1|2||m）|（1|2||n） 令=1|2||

6、m、=1|2||n，則上式為： PP|。 消除直接左遞歸后變成 PP PP| 用1|2||m替代，用1|2||n替代，則有 P（1|2||n）P P（1|2||m）P | 等價(jià)于 P1P|2P||nP P1P|2 P||m P |,8,4.3 不帶回溯的自上而下分析法的基本原理,設(shè)文法G有產(chǎn)生式：A1|2||n 帶回溯的自上而下的分析法 采用試探法，對(duì)于1、2直至n逐一試探。 不帶回溯的自上而下的分析法 在推導(dǎo)時(shí)，根據(jù)面臨的輸入符號(hào)去找出A的那個(gè)唯一正確的候選式。 對(duì)于文法某一句型，只要該文法不是二義文法，從非終結(jié)符A出發(fā)的最左推導(dǎo)只有一個(gè)候選是正確的。 如果該候選式獲得匹配，那么

7、這個(gè)匹配決不會(huì)是虛假的。若該候選式無(wú)法完成匹配任務(wù)，則任何其它候選式也肯定無(wú)法完成。,9,算法思想如下： 引入候選式的first集定義 first()=aa，aVT。 first()直觀意義是：從候選式出發(fā)，推導(dǎo)出的所有符號(hào)串的第一個(gè)終結(jié)符，都屬于這個(gè)集合。 根據(jù)定義，求出每個(gè)候選式i的first集，設(shè)： first(1)=a1、b1、 first(2)=a2、b2、 first(n)=an、bn、 根據(jù)當(dāng)前輸入符號(hào)，選擇候選式進(jìn)行推導(dǎo)。 if (t.codefirst(i)) 用Ai推導(dǎo)（1in） else 報(bào)錯(cuò) 由于推導(dǎo)的唯一性，要求first(i)first(j)=，其中1i,jn、

8、ij。,10,進(jìn)一步考慮（A） 設(shè)文法G有產(chǎn)生式A1|2||n|，因A無(wú)需任何字符匹配（相當(dāng)于在句型推導(dǎo)中丟棄A），故當(dāng)t.codefirst(i)不能簡(jiǎn)單地處理為出錯(cuò)，需進(jìn)一步分析，A匹配于空字可能是一個(gè)正確的選擇。 引入非終結(jié)符follow集定義 follow(A)=a|SAa，aVT follow(A)的直觀意義是：在所有句型中緊跟在非終結(jié)符A之后的終結(jié)符。 若當(dāng)前處理符號(hào)屬于follow(A)，則用A進(jìn)行推導(dǎo)（相當(dāng)于在句型推導(dǎo)中丟棄A），當(dāng)前處理符號(hào)參加下一次匹配。 修改分析算法 if (t.codefirst(i)) 用Ai推導(dǎo)（1in） else if (t.codefoll

9、ow(A)) 用A推導(dǎo) else 報(bào)錯(cuò) 由于推導(dǎo)的唯一性，要求first(i)first(j)=，first(i)follow(A) = ，其中1i,jn、ij。,11,4.4 提取左因子,實(shí)例引入 例定義無(wú)符號(hào)整數(shù)的文法 NDN|D D0|1|2|3|4|5|6|7|8|9 因first(DN)first(D)=0,1,2,3,4,5,6,7,8,9，故文法含有左因子。 解決方法 提取左因子，引進(jìn)產(chǎn)生式，將文法改造為G。 ND N NN| D0|1|2|3|4|5|6|7|8|9|0 提取左因子一般規(guī)則 考慮一般情況，設(shè)非終結(jié)符P的規(guī)則為 P1|2||n，(VTVN)+，i(VT

10、VN)* 引進(jìn)非終結(jié)符P，可以把這些規(guī)則改寫(xiě)成 PP P1|2||n,12,先討論文法符號(hào)，然后再討論候選式、任意文法符號(hào)串的first集的構(gòu)造。 first集定義 是文法G的任一符號(hào)串（包括候選式），(VTVN)* first()=aa，aVT 若，則規(guī)定first()。 first()直觀意義是：從推導(dǎo)出的所有符號(hào)串的第一個(gè)終結(jié)符。或者，從可推導(dǎo)至空字。 文法符號(hào)first集構(gòu)造算法 終結(jié)符的first集為終結(jié)符本身。 觀察每個(gè)產(chǎn)生式，若有Xa，其中aVT，則afirst(X)；若X，則first(X)。 觀察每個(gè)產(chǎn)生式，若有XY，其中YVN，則將first(Y)中的非元素（記為fir

11、st(Y)/）加到first(X)中。,4.5.1 first集的定義及構(gòu)造算法,13,證： 設(shè)終結(jié)符afirst(Y)，根據(jù)定義有Ya。 XY XYa 即Xa，根據(jù)定義有afirst(X)。 考慮更一般情況,XY1Y2YiYn,其中Y1、Y2、Yi-1VN。 若first(Y1)中含有，則將first(Y2)/加到first(X)中，否則終止計(jì)算。 若first(Y1)和first(Y2)中含有，則將first(Y3)/加到first(X)中，否則終止計(jì)算。 若first(Y1)、first(Y2)、first(Yi-1)均含有，即Y1Y2Yi-1，則把first(Yi)/加到first

12、(X)中，否則終止計(jì)算。 若所有first(Yj) 均含有(1jn)，即Y1Y2Yn，則first(X)。 反復(fù)使用規(guī)則，直至每個(gè)非終結(jié)符的first集不再增長(zhǎng)為止。規(guī)則實(shí)質(zhì)上是一個(gè)傳遞規(guī)則。,14,例，文法G如下所示, 求文法符號(hào)的first集。 ETE E+TE| TFT T*FT| F(E) | i | x | y 解：文法符號(hào)first集的計(jì)算規(guī)則如下,15,在“規(guī)則”列處填入的是計(jì)算公式，需多次重復(fù)計(jì)算，直至每個(gè)非終結(jié)符的first集不再增長(zhǎng)為止。計(jì)算過(guò)程如下,說(shuō)明： 由于終結(jié)符的first集計(jì)算較為簡(jiǎn)單，在計(jì)算過(guò)程中不再列出。 在計(jì)算E的 first集時(shí)（ETE），因fir

13、st(T)不含，故沒(méi)有必要考慮E的first集，同理T的first集計(jì)算（TFT）。 計(jì)算也可從下至上進(jìn)行。,16,候選式first集構(gòu)造算法 設(shè)A，=X1X2Xn，計(jì)算規(guī)則如下所示： 置first()=first(X1)/。 若first(X1)，則把first(X2)/加至first()中；若first(X1)且first(X2)，則把first(X3)/加至first()；；依次類(lèi)推。 若所有的first(Xi)均含有,其中1in，則first()。特別當(dāng)=,則first()=。 接上例，求文法G候選式的first集： ETEfirst(TE)=first(T) /=(,i,x,y E+

14、TE|first(+TE)=+,first()= TFTfirst(FT)=first(F) /=(,i,x,y T*FT|first(*FT)=*,first()= F(E)|ifirst((E))=( 、first(i)=i Fx|yfirst(x)=x、first(y)=y,任一文法符號(hào)串的first集構(gòu)造算法 設(shè)AX1X2Xi-1XiXi+1Xn，求XiXi+1Xn的first集。 令= XiXi+1Xn，參照即可。,17,4.5.2 follow集的定義及構(gòu)造算法,follow集定義 設(shè)S是文法開(kāi)始符號(hào)，對(duì)于文法的任何非終結(jié)符A follow(A)=aSAa，aVT 特別是，若

15、SA，規(guī)定#follow(A)。 （注：由于算法的需要，人為地在源程序尾部添加了#，特別規(guī)定因此而來(lái)） follow(A)直觀意義是：在所有句型中緊跟在非終結(jié)符A之后的終結(jié)符或#。 follow集構(gòu)造算法 對(duì)于文法開(kāi)始符號(hào)S，因?yàn)镾S，故#follow(S)。 觀察每個(gè)產(chǎn)生式，若AB，其中、(VTVN)+， BVN，則把first()/加至follow(B)。 觀察每個(gè)產(chǎn)生式，若AB或AB()，則把follow(A)加至follow(B)。,18,證：設(shè)afollow(A)，根據(jù)定義有SAa。 AB SAaB a 因a在句型中緊跟在B之后，故afollow(B)。,反復(fù)使用第條規(guī)則，直至每個(gè)

16、非終結(jié)符的follow集不再增長(zhǎng)為止。第條規(guī)則實(shí)質(zhì)上是一條傳遞規(guī)則。 例，文法G如下所示，求非終結(jié)符的follow集。 ET Efirst(E) /= + E+TE ETFTfirst(T) /= * T*FT T F(E)first( ) )=) Fi Fx Fy,19,解：根據(jù)上述規(guī)則，非終結(jié)符follow集的計(jì)算規(guī)則如下,根據(jù)ETE，follow(E)應(yīng)加至follow(E)；因E，所以follow(E)還應(yīng)加至follow(T)。同理E+TE、TFT、T*FT。 follow集的計(jì)算也可從下至上進(jìn)行。,“規(guī)則”列處填入的是計(jì)算公式，需多次重復(fù)計(jì)算，直至每個(gè)非終結(jié)符的follow集不再

17、增長(zhǎng)為止。計(jì)算過(guò)程如下,20,4.6 遞歸下降分析法,遞歸下降分析法思想是：讓每個(gè)非終結(jié)符對(duì)應(yīng)一個(gè)過(guò)程（函數(shù)）。根據(jù)上述文法，構(gòu)造遞歸下降分析程序，程序用類(lèi)C語(yǔ)言描述。,void E( )// ETE T;E; ,void E( )// E+TE| if (t.code==+)cinft.codet.val;T;E; ,void T( )// TFT F;T; ,void T( )// T*FT| if (t.code==*)cinft.codet.val;F;T ,void F( )// F(E) | i | x | y if (t.code==() cinft.codet.va

18、l; E;if (t.code==)) cinft.codet.val; else if (t.code==i|| t.code==x|| t.code==y) cinft.codet.val; ,struct code_valchar code;char val20; t; ifstream cinf(lex_r.txt,ios::in);,21,為了便于理解，源程序“(a+b)*c”用單詞種別“(i+i)*i#”表示，手工計(jì)算如下： step 調(diào)用過(guò)程(函數(shù))t.cod文件Lex_r 0)E(i+i)*i# 1)TE(i+i)*i# 2)FTE(i+i)*i# 3)ESTEi+i)*i

19、# S代表語(yǔ)句if (t.code==))cinft.codet.val; 4)TESTEi+i)*i# 5)FTESTEi+i)*i# 6)TESTE (T匹配于)+i)*i# 7)ESTE+i)*i# 8)TESTEi)*i# 9)FTESTEi)*i# 10)TESTE(T匹配于))*i# 11)ESTE (E匹配于))*i# 12)STE)*i# 13)TE*i# 14)FTEi# 15)TE(T匹配于)# 16)E(E匹配于)# 17)(回到主程序結(jié)束處即E之后) #,22,4.7 預(yù)測(cè)分析法,遞歸下降分析法是利用高級(jí)語(yǔ)言的遞歸過(guò)程（函數(shù)）來(lái)實(shí)現(xiàn)的，只有當(dāng)高級(jí)語(yǔ)言的編譯系統(tǒng)允許過(guò)程（

20、函數(shù)）遞歸調(diào)用，遞歸下降分析法才有意義?，F(xiàn)考慮一個(gè)不使用遞歸的更一般的實(shí)用方法，這種分析法是由分析表和控制程序構(gòu)成。,預(yù)測(cè)分析法基本原理 產(chǎn)生式的一般形式為： A1|2||n| 設(shè)當(dāng)前輸入符號(hào)為a，根據(jù)下述原則 if (afirst(i)) 用Ai推導(dǎo)（1in） else if (afollow(A)) 用A推導(dǎo) else 報(bào)錯(cuò),23,構(gòu)造分析表如下,分析表構(gòu)造規(guī)則 構(gòu)造所有候選式的first集，構(gòu)造所有非終結(jié)符的follow集。 對(duì)于文法的每個(gè)產(chǎn)生式A執(zhí)行和。 對(duì)于每個(gè)終結(jié)符afirst()，把A加至MAa。 若first()，則對(duì)于每個(gè)終結(jié)符bfollow(A)，把A加至MAb。 把所有

21、未定義的MAc標(biāo)上“出錯(cuò)標(biāo)志”（cVT）。,24,預(yù)測(cè)分析控制程序?qū)崿F(xiàn) 數(shù)據(jù)結(jié)構(gòu) M:二維數(shù)組，存放預(yù)測(cè)分析表。 stack:符號(hào)棧，初始時(shí)為#S（S為開(kāi)始符號(hào)）。 X:表示棧頂符號(hào) t.code:當(dāng)前處理單詞種別 算法描述（暫不考慮出錯(cuò)情況） 預(yù)測(cè)分析控制程序任何時(shí)刻的動(dòng)作，都按照棧頂符號(hào)X和當(dāng)前輸入符號(hào)t.code行事（ XPop(stack) ），控制程序每次執(zhí)行下述三種可能的動(dòng)作之一。 若X 和 t.code 均為 #，則分析成功，輸入串為合法句子，終止分析過(guò)程。 若X是終結(jié)符，并且X和t.code相等，表示期望的終結(jié)符號(hào)和輸入符號(hào)相等，則讀入下一個(gè)單詞二元式。 若X是非終結(jié)符，則查

22、預(yù)測(cè)分析表。若MXt.code存放著一條關(guān)于X的一個(gè)產(chǎn)生式，那么把產(chǎn)生式右部符號(hào)串按反序壓入stack棧。若右部符號(hào)串為空字，則意味著無(wú)任何文法符號(hào)進(jìn)棧。,25,假設(shè)由單詞種別構(gòu)成的源程序?yàn)椤癷+i#”，手工計(jì)算如下： step stackXt.code 文件Lex_r.txt 0)#Ei+i# 1)#Ei+i# #ETi+i# 2)#ETi+i# #ETFi+i# 3)#ETFi+i# #ETii+i# 4)#ETii+i# #ET+i# 5)#ET+i# #E+i# 6)#E+i# #ET++i# 7)#ET++i# #ETi#,26,step stackXt.code 文件Lex_r.t

23、xt 7)#ET++i# #ETi# 8)#ETi# #ETFi# 9)#ETFi# #ETii# 10)#ETii# #ET# 11)#ET# #E# 12)#E# ## 13) ## Acc,預(yù)測(cè)分析法不僅避免了過(guò)程（函數(shù)）的遞歸調(diào)用，并且使得自上而下的語(yǔ)法分析器的自動(dòng)構(gòu)造成為可能。,27,1. procedure LL1 2. 初始化符號(hào)棧 3push(符號(hào)棧, #):push(符號(hào)棧, S) 4. t.codecode:t.valval//從文件讀第一個(gè)單詞的二元式 5.donefalse 6.repeat 7. Xpop(狀態(tài)棧) 8. if X=# then 9.if X

24、= t.code then 10. output ”Acc”:donetrue 11.end if //否則出錯(cuò) 12. else if XVT then 13. if X= t.code then 14. t.code code:t.valval//從文件讀下一個(gè)單詞的二元式 15.end if //否則出錯(cuò) 16. else if XVN then 17.if MXt.code=X then//= X1X2Xn 18. for i|| downto 1 19.push(狀態(tài)棧,Xi) 20. end for 21.end if 22. end if //否則出錯(cuò) 23.unt

25、il done 24. end procedure,28,預(yù)測(cè)分析法討論 預(yù)測(cè)分析法是由分析表和控制程序構(gòu)成的，控制程序與文法無(wú)關(guān)，分析表隨文法而異。 在預(yù)測(cè)分析表中，若某一單元持有一個(gè)以上產(chǎn)生式，則稱(chēng)該預(yù)測(cè)分析表含多重定義，多重定義使得控制程序無(wú)法工作。 一個(gè)文法，若它的預(yù)測(cè)分析表不含多重定義，則稱(chēng)該文法是LL(1)文法、分析表為L(zhǎng)L(1)分析表（LL是指從左到右的左分析器，1表示向前看一個(gè)符號(hào)）。 一個(gè)文法是LL(1)的，對(duì)于文法的每一個(gè)非終結(jié)符的任何兩個(gè)不同候選式（A|），下述條件成立： first()first()= 若，則first()follow(A)= 二義文法不是LL(1)文法

26、,29,二義文法在預(yù)測(cè)分析法中的應(yīng)用 考慮文法G： SfCtS | fCtSeS | a Ci a表示普通語(yǔ)句，C表示布爾表達(dá)式。經(jīng)提取公因子后為 SfCtSS | a SeS | Ci 預(yù)測(cè)分析表如下：,因MSe含有二重定義，故分析表不是LL(1)分析表。,30,現(xiàn)用手工方法來(lái)修改二義文法的分析表，消除分析表的二重定義。設(shè)輸入串為fitaea#，其執(zhí)行過(guò)程如下所示： step stackXt.code文件Lex_r.txt 0)#Sfitaea# 1)#Sfitaea# #SStCffitaea# 2)#SStCffitaea# #SStC itaea# 3)#SStCitaea# #SStiitaea# 4)#SStiitaea# #SSttaea# 5)#SSttaea# #SSaea# 6)#SSaea# #Saaea# 7)#Saaea# #Sea#,31,step stackXt.code文件Lex_r.txt 8)#Sea#(采用S) #ea# 9)#ea# Err 在第8步不使用S，而選用SeS。 8)#Sea#(采用SeS) #Seea# 9)#Seea# #Sa# 10)#Sa# #aa# 11)#aa# ## 12)## Acc 保留SeS去掉S，意味著把e和最近的t相結(jié)合。對(duì)于實(shí)際使用的語(yǔ)言，這相當(dāng)于把else和最近的then相結(jié)合。,32,結(jié)束,