自上而下語法分析PPT課件

1、自上而下語法分析編譯技術之四主講 魯 斌2v高級語言的語法結構適合用上下無關文法描述，因高級語言的語法結構適合用上下無關文法描述，因此，我們將上下文無關文法作為語法分析的基礎此，我們將上下文無關文法作為語法分析的基礎v本章和下一章，我們將介紹編譯程序構造中的一些本章和下一章，我們將介紹編譯程序構造中的一些典型的語法分析方法典型的語法分析方法34.1 概述概述v語法分析是編譯過程的核心部分。它的任務是在詞法分析識語法分析是編譯過程的核心部分。它的任務是在詞法分析識別出單詞符號串的基礎上，分析并判定程序的語法結構是否別出單詞符號串的基礎上，分析并判定程序的語法結構是否符合語法規(guī)則符合語法規(guī)則v下圖

2、表明了語法分析器在編譯程序中的地位下圖表明了語法分析器在編譯程序中的地位v按照語法分析樹的建立方法，我們可以粗略地把語法分析方按照語法分析樹的建立方法，我們可以粗略地把語法分析方法分為兩類：一類是法分為兩類：一類是自上而下分析法自上而下分析法，另一類為，另一類為自下而上分自下而上分析法析法源程序源程序詞法分析器詞法分析器單詞符號單詞符號取下一取下一單詞符號單詞符號語法分析器語法分析器語法語法分析樹分析樹后續(xù)部分后續(xù)部分符符 號號 表表4例：自頂向下構造最左推導（aabbaa) SaASa A SbA SS baASaSbSAaaba aSbAS aabAS aabbaS aabbaa aAS

3、S54.2 4.2 自上而下分析面臨的問題自上而下分析面臨的問題v自上而下分析的一般方法：對任何輸入串，用一切自上而下分析的一般方法：對任何輸入串，用一切可能的方法從文法開始符號（根結）出發(fā)，自上而可能的方法從文法開始符號（根結）出發(fā)，自上而下地為輸入串建立一棵語法樹，或尋找一個最左推下地為輸入串建立一棵語法樹，或尋找一個最左推導導v這種分析過程本質上是一種試探過程，是反復使用這種分析過程本質上是一種試探過程，是反復使用不同產生式謀求匹配輸入串的過程不同產生式謀求匹配輸入串的過程6v例例4.1：假定有文法：假定有文法SxAyAab|a分析輸入串分析輸入串xay（記為（記為w）。）。SxAySx

4、AyaabSxAy(a)(b)(c)7v例例4.2：假定有文法：假定有文法SSaSb分析輸入串分析輸入串baaa。8v由上例看到，自上而下分析法存在許多困難和缺點由上例看到，自上而下分析法存在許多困難和缺點n文法的左遞歸性文法的左遞歸性PP使分析陷入無限循環(huán)使分析陷入無限循環(huán)n回溯的不確定性，要求我們將已經完成工作推倒重來回溯的不確定性，要求我們將已經完成工作推倒重來n虛假匹配問題虛假匹配問題n難于知道出錯位置難于知道出錯位置n效率低，代價高，實踐價值不大效率低，代價高，實踐價值不大v因此，為解決這些問題我們要消除左遞歸和回溯因此，為解決這些問題我們要消除左遞歸和回溯+94.3 LL(1) 分

5、析法分析法4.3.1 左遞歸的消除左遞歸的消除4.3.2 消除回溯、提左因子消除回溯、提左因子4.3.3 LL(1)文法文法104.3.1 左遞歸的消除左遞歸的消除v一般而言，假定關于一般而言，假定關于A的全部產生式是的全部產生式是AA 1| A 2| A m| 1| 2 | | n 其中，每個其中，每個 都不等于都不等于 ，而每個，而每個 都不以都不以A開頭，開頭，那么，消除那么，消除A的直接左遞歸性就是把這些規(guī)則改寫的直接左遞歸性就是把這些規(guī)則改寫成：成： A 1 A| 2 A| n A A1A| 2A| | mA| 11v例例4.3：文法文法EE+T|TTT*F|FF(E)|i消去直接左

6、遞歸：消去直接左遞歸：ETEE+TE|TFT （4.1）T*FT|F(E)|iv直接左遞歸和非直接左遞歸的消除方法均在必須掌握之列直接左遞歸和非直接左遞歸的消除方法均在必須掌握之列12v若一個文法不含回路（若一個文法不含回路（AA），也不含以），也不含以為右部為右部的產生式，則消除一切左遞歸的算法是：的產生式，則消除一切左遞歸的算法是：把文法把文法G的所有非終結符排序：的所有非終結符排序：A1, A2, , AnFOR i:=1 TO n DOBEGIN FOR j:=1 TO i-1 DO 把形如把形如AiAj的規(guī)則改寫成的規(guī)則改寫成 Ai1|2|k 其中其中Aj1|2|k是關于是關于Aj的

7、所有規(guī)則；的所有規(guī)則； 消除關于消除關于Ai規(guī)則的直接左遞歸性規(guī)則的直接左遞歸性END化簡上述文法化簡上述文法*13例例4.4：考慮文法：考慮文法：SQc|c Q Rb|b R Sa|a 消除左遞歸。消除左遞歸。解：解：將終結符排序為將終結符排序為R、Q、S。對于。對于R不存在直接左遞歸。把不存在直接左遞歸。把R帶入帶入到到Q中有關的候選式：中有關的候選式： Q Sab|ab|b 現(xiàn)在現(xiàn)在Q同樣不含直接左遞歸，把它帶入同樣不含直接左遞歸，把它帶入S的有關候選式：的有關候選式： S Sabc|abc|bc|c 經消除經消除S的直接左遞歸后我們們得到整個文法的直接左遞歸后我們們得到整個文法 S a

8、bcS|bcS|cS S abcS| Q Sab|ab|b R Sa|a 由于關于由于關于Q,R的規(guī)則式多余的則可化簡的規(guī)則式多余的則可化簡得到：得到： S abcS|bcS|cS SabcS| 144.3.2 消除回溯、提左因子消除回溯、提左因子v令令G是一個不含左遞歸的文法，對是一個不含左遞歸的文法，對G 的所有的非終的所有的非終結符號的每個候選結符號的每個候選 定義它的終結首符集定義它的終結首符集FIRST( )為：為： FIRST( )=a| *a,a VTv若若* ，則規(guī)定，則規(guī)定 FIRST( )。 換句話說換句話說FIRST( )是是 的所有可能推導的開頭終結符或可能的所有可能推

9、導的開頭終結符或可能的的 15v如果非終結符如果非終結符A 的所有候選首符集兩兩不相交，即的所有候選首符集兩兩不相交，即A的任何兩個不同的候選的任何兩個不同的候選 i和和 j FIRST( i) FIRST( j) = 那么，當要求那么，當要求A匹配輸入串時，匹配輸入串時，A 就能根據(jù)它所面就能根據(jù)它所面臨的第一個輸入符號臨的第一個輸入符號a，準確地指派某個候選前去，準確地指派某個候選前去執(zhí)行任務。這個候選就是那個終結首符集含執(zhí)行任務。這個候選就是那個終結首符集含a 的的 16v如何把一個文法改造成任何終結首符集的所有候選首符集兩如何把一個文法改造成任何終結首符集的所有候選首符集兩兩不相交呢？

10、其辦法是兩不相交呢？其辦法是提取公共左因子提取公共左因子v假定關于假定關于A 的規(guī)則是的規(guī)則是A1| 2| |n| 1| 2| | m （其中每個（其中每個 不以不以 開頭）開頭） 那末，可以把這些規(guī)則改寫成：那末，可以把這些規(guī)則改寫成：A A| 1| 2| | mA 1 | 2 | | n 17例：例：有產生式有產生式 B bBcA|b 由于由于FIRST(bBcA) FIRST(b) =b ，則需要提，則需要提取公共左因子，將產生式改寫成：取公共左因子，將產生式改寫成：B bCC BcA| 18 v 問題問題 例：例：考慮文法考慮文法4.1，對輸入串，對輸入串i+i進行自上而下分析進行自上

11、而下分析EFETT(b)i+iIPi+iIP(a)ETEi+iIP(c)FTTEEiEFETT(d)i+iIPiEi+iFEIPTT(e)i+ETiFTETEE+TE|TFTT*FT|F(E)|i19v假定假定S是文法是文法G開始符號，對任何非終結符開始符號，對任何非終結符A定義：定義： FOLLOW(A) = a | S* Aa, a VT v若若S* A， 則規(guī)定則規(guī)定# FOLLOW(A). 也就是說，也就是說，F(xiàn)OLLOW(A)是所有句型中出現(xiàn)在緊接是所有句型中出現(xiàn)在緊接A之后的終結之后的終結符或符或#v因此，當非終結符因此，當非終結符A面臨輸入符號面臨輸入符號a，且，且a不屬于不屬于

12、A的任意候選首符集但的任意候選首符集但A的某個候選首符集包含的某個候選首符集包含 時，時，只有當只有當aFOLLOW(A)，才可能允許，才可能允許A自動匹配自動匹配204.3.3 LL(1)文法文法v判斷某給定文法是否為判斷某給定文法是否為LL(1)文法其條件為：文法其條件為：文法不含左遞歸文法不含左遞歸對于文法中每個非終結符對于文法中每個非終結符A的各個產生式的候選首符集的各個產生式的候選首符集兩兩不相交。即，若兩兩不相交。即，若 A 1 | 2 | n 則：則： FIRST( i) FIRST( j) = （i j )對文法中每一個非終結符對文法中每一個非終結符A，若它存在某個候選首符集，

13、若它存在某個候選首符集包含包含 ，則，則 FIRST(A) FLLOW(A)= v一個文法若滿足以上條件，則稱該文法一個文法若滿足以上條件，則稱該文法G為為LL(1)文法文法21v對于對于LL(1)文法，可以對其輸入串進行有效的無回文法，可以對其輸入串進行有效的無回溯的自上而下分析。假設要用非終結符溯的自上而下分析。假設要用非終結符A匹配，輸匹配，輸入符號入符號a，A的所有產生式為的所有產生式為A 1 | 2 | nn若若a FIRST( i)，則指派，則指派 i執(zhí)行匹配任務執(zhí)行匹配任務n若若a不屬于任何一個候選首符集，則不屬于任何一個候選首符集，則u若若FIRST( i)且且a FLLOW(

14、A)，則讓，則讓A與與 自動匹配自動匹配u否則，否則，a的出現(xiàn)是一種語法錯誤的出現(xiàn)是一種語法錯誤224.4 遞歸下降分析法遞歸下降分析法v當一個文法滿足當一個文法滿足LL(1)條件時，我們就可以構造一條件時，我們就可以構造一個不帶回溯的自上而下分析程序，這個分析程序由個不帶回溯的自上而下分析程序，這個分析程序由一組遞歸過程組成，每個過程對應文法的一個非終一組遞歸過程組成，每個過程對應文法的一個非終結符。這樣一個分析程序稱為結符。這樣一個分析程序稱為遞歸下降分析器遞歸下降分析器23v例如，文法例如，文法4.1的每個非終結符所對應的遞的每個非終結符所對應的遞歸過程如下：歸過程如下：PROCEDUR

15、E E; PROCEDURE T;BEGIN BEGINT;E F;TEND; END;PROCEDURE E; PROCEDURE T;IF SYM=+ THEN IF SYM=* THENBEGIN BEGIN ADVANCE; ADVANCE;T;E F;TEND; END;PROCEDURE F;IF SYM=i THEN ADVANCE ELSE IF SYM=( THEN BEGIN ADVANCE; E; IF SYM=) THEN ADVANCE ELSE ERROR END ELSE ERROR;ETEE+TE|TFTT*FT|F(E)|i244.5 預測分析法預測分析法v使

16、用高級語言的遞歸過程描述遞歸下降分析器，只使用高級語言的遞歸過程描述遞歸下降分析器，只有當具有實現(xiàn)這種過程的編譯系統(tǒng)時才有實際意義有當具有實現(xiàn)這種過程的編譯系統(tǒng)時才有實際意義v實現(xiàn)實現(xiàn)LL(1)分析的另一種有效方式是使用一張分析分析的另一種有效方式是使用一張分析表和一個棧進行聯(lián)合控制。我們現(xiàn)在介紹的表和一個棧進行聯(lián)合控制。我們現(xiàn)在介紹的預測分預測分析程序析程序就是屬于這種類型的就是屬于這種類型的LL(1)分析器分析器254.5.1預測分析程序工作過程預測分析程序工作過程v預測分析表是一個預測分析表是一個MA, a形式的矩陣形式的矩陣v對于任何對于任何(X,a)，總控程序執(zhí)行下述動作之一，總控程

17、序執(zhí)行下述動作之一n若若X=a=#，則分析成功，停止，則分析成功，停止n若若X=a#，則把，則把X從從STACK棧頂逐出，讓棧頂逐出，讓a指向下一個輸入符號指向下一個輸入符號n若若X是一個非終結符，則依據(jù)分析表是一個非終結符，則依據(jù)分析表M中的不同內容作不同處理中的不同內容作不同處理a#輸入串輸入串總控程序總控程序預測分析表預測分析表Mx#輸出輸出26v預測分析器的總控程序：預測分析器的總控程序：置置 ip指向指向 w#的第一個符號；令的第一個符號；令X為棧頂符號，為棧頂符號，a是是 ip所指向的符號所指向的符號BEGINpush(st,#); push(st,S);FLAG:=TRUE;WH

18、ILE FLAG DOBEGIN IF X VT THEN IF X=a THEN pop(st); ip:=ip+1 ELSE ERROR ELSE IF X=# THEN IF X=a THEN FLAG:=FALSE ELSE ERROR ELSE IF Mx,a=XX1X2Xk THEN pop(st);push(st,Xk);push(st,X1) ELSE ERROR、END OF WHILE;STOPEND27 i1 + i2 * i3 #輸入輸入預測分析控制程序#E ET TF i ET+ TF i ETEFTEi1TEi1E i1+TE i1+FTE i1+i2TE棧ETEE

19、+TE|TFTT*FT|F(E) | i28例：例：輸入串為輸入串為i1+i2，利用分析表進行預測分析。，利用分析表進行預測分析。符號棧符號棧 輸入串輸入串 MX,b1 #E i1+i2# E TE2 #ET i1+i2# T FT3 #ETF i1+i2# F i4 #ET i i1+i2# 匹配匹配5 # ET +i2# T 6 #E +i2# E +TE7 #ET+ +i2# 匹配匹配8 # ET i2# T FT 9 #ETF i2# F i10 #ETi i2# 匹配匹配11 #ET # T 12 #E # E 13 # # 接受接受ETEE+TE|TFTT*FT|F(E) | ii

20、+*()#ETETEE+TETFTFTT*FTFi(E)29v計算計算FIRSTFIRST集集若若X X V V , ,則則FIRST(X)=XFIRST(X)=X若若X X V VN N, ,且有產生式且有產生式X Xa a，則把，則把a a加入到加入到FIRST(X)FIRST(X)中中; ;若若X X也是一條產生式也是一條產生式, ,則把則把 也加到也加到FIRST(X)FIRST(X)中中若若X XY Y是一個產生式且是一個產生式且Y Y V VN N, ,則把則把FIRST(Y)FIRST(Y)中的所有中的所有非非 元元素都加到素都加到FIRST(X)FIRST(X)中中; ;若若X

21、 X Y Y1 1Y Y2 2Y YK K 是一個產是一個產生式生式,Y,Y1 1,Y,Y2 2, ,Y,Y(i-1)(i-1)都是非終結符都是非終結符, ,而且而且, ,對于任何對于任何j,1j,1j j i-i-1, FIRST(Y1, FIRST(Yj j) )都含有都含有 ( (即即Y Y1 1.Y.Y(i-1) (i-1) =* ), ),則把則把FIRST(YFIRST(Yi i) )中的所有非中的所有非 元素都加到元素都加到FIRST(X)FIRST(X)中中; ;特特別是別是, ,若所有的若所有的FIRST(YFIRST(Yj j , , j=1,2,j=1,2,K),K)均含

22、有均含有 , ,則把則把 加到加到FRIST(X)FRIST(X)中中 4.5.2 預測分析表的構造預測分析表的構造30v求求First(), =X1 1X2 2Xn n 置置FIRST(FIRST()=FIRST()=FIRST(X1)1) 若對任何若對任何1ji-1, 1ji-1, FIRST(XFIRST(Xj j) )，則把，則把FIRST(FIRST(Xi)i) 加入加入FIRST(FIRST() )中中特別是特別是, ,若所有的若所有的FIRST(XFIRST(Xj j) )均含有均含有 , 1jn, 1jn，則把，則把 加加到到FRIST(FRIST() )中中v顯然，若顯然，若

23、= = ，則，則FIRST(FIRST()=)= 31v計算計算FOLLOWFOLLOW集集對于文法的開始符號對于文法的開始符號S,S,置置# #于于FOLLOW(S)FOLLOW(S)中中若若 BB是一個產生式是一個產生式, ,則把則把FIRST()FIRST() 加至加至FOLLOW(B)FOLLOW(B)中中若若BB是一個產生式是一個產生式, ,或或BB是一個產生式而是一個產生式而=* ( (即即 FIRST()FIRST()），則把），則把FOLLOWFOLLOW（A A）加至）加至FOLLOWFOLLOW（B B）中）中32 例例4.8 對于文法對于文法 ETE E +TE| T F

24、T T *FT| F (E)| i 我們構造每個非終結符的我們構造每個非終結符的FIRST和和FOLLOW集合集合 解：解：FIRST(E) = (, i FOLLOW(E) = ), # FIRST(E) = +, FOLLOW(E) = ), # FIRST(T) = (, i FOLLOW(T) = +, ), # FIRST(T) = *, FOLLOW(T) =+ , ), # FIRST(F) = (, i FOLLOW(F) =*, +, ) , # 在這里我們要注意在這里我們要注意FOLLOW(F)的求解過程其中：的求解過程其中：v因為因為T FT，所以，所以FIRST(T)

25、=*應加入應加入FOLLOW(F)中中v因為因為T ,所以將所以將FOLLOW(T)=+, ), #加到加到FOLLOW(F)中中33v構造分析表構造分析表M的算法是：的算法是：對文法對文法G的每個產生式的每個產生式A執(zhí)行第二步和第三步；執(zhí)行第二步和第三步；對于每個終結符對于每個終結符a FIRST( )，把，把A加到加到MA,a中；中；若若FIRST( ) ，則對任何的，則對任何的b FOLLOW(A)把把A加至加至MA,b中；中；把所有無定義的把所有無定義的MA,a標上標上“出錯標志出錯標志”v一個文法一個文法G的預測分析表的預測分析表M不含多重定義入口，當且僅不含多重定義入口，當且僅當該

26、文法為當該文法為LL(1)的的34例：例：構造文法構造文法4.1的分析表。的分析表。 ETE FIRST(TE) = (, i E +TE | FIRST(+TE)=+ FOLLOW(E)=)， T FT FIRST(FT) = (, i T *FT | FIRST(*FT)=* FOLLOW(T)=+,)，F(xiàn) (E) | i FIRST(E)=( FIRST(i)=i ETEE+TE|TFTT*FT|F(E) | ii+*()#ETETEE +TE TFTFTT *FT F i ( E )35i+*()#ETETEE +TE TFTFTT *FT F i ( E )符號棧符號棧#E#ET#E

27、TF#ETi#ET#E#ET+#ET#ETF#ETi#ET#ETF*#ETF#ETi#ET#E#輸入串輸入串i+i*i#i+i*i#i+i*i#i+i*i#+i*i#+i*i#+i*i#i*i#i*i#i*i#*i#*i#i#i#產生式產生式/動作動作ETETFTF iT E +TET FTF iT *FTF iT E 例：輸入例：輸入 i+i*iETEE+TE|TFTT*FT|F(E) | i36v例：例：已知文法已知文法GA為為AaABe|a BBb|d試給出與試給出與GA等價的等價的LL(1)文法文法GA構造構造GA的預測分析表，并給出輸入串的預測分析表，并給出輸入串aade#的分析過程

28、的分析過程 解：解：文法文法GA不是不是LL(1)文法的原因是：文法的原因是：n產生式產生式AaABe|a，使得，使得FIRST(aABe)FIRST(a)=a n產生式產生式BBb|d含有左遞歸含有左遞歸要構造與要構造與GA等價的等價的LL(1)文法，就要消除上述兩種問題文法，就要消除上述兩種問題37將將AaABe|a修改為：修改為：AaC CABe| 將將BBb|d修改為：修改為： BdB BbB| 因此得到文法因此得到文法GA： AaC BdB BbB| CABe| 求每一個非終結符的求每一個非終結符的FIRST集：集：FIRST(A)=a FIRST(B)=d FIRST(B)=b,

29、FIRST(C)=a, 求每一個非終結符的求每一個非終結符的FOLLOW集：集：FOLLOW(A)=#FIRST(Be)=#, d FOLLOW(B)=FIRST(e)=eFOLLOW(B)=FOLLOW(B)=e FOLLOW(C)=FOLLOW(A)= #, d對對BbB| ，有，有FIRST(B)FOLLOW(B)=b, e= 對對CABe| ，有，有FIRST(C)FOLLOW(C)= a, #, d= 而文法的其他產生式都只有一個非而文法的其他產生式都只有一個非 的右部，因而滿足的右部，因而滿足LL(1)文法的要求，文法的要求，即分析過程中不會出現(xiàn)回溯。即分析過程中不會出現(xiàn)回溯。所以

30、文法所以文法GA就是所求的與原文法等價的就是所求的與原文法等價的LL(1)文法。文法。38v構造構造GA的預測分析表的預測分析表對對AaC，F(xiàn)IRST(aC)=a, MA, a=” AaC”對對BdB，F(xiàn)IRST(dB)=d, MB, d=”BdB”對對BbB| ，F(xiàn)IRST(bB)=b, MB, b=”BbB”FOLLOW(B)=e, MB, e=” B”對對CABe| ，F(xiàn)IRST(ABe)=a, MC, a=”CABe”FOLLOW(C)=#, d, MC, #=”C”, MC, d=”C”39v所以得到的所以得到的LL(1)分析表是：分析表是：abde#AAaCBBdBBBbBBCCA

31、BeCC40v對輸入串對輸入串aade#的分析的分析過程如下：過程如下：步驟步驟符號棧符號棧輸入串輸入串產生式產生式/動作動作1#Aaade#AaC2#Caaade#匹配匹配3#Cade#CABe4#eBAade#AaC5#eBCaade#匹配匹配6#eBCde#C7#eBde#BdB8#eBdde#匹配匹配9#eBe#B10#ee#匹配匹配11#接受接受41例題與習題解答例題與習題解答例例1：試構造與下列文法試構造與下列文法GS等價的無左遞歸文法。等價的無左遞歸文法。 GS: SSa|Nb|c (1) N Sd|Ne|f (2)解：解：以以S,NS,N為序為序, ,對于對于（1）我們引入新非

32、終結符）我們引入新非終結符S 則：則： S NbS |cS 1 SaS| 2 將將 S代入代入 （2） N Ne |NbSd |cSd |f 引入新非終結符引入新非終結符N N cSdN |fN 3 N eN |bSdN | 442例例2：文法文法G的規(guī)則集為的規(guī)則集為; P begin d : X end X d : X | sY Y : sY | 做出該文法做出該文法LL(1)分析表。分析表。解：解： 非終結符只有非終結符只有 P , X ,Y 只有只有FIRST(Y)含有含有 ，則需要求出，則需要求出FOLLOW(Y)且且 FOLLOW(Y) =FOLLOE(X)=end則有則有LL(1

33、)表：表： begin d : end s #P begin d : X endX d : X sYY :sY 練練 習習43 例例3：給出語言給出語言L=1na0n1ma0m|n0, m=0 的的LL(1)文法文法GS并說并說明其理由。明其理由。 解：解：觀察句子觀察句子,發(fā)現(xiàn)可分成兩部分發(fā)現(xiàn)可分成兩部分 1na0n 和和 1ma0m兩部分中符號的兩部分中符號的個數(shù)個數(shù)n和和m沒有制約關系。則可改造成下列文法：沒有制約關系。則可改造成下列文法： S AB A 1A0 |1a0 B 1B0 |a 對于產生式對于產生式 A 1A0 |1a0 兩個候選式兩個候選式 FIRST(1A0) FIRST(1a0)=1 所以上邊文法不是所以上邊文法不是LL(1)文法：需左提公因子，得到：文法：需左提公因子，得到： S AB A 1C C A0 |a0 B 1B0 |a 此文法滿足此文法滿足LL(1)文法的要求。文法的要求。44例例4：文法文法GS： S(L) | a L L,S | S 請消除左遞歸，并構造請消除左遞歸，并構造LL(1)預測分析表，并說明對輸入串預測分析表，并說明對輸入串(a，(a，a)的分析過程。的分析過程。 解：解：將所給文法