1、第一章 引論,編譯程序 把某一種高級語言程序等價地轉(zhuǎn)換成另一種低級語言程序(如匯編語言或機器語言程序)的程序，是一種翻譯程序。,C語言 Pascal語言 Fortran語言,編譯之后是否可以執(zhí)行？,表 格 管 理,詞法分析,語法分析,語義分析,中間代碼生成,代碼優(yōu)化,目標(biāo)代碼生成,出 錯 處 理,源程序,目標(biāo)程序,編譯過程,begin x:=9; if x0 then x:=2*x+1/3 end,3 begin 1 x 4 := 2 9 5 ; 3 if 1 x 4 2 0 3 then 1 x 4 := 2 2 4 * 1 x 4 + 2 1 4 / 2 3 3 end 5 #,語法分析,

2、對于文法： GE: E-E+T|T T-T*F|F F-i|(E) 分析句子i+i*i是否符合文法。,輸入串i+i*i#的分析過程,7,6,5,4,3,2,1,所用產(chǎn)生式,剩余輸入串,分析棧,步驟,begin x:=9; if x0 then x:=2*x+1/3 end,ac:=d;ecdfc:=d*c+d/db,其中終結(jié)符對應(yīng)關(guān)系： begin a endb IDc NUMd ife thenf,文法G: （1）：=beginend （2）：= （3）：=;|CD|ecdfc:=d*c+d/db,A-a B b B-CD D-;CD|ecdfc:=d*c+d/db,A-a B b B-CD

3、 D-;CD| G-HI I-+HI|-HI|HI|JK K-*JK|/J| if x0 then x:=2*x+1/3 end,二元式 3 begin 1 x 4 := 2 9 5 ; 3 if 1 x 4 2 0 3 then 1 x 4 := 2 2 4 * 1 x 4 + 2 1 4 / 2 3 3 end 5 #,按照詞法規(guī)則構(gòu)造正規(guī)式（正規(guī)文法）； 正規(guī)式NFA（正規(guī)文法NFA）； NFADFA； DFA最小化； 根據(jù)DFA構(gòu)造詞法分析程序。,正規(guī)式和正規(guī)文法是等價的正規(guī)式和正規(guī)文法與有窮自動機是等價的,RG Gr RNFA NFAR GNFA NFAG,RNFA,x,y,(a|b

4、)* abb,x,0,y,(a|b)*,abb,a,1,2,b,b,I Ia Ib Ic,1,4 2,3 ,2,3 2 4 3,4,2 2 4 ,4 ,3,4 3,4,（1）構(gòu)造一張表，它共有+1列 第一列表示新的狀態(tài)，后三列表示當(dāng)前狀態(tài)遇到中的字符a，b，c后的后繼狀態(tài)。 （2）第一行第一列為-closure(S) （3）求IaIbIc （4）對表中出現(xiàn)的新狀態(tài)分別計算IaIbIc （5）將狀態(tài)子集重新命名,-closure（S）=,初始劃分得，非終態(tài)組1,2,3,4和終態(tài)組5,6,7 檢查子集1,2,3,4 1,2,3,4a=?不屬于已有的子集，故要繼續(xù)劃分 又 1,2a=6,7包含于5,

5、6,7 3,4a=1,4包含于1,2,3,4 可以分為1,2,3,4和5,6,7 考察1,2 1,2b=3包含于3,4 不再分割1,2集合，劃分仍為1,2,3,4和5,6,7,第五章 自上而下語法分析,語法分析的任務(wù) 對于文法： GE: E-E+T|T T-T*F|F F-i|(E) 分析句子i+i*i是否符合文法。,第五章 自上而下語法分析,要求文法是LL(1)文法。 若文法中包含左公共因子或左遞歸，那么一定不是LL(1)文法。 構(gòu)造預(yù)測分析表 語法分析,3 輸入串i+i*i#的分析過程,7,6,5,4,3,2,1,所用產(chǎn)生式,剩余輸入串,分析棧,步驟,第六章 自底向上語法分析法,自底向上語

6、法分析的思想、實現(xiàn)方式、關(guān)鍵問題,1.簡單優(yōu)先分析法,基本思想：按一定原則定義文法中所有符號（終結(jié)符和非終結(jié)符）之間的優(yōu)先關(guān)系，按照這種關(guān)系確定歸約過程中的句柄并實行歸約。 是一種規(guī)范歸約。 要求文法是簡單優(yōu)先文法 簡單優(yōu)先分析法準(zhǔn)確、規(guī)范，但效率低，不實用，不流行。,句型N1 Nn中NiNj是句柄，則 N1Ni-1 Ni Nj Nj+1Nn,2.算符優(yōu)先分析法,基本思想：只定義文法中終結(jié)符之間的優(yōu)先關(guān)系（不考慮非終結(jié)符），并由這種關(guān)系指導(dǎo)分析過程 要求文法是算符優(yōu)先文法 不是規(guī)范歸約 算符優(yōu)先分析法分析速度快，特別適用于表達(dá)式的分析。缺點是不規(guī)范，常常要采用適當(dāng)措施克服其缺點。,分析過程 i

7、+i*i,步驟,符號棧,輸入串,優(yōu)先關(guān)系,動作,1,2,3,4,5,6,7,8,9,10,11,#,#i,#E,#E+,#E+i,#E+E,#E+E*,#E+E*i,#E+E*E,#E+E,#E,#,#,#,#,i#,*i#,*i#,i*i#,+i*i#,+i*i#,i+i*i#,#i,i+,#+,+i,i*,+*,*i,i#,*#,+#,移進,移進,移進,移進,移進,規(guī)約,規(guī)約,規(guī)約,規(guī)約,規(guī)約,接受,構(gòu)造算符優(yōu)先關(guān)系表，證明算法優(yōu)先文法 FirstVT LastVT = ,實際上在算符優(yōu)先分析過程中，我們每次對棧頂形成的最左素短語進行歸約，而不是對句柄進行歸約。,7LR分析法,一.LR分析

8、法,LR分析方法是當(dāng)前最被廣泛應(yīng)用的無回溯的“移進-歸約”方法。,根據(jù)當(dāng)前分析棧中的符號串（通常以狀態(tài)表示） 和向右順序查看輸入串的K個（K=0）符號就可唯一地確定分析器的動作是移進還是歸約和用哪個產(chǎn)生式歸約。,LR(0),SLR(1),根據(jù)當(dāng)前分析棧中的符號串（通常以狀態(tài)表示）和向右順序查看輸入串的K個（K=0）符號就可唯一地確定分析器的動作是移進還是歸約和用哪個產(chǎn)生式歸約。,四種LR類型： LR(0)、SLR(1)、LALR(1)、LR(1)功能逐個增強 四種LR類型的文法是真包含關(guān)系,文法GS：(1) S aAcBe(2) A b(3) A Ab(4) B d,輸入串a(chǎn)bbcde的分析過

9、程,(1),0,#,abbcde#,S2,(2),02,#a,bbcde#,S4,(3),024,#ab,bcde#,r2,3,(4),023,#aA,bcde#,S6,(5),0236,#aAb,cde#,r3,3,(6),023,#aA,cde#,S5,(7),0235,#aAc,de#,S8,(8),02358,#aAcd,e#,r4,7,(9),02357,#aAcB,e#,S9,(10),023579,#aAcBe,#,r1,1,(11),01,#S,#,acc,四種分析表構(gòu)造,LR(0)分析表與SLR(1)分析表 不同： SLR(1)分析表對于LR(0)項目集規(guī)范族中的歸約項目A，

10、只在Follow(A)終結(jié)符的對應(yīng)位置置rj，而LR(0)分析表將所有終結(jié)符對應(yīng)位置均置rj。 LR(1)分析表與LALR(1)分析表 不同： LR(1)利用First()作為向前搜索符 LALR(1)對LR(1)項目集規(guī)范族合并同心集，有可能造成新的歸約和歸約沖突,合并同心項目集可能會引起沖突 同心集的合并不會引起新的移進歸約沖突 同心集的合并有可能產(chǎn)生新的歸約歸約沖突,G: (0) S S (1) S aAd (2) S bBd (3) S aBe (4) S bAe (5) A c (6) B c,項目集,A c , d B c , e,項目集,A c , e B c , d,合并同心集

11、,A c , d/e B c , d/e,由于合并同心即后存在 歸約歸約沖突， 因此不是LALR(1)文法,LALR的能力弱于LR,構(gòu)造LR(1)項目集規(guī)范族 (見書),產(chǎn)生歸約-歸約沖突,第八章,語義分析的任務(wù)，主要方法,例 簡單算術(shù)表達(dá)式求值的屬性文法 L E print(E.val) EE1+T E.val :E1.val +T.val ET E.val :T.val TT1*digit T.val :T1.val * digit.lexval Tdigit T.val :digit.lexval ,分析并計算23*5的過程,(0) SE if error1 then print E.V

12、AL (1) EE1+E2 if E1.TYPE=int AND E2.TYPE=int then begin E.VAL:=E1.VAL + E2.VAL; E.YTPE:=int; end else if E1.TYPE=real AND E2.TYPE=real then begin E.VAL:=E1.VAL + E2.VAL; E.YTPE:=real; end else error=1 (3) E(E1) E.VAL:=E1.VAL;E.TYPE:=E1.TYPE (4) En E.VAL:=n.LEXVAL;E.TYPE:=n.LEXTYPE ,布爾表達(dá)式的翻譯,直接翻譯 優(yōu)化翻

13、譯,if af then X:=Y+Z else X:=Y-Z 翻譯為四元式序列：,E,E,or,E,E3,and,E4,a,b,c,d,e,f,1,2,if,then,C,S1,X :=,else,TP,S2,S,1：( j , a , b , 0 ) 2：( jump,3) 3：( j , c , d , 5) 4：( jump, 0 ) 5：( j , e , f , 1) 6：( jump,4) E.begin=1 E.true=5 E.false=6 7: (+,y,z,t1) 8: (:=,t1,-,x) q=9 9: (jump,-,-,0) 10: (-,y,z,t2) 11: (:=,t2,-,x) S.chain=9,7,7,C.chain=6,E,Y + Z,X :=,Y - Z,E,10,Tp.chain=9,0=9,S.chain=9,0=9,S1.chain=0,S2.chain=0,10,第十一章,優(yōu)化技術(shù) 基本塊劃