第四章語法自頂向下方法

1、主要內容：主要內容：l自頂向下語法分析的基本思想自頂向下語法分析的基本思想l三個重要的集合三個重要的集合 l自頂向下分析的條件自頂向下分析的條件l遞歸下降語法分析遞歸下降語法分析lLL(1)LL(1)語法分析語法分析q語法分析器和識別器語法分析器和識別器q語法分析的功能語法分析的功能q語法錯誤類別語法錯誤類別q語法錯誤的處理語法錯誤的處理 q自頂向下分析的基本思想自頂向下分析的基本思想 l 語法分析器和識別器語法分析器和識別器l 語法分析器的功能：語法分析器的功能：l 語法錯誤類別語法錯誤類別 程序的開始符，語句（表達式）的開始符程序的開始符，語句（表達式）的開始符 （后繼符）錯（后繼符）錯

2、標識符（常量）錯：該出現(xiàn)時未出現(xiàn)標識符（常量）錯：該出現(xiàn)時未出現(xiàn) 括號類錯誤：不匹配括號類錯誤：不匹配 分隔符錯：分隔符錯：assignmentassignmentToken/TokenListParser語法樹語法樹/語法錯誤信息語法錯誤信息l 語法錯誤處理語法錯誤處理 要求：要求：報告錯誤出現(xiàn)的位置報告錯誤出現(xiàn)的位置 修復錯誤并繼續(xù)檢查后續(xù)部分修復錯誤并繼續(xù)檢查后續(xù)部分 執(zhí)行開銷不應太大執(zhí)行開銷不應太大 處理策略：處理策略：1 1）緊急方式恢復；）緊急方式恢復； 2 2）短語級恢復；）短語級恢復；3 3）出錯產生式；）出錯產生式；4 4）全局糾正。）全局糾正。 從文法開始符出發(fā)試圖推導出所

3、給的終極符串。從文法開始符出發(fā)試圖推導出所給的終極符串。 例例 Gz : 1 Z aBd 2 B d 3 B c 4 B bB 對給定的終極符串對給定的終極符串abcd，推導過程：推導過程： Z 1 aBd 4 abBd 3 abcd Z Za aB Bd db bB Bc c aBd # abcd # aBd # abcd # MatchMatch Bd # bcd # Bd # bcd # DerivationDerivation bBd # bcd # bBd # bcd # MatchMatch Bd # cd # Bd # cd # DerivationDerivation cd #

4、 cd # cd # cd # MatchMatch d # d # d # d # MatchMatch # # Success # # Success自頂向下的語法分析過程【自頂向下的語法分析過程【Sf,Rest,Action(D/M/S/E)Sf,Rest,Action(D/M/S/E)】 Z # abcd # DerivationZ # abcd # Derivation設設G=(VT，VN，S，P)是上下文無關文法是上下文無關文法, (VT VN )*，則：，則： First( )= a VT | * a. (if * then else ) 作用：可以根據當前的輸入符號是屬于哪個產

5、生作用：可以根據當前的輸入符號是屬于哪個產生式右部的首符集而決定選擇相應產生式進行推導。式右部的首符集而決定選擇相應產生式進行推導。 文法文法G3S: S aA | d A bAS | 輸入串輸入串W=abd。自頂向下的推導過程為自頂向下的推導過程為: S aA abAS abS abd相應的語法樹為：相應的語法樹為：S Sa aA Ab bA AS S d d設設G=(VG=(VT T，V VN N，S S，P)P)是上下文無關文法，是上下文無關文法，A A V VN N，S S是開始符號，則：是開始符號，則：Follow(A)Follow(A)= a = a V VT T | S | S+

6、 + .Aa. .Aa. (if S(if S* *.A then # else .A then # else ) ) 作用：當文法中存在作用：當文法中存在產生式產生式形如：形如：A A時，時，如果當前的字符屬于如果當前的字符屬于Follow(A)Follow(A)，則用空取，則用空取代代A A的出現(xiàn)。的出現(xiàn)。lFirst(First( ) )= a = a V VT T | | * * a. a. (if (if * * then then else else ) ) lFollow(A)Follow(A)= a = a V VT T | S | S+ + .Aa. .Aa. (if S(i

7、f S* *.A then # else .A then # else ) )lPredict(APredict(A ) ) = First(= First( ) ) ， 當當First(First( ) )= First(= First( )-)- Follow(A) Follow(A) ，當當First(First( ) )對每一文法符號對每一文法符號X X計算計算First(X)First(X)l若若X X V VT T, ,First(X)=XFirst(X)=Xl若若X X V VN N則則 First(X)=a| XFirst(X)=a| Xaa PSet,aPSet,a V VT

8、 T l若若X X V VN N, ,且有產生式且有產生式X X, ,則則 First(X)First(X)l若若X X V VN N, ,有產生式有產生式X XY Y1 1Y Y2 2YYn n，且且Y Y1 1,Y,Y2 2,Y,Yi i V VN N 當當Y Y1 1,Y,Y2 2,Y,Yi-1i-1* * ， 則則First(YFirst(Y1 1)-)- ,First(Y,First(Y2 2)-)- , First(Y First(Yi-1i-1)-)- , First(Y, First(Yi i) )都包含在都包含在First(X)First(X)中中。 當當Y Yi i * *

9、 (i=1,2,n), (i=1,2,n), 將將 并入并入First(X)First(X) 中。中。若符號串若符號串 = =X X1 1X X2 2XXn n，l當當X X1 1,X,X2 2,X,Xi-1i-1* * ，X Xi i不能不能 * * ，則，則First(First( )=)= 1 1i-1i-1(First(X(First(Xj j)-)- ) ) First(X First(Xi i) )l若所有若所有X Xi i都能都能* * ，則，則First(First( )= )= 1 1n nFirst(XFirst(Xj j) )1:1:對所有對所有A A V VN N，令令

10、Follow(A):= Follow(A):= ；對開始符對開始符S,S, 令令Follow(S):=# Follow(S):=# ； 2:2:若有產生式若有產生式AxByAxBy， 如果如果First(y) First(y) 則：則： Follow(B):= First(y)Follow(B):= First(y) 否則否則 Follow(B):=(First(y)Follow(B):=(First(y) ) ) Follow(A) Follow(A)3:3:重復重復2 2和和3 3，直至對所有，直至對所有A A V VN N，F(xiàn)ollow(A)Follow(A)收收 斂為止。斂為止。lPr

11、edict(A ) = First( ) ，當當First( )不含不含 = First( )- Follow(A) ， 當當First( )含含 例子：E E T E T EE E + T E + T E | | T T F T F TT T * * F T F T | | F F id | ( E ) id | ( E )lPredict( ETE ) = first(TE) = id , ( lPredict( E +TE ) = first(+TE) = + lPredict( E ) = follow(E) = ) , # lPredict( T FT ) = first(FT) =

12、 id , ( lPredict( T *FT ) = first(*FT) = * lPredict( T ) = follow(T) = + , ) , # lPredict( F id ) = first(id) = id lPredict( F (E) ) = first(E) = ( q自頂向下分析方法的條件：自頂向下分析方法的條件： predict(Apredict(A k k) ) predict(Apredict(A j j )=)=，當當k k j j q產生式產生式AA 被選擇的條件是：被選擇的條件是： 當前的輸入符屬于當前的輸入符屬于predict(predict(AA

13、) )。q至多一個產生式被選擇的條件是：至多一個產生式被選擇的條件是： predict(A predict(A k k) ) predict(A predict(A j j )=)=，當當k k j jl自頂向下分析的條件自頂向下分析的條件遞歸下降法遞歸下降法( (Recursive-Descent Parsing)Recursive-Descent Parsing) 對每個非終極符按其產生式結構產生相對每個非終極符按其產生式結構產生相應語法分析子程序應語法分析子程序. . 終極符產生匹配命令終極符產生匹配命令 非終極符則產生調用命令非終極符則產生調用命令 文法遞歸相應子程序也遞歸，所以稱這文

14、法遞歸相應子程序也遞歸，所以稱這種方法為種方法為遞歸子程序方法或遞歸下降法遞歸子程序方法或遞歸下降法則對應產生式右部的語法分析程序部分則對應產生式右部的語法分析程序部分如下：如下：begin Match($while)； Exp； Match($do)； Stm end whilewhile xyxy dodo if xz then x:= x+y else x:= yif xz then x:= x+y else x:= y Begin Begin Match($while)Match($while); ; ExpExp; ; Match($do)Match($do); ; StmStm E

15、nd Endl 當產生式中形如當產生式中形如: : A A 1 1| | 2 2| | | | n n 則按下面的方法編寫子程序則按下面的方法編寫子程序A A： procedure A( )procedure A( ) begin if token begin if token Predict(APredict(A1 1) then ) then ( ( 1 1) ) else else if token if token Predict(APredict(A2 2) then ) then ( ( 2 2) ) else else if token if token Predict(APre

16、dict(An) then n) then ( ( n n) ) else else err( ) err( ) end end 其中對其中對 i=X1X2Xn， ( i) = (X1); (X2); (Xn); 如果如果X V VN N， (X)= X 如果如果X V VT T， (X)= Match(X) 如果如果X= , ( ) = skip(空語句空語句)假設有文法假設有文法Z Z a a B B a aB B b b B B | | c c則相應的遞歸子程序可如下：則相應的遞歸子程序可如下：procedure procedure Z( )Z( )beginbegin ifif tok

17、en=a token=a thenthen Match(a)Match(a)； B B； Match(a)Match(a) else else err( )err( )end;end;procedureprocedure B ( ) B ( )beginbegin if if token = b token = b thenthen Match(b)Match(b); ; B; B; elseelse if if token = token = c c thenthen Match(c);Match(c); elseelse err( )err( )end;end;主程序：主程序：BeginB

18、egin ReadToken ReadToken; ; Z Z endendReadTokenReadTokenReadTokenReadTokenlLL(1)LL(1)是是LL(k)LL(k)的特例的特例, ,其中的其中的k k則表示向前看則表示向前看k k個符號。個符號。 lLL(1)LL(1)方法和遞歸下降法屬于同一級別的自頂方法和遞歸下降法屬于同一級別的自頂向下分析法，但有一些區(qū)別向下分析法，但有一些區(qū)別. . 遞歸下降法對每個非終極符產生子程序，而遞歸下降法對每個非終極符產生子程序，而LL(1)LL(1)方方法則產生法則產生LLLL分析表；分析表；遞歸下降法能判斷每個產生式的結束，而

19、遞歸下降法能判斷每個產生式的結束，而LL(1)LL(1)方法方法則不能；則不能；遞歸下降法分析法不用符號棧，而遞歸下降法分析法不用符號棧，而LL(1)LL(1)方法則用符方法則用符號棧。號棧。 對于任一非終極符對于任一非終極符A A，其任意兩個產生式其任意兩個產生式AA 和和AA ，都要滿足下面條件：都要滿足下面條件： Predict(APredict(A ) ) Predict(APredict(A )= )= 滿足這一條件的文法稱為滿足這一條件的文法稱為LL(1)LL(1)文法。文法。 l文法文法GA: A GA: A a B c a B c11l B B d d 22| b B| b B

20、33l輸入串：輸入串：abbdcabbdcl分析過程：分析過程：l( (A,abbdc)A,abbdc)1 1(aBc,abbdc) (aBc,abbdc) (Bc,bbdc) (Bc,bbdc) 3 3(bBc,bbdc) (bBc,bbdc) (Bc,bdc) (Bc,bdc) 3 3 (bBc,bdc) (bBc,bdc) (Bc,dc) (Bc,dc) 2 2 (dc,dc) (dc,dc) (c,c) (c,c) ( , )( , )l替換：替換：當當X X1 1 V VN N時選相應候選式時選相應候選式 去替換去替換X X1 1。l匹配：匹配：當當X X1 1 V VT T時它與時

21、它與Y Y1 1進行匹配，其結果可進行匹配，其結果可能成功，也可能失敗，如果成功則去掉能成功，也可能失敗，如果成功則去掉X X1 1和和Y Y1 1，否則報錯。否則報錯。l接受：接受：當格局為（空，空）時報分析成功。當格局為（空，空）時報分析成功。l報錯：報錯：出錯后，停止分析。出錯后，停止分析。lLLLL（1 1）語法分析表（）語法分析表（LLLL（1 1）矩陣）矩陣）lLLLL（1 1）語法分析驅動程序）語法分析驅動程序lT T：V VN N V VT T P P Error Error T(A,t)=AT(A,t)=A 若若t t Predict( APredict( A ) ) T(A

22、,t)=Error T(A,t)=Error 否則否則 其中其中P P表示所有產生式的集合表示所有產生式的集合 StackInputa 棧為空情形的處理棧為空情形的處理 X VT情形的處理情形的處理 X VN情形的處理情形的處理 XLL1分析分析表表11初始化：初始化： Stack :=emptyStack :=empty；Push(S)Push(S)；22讀下一個輸入符：讀下一個輸入符： Read(a)Read(a)；33若當前格局是若當前格局是( ( empty, # )empty, # )，則成功結束；則成功結束； 否則轉下；否則轉下；44設當前格局為（設當前格局為（ X., a.)X.

23、, a.)，則則 若若 X X V VT T & X=a& X=a 則則 Pop(1)Pop(1)；Read(a)Read(a)；goto 3 goto 3 若若 X X V VT T & X & X a a 則則 ErrorError； 若若 X X V VN N，則：則： if T(X,a)=XYif T(X,a)=XY1 1Y Y2 2 Y Yn n then Pop(1)then Pop(1)；Push(YPush(Y1 1 , ,.,Y,Yn n) )；goto3 goto3 else Error else Error l文法文法G:G: E TE1E+TE2| 3TFT4T*FT5| 6Fid7|(E)8符號串符號串 i + i i + i * * i #