編譯原理Chapt1

1、江西財經(jīng)大學信息管理學院江西財經(jīng)大學信息管理學院編譯方法編譯方法主講：錢忠勝主講：錢忠勝 博士博士計算機系計算機系 系統(tǒng)軟件課程組系統(tǒng)軟件課程組Tel: 079183983891(O)Email: 編譯方法第一章第一章 引引 論論江西財經(jīng)大學信息管理學院江西財經(jīng)大學信息管理學院n介紹程序設計語言編譯程序構造的基本原介紹程序設計語言編譯程序構造的基本原理和基本實現(xiàn)技術理和基本實現(xiàn)技術n領悟計算機理論的精髓，從實現(xiàn)的角度重領悟計算機理論的精髓，從實現(xiàn)的角度重新審視軟件的開發(fā)新審視軟件的開發(fā)江西財經(jīng)大學信息管理學院江西財經(jīng)大學信息管理學院n編譯理論與方法編譯理論與方法計算機科學與技術中理論和實踐相結(jié)

2、合的最好計算機科學與技術中理論和實踐相結(jié)合的最好典范典范 ACM 圖靈獎，授予在計算機技術領域作出突出圖靈獎，授予在計算機技術領域作出突出貢獻的科學家貢獻的科學家n自自1966年以來（截止年以來（截止2009年）的所有年）的所有55位圖靈獎獲位圖靈獎獲得者中，有近得者中，有近1/3的科學家是因為在程序設計語言和的科學家是因為在程序設計語言和編譯方面的成就而獲得該項獎勵編譯方面的成就而獲得該項獎勵n程序設計語言和編譯的發(fā)展集中體現(xiàn)了計算機科學程序設計語言和編譯的發(fā)展集中體現(xiàn)了計算機科學發(fā)展的重要成果與精華發(fā)展的重要成果與精華n計算機應用能發(fā)展到今天，編譯技術的發(fā)展有著極計算機應用能發(fā)展到今天，編

3、譯技術的發(fā)展有著極其重要的、不可替代的作用其重要的、不可替代的作用江西財經(jīng)大學信息管理學院江西財經(jīng)大學信息管理學院n整個整個20世紀世紀50年代，編譯程序的編寫一直年代，編譯程序的編寫一直被認為是一個難題，第一個被認為是一個難題，第一個FORTRAN語言語言(1954年年)編譯程序整整花了編譯程序整整花了18年才得以實年才得以實現(xiàn)。現(xiàn)。江西財經(jīng)大學信息管理學院江西財經(jīng)大學信息管理學院源語言源語言程序程序目標語目標語言程序言程序翻譯翻譯程序程序翻譯翻譯一、什么是編譯程序一、什么是編譯程序q翻譯程序翻譯程序 把某一種語言程序把某一種語言程序( (稱為稱為源語言程序源語言程序) )等價地轉(zhuǎn)等價地轉(zhuǎn)換

4、成另一種語言程序換成另一種語言程序( (稱為稱為目標語言程序目標語言程序) )的程序的程序江西財經(jīng)大學信息管理學院江西財經(jīng)大學信息管理學院高級語高級語言程序言程序機器語機器語言程序言程序結(jié)果結(jié)果編譯編譯程序程序翻譯翻譯運行運行一、什么是編譯程序一、什么是編譯程序q編譯程序編譯程序(compiler)(compiler) 把某一種把某一種高級語言程序高級語言程序等價地轉(zhuǎn)換成另一種等價地轉(zhuǎn)換成另一種低級語低級語言程序言程序( (如匯編語言或機器語言程序如匯編語言或機器語言程序) )的程序的程序診斷編譯程序診斷編譯程序優(yōu)化編譯程序優(yōu)化編譯程序交叉編譯程序交叉編譯程序可變目標編譯程序可變目標編譯程序江

5、西財經(jīng)大學信息管理學院江西財經(jīng)大學信息管理學院一、什么是編譯程序一、什么是編譯程序q解釋程序解釋程序 把源語言寫的源程序作為輸入，但不產(chǎn)生目標程序，把源語言寫的源程序作為輸入，但不產(chǎn)生目標程序，而是邊解釋邊執(zhí)行源程序本身而是邊解釋邊執(zhí)行源程序本身源程序源程序結(jié)果結(jié)果解釋解釋程序程序解釋執(zhí)行解釋執(zhí)行江西財經(jīng)大學信息管理學院江西財經(jīng)大學信息管理學院編譯程序編譯程序 vs. 解釋程序解釋程序編譯解釋江西財經(jīng)大學信息管理學院江西財經(jīng)大學信息管理學院江西財經(jīng)大學信息管理學院江西財經(jīng)大學信息管理學院n在編譯的每個階段都有可能發(fā)現(xiàn)錯誤，最簡單的在編譯的每個階段都有可能發(fā)現(xiàn)錯誤，最簡單的處理是：終止編譯程序工

6、作，指出錯誤的地點和處理是：終止編譯程序工作，指出錯誤的地點和類型。類型。n目前有些高級語言的翻譯程序同時具有解釋和編目前有些高級語言的翻譯程序同時具有解釋和編譯兩種功能，在調(diào)試時采用解釋方式，調(diào)試過程譯兩種功能，在調(diào)試時采用解釋方式，調(diào)試過程中若發(fā)現(xiàn)錯誤，翻譯程序立即暫停工作，并用特中若發(fā)現(xiàn)錯誤，翻譯程序立即暫停工作，并用特殊記號指示當前錯誤的位置；當調(diào)試完成后，可殊記號指示當前錯誤的位置；當調(diào)試完成后，可利用翻譯程序的編譯功能，將源程序翻譯成機器利用翻譯程序的編譯功能，將源程序翻譯成機器碼程序。碼程序。n機器碼程序通常存放在擴展名為機器碼程序通常存放在擴展名為.exe的文件中，的文件中，它

7、可在操作系統(tǒng)環(huán)境下脫離翻譯程序直接運行。它可在操作系統(tǒng)環(huán)境下脫離翻譯程序直接運行。江西財經(jīng)大學信息管理學院江西財經(jīng)大學信息管理學院二、編譯過程二、編譯過程n把英文翻譯為中文把英文翻譯為中文 識別出句子中的一個個單詞；識別出句子中的一個個單詞；分析句子的語法結(jié)構；分析句子的語法結(jié)構；根據(jù)句子的含義進行初步翻譯；根據(jù)句子的含義進行初步翻譯；對譯文進行修飾；對譯文進行修飾；寫出最后的譯文。寫出最后的譯文。 詞法分析詞法分析語法分析語法分析中間代碼中間代碼產(chǎn)生產(chǎn)生優(yōu)化優(yōu)化目標代碼目標代碼產(chǎn)生產(chǎn)生江西財經(jīng)大學信息管理學院江西財經(jīng)大學信息管理學院二、編譯過程二、編譯過程n編譯程序的工作一般分為五個階段編譯

8、程序的工作一般分為五個階段: :詞法分析詞法分析語法分析語法分析中間代碼產(chǎn)生（語義分析）中間代碼產(chǎn)生（語義分析）優(yōu)化優(yōu)化目標代碼產(chǎn)生目標代碼產(chǎn)生江西財經(jīng)大學信息管理學院江西財經(jīng)大學信息管理學院1.1.詞法分析詞法分析n任務任務: : 輸入源程序，對構成源程序的字輸入源程序，對構成源程序的字符串進行掃描和分解，識別出一個個單符串進行掃描和分解，識別出一個個單詞符號。詞符號。n依循的原則：構詞規(guī)則依循的原則：構詞規(guī)則n描述工具：有限自動機描述工具：有限自動機nFOR i := 1 TO 100 DOFOR i := 1 TO 100 DO 保留字保留字 標識符標識符 等符等符 整常數(shù)整常數(shù) 保留字

9、保留字 整常數(shù)整常數(shù) 保留字保留字江西財經(jīng)大學信息管理學院江西財經(jīng)大學信息管理學院2.2.語法分析語法分析n任務任務: :在詞法分析的基礎上，根據(jù)語言的語在詞法分析的基礎上，根據(jù)語言的語法規(guī)則把單詞符號串分解成各類語法單位。法規(guī)則把單詞符號串分解成各類語法單位。n依循的原則：語法規(guī)則依循的原則：語法規(guī)則n描述工具：上下文無關文法描述工具：上下文無關文法nZ := X + 0.618 Z := X + 0.618 * * Y Y 算術表達式，賦值語句算術表達式，賦值語句江西財經(jīng)大學信息管理學院江西財經(jīng)大學信息管理學院3.3.中間代碼產(chǎn)生（語義分析）中間代碼產(chǎn)生（語義分析）n任務任務: :對各類不

10、同語法范疇按語言的語義對各類不同語法范疇按語言的語義進行初步翻譯。進行初步翻譯。n依循的原則：語義規(guī)則依循的原則：語義規(guī)則n中間代碼中間代碼: :三元式、四元式、語法樹、后三元式、四元式、語法樹、后綴式等綴式等nZ:=X + 0.618 Z:=X + 0.618 * * Y Y 翻譯成四元式為翻譯成四元式為(1) (1) * * 0.618 Y T1 0.618 Y T1(2) + X T1 T2(2) + X T1 T2(3) := T2 _ Z(3) := T2 _ Z江西財經(jīng)大學信息管理學院江西財經(jīng)大學信息管理學院4.4.優(yōu)化優(yōu)化n任務：對于前階段產(chǎn)生的中間代碼進行任務：對于前階段產(chǎn)生的

11、中間代碼進行加工變換，以期在最后階段產(chǎn)生更高效加工變換，以期在最后階段產(chǎn)生更高效的目標代碼。的目標代碼。n依循的原則：程序的等價變換規(guī)則依循的原則：程序的等價變換規(guī)則FOR K:=1 TO 100 DOFOR K:=1 TO 100 DO BEGIN BEGIN X:=I+1; X:=I+1; M := I + 10 M := I + 10 * * K; K; N := J + 10 N := J + 10 * * K; K; END END江西財經(jīng)大學信息管理學院江西財經(jīng)大學信息管理學院中間代碼（一）中間代碼（一）序號序號 OPROPR OPN1OPN1 OPN2 RESULT OPN2 R

12、ESULT 注釋注釋(1)(1) :=:=1 1 K K:=1 K K:=1(2)(2) jj100100 K K (10) if (100K) (10) if (100K) goto (10) goto (10)(3)(3) + +I I 1 1 X X X:=I+1 X:=I+1(4)(4) * *1010 K K T1 T1 T1:=10 T1:=10* *K K(5)(5) + +I I T1 T1 M M M:=I+T1 M:=I+T1(6)(6) * *1010 K K T2 T2 T2:=10 T2:=10* *K K(7)(7) + +J J T2 T2 N N N:=J+T2

13、 N:=J+T2(8)(8) + +K K 1 1 K K K:=K+1 K:=K+1(9)(9) j j (2) (2) goto (2) goto (2)(10)(10)400次加法次加法200次乘法次乘法江西財經(jīng)大學信息管理學院江西財經(jīng)大學信息管理學院轉(zhuǎn)換后的等價代碼（二）轉(zhuǎn)換后的等價代碼（二）序號序號 OPROPR OPN1OPN1 OPN2OPN2 RESULT RESULT注釋注釋(1)(1) + +I I 1 1 X X X:=I+1 X:=I+1(2)(2) :=:=I I M M M:=I M:=I(3)(3) :=:=J J N N N:=J N:=J(4)(4) :=:=

14、1 1 K K K:=1 K:=1(5)(5) jj100100 K K(10)(10) if (100K) if (100K) goto (10) goto (10)(6)(6) + +M M 10 10 M M M:=M+10 M:=M+10(7)(7) + +N N 10 10 N N N:=N+10 N:=N+10(8)(8) + +K K 1 1 K K K:=K+1 K:=K+1(9)(9) j j(5)(5) goto (5) goto (5)(10)(10)301次加法次加法江西財經(jīng)大學信息管理學院江西財經(jīng)大學信息管理學院5.5.目標代碼產(chǎn)生目標代碼產(chǎn)生n任務任務: : 把中間

15、代碼變換成特定機器上的目把中間代碼變換成特定機器上的目標代碼。標代碼。n依賴于硬件系統(tǒng)結(jié)構和機器指令的含義依賴于硬件系統(tǒng)結(jié)構和機器指令的含義n目標代碼三種形式目標代碼三種形式: :絕對指令代碼絕對指令代碼: : 可直接運行可直接運行 可重新定位指令代碼可重新定位指令代碼: : 需要連接裝配需要連接裝配匯編指令代碼匯編指令代碼: : 需要進行匯編需要進行匯編江西財經(jīng)大學信息管理學院江西財經(jīng)大學信息管理學院模塊模塊Aa模塊模塊Bb模塊模塊Cc模塊模塊Aa模塊模塊Bb模塊模塊Cc模塊模塊Aa模塊模塊Bb模塊模塊Cc江西財經(jīng)大學信息管理學院江西財經(jīng)大學信息管理學院5.5.目標代碼產(chǎn)生目標代碼產(chǎn)生江西財

16、經(jīng)大學信息管理學院江西財經(jīng)大學信息管理學院三、編譯程序結(jié)構三、編譯程序結(jié)構1.1.編譯程序總框編譯程序總框江西財經(jīng)大學信息管理學院江西財經(jīng)大學信息管理學院四元式四元式單詞符號單詞符號語法單位語法單位四元式四元式目標代碼目標代碼詞法分析器詞法分析器語法分析器語法分析器語義分析與中間代碼語義分析與中間代碼生成器生成器優(yōu)化段優(yōu)化段源程序源程序表表格格管管理理出出錯錯處處理理目標代碼生成器目標代碼生成器江西財經(jīng)大學信息管理學院江西財經(jīng)大學信息管理學院2.2.表格和表格管理表格和表格管理n常見的表格常見的表格: :符號名表，常數(shù)表，標號表，符號名表，常數(shù)表，標號表，過程引用表。過程引用表。n格式格式:

17、: 名字信息江西財經(jīng)大學信息管理學院江西財經(jīng)大學信息管理學院例例: PASCAL: PASCAL程序段：程序段：PROCEDURE INCWAP(MPROCEDURE INCWAP(M，N:INTEGER);N:INTEGER);LABEL START;LABEL START;VARVAR K:INTEGER; K:INTEGER;BEGINBEGINSTART:START: K:=M+1; K:=M+1; M:=N+4; M:=N+4; N:=K; N:=K;END.END.江西財經(jīng)大學信息管理學院江西財經(jīng)大學信息管理學院PROCEDURE INCWAP(MPROCEDURE INCWAP(

18、M，N:INTEGER);N:INTEGER);LABEL START;LABEL START;VARVAR K:INTEGER; K:INTEGER;BEGINBEGINSTART:START: K:=M+1; K:=M+1; M:=N+4; M:=N+4; N:=K; N:=K;END.END.江西財經(jīng)大學信息管理學院江西財經(jīng)大學信息管理學院PROCEDURE INCWAP(MPROCEDURE INCWAP(M，N:INTEGER);N:INTEGER);LABEL START;LABEL START;VARVAR K:INTEGER; K:INTEGER;BEGINBEGINSTART

19、:START: K:=M+1; K:=M+1; M:=N+4; M:=N+4; N:=K; N:=K;END.END.江西財經(jīng)大學信息管理學院江西財經(jīng)大學信息管理學院PROCEDURE INCWAP(MPROCEDURE INCWAP(M，N:INTEGER);N:INTEGER);LABEL START;LABEL START;VARVAR K:INTEGER; K:INTEGER;BEGINBEGINSTART:START: K:=M+1; K:=M+1; M:=N+4; M:=N+4; N:=K; N:=K;END.END.江西財經(jīng)大學信息管理學院江西財經(jīng)大學信息管理學院PROCEDUR

20、E INCWAP(MPROCEDURE INCWAP(M，N:INTEGER);N:INTEGER);LABEL START;LABEL START;VARVAR K:INTEGER; K:INTEGER;BEGINBEGINSTART:START: K:=M+1; K:=M+1; M:=N+4; M:=N+4; N:=K; N:=K;END.END.江西財經(jīng)大學信息管理學院江西財經(jīng)大學信息管理學院江西財經(jīng)大學信息管理學院江西財經(jīng)大學信息管理學院PROCEDURE INCWAP(MPROCEDURE INCWAP(M，N:INTEGER);N:INTEGER);LABEL START;LABE

21、L START;VARVAR K:INTEGER; K:INTEGER;BEGINBEGINSTART:START: K:=M+1; K:=M+1; M:=N+4; M:=N+4; N:=K; N:=K;END.END.江西財經(jīng)大學信息管理學院江西財經(jīng)大學信息管理學院3.3.出錯處理出錯處理n出錯處理程序：出錯處理程序：發(fā)現(xiàn)發(fā)現(xiàn)源程序中的源程序中的錯誤，把錯誤，把有關錯誤信息報告給用戶有關錯誤信息報告給用戶語法錯誤語法錯誤語義錯誤語義錯誤 江西財經(jīng)大學信息管理學院江西財經(jīng)大學信息管理學院4.4.遍遍(pass)(pass)n所謂所謂 遍遍 ， 就是對源程序或源程序的中間就是對源程序或源程序的中

22、間表示從頭到尾掃描一次。表示從頭到尾掃描一次。n階段與遍是不同的概念。一遍可以由若干階段與遍是不同的概念。一遍可以由若干段組成，一個階段也可以分若干遍來完成。段組成，一個階段也可以分若干遍來完成。江西財經(jīng)大學信息管理學院江西財經(jīng)大學信息管理學院5.5. 編譯前端與后端編譯前端與后端n編譯前端編譯前端：與源語言有關，如詞法分析，語：與源語言有關，如詞法分析，語法分析，語義分析與中間代碼產(chǎn)生，與機器法分析，語義分析與中間代碼產(chǎn)生，與機器無關的優(yōu)化無關的優(yōu)化n編譯后端編譯后端：與目標機有關，與目標機有關的：與目標機有關，與目標機有關的優(yōu)化，目標代碼產(chǎn)生優(yōu)化，目標代碼產(chǎn)生優(yōu)點：減少對內(nèi)存容量的要求，程

23、序邏輯結(jié)構清優(yōu)點：減少對內(nèi)存容量的要求，程序邏輯結(jié)構清晰晰; ; 優(yōu)化更充分，有利于移植。優(yōu)化更充分，有利于移植。不足不足: : 編譯程序運行的效率低編譯程序運行的效率低源語言源語言中間語言中間語言目標語言目標語言前端前端后端后端江西財經(jīng)大學信息管理學院江西財經(jīng)大學信息管理學院四、四、編譯程序與程序設計環(huán)境編譯程序與程序設計環(huán)境 n程序設計環(huán)境程序設計環(huán)境 編輯程序編輯程序 編譯程序編譯程序連接程序連接程序 調(diào)試工具調(diào)試工具 n集成化的程序設計環(huán)境集成化的程序設計環(huán)境 江西財經(jīng)大學信息管理學院江西財經(jīng)大學信息管理學院五、編譯程序生成五、編譯程序生成n以匯編語言和機器語言為工具以匯編語言和機器語

24、言為工具優(yōu)點優(yōu)點: : 可以針對具體的機器，充分發(fā)揮計可以針對具體的機器，充分發(fā)揮計算機的系統(tǒng)功能。生成的程序效率高。算機的系統(tǒng)功能。生成的程序效率高。缺點缺點: : 程序難讀、難寫、易出錯、難維護、程序難讀、難寫、易出錯、難維護、生產(chǎn)的效率低。生產(chǎn)的效率低。江西財經(jīng)大學信息管理學院江西財經(jīng)大學信息管理學院五、編譯程序生成五、編譯程序生成n高級語言書寫高級語言書寫 S T I S 源程序 T 目標程序 I 實現(xiàn)語言優(yōu)點優(yōu)點: : 程序易讀、易理解、容易維護、程序易讀、易理解、容易維護、生產(chǎn)的效率高。生產(chǎn)的效率高。缺點缺點: : 難以充分發(fā)揮計算機的系統(tǒng)功能，難以充分發(fā)揮計算機的系統(tǒng)功能，生成的

25、程序效率低。生成的程序效率低。江西財經(jīng)大學信息管理學院江西財經(jīng)大學信息管理學院五、編譯程序生成五、編譯程序生成n高級語言書寫高級語言書寫利用已有的某種語言的編譯程序?qū)崿F(xiàn)另一語利用已有的某種語言的編譯程序?qū)崿F(xiàn)另一語言的編譯程序。言的編譯程序。L1語言語言A代碼代碼P1:A代碼代碼L2語言語言A代碼代碼P2: L1語言語言L2語言語言A代碼代碼P2:A代碼代碼同一臺機器同一臺機器不同的語言不同的語言江西財經(jīng)大學信息管理學院江西財經(jīng)大學信息管理學院五、編譯程序生成五、編譯程序生成n 移植方法移植方法把一種機器上的編譯程序移植到另一種機器把一種機器上的編譯程序移植到另一種機器上。上。L語言語言A代碼代

26、碼P1:A代碼代碼L語言語言B代碼代碼P2: L語言語言L語言語言B代碼代碼P2:A代碼代碼L語言語言B代碼代碼P2: L語言語言L語言語言B代碼代碼P2:B代碼代碼同一種語言同一種語言不同的機器不同的機器江西財經(jīng)大學信息管理學院江西財經(jīng)大學信息管理學院L1+L2+.+LnL1+L2五、編譯程序生成五、編譯程序生成n自展技術自展技術L1江西財經(jīng)大學信息管理學院江西財經(jīng)大學信息管理學院五、編譯程序生成五、編譯程序生成n編譯程序自動產(chǎn)生編譯程序自動產(chǎn)生編譯程序編譯程序- -編譯程序，編譯程序書寫系統(tǒng)編譯程序，編譯程序書寫系統(tǒng)LEX LEX 詞法分析程序產(chǎn)生器詞法分析程序產(chǎn)生器YACC YACC 語

27、法分析程序產(chǎn)生器語法分析程序產(chǎn)生器編譯程序編譯程序自動產(chǎn)生器自動產(chǎn)生器L語言的語法描述語言的語法描述語義描述語義描述目標語言目標語言或機器描述或機器描述L語言的語言的編譯程序編譯程序江西財經(jīng)大學信息管理學院江西財經(jīng)大學信息管理學院六、關于學習編譯原理六、關于學習編譯原理n 構造編譯程序的前提構造編譯程序的前提掌握源語言掌握源語言掌握目標語言掌握目標語言掌握編譯方法掌握編譯方法江西財經(jīng)大學信息管理學院江西財經(jīng)大學信息管理學院六、關于學習編譯原理六、關于學習編譯原理n意義意義學習編譯程序構造的原理、方法、技術學習編譯程序構造的原理、方法、技術更好地理解高級語言更好地理解高級語言編譯的原理和方法有助于構造一些實用的工具編譯的原理和方法有助于構造一些實用的工具培養(yǎng)計算思維，提升系統(tǒng)認識能力（在系統(tǒng)的級別上重新認識算法培養(yǎng)計算思維，提升系統(tǒng)認識能力（在系統(tǒng)的級別上重新認識算法和程序）和程序）培養(yǎng)形式化描述能力培養(yǎng)形式化描述能力 提高對計算機系統(tǒng)的總體認識能力提高對計算機系統(tǒng)的總體認識能