1、第四章 語法分析,自上而下分析法： 從文法的開始符號出發(fā)，反復使用文法的產(chǎn)生式，為待識別句子建立一個最左推導，以尋找與輸入符號串匹配的推導。 自下而上分析法： 從輸入符號串開始，逐步進行歸約，從葉子節(jié)點，由底上向上逐步建立一棵完整的語法樹，直至歸約到文法的開始符號（樹根）。,自頂向下分析 遞歸下降分析法（遞歸子程序法） 預測分析法LL(1) 注意：首先消除左遞歸和提取左公因子。 自底向上分析 算符優(yōu)先分析 LR分析: SLR(1), LR(1), LALR(1),FIRST集：設G=(VN,VT,P，S)是上下文無關文法 FIRST（）=a| =a,aVT, , V* 若 =則規(guī)定FRIST（

2、）,*,*,開始符號FIRST集和后跟符號FOLLOW集,自上而下分析,LL(1)文法,一個文法G是LL（1）的，當且僅當對于G的每一個非終結符的任何兩個不同產(chǎn)生式ij ，下面的條件成立：,FIRST (i ) FIRST (j ) = ,對文法G的所有含有產(chǎn)生式的非終結符A定義它的FOLLOW(A)。對含有的A的所有候選式i ，希望有 FIRST (i ) FOLLOW (A ) = ,LL(1)含義： L：從左至右順序掃描輸入串； L：按最左推導方式； 1：每一次推導均向前查看一個輸入符號準確指派產(chǎn)生式。 LL(1)文法性質: 沒有公共左因子； 無二義性； 不含左遞歸。,LL（1）文法的判

3、別： 對文法計算FIRST、FOLLOW集合 判別文法是否為LL（1）文法,1）消除左遞歸： 消除直接左遞歸, 消除間接左遞歸,非LL(1)文法的改造,2）提左公因子 將產(chǎn)生式A | 變換為： A B B | ,預測分析法,對文法構造預測分析表,2）根據(jù)算法構造預測分析表,ETE,ETE,TFT,TFT,Fi,F (E),E +TE,E,E,T *FT,T,T,T,1）求出各非終結符的First集和Follow集,從輸入串開始，進行最左歸約，直到到達文法的開始符號為止。 大致過程：把輸入符號逐個移進到一個棧里，當棧頂形成某個產(chǎn)生式的右部（ 句柄）時，把棧頂?shù)倪@一部分替換成（歸約為）它的左部符號

4、。稱作“移進歸約”分析。,自下而上分析,算符優(yōu)先分析法,在文法的相鄰符號之間建立優(yōu)先關系。 從左到右依次掃描某句型中符號，且每掃視一個符號都檢查它和后繼符號間優(yōu)先關系，以期找到句柄。,簡單優(yōu)先分析法,在文法的相鄰終結符號符號之間建立優(yōu)先關系。 從左到右依次掃描某句型中符號，且每掃視一個符號都檢查它和后繼符號間優(yōu)先關系，以期找到最左素短語。,優(yōu)先分析,LR分析,特征: 規(guī)范的； 符號棧中的符號是規(guī)范句型的前綴，且不含句柄以后的任何符號(活前綴)； 分析決策依據(jù)棧頂狀態(tài)和現(xiàn)行輸入符號。識別活前綴的 DFA. 四種技術 LR(0) SLR(1) LR(1) LALR(1),LR分析器概述,總控程序,

5、LR分析器的總控程序,總控程序的動作由當前棧頂狀態(tài)Sm和掃描符號ai查表決定。 1、移進 把(Sm, ai)的下一狀態(tài)S=GOTOSm，ai連同掃描符號進棧，棧頂成(S, ai)，掃描指針后移； 2、歸約 用產(chǎn)生式A進行歸約。若的長度為，則彈出棧頂項，使棧頂狀態(tài)變?yōu)镾m- ，然后將(Sm- ,A)的下一狀態(tài)S=GOTOSm- ,A連同A一起入棧，棧頂變?yōu)?S,A)。掃描指針不動，即不改變現(xiàn)行輸入符號。 3、接受 4、報錯 注：不管哪一類分析程序，總控程序的動作都一樣。,例：由文法的LR分析表分析輸入串 i*ii的LR動作過程。 1） E E+T 2）E T 3）T T*F 4）T F 5）F

6、(E) 6）F i,利用這張分析表分析輸入串i*i+i的LR動作過程,0,#,i*i+i#,05,移進，狀態(tài)轉到5,03,#F,*i+i#,r6歸約，0態(tài)遇F轉3態(tài),#i,*i+i#,02,#T,*i+i#,r4歸約，0態(tài)遇T轉2態(tài),027,#T*,i+i#,移進，狀態(tài)轉到7,0275,#T*i,+i#,移進，狀態(tài)轉到5,02710,#T*F,+i#,r6歸約,02,#T,+i#,r3歸約,01,#E,+i#,r2歸約,016,#E+,i#,移進,0165,#E+i,#,移進,0163,#E+F,#,r6歸約,0169,#E+T,#,r4歸約,01,#E,#,r1歸約,成功,構造LR分析表的基

7、本方法,構造基本分析表的基本策略： 構造文法G的一個DFA，用于識別所有活前綴。 生成文法G的LR項目 對文法G的每個產(chǎn)生式右部添加一個圓點，稱為G的一個LR(0)項目(簡稱項目)。 A 或A,Aa,aVT 移進項目 AB,BVN 待歸約項目,A 歸約項目,SS, SS 接受項目,識別所有規(guī)范句型全部活前綴的DFA,DFA的每個狀態(tài)由若干LR項目集來表示。整個狀態(tài)集稱為LR項目集規(guī)范族。 將文法進行拓廣，即增加產(chǎn)生式SS，并令S S作為初態(tài)項目I0。 定義和構造項目集的閉包。設I是拓廣文法G的一個項目集，則定義和構造I的閉包CLOSURE(I)。 確定狀態(tài)轉移。 利用轉換函數(shù)GO實現(xiàn)。 構造L

8、R項目集規(guī)范族Q。將所有項目集，以及所有狀態(tài)間轉移全部構造出來。,LR(0)分析表的構造,SLR(1)分析表的構造,LR(1)分析表的構造,LR(1)項目：形如(A，a)的二元式稱為LR(1)項目。其中A是文法的一個產(chǎn)生式，a是終結符，稱為搜索符。,若項目AIk，則對任何終結符a Follow(A)，置ACTIONk,a=rj；其中j是產(chǎn)生式A的編號，即按該產(chǎn)生式進行歸約。,若規(guī)約項目AIi, 則對任何終結符a, 置ACTIONi, a為“用產(chǎn)生式A進行規(guī)約”，簡記為“rj”;其中，假定A為文法G的第j個產(chǎn)生式；,1、設文法G(S): SS+aF|aF|+aF F*aF|*a 消除左遞歸和回溯

9、； 構造相應的FIRST和FOLLOW集合； 構造預測分析表,練習,答： SaFS|+aFS S+aFS| F*aF FF|,FIRST(S)=a,+ FOLLOW(S)=#FIRST(S)=+, FOLLOW(S)=#FIRST(F)=* FOLLOW(F)=+,#FIRST(F)=*,) FOLLOW(F)=+,#,2、文法G：EE+T|P T T+P P (E)|i 則句型P+T+i的句柄和最左素短語分別是_ A. P+T和i B. P和i C. i和P+T+i D. P和P 3、文法G：Sb|(T) T T,S|S 則FIRSTVT(T)=_ A. b,( B. b,) C. b,(

10、, ， D. b,), 4、文法G：EE*T|T T T+i|i 句子1+2*8+6按該文法進行歸約，其值為_ A. 23 B. 42 C. 30 D. 17 5、一個_指明了在分析過程的某時刻所能看到產(chǎn)生式多大一部分。 A. 活前綴 B. 前綴 C. 項目 D. 項目集 6、對LR分析表的構造，不可能存在 動作沖突。 A移進/移進 B歸約/歸約 C移進/歸約 D.以上都不對,B,C,B,C,A,7、請指出下圖的LR分析表（a）、（b）、（c）分屬于LR(0)、SLR(1)、LR(1)中的那一種，并說明理由。,解答： (a)表為LR(1)分析表，因為在不同行有相同的r2存在； (b)表為LR(

11、0)分析表，因為有rj的行每行都填滿了，且同一行j相同，不同行j不同 (c)表為SLR(1)分析表，因為存在沒填滿rj的行，且不同行j不同。,(a),(b),(c),8、給出文法GS及圖所示的LR(1)項目集規(guī)范族中的0、1、2、3、4。 GS: SS;B|B BBaA|A Ab(S),S S;B, #/;,S B, #/;,B BaA, #/;/a,B A, #/;/a,A b(S), #/;/a,S S , #,S S ;B, #/;,S B , #/;,B B aA, #/;/a,B A , #/;/a,A b (S), #/;/a,b,A,B,S,9、判定下面的文法是否為SLR(1)文法，若不是，請重寫一個等價的SLR（1）文法。 GS: SMa|bMc|dc|bda Md,S S,S Ma,S bMc,S dc,S bda,M d,S b Mc,S b da,S bd a,M d ,b,M d,d,因為a是M的后繼符號之一，因此在上面最右邊一個項目集中有移進歸約沖突。等價的SLR（1）文法GS: S da|bdc|dc|bda,10、證明文法GS：SAaAb|BbBa A B 是LL（1）文法，但不是SLR（1）文法。,證明：FIRST(A