1、國防科技大學計算機系國防科技大學計算機系602教研室教研室編譯原理王王 挺挺計算機系計算機系602教研室教研室Tel: 4573649(O)Email: 網(wǎng)上教學系統(tǒng)網(wǎng)上教學系統(tǒng): 070606302: 編譯原理編譯原理http:/ 國防科技大學計算機系國防科技大學計算機系602教研室教研室第一章第一章 引引 論論n本課程介紹程序設(shè)計語言編譯程序構(gòu)造的本課程介紹程序設(shè)計語言編譯程序構(gòu)造的基本原理和基本實現(xiàn)技術(shù)基本原理和基本實現(xiàn)技術(shù). .國防科技大學計算機系國防科技大學計算機系602教研室教研室第一章第一章 引引 論論n編譯理論與方法編譯理論與方法計算機科學與技術(shù)中理論和實踐相結(jié)合的最好計算機科

2、學與技術(shù)中理論和實踐相結(jié)合的最好典范典范 ACM 圖靈獎，授予在計算機技術(shù)領(lǐng)域作出突出圖靈獎，授予在計算機技術(shù)領(lǐng)域作出突出貢獻的科學家貢獻的科學家n程序設(shè)計語言、編譯理論與方法約占程序設(shè)計語言、編譯理論與方法約占1/3國防科技大學計算機系國防科技大學計算機系602教研室教研室源語言源語言程序程序目標語目標語言程序言程序翻譯翻譯程序程序翻譯翻譯一一. 什么是編譯程序什么是編譯程序q翻譯程序翻譯程序 把某一種語言程序把某一種語言程序( (稱為稱為源語言程序源語言程序) )等價地轉(zhuǎn)等價地轉(zhuǎn)換成另一種語言程序換成另一種語言程序( (稱為稱為目標語言程序目標語言程序) )的程序的程序國防科技大學計算機系

3、國防科技大學計算機系602教研室教研室高級語高級語言程序言程序機器語機器語言程序言程序結(jié)果結(jié)果編譯編譯程序程序翻譯翻譯運行運行一一. 什么是編譯程序什么是編譯程序q編譯程序編譯程序(compiler)(compiler) 把某一種把某一種高級語言程序高級語言程序等價地轉(zhuǎn)換成另一種等價地轉(zhuǎn)換成另一種低級語低級語言程序言程序( (如匯編語言或機器語言程序如匯編語言或機器語言程序) )的程序的程序診斷編譯程序診斷編譯程序優(yōu)化編譯程序優(yōu)化編譯程序交叉編譯程序交叉編譯程序可變目標編譯程序可變目標編譯程序國防科技大學計算機系國防科技大學計算機系602教研室教研室一一. 什么是編譯程序什么是編譯程序q解釋程

4、序解釋程序 把源語言寫的源程序作為輸入，但不產(chǎn)生目標程序，把源語言寫的源程序作為輸入，但不產(chǎn)生目標程序，而是邊解釋邊執(zhí)行源程序本身而是邊解釋邊執(zhí)行源程序本身源程序源程序結(jié)果結(jié)果解釋解釋程序程序解釋執(zhí)行解釋執(zhí)行國防科技大學計算機系國防科技大學計算機系602教研室教研室編譯程序編譯程序 vs. 解釋程序解釋程序編譯解釋國防科技大學計算機系國防科技大學計算機系602教研室教研室二二. . 編譯過程編譯過程n把英文翻譯為中文把英文翻譯為中文 識別出句子中的一個個單詞；識別出句子中的一個個單詞；分析句子的語法結(jié)構(gòu)；分析句子的語法結(jié)構(gòu)；根據(jù)句子的含義進行初步翻譯；根據(jù)句子的含義進行初步翻譯；對譯文進行修飾

5、；對譯文進行修飾；寫出最后的譯文。寫出最后的譯文。 詞法分析詞法分析語法分析語法分析中間代碼中間代碼產(chǎn)生產(chǎn)生優(yōu)化優(yōu)化目標代碼目標代碼產(chǎn)生產(chǎn)生國防科技大學計算機系國防科技大學計算機系602教研室教研室二二. . 編譯過程編譯過程n編譯程序的工作一般分為五個階段編譯程序的工作一般分為五個階段: :詞法分析詞法分析語法分析語法分析中間代碼產(chǎn)生中間代碼產(chǎn)生優(yōu)化優(yōu)化目標代碼產(chǎn)生目標代碼產(chǎn)生國防科技大學計算機系國防科技大學計算機系602教研室教研室1. 1. 詞法分析詞法分析n任務(wù)任務(wù): : 輸入源程序，對構(gòu)成源程序的字輸入源程序，對構(gòu)成源程序的字符串進行掃描和分解，識別出一個個單符串進行掃描和分解，識別

6、出一個個單詞符號。詞符號。n依循的原則：構(gòu)詞規(guī)則依循的原則：構(gòu)詞規(guī)則n描述工具：有限自動機描述工具：有限自動機nFOR I := 1 TO 100 DOFOR I := 1 TO 100 DO 保留字保留字 標識符標識符 等符等符 整常數(shù)整常數(shù) 保留字保留字 整常數(shù)整常數(shù) 保留字保留字國防科技大學計算機系國防科技大學計算機系602教研室教研室2. 2. 語法分析語法分析n任務(wù)任務(wù): :在詞法分析的基礎(chǔ)上，根據(jù)語言的語在詞法分析的基礎(chǔ)上，根據(jù)語言的語法規(guī)則把單詞符號串分解成各類語法單位。法規(guī)則把單詞符號串分解成各類語法單位。n依循的原則：語法規(guī)則依循的原則：語法規(guī)則n描述工具：上下文無關(guān)文法描述

7、工具：上下文無關(guān)文法nZ := X + 0.618 Z := X + 0.618 * * Y Y 算術(shù)表達式，賦值語句算術(shù)表達式，賦值語句國防科技大學計算機系國防科技大學計算機系602教研室教研室3. 3. 中間代碼產(chǎn)生中間代碼產(chǎn)生n任務(wù)任務(wù): :對各類不同語法范疇按語言的語義對各類不同語法范疇按語言的語義進行初步翻譯。進行初步翻譯。n依循的原則：語義規(guī)則依循的原則：語義規(guī)則n中間代碼中間代碼: :三元式，四元式，樹形結(jié)構(gòu)等三元式，四元式，樹形結(jié)構(gòu)等nZ:=X + 0.618 Z:=X + 0.618 * * Y Y 翻譯成四元式為翻譯成四元式為(1) (1) * * 0.618 Y T1 0

8、.618 Y T1(2) + X T1 T2(2) + X T1 T2(3) := T2 _ Z(3) := T2 _ Z國防科技大學計算機系國防科技大學計算機系602教研室教研室4. 4. 優(yōu)化優(yōu)化n任務(wù)：對于前階段產(chǎn)生的中間代碼進行任務(wù)：對于前階段產(chǎn)生的中間代碼進行加工變換，以期在最后階段產(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

9、 * * K; K; N := J + 10 N := J + 10 * * K; K; END END國防科技大學計算機系國防科技大學計算機系602教研室教研室中間代碼（一）中間代碼（一）序號序號 OPROPR OPN1OPN1 OPN2 RESULT OPN2 RESULT 注釋注釋(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

10、 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 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)國防科技大學計算機系國防科技大學計算機系602教研室教研室轉(zhuǎn)換后的等價代碼（二）轉(zhuǎn)換后的等價代碼（二）序號序號 OPROPR OPN1OPN1 OPN2OPN

11、2 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) :=:=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

12、 K K K:=K+1 K:=K+1(9)(9) j j(5)(5) goto (5) goto (5)(10)(10)國防科技大學計算機系國防科技大學計算機系602教研室教研室5. 5. 目標代碼產(chǎn)生目標代碼產(chǎn)生n任務(wù)任務(wù): : 把中間代碼變換成特定機器上的目把中間代碼變換成特定機器上的目標代碼。標代碼。n依賴于硬件系統(tǒng)結(jié)構(gòu)和機器指令的含義依賴于硬件系統(tǒng)結(jié)構(gòu)和機器指令的含義n目標代碼三種形式目標代碼三種形式: :絕對指令代碼絕對指令代碼: : 可直接運行可直接運行 可重新定位指令代碼可重新定位指令代碼: : 需要連接裝配需要連接裝配匯編指令代碼匯編指令代碼: : 需要進行匯編需要進行匯編國防

13、科技大學計算機系國防科技大學計算機系602教研室教研室模塊模塊Aa模塊模塊Bb模塊模塊Cc模塊模塊Aa模塊模塊Bb模塊模塊Cc模塊模塊Aa模塊模塊D模塊模塊Cc國防科技大學計算機系國防科技大學計算機系602教研室教研室5. 5. 目標代碼產(chǎn)生目標代碼產(chǎn)生n例例: b=a+2 MOV a, R1ADD #2, R1MOV R1, b 0001 01 00 00000000 *0011 01 10 00000010 0100 01 00 00000100 * L=00001111 0001 01 00 000011110011 01 10 000000100100 01 00 00010011 國

14、防科技大學計算機系國防科技大學計算機系602教研室教研室三三. . 編譯程序結(jié)構(gòu)編譯程序結(jié)構(gòu)n編譯程序總框編譯程序總框國防科技大學計算機系國防科技大學計算機系602教研室教研室四元式四元式單詞符號單詞符號語法單位語法單位四元式四元式目標代碼目標代碼詞法分析器詞法分析器語法分析器語法分析器語義分析與中間代碼語義分析與中間代碼生成器生成器優(yōu)化段優(yōu)化段源程序源程序表表格格管管理理出出錯錯處處理理目標代碼生成器目標代碼生成器國防科技大學計算機系國防科技大學計算機系602教研室教研室2. 2. 表格和表格管理表格和表格管理n常見的表格常見的表格: :符號名表，常數(shù)表，標號表，符號名表，常數(shù)表，標號表，入

15、口名表，過程引用表。入口名表，過程引用表。n格式格式: : 名字信息國防科技大學計算機系國防科技大學計算機系602教研室教研室例例: 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.國防科技大學計算機系國防科技大學計算機系602教研室

16、教研室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.表 0.1 符號名表 SNTNAMEINFORMATIONM形式參數(shù)，整型，值參數(shù)N形式參數(shù)，整型，值參數(shù)K整型，變量國防科技大學計算機系國防科技大學計算機系602教研室教研室表 0.2 常數(shù)表 CT值(VALUE)(1)1

17、(2)4PROCEDURE 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.國防科技大學計算機系國防科技大學計算機系602教研室教研室表 0.3 入口名表 ENTNAMEINFORMATION(1)INCWAP 二目子程序,入口四元式:1PROCEDURE INCWAP(MPROCEDURE IN

18、CWAP(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.國防科技大學計算機系國防科技大學計算機系602教研室教研室 表 0.4 標號表 LTNAME INFORMATION(1)START 四元式:(4)PROCEDURE INCWAP(MPROCEDURE INCWAP(M，N:INTEGER);N:INTEGER);LABEL START;

19、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.國防科技大學計算機系國防科技大學計算機系602教研室教研室表 0.1 符號名表 SNTNAMEINFORMATIONM形式參數(shù)，整型，值參數(shù)N形式參數(shù)，整型，值參數(shù)K整型，變量表 0.2 常數(shù)表 CT值(VALUE)(1)1(2)4表 0.3 入口名表 ENTNAMEINFORMATION(1)INCWAP 二目子程序,入口四元式:1 表 0.4 標號表 LTNAME

20、INFORMATION(1)START 四元式:(4)國防科技大學計算機系國防科技大學計算機系602教研室教研室 表 0.5 四元式表 QTOPROPN1OPN2RESULT(1)link(2)parINCWAP1M(3)parINCWAP2N(4)+M1K(5)+N4M(6):=KN(7) returnPROCEDURE INCWAP(MPROCEDURE INCWAP(M，N:INTEGER);N:INTEGER);LABEL START;LABEL START;VARVAR K:INTEGER; K:INTEGER;BEGINBEGINSTART:START: K:=M+1; K:=M+

21、1; M:=N+4; M:=N+4; N:=K; N:=K;END.END.國防科技大學計算機系國防科技大學計算機系602教研室教研室3. 3. 出錯處理出錯處理n出錯處理程序：出錯處理程序：發(fā)現(xiàn)發(fā)現(xiàn)源程序中的源程序中的錯誤，把錯誤，把有關(guān)錯誤信息報告給用戶有關(guān)錯誤信息報告給用戶語法錯誤語法錯誤語義錯誤語義錯誤 國防科技大學計算機系國防科技大學計算機系602教研室教研室4. 4. 遍遍(pass)(pass)n所謂所謂 遍遍 ， 就是對源程序或源程序的中間就是對源程序或源程序的中間表示從頭到尾掃描一次。表示從頭到尾掃描一次。n階段與遍是不同的概念。一遍可以由若干階段與遍是不同的概念。一遍可以由

22、若干段組成，一個階段也可以分若干遍來完成。段組成，一個階段也可以分若干遍來完成。國防科技大學計算機系國防科技大學計算機系602教研室教研室5. 編譯前端與后端編譯前端與后端n編譯前端編譯前端：與源語言有關(guān)，如詞法分析，語：與源語言有關(guān)，如詞法分析，語法分析，語義分析與中間代碼產(chǎn)生，與機器法分析，語義分析與中間代碼產(chǎn)生，與機器無關(guān)的優(yōu)化無關(guān)的優(yōu)化n編譯后端編譯后端：與目標機有關(guān)，與目標機有關(guān)的：與目標機有關(guān)，與目標機有關(guān)的優(yōu)化，目標代碼產(chǎn)生優(yōu)化，目標代碼產(chǎn)生優(yōu)點：減少對內(nèi)存容量的要求，程序邏輯結(jié)構(gòu)清優(yōu)點：減少對內(nèi)存容量的要求，程序邏輯結(jié)構(gòu)清晰晰; ; 優(yōu)化更充分，有利于移植。優(yōu)化更充分，有利于移

23、植。不足不足: : 編譯程序運行的效率低編譯程序運行的效率低源語言源語言中間語言中間語言目標語言目標語言前端前端后端后端國防科技大學計算機系國防科技大學計算機系602教研室教研室JAVA語言語言操作系統(tǒng)平臺操作系統(tǒng)平臺Java虛擬機虛擬機(解釋器解釋器)Java編譯器編譯器Java源程序源程序(.java)Java虛擬機代碼虛擬機代碼(.class)解釋執(zhí)行解釋執(zhí)行國防科技大學計算機系國防科技大學計算機系602教研室教研室四四. .編譯程序與程序設(shè)計環(huán)境編譯程序與程序設(shè)計環(huán)境 n程序設(shè)計環(huán)境程序設(shè)計環(huán)境 編輯程序編輯程序 編譯程序編譯程序連接程序連接程序 調(diào)試工具調(diào)試工具 n集成化的程序設(shè)計環(huán)

24、境集成化的程序設(shè)計環(huán)境 國防科技大學計算機系國防科技大學計算機系602教研室教研室.NET Framework與VS.NETOperating SystemCommon Language RuntimeADO.NET: Data and XMLASP.NET: Web Services & Web FormsWindowsFormsCommon Language SpecificationVisual Studio.NETVBC+C#JScript國防科技大學計算機系國防科技大學計算機系602教研室教研室五五. .編譯程序生成編譯程序生成n以匯編語言和機器語言為工具以匯編語言和機器語言

25、為工具優(yōu)點優(yōu)點: : 可以針對具體的機器，充分發(fā)揮計可以針對具體的機器，充分發(fā)揮計算機的系統(tǒng)功能。生成的程序效率高。算機的系統(tǒng)功能。生成的程序效率高。缺點缺點: : 程序難讀、難寫、易出錯、難維護、程序難讀、難寫、易出錯、難維護、生產(chǎn)的效率低。生產(chǎn)的效率低。國防科技大學計算機系國防科技大學計算機系602教研室教研室五五. .編譯程序生成編譯程序生成n高級語言書寫高級語言書寫 S T I S 源程序 T 目標程序 I 實現(xiàn)語言優(yōu)點優(yōu)點: : 程序易讀、易理解、容易維護、程序易讀、易理解、容易維護、生產(chǎn)的效率高。生產(chǎn)的效率高。缺點缺點: : 難以充分發(fā)揮計算機的系統(tǒng)功能，難以充分發(fā)揮計算機的系統(tǒng)功

26、能，生成的程序效率低。生成的程序效率低。國防科技大學計算機系國防科技大學計算機系602教研室教研室五五. .編譯程序生成編譯程序生成n高級語言書寫高級語言書寫利用已有的某種語言的編譯程序?qū)崿F(xiàn)另一語利用已有的某種語言的編譯程序?qū)崿F(xiàn)另一語言的編譯程序。言的編譯程序。L1語言語言A代碼代碼P1:A代碼代碼L2語言語言A代碼代碼P2: L1語言語言L2語言語言A代碼代碼P2:A代碼代碼國防科技大學計算機系國防科技大學計算機系602教研室教研室五五. .編譯程序生成編譯程序生成n 移植方法移植方法把一種機器上的編譯程序移植到另一種機器把一種機器上的編譯程序移植到另一種機器上。上。L語言語言A代碼代碼P1:A代碼代碼L語言語言B代碼代碼P2: L語言語言L語言語言B代碼代碼P2:A代碼代碼L語言語言B代碼代碼P2: L語言語言L語言語言B代碼代碼P2:B代碼代碼國防科技大學計算機系國防科技大學計算機系602教研室教研室L1+L2+.+LnL1+L2五五.