編譯原理第一章緒論

1、編譯原理編譯原理山東科技大學(xué)信息學(xué)院張鵬張鵬v本課程主要內(nèi)容涉及：本課程主要內(nèi)容涉及：高級(jí)程序設(shè)計(jì)語(yǔ)言高級(jí)程序設(shè)計(jì)語(yǔ)言形式語(yǔ)言理論的基本概念形式語(yǔ)言理論的基本概念構(gòu)造編譯程序的基本概念、原理和技術(shù)構(gòu)造編譯程序的基本概念、原理和技術(shù)基于基于形式語(yǔ)言理論形式語(yǔ)言理論有關(guān)概念來(lái)討論有關(guān)概念來(lái)討論編譯實(shí)現(xiàn)問(wèn)題編譯實(shí)現(xiàn)問(wèn)題即：即： 編譯原理編譯原理=形式語(yǔ)言理論形式語(yǔ)言理論+ +編譯技術(shù)編譯技術(shù)1. 1. 主要內(nèi)容主要內(nèi)容2.2.編譯理論與其他課程關(guān)系編譯理論與其他課程關(guān)系編譯理論編譯理論自動(dòng)機(jī)和形式語(yǔ)言離散數(shù)學(xué)數(shù)據(jù)結(jié)構(gòu)操作系統(tǒng)信息的表示和組織信息的表示和組織 理論支持理論支持 控制對(duì)象控制對(duì)象高級(jí)語(yǔ)言

2、實(shí)施實(shí)施基礎(chǔ)基礎(chǔ)3.編譯程序在計(jì)算機(jī)系統(tǒng)中的地位v編譯系統(tǒng)是一種系統(tǒng)軟件。軟件：計(jì)算機(jī)系統(tǒng)中的程序及其文檔。系統(tǒng)軟件：居于計(jì)算機(jī)系統(tǒng)中最靠近硬件的一層，其他軟件一般都通過(guò)系統(tǒng)軟件發(fā)揮作用。和具體的應(yīng)用領(lǐng)域無(wú)關(guān)，如編譯系統(tǒng)和操作系統(tǒng)等。語(yǔ)言處理系統(tǒng)：把軟件語(yǔ)言書(shū)寫(xiě)的各種源代碼處理成可在計(jì)算機(jī)上執(zhí)行的程序，如編譯系統(tǒng)。裸機(jī)操作系統(tǒng)語(yǔ)言處理系統(tǒng)應(yīng)用軟件層計(jì)算機(jī)系統(tǒng)計(jì)算機(jī)系統(tǒng)v用于編譯器編譯器的設(shè)計(jì)v一般的軟件設(shè)計(jì)：文本編輯器、自動(dòng)排版、模式識(shí)文本編輯器、自動(dòng)排版、模式識(shí)別、程序自動(dòng)驗(yàn)證、程序自動(dòng)調(diào)試、別、程序自動(dòng)驗(yàn)證、程序自動(dòng)調(diào)試、v程序格式化工具程序格式化工具：使程序呈現(xiàn)清晰的結(jié)構(gòu)(Source

3、insight, Editplus)v編譯原理在反病毒技術(shù)反病毒技術(shù)中的研究和應(yīng)用 v交叉編譯交叉編譯技術(shù)：如嵌入式應(yīng)用嵌入式應(yīng)用v硬件描述語(yǔ)言硬件描述語(yǔ)言及其編譯技術(shù)：如芯片設(shè)芯片設(shè)計(jì)v為計(jì)算機(jī)分析和理解自然語(yǔ)言提供參考為計(jì)算機(jī)分析和理解自然語(yǔ)言提供參考4.為什么要學(xué)習(xí)編譯原理？5.課程考核方法v閉卷考試,同時(shí)作業(yè)完成情況和上機(jī)實(shí)踐的結(jié)果占一定的比例。 v考試成績(jī) = v 80%考試成績(jī)+考勤考勤和作業(yè) （20%）v（1）編譯原理（第二版），編譯原理（第二版），清華大學(xué)出版社，張素琴，呂映芝等編著，2005。v（2）陳火旺等，程序設(shè)計(jì)語(yǔ)言編譯原理程序設(shè)計(jì)語(yǔ)言編譯原理 （第3版），國(guó)防工業(yè)出版

4、社，2000v（3 3）陳意云、張昱，編譯原理編譯原理，高等教育出版社， 2003v（4 4）編譯原理及實(shí)踐）編譯原理及實(shí)踐 馮博琴譯 機(jī)械工業(yè)出版社 2000 年 3 月(lex and yacc 介紹，Tiny語(yǔ)言)6. 教材和參考書(shū)編譯原理的經(jīng)典書(shū)籍龍書(shū)，虎書(shū)，鯨書(shū)v龍書(shū)龍書(shū)(Dragon book)Alfred V.Aho, Ravi Sethi Jeffrey D .Ullman , Compilers:Principles, Techniques, and Tools, Addison-Wesly,1986 。v第二版已經(jīng)出版。v國(guó)內(nèi)教材的主要參考。英文第一版中文第一版紅龍書(shū)本科教

5、學(xué)版 英文第二版中文第二版紫龍書(shū)英文第三版？綠龍書(shū)vAlfred VAho 哥倫比亞大學(xué)，美國(guó)科學(xué)與藝術(shù)學(xué)院及國(guó)家工程學(xué)院院士，曾獲得IEEE的馮諾伊曼獎(jiǎng)。 Jeffrey D. Ullman 斯坦福大學(xué)的計(jì)算機(jī)科學(xué)教授。杰出教育家，出版了15本著作，發(fā)表了170篇技術(shù)論文 v鯨書(shū)鯨書(shū)(Whale book)Steven S.MuchnickSteven S.MuchnickAdvanced Compiler Design and Advanced Compiler Design and ImplementationImplementationv高級(jí)編譯器設(shè)計(jì)與實(shí)現(xiàn) 趙克佳譯 機(jī)械工業(yè)出版社

6、2005年7月 v本書(shū)涵蓋了現(xiàn)代微處理器編譯器的設(shè)計(jì)和實(shí)現(xiàn)方面的所有高級(jí)主題。v深入闡述優(yōu)化問(wèn)題v虎書(shū)虎書(shū)(Tiger book)書(shū)名是：Modern Compiler Implementation Modern Compiler Implementation in Java/C+/ML, Second Editionin Java/C+/ML, Second Edition作者是：Andrew W.AppelAndrew W.Appel, with Jens Palsberg 現(xiàn)代編譯原理-C語(yǔ)言描述 趙克佳譯 人民郵電出版社 2006年4月 v書(shū)中專(zhuān)門(mén)提供了一個(gè)用C語(yǔ)言編寫(xiě)的實(shí)習(xí)項(xiàng)目，包括

7、前端和后端設(shè)計(jì)，可以在一學(xué)期內(nèi)創(chuàng)建一個(gè)功能完整的編譯器。 1.1 程序設(shè)計(jì)語(yǔ)言概述 程序設(shè)計(jì)語(yǔ)言：程序設(shè)計(jì)語(yǔ)言：用來(lái)編寫(xiě)計(jì)算機(jī)程序的語(yǔ)言。 JAVASCRIPT, ASP, PHP, PERL20其他面向特定應(yīng)用領(lǐng)域的語(yǔ)言1互連網(wǎng)應(yīng)用：HTML、XML2計(jì)算機(jī)輔助設(shè)計(jì)：MATLAB3集成電路設(shè)計(jì)：VHDL、Verilog4虛擬現(xiàn)實(shí)：VRML問(wèn)題： 如何將形形色色的語(yǔ)言翻譯成可以在計(jì)算機(jī)上運(yùn)行的0、1串低級(jí)語(yǔ)言低級(jí)語(yǔ)言v在1940年左右，電子數(shù)字計(jì)算機(jī)剛出現(xiàn)，程序設(shè)計(jì)都是用機(jī)器語(yǔ)言（Machine Language） v機(jī)器語(yǔ)言機(jī)器語(yǔ)言：直接用計(jì)算機(jī)能夠識(shí)別的二進(jìn)制代碼指令來(lái)編寫(xiě)程序的語(yǔ)言。由二

8、進(jìn)制的指令代碼組成。v1 + 3 1 + 3 表示為表示為 10000001 10000001 00000001 00000001 1000001110000011v屬性：最底層的語(yǔ)言，不需要翻譯就可以直接被計(jì)算機(jī)硬件識(shí)別。對(duì)應(yīng)不同的計(jì)算機(jī)硬件有不同的機(jī)器語(yǔ)言。v特點(diǎn)：執(zhí)行速度快，但編寫(xiě)程序的難度大，修改、調(diào)試不方便，直觀性差，不易移植.v匯編語(yǔ)言匯編語(yǔ)言：又稱為符號(hào)語(yǔ)言。與機(jī)器語(yǔ)言一一對(duì)應(yīng)，采用能幫助記憶的英文縮寫(xiě)符號(hào)（指令助記符）來(lái)代替機(jī)器語(yǔ)言指令中的操作碼，用地址符號(hào)來(lái)代替地址碼。v用指令助記符及地址符號(hào)書(shū)寫(xiě)的指令稱為匯編指令，用匯編指令編寫(xiě)的程序稱為匯編語(yǔ)言源程序。v X+Y X+Y

9、表示為表示為 ADD X YADD X Yv機(jī)器不能直接識(shí)別匯編語(yǔ)言程序，必須把它翻譯為機(jī)器語(yǔ)言程序才能執(zhí)行。 匯編語(yǔ)言特點(diǎn)匯編語(yǔ)言特點(diǎn)v優(yōu)點(diǎn)：優(yōu)點(diǎn)：大大提高了編程的速度和準(zhǔn)確度，人們至今仍在使用，在編碼需要極快的速度和極高的簡(jiǎn)潔程度時(shí)尤為如此。v缺點(diǎn)：缺點(diǎn)：編寫(xiě)不容易，閱讀和理解困難；嚴(yán)格依賴于特定的機(jī)器，為一種計(jì)算機(jī)編寫(xiě)的代碼在應(yīng)用于另一種計(jì)算機(jī)時(shí)必須完全重寫(xiě)。低級(jí)語(yǔ)言特點(diǎn)低級(jí)語(yǔ)言特點(diǎn)( (缺點(diǎn)缺點(diǎn)) )： 低級(jí)語(yǔ)言是依賴于具體的計(jì)算機(jī)硬件的語(yǔ)言，使用起來(lái)既繁瑣又容易出錯(cuò)，程序不便于閱讀和交流，實(shí)用性差。高級(jí)語(yǔ)言高級(jí)語(yǔ)言v高級(jí)語(yǔ)言高級(jí)語(yǔ)言：與具體的計(jì)算機(jī)硬件無(wú)關(guān)，是面向：與具體的計(jì)算機(jī)硬件

10、無(wú)關(guān)，是面向問(wèn)題的程序設(shè)計(jì)語(yǔ)言，其表達(dá)方式接近于自然問(wèn)題的程序設(shè)計(jì)語(yǔ)言，其表達(dá)方式接近于自然語(yǔ)言和數(shù)學(xué)語(yǔ)言，易于人們接受和掌握。語(yǔ)言和數(shù)學(xué)語(yǔ)言，易于人們接受和掌握。 v采用類(lèi)似于采用類(lèi)似于數(shù)學(xué)公式數(shù)學(xué)公式的書(shū)寫(xiě)方式：的書(shū)寫(xiě)方式：x x = 1 + 3 = 1 + 3v特點(diǎn)特點(diǎn)：獨(dú)立于具體的計(jì)算機(jī)硬件，程序的編制：獨(dú)立于具體的計(jì)算機(jī)硬件，程序的編制和調(diào)試方便，通用性和可移植性好。和調(diào)試方便，通用性和可移植性好。v在計(jì)算機(jī)執(zhí)行之前，需要通過(guò)編譯程序翻譯成在計(jì)算機(jī)執(zhí)行之前，需要通過(guò)編譯程序翻譯成目標(biāo)語(yǔ)言程序，或需要通過(guò)解釋程序邊解釋?zhuān)繕?biāo)語(yǔ)言程序，或需要通過(guò)解釋程序邊解釋?zhuān)厛?zhí)行。邊執(zhí)行。v時(shí)間與空

11、間效率比較低。時(shí)間與空間效率比較低。 比較比較 機(jī)器語(yǔ)言機(jī)器語(yǔ)言匯編語(yǔ)言匯編語(yǔ)言高級(jí)語(yǔ)言高級(jí)語(yǔ)言硬件識(shí)別硬件識(shí)別是唯一可以識(shí)是唯一可以識(shí)別的語(yǔ)言別的語(yǔ)言不可識(shí)別不可識(shí)別不可識(shí)別不可識(shí)別是否可直是否可直接執(zhí)行接執(zhí)行 可直接執(zhí)行可直接執(zhí)行不可，需匯不可，需匯編、連接編、連接不可，需編譯不可，需編譯/ /解解釋、連接釋、連接 特點(diǎn)特點(diǎn)面向機(jī)器面向機(jī)器占用內(nèi)存少占用內(nèi)存少執(zhí)行速度快執(zhí)行速度快使用不方便使用不方便面向機(jī)器面向機(jī)器占用內(nèi)存少占用內(nèi)存少執(zhí)行速度快執(zhí)行速度快較為直觀較為直觀與機(jī)器語(yǔ)言與機(jī)器語(yǔ)言一一對(duì)應(yīng)一一對(duì)應(yīng)v面向問(wèn)題面向問(wèn)題/ /對(duì)象對(duì)象v占用內(nèi)存大占用內(nèi)存大v執(zhí)行速度相對(duì)慢執(zhí)行速度相對(duì)慢v

12、標(biāo)準(zhǔn)化程度高標(biāo)準(zhǔn)化程度高v便于程序交換，便于程序交換，使用方便使用方便 定位定位低級(jí)語(yǔ)言，極低級(jí)語(yǔ)言，極少使用少使用低級(jí)語(yǔ)言，低級(jí)語(yǔ)言，很少使用很少使用高級(jí)語(yǔ)言，種類(lèi)多，高級(jí)語(yǔ)言，種類(lèi)多，常用常用各級(jí)語(yǔ)言的比較各級(jí)語(yǔ)言的比較什么是編譯程序v編譯程序是現(xiàn)代計(jì)算機(jī)系統(tǒng)的基本組成部分。編譯程序是現(xiàn)代計(jì)算機(jī)系統(tǒng)的基本組成部分。編譯程序的功能：把高級(jí)語(yǔ)言程序翻譯成等編譯程序的功能：把高級(jí)語(yǔ)言程序翻譯成等價(jià)的低級(jí)語(yǔ)言程序。價(jià)的低級(jí)語(yǔ)言程序。v源程序源程序( (稱作源語(yǔ)言稱作源語(yǔ)言) ) v目標(biāo)程序目標(biāo)程序( (稱作目標(biāo)語(yǔ)言稱作目標(biāo)語(yǔ)言) )編譯程序高級(jí)語(yǔ)言源程序的執(zhí)行通常分兩個(gè)階段:源程序(高級(jí)語(yǔ)言)編譯

13、程序計(jì)算機(jī)目標(biāo)程序(機(jī)器語(yǔ)言)編譯階段編譯階段初始數(shù)據(jù)目標(biāo)程序計(jì)算機(jī)運(yùn)行系統(tǒng)計(jì)算結(jié)果運(yùn)行階段運(yùn)行階段源程序源程序目標(biāo)程序目標(biāo)程序可執(zhí)行程序可執(zhí)行程序 編輯編輯 程序程序匯編或匯編或編譯程序編譯程序連接連接 程序程序用于編寫(xiě)高用于編寫(xiě)高級(jí)語(yǔ)言程序級(jí)語(yǔ)言程序把目標(biāo)程序以及所需的功能庫(kù)等轉(zhuǎn)換成一個(gè)可執(zhí)行的裝入程序。完成此功能的程序叫連接程序。編譯方式是將源程序整個(gè)地編譯方式是將源程序整個(gè)地翻譯成目標(biāo)程序的方式。完翻譯成目標(biāo)程序的方式。完成此功能的程序叫編譯程序。成此功能的程序叫編譯程序。解釋型的語(yǔ)言解釋型的語(yǔ)言-腳本語(yǔ)言腳本語(yǔ)言 1.腳本語(yǔ)言腳本語(yǔ)言(JavaScript,VBscript等等)介于

14、介于HTML和和C, C+, Java, C#等編程語(yǔ)言之間。等編程語(yǔ)言之間。 HTML是格式化和鏈結(jié)文本。是格式化和鏈結(jié)文本。 編程語(yǔ)言通常用于向機(jī)器發(fā)出一系列復(fù)雜的指編程語(yǔ)言通常用于向機(jī)器發(fā)出一系列復(fù)雜的指令。令。 2.腳本語(yǔ)言與編程語(yǔ)言也有很多相似地方，其腳本語(yǔ)言與編程語(yǔ)言也有很多相似地方，其函數(shù)與編程語(yǔ)言比較相象一些。但是編程語(yǔ)函數(shù)與編程語(yǔ)言比較相象一些。但是編程語(yǔ)言的語(yǔ)法和規(guī)則更為嚴(yán)格和復(fù)雜一些言的語(yǔ)法和規(guī)則更為嚴(yán)格和復(fù)雜一些. v3. 腳本語(yǔ)言一般都有相應(yīng)的腳本引擎（虛腳本語(yǔ)言一般都有相應(yīng)的腳本引擎（虛擬機(jī)）來(lái)解釋執(zhí)行。比如：擬機(jī)）來(lái)解釋執(zhí)行。比如：JAVASCRIPT, ASP,

15、 PHP,PERL要解釋器才能運(yùn)行，都是要解釋器才能運(yùn)行，都是腳本語(yǔ)言。腳本語(yǔ)言。v4.腳本語(yǔ)言是一種解釋性的語(yǔ)言腳本語(yǔ)言是一種解釋性的語(yǔ)言, 不象不象cc+等可以編譯獨(dú)立執(zhí)行的等可以編譯獨(dú)立執(zhí)行的exe 文件。文件。v5.腳本語(yǔ)言代碼一般都是以文本形式存在腳本語(yǔ)言代碼一般都是以文本形式存在,類(lèi)似于一種命令的序列。類(lèi)似于一種命令的序列。編譯和解釋程序的運(yùn)行方式：功能功能工作結(jié)果工作結(jié)果實(shí)現(xiàn)技術(shù)上實(shí)現(xiàn)技術(shù)上編譯編譯程序程序源程序的一個(gè)轉(zhuǎn)換轉(zhuǎn)換系統(tǒng)源程序的目標(biāo)代碼目標(biāo)代碼把中間代碼轉(zhuǎn)換成目標(biāo)程序解釋解釋程序程序源程序的一個(gè)執(zhí)行執(zhí)行系統(tǒng)源程序的執(zhí)行結(jié)果執(zhí)行結(jié)果執(zhí)行中間代碼解釋程序和編譯程序的區(qū)別編譯

16、相當(dāng)于全文翻譯，全部翻譯完才執(zhí)行。解釋就相當(dāng)于同聲翻譯，邊翻譯邊執(zhí)行。 特點(diǎn)：v1編譯器：工作效率高，即時(shí)間快、空間省；交互性與動(dòng)態(tài)特性差、可移植性差。大多數(shù)采用此種方法翻譯；v2解釋器：工作效率低，即時(shí)間慢、空間費(fèi)；交互性與動(dòng)態(tài)特性好、可移植性好。基本功能：二者相同；v所采用的技術(shù)：從翻譯的角度來(lái)講，兩種方式所涉及的原理、方法、技術(shù)相似。注意：注意：v編譯結(jié)果不一定編譯成機(jī)器代碼，只需要編編譯結(jié)果不一定編譯成機(jī)器代碼，只需要編譯成機(jī)器可以運(yùn)行的代碼，這里的機(jī)器也可譯成機(jī)器可以運(yùn)行的代碼，這里的機(jī)器也可以是虛擬機(jī)。通常編譯的結(jié)果是以是虛擬機(jī)。通常編譯的結(jié)果是exeexe文件或文件或中間代碼文件

17、。中間代碼文件。vJavaJava可以看作是半編譯半解釋的語(yǔ)言，可以看作是半編譯半解釋的語(yǔ)言，通過(guò)通過(guò)把把javajava源代碼編譯成源代碼編譯成javajava虛擬機(jī)可以識(shí)別的虛擬機(jī)可以識(shí)別的字節(jié)碼；字節(jié)碼；再通過(guò)虛擬機(jī)解釋執(zhí)行，可以稱作再通過(guò)虛擬機(jī)解釋執(zhí)行，可以稱作是一種折中。是一種折中。vJavaJava虛擬機(jī)的初衷是因?yàn)樘摂M機(jī)的初衷是因?yàn)榭缙脚_(tái)跨平臺(tái)而不是效率而不是效率的考慮。的考慮。 程序設(shè)計(jì)語(yǔ)言特點(diǎn)和發(fā)展程序設(shè)計(jì)語(yǔ)言特點(diǎn)和發(fā)展語(yǔ)言發(fā)展階段語(yǔ)言發(fā)展階段：1. 1.機(jī)器語(yǔ)言機(jī)器語(yǔ)言 0101碼碼 2.2.符號(hào)語(yǔ)言符號(hào)語(yǔ)言 匯編語(yǔ)言匯編語(yǔ)言3.3.高級(jí)語(yǔ)言高級(jí)語(yǔ)言 第一種高級(jí)語(yǔ)言-For

18、tranFortranFortran ：19531953年年1212月，月， IBMIBM公司程序師約翰公司程序師約翰巴科斯巴科斯(J. (J. Backus1924Backus1924年年1212月月3 3日日20072007年年3 3月月1717日）日） ：背景：背景：“程序設(shè)計(jì)相當(dāng)昂貴，租借機(jī)器要花去好幾百萬(wàn)，程序設(shè)計(jì)相當(dāng)昂貴，租借機(jī)器要花去好幾百萬(wàn)，而程序設(shè)計(jì)的費(fèi)用卻只多不少。而程序設(shè)計(jì)的費(fèi)用卻只多不少?！?” 1 9 5 41 9 5 4年年 ，第一個(gè)完全脫離機(jī)器硬件的高級(jí)語(yǔ)言，科學(xué)，第一個(gè)完全脫離機(jī)器硬件的高級(jí)語(yǔ)言，科學(xué)計(jì)算語(yǔ)言的計(jì)算語(yǔ)言的,“,“公式翻譯語(yǔ)言公式翻譯語(yǔ)言”( FO

19、Rmula ( FORmula TRANslatorTRANslator）, ,注重科學(xué)計(jì)算、注重執(zhí)行效率注重科學(xué)計(jì)算、注重執(zhí)行效率 . .19661966年，美國(guó)統(tǒng)一了它的標(biāo)準(zhǔn)，稱為年，美國(guó)統(tǒng)一了它的標(biāo)準(zhǔn)，稱為FORTRAN 66FORTRAN 66語(yǔ)言。語(yǔ)言。 4040多年過(guò)去，多年過(guò)去，F(xiàn)ORTRANFORTRAN仍然是科學(xué)計(jì)算選用的語(yǔ)言仍然是科學(xué)計(jì)算選用的語(yǔ)言之一之一(Fortran 77(Fortran 77，F(xiàn)ortran 90/95 )Fortran 90/95 )。巴科斯因此獲得了巴科斯因此獲得了19771977年度年度“圖靈獎(jiǎng)圖靈獎(jiǎng)”。20042004年年5 5月，月，F(xiàn)or

20、tran 2003Fortran 2003，F(xiàn)ortranFortran語(yǔ)言新標(biāo)準(zhǔn)語(yǔ)言新標(biāo)準(zhǔn) . .AlgolAlgol 60 60 ，1960 1960 年年, , 國(guó)際代數(shù)語(yǔ)言，首次引進(jìn)了局部變量和國(guó)際代數(shù)語(yǔ)言，首次引進(jìn)了局部變量和遞歸的概念。沒(méi)有被廣泛運(yùn)用，但它演變?yōu)槠渌绦蛘Z(yǔ)遞歸的概念。沒(méi)有被廣泛運(yùn)用，但它演變?yōu)槠渌绦蛘Z(yǔ)言的概念基礎(chǔ)言的概念基礎(chǔ) COBOLCOBOL語(yǔ)言語(yǔ)言 ：面向商業(yè)的通用語(yǔ)言面向商業(yè)的通用語(yǔ)言(COmmon(COmmon Business Business Oriented Language) 1959Oriented Language) 1959年年5 5月，格

21、雷斯月，格雷斯. .霍波霍波（G.HopperG.Hopper）博士領(lǐng)導(dǎo)設(shè)計(jì)。）博士領(lǐng)導(dǎo)設(shè)計(jì)。正式發(fā)布于正式發(fā)布于19601960年年4 4月，稱為月，稱為Cobol-60Cobol-60， 最新最新COBOL 2002COBOL 2002。 僅有加、減、乘、除及乘方這五種簡(jiǎn)單的算術(shù)運(yùn)算，不僅有加、減、乘、除及乘方這五種簡(jiǎn)單的算術(shù)運(yùn)算，不適于適于科學(xué)計(jì)算科學(xué)計(jì)算。用在財(cái)會(huì)工作、統(tǒng)計(jì)報(bào)表、計(jì)劃編制、。用在財(cái)會(huì)工作、統(tǒng)計(jì)報(bào)表、計(jì)劃編制、情報(bào)檢索、人事管理等數(shù)據(jù)管理及商業(yè)數(shù)據(jù)處理領(lǐng)域。情報(bào)檢索、人事管理等數(shù)據(jù)管理及商業(yè)數(shù)據(jù)處理領(lǐng)域。 用用COBOLCOBOL寫(xiě)作的軟件，要比其他語(yǔ)言多得多。只要寫(xiě)作的

22、軟件，要比其他語(yǔ)言多得多。只要大型大型機(jī)機(jī)存在，存在，COBOLCOBOL就不會(huì)消失就不會(huì)消失 曾經(jīng)產(chǎn)生巨大影響曾經(jīng)產(chǎn)生巨大影響-“-“千年蟲(chóng)千年蟲(chóng)”（Y2KY2K）事件。）事件。 vBASICBASIC :1960年代中期，美國(guó)達(dá)特默斯學(xué)院(Dartmouth)約翰凱梅尼（J.Kemeny）和托馬斯卡茨（T.Kurtz）認(rèn)為，象FORTRAN那樣的語(yǔ)言都是為專(zhuān)業(yè)人員設(shè)計(jì)，希望能為無(wú)經(jīng)驗(yàn)的人提供一種簡(jiǎn)單的語(yǔ)言，非計(jì)算機(jī)專(zhuān)業(yè)的學(xué)會(huì)使用電腦。v 在簡(jiǎn)化FORTRAN語(yǔ)言的基礎(chǔ)上，研制出一種“初學(xué)者通用符號(hào)指令代碼”（Beginners All purpose Symbolic Intruction

23、 Code），簡(jiǎn)稱BASIC。v基本BASICBASIC 只有17條語(yǔ)句，12個(gè)函數(shù)和3個(gè)命令，由于BASIC語(yǔ)言易學(xué)易用，很快成為最流行的語(yǔ)言之一。v經(jīng)過(guò)不斷改進(jìn)后， 它一直沿用至今，出現(xiàn)了象QBASIC、VB、VB.net等新一代BASIC版本。結(jié)構(gòu)化高級(jí)語(yǔ)言（結(jié)構(gòu)化高級(jí)語(yǔ)言（1 9 7 01 9 7 0 ）PascalPascal：瑞士聯(lián)邦技術(shù)學(xué)院尼克勞斯瑞士聯(lián)邦技術(shù)學(xué)院尼克勞斯沃爾斯沃爾斯(N. (N. Wirth) Wirth) 教授教授發(fā)明了一種簡(jiǎn)單明晰的語(yǔ)言-PASCAL語(yǔ)言。PASCAL語(yǔ)言語(yǔ)法嚴(yán)謹(jǐn)，層次分明，程序易寫(xiě)，可讀性好，是第一個(gè)結(jié)構(gòu)化的編程語(yǔ)言。用作教學(xué)語(yǔ)言，系統(tǒng)程序

24、設(shè)計(jì)語(yǔ)言等。 后繼語(yǔ)言Delphi。 Wirth Wirth 獲獲19841984年度年度“圖靈獎(jiǎng)圖靈獎(jiǎng)”。Pascal:法國(guó)著名的數(shù)學(xué)家、物理學(xué)家、 哲學(xué)家和散文家 C C 語(yǔ)言：語(yǔ)言：AT&TAT&T貝爾實(shí)驗(yàn)室的鄧尼斯貝爾實(shí)驗(yàn)室的鄧尼斯里奇里奇 (D.Ritchie(D.Ritchie) ) 和肯和肯湯姆森湯姆森(K. Thompson)(K. Thompson)，（里奇最初的貢獻(xiàn)是開(kāi)，（里奇最初的貢獻(xiàn)是開(kāi)發(fā)了發(fā)了UnixUnix操作系統(tǒng)）。操作系統(tǒng)）。 19701970年，作為年，作為UnixUnix的一項(xiàng)的一項(xiàng)“副產(chǎn)品副產(chǎn)品”，完成了，完成了C C語(yǔ)語(yǔ)言的開(kāi)發(fā)（原型言的

25、開(kāi)發(fā)（原型ALGOL 60ALGOL 60 ），為了用它編寫(xiě)），為了用它編寫(xiě)UnixUnix。這種語(yǔ)言結(jié)合了匯編語(yǔ)言和高級(jí)語(yǔ)言的優(yōu)點(diǎn)，大受程這種語(yǔ)言結(jié)合了匯編語(yǔ)言和高級(jí)語(yǔ)言的優(yōu)點(diǎn)，大受程序設(shè)計(jì)師的青睞序設(shè)計(jì)師的青睞 。 里奇用里奇用C C語(yǔ)言重寫(xiě)了語(yǔ)言重寫(xiě)了UNIXUNIX，使得，使得UNIXUNIX成為第一個(gè)成為第一個(gè)用高級(jí)語(yǔ)言寫(xiě)作的操作系統(tǒng)。正因?yàn)槿绱?，用高?jí)語(yǔ)言寫(xiě)作的操作系統(tǒng)。正因?yàn)槿绱耍琔NIXUNIX才才大為流行，因?yàn)榇鬄榱餍?，因?yàn)镃 C語(yǔ)言代碼要比用機(jī)器碼易讀易懂，語(yǔ)言代碼要比用機(jī)器碼易讀易懂，更方便地移植到任何機(jī)器上去。更方便地移植到任何機(jī)器上去。 19831983年度的年度的“

26、圖靈獎(jiǎng)圖靈獎(jiǎng)” ” 面向?qū)ο蟾呒?jí)語(yǔ)言面向?qū)ο蟾呒?jí)語(yǔ)言 SIMULA 67SIMULA 67: 20: 20世紀(jì)世紀(jì)6060年代開(kāi)發(fā)的年代開(kāi)發(fā)的SimulaSimula 67 67，它是面向?qū)ο笳Z(yǔ)言的鼻祖。它將它是面向?qū)ο笳Z(yǔ)言的鼻祖。它將AlgolAlgol 60 60中中的塊結(jié)構(gòu)向前推進(jìn)了一大步，提出了對(duì)象的的塊結(jié)構(gòu)向前推進(jìn)了一大步，提出了對(duì)象的概念。概念。 Smalltalk-80: Smalltalk-80: 是最有影響的面向?qū)ο蟮恼Z(yǔ)言是最有影響的面向?qū)ο蟮恼Z(yǔ)言之一。它豐富了面向?qū)ο蟮母拍睢Ｔ撜Z(yǔ)言并之一。它豐富了面向?qū)ο蟮母拍睢Ｔ撜Z(yǔ)言并入了入了SimulaSimula語(yǔ)言的許多面向?qū)ο蟮奶?/p>

27、征，包語(yǔ)言的許多面向?qū)ο蟮奶卣鳎?lèi)和繼承等。括類(lèi)和繼承等。 v C+ C+v比加尼比加尼斯楚士舒普斯楚士舒普 （Bjarne StroustrupBjarne Stroustrup） AT&T、貝爾實(shí)驗(yàn)室和ACM成員。 v 1979年，B. S開(kāi)始開(kāi)發(fā)一種語(yǔ)言，當(dāng)時(shí)稱為“C with Class”， 19831983年正式取名為年正式取名為C+C+，在經(jīng)歷了不斷修訂后，于在經(jīng)歷了不斷修訂后，于19941994年制定了年制定了ANSI ANSI C+C+標(biāo)準(zhǔn)的草案；標(biāo)準(zhǔn)的草案；v 1998年，ANSI/ISO C+標(biāo)準(zhǔn)建立，同年， B. S推出了其經(jīng)典著作The C+ Program

28、ming Language的第三版。Python1. 1.PythonPython是一種面向?qū)ο蟮慕忉屝缘挠?jì)算機(jī)程序設(shè)是一種面向?qū)ο蟮慕忉屝缘挠?jì)算機(jī)程序設(shè)計(jì)語(yǔ)言，也是一種功能強(qiáng)大而完善的通用型語(yǔ)言；計(jì)語(yǔ)言，也是一種功能強(qiáng)大而完善的通用型語(yǔ)言；2.2.已經(jīng)具有十多年的發(fā)展歷史，成熟且穩(wěn)定；已經(jīng)具有十多年的發(fā)展歷史，成熟且穩(wěn)定；3.3.具有腳本語(yǔ)言中最豐富和強(qiáng)大的類(lèi)庫(kù)，足以支持具有腳本語(yǔ)言中最豐富和強(qiáng)大的類(lèi)庫(kù)，足以支持絕大多數(shù)日常應(yīng)用；絕大多數(shù)日常應(yīng)用；4.4.具有非常簡(jiǎn)捷而清晰的語(yǔ)法特點(diǎn)，適合完成各種具有非常簡(jiǎn)捷而清晰的語(yǔ)法特點(diǎn)，適合完成各種高層任務(wù)，幾乎可以在所有的操作系統(tǒng)中運(yùn)行。高層任務(wù)，幾

29、乎可以在所有的操作系統(tǒng)中運(yùn)行。vPythonPython的創(chuàng)始人為的創(chuàng)始人為Guido van RossumGuido van Rossum。19891989年圣誕節(jié)期間，在阿姆斯特丹，年圣誕節(jié)期間，在阿姆斯特丹，GuidoGuido為了打發(fā)圣誕節(jié)的無(wú)趣，決心開(kāi)發(fā)一個(gè)新的為了打發(fā)圣誕節(jié)的無(wú)趣，決心開(kāi)發(fā)一個(gè)新的腳本解釋程序，做為腳本解釋程序，做為 ABC ABC 語(yǔ)言的一種繼承。語(yǔ)言的一種繼承。之所以選中之所以選中 PythonPython（大蟒蛇的意思）作為（大蟒蛇的意思）作為程序的名字，是因?yàn)樗且粋€(gè)程序的名字，是因?yàn)樗且粋€(gè)Monty Monty PythonPython的飛行馬戲團(tuán)的愛(ài)好

30、者。的飛行馬戲團(tuán)的愛(ài)好者。v現(xiàn)在現(xiàn)在googlegoogle工作，工作， PythonPython是是googlegoogle的開(kāi)發(fā)語(yǔ)言之一的開(kāi)發(fā)語(yǔ)言之一 （C C，JavaJava）Python 優(yōu)點(diǎn)優(yōu)點(diǎn)vPythonPython是免費(fèi)的是免費(fèi)的vPythonPython是可移植的是可移植的 vPythonPython的強(qiáng)大功能的強(qiáng)大功能 vPythonPython的可擴(kuò)展性：的可擴(kuò)展性：PythonPython和和C C可以一起工可以一起工作。它可以嵌入到作。它可以嵌入到C C或者或者C+C+的應(yīng)用程序當(dāng)中的應(yīng)用程序當(dāng)中v PythonPython的簡(jiǎn)單性：語(yǔ)言的核心很小，語(yǔ)義和的簡(jiǎn)單性：

31、語(yǔ)言的核心很小，語(yǔ)義和樣式非常簡(jiǎn)單。樣式非常簡(jiǎn)單。 vJAVAv詹姆斯高斯林（James Gosling）等人于1990年代初開(kāi)發(fā)。v最初被命名為Oak，用于解決諸如電視機(jī)、電話、鬧鐘、烤面包機(jī)等家用電器的控制和通訊問(wèn)題。由于這些智能化家電的市場(chǎng)需求沒(méi)有預(yù)期的高，Sun放棄了該項(xiàng)計(jì)劃。v就在Oak幾近失敗之時(shí)，隨著互聯(lián)網(wǎng)的發(fā)展，Sun看到了Oak在計(jì)算機(jī)網(wǎng)絡(luò)上的廣闊應(yīng)用前景，于是改造了Oak，在1995年5月以“Java”的名稱正式發(fā)布了。 JavaJava伴隨著互聯(lián)網(wǎng)的迅猛發(fā)展而發(fā)展，逐伴隨著互聯(lián)網(wǎng)的迅猛發(fā)展而發(fā)展，逐漸成為重要的網(wǎng)絡(luò)編程語(yǔ)言。漸成為重要的網(wǎng)絡(luò)編程語(yǔ)言。 軟件的發(fā)展2020世

32、紀(jì)世紀(jì)7070年代：因受益于結(jié)構(gòu)化程序設(shè)年代：因受益于結(jié)構(gòu)化程序設(shè)計(jì)，美國(guó)導(dǎo)彈預(yù)警系統(tǒng)達(dá)計(jì)，美國(guó)導(dǎo)彈預(yù)警系統(tǒng)達(dá)385385萬(wàn)句。萬(wàn)句。2020世紀(jì)世紀(jì)8080年代：借助軟件工程的方法美年代：借助軟件工程的方法美國(guó)航天飛機(jī)監(jiān)控系統(tǒng)達(dá)國(guó)航天飛機(jī)監(jiān)控系統(tǒng)達(dá)40004000萬(wàn)句。萬(wàn)句。 2020世紀(jì)世紀(jì)9090年代：可視化和面向?qū)ο蟮木幠甏嚎梢暬兔嫦驅(qū)ο蟮木幊陶Z(yǔ)言，以其迅捷的編譯速度、強(qiáng)大的程語(yǔ)言，以其迅捷的編譯速度、強(qiáng)大的功能和易學(xué)靈活的特點(diǎn)功能和易學(xué)靈活的特點(diǎn) 。Windows 98有有1800萬(wàn)行代碼；萬(wàn)行代碼；Windows XP為為3500萬(wàn)行；萬(wàn)行；Windows Vista的代碼行數(shù)

33、達(dá)到了的代碼行數(shù)達(dá)到了5000萬(wàn)行。萬(wàn)行。 v2 2 高級(jí)語(yǔ)言的參數(shù)傳遞高級(jí)語(yǔ)言的參數(shù)傳遞v 過(guò)程（或函數(shù)）的定義和調(diào)用是程序設(shè)計(jì)語(yǔ)過(guò)程（或函數(shù)）的定義和調(diào)用是程序設(shè)計(jì)語(yǔ)言的主要特征之一，也是模塊化程序設(shè)計(jì)的主要言的主要特征之一，也是模塊化程序設(shè)計(jì)的主要手段和節(jié)省程序代碼、擴(kuò)充語(yǔ)言能力的主要途徑。手段和節(jié)省程序代碼、擴(kuò)充語(yǔ)言能力的主要途徑。v 過(guò)程（或函數(shù)）在定義之后就可以在程序的過(guò)程（或函數(shù)）在定義之后就可以在程序的其它地方調(diào)用它。調(diào)用與被調(diào)用者之間的信息交其它地方調(diào)用它。調(diào)用與被調(diào)用者之間的信息交流可以通過(guò)全局量或由參數(shù)傳遞來(lái)實(shí)現(xiàn)。流可以通過(guò)全局量或由參數(shù)傳遞來(lái)實(shí)現(xiàn)。v參數(shù)：參數(shù)：v形式參

34、數(shù)（定義）形式參數(shù)（定義）v實(shí)在參數(shù)（調(diào)用）實(shí)在參數(shù)（調(diào)用）程序設(shè)計(jì)語(yǔ)言中參數(shù)傳遞的實(shí)現(xiàn) #include “stdio.h#include “stdio.h”int max(int x, intint max(int x, int y) /x y) /x和和y y稱為形式參數(shù)，簡(jiǎn)稱形參。稱為形式參數(shù)，簡(jiǎn)稱形參。 int int z; z; if (xy) z=x; if (xy) z=x; else z=y; else z=y; return(z return(z); ); void main()void main() int a,b,c int a,b,c; ; scanf(“%d%d”,

35、&a,&b scanf(“%d%d”,&a,&b); ); c=max(a,b c=max(a,b); /); /其中的其中的a a和和b b稱為實(shí)在參數(shù)稱為實(shí)在參數(shù) printf(“max=%dn”,cprintf(“max=%dn”,c); ); v2 2 參數(shù)傳遞參數(shù)傳遞v參數(shù)傳遞分類(lèi)參數(shù)傳遞分類(lèi)(1) (1) 傳地址傳地址 (2)(2)傳值傳值 (3) (3) 傳名字傳名字 (4)(4)傳結(jié)果傳結(jié)果 除以上四種參數(shù)傳遞方法之外，還有其他參數(shù)傳除以上四種參數(shù)傳遞方法之外，還有其他參數(shù)傳遞的方式。遞的方式。 (1)(1)傳地址傳地址 把實(shí)在參數(shù)的地址傳遞給相

36、應(yīng)的形式參數(shù)。把實(shí)在參數(shù)的地址傳遞給相應(yīng)的形式參數(shù)。 過(guò)程（或函數(shù)）的每個(gè)形式參數(shù)都對(duì)應(yīng)一個(gè)相應(yīng)過(guò)程（或函數(shù)）的每個(gè)形式參數(shù)都對(duì)應(yīng)一個(gè)相應(yīng)的內(nèi)存空間，稱為形式單元。形式單元用來(lái)存放的內(nèi)存空間，稱為形式單元。形式單元用來(lái)存放相應(yīng)的實(shí)在參數(shù)的地址。當(dāng)調(diào)用一個(gè)過(guò)程（或函相應(yīng)的實(shí)在參數(shù)的地址。當(dāng)調(diào)用一個(gè)過(guò)程（或函數(shù)）時(shí)，調(diào)用段首先把數(shù)）時(shí)，調(diào)用段首先把實(shí)在參數(shù)的地址實(shí)在參數(shù)的地址傳遞到一傳遞到一個(gè)個(gè)臨時(shí)設(shè)置的工作單元臨時(shí)設(shè)置的工作單元中。中。 當(dāng)程序轉(zhuǎn)入被調(diào)用段之后，被調(diào)用段再把臨時(shí)當(dāng)程序轉(zhuǎn)入被調(diào)用段之后，被調(diào)用段再把臨時(shí)設(shè)置的工作單元中的實(shí)參地址取進(jìn)自己相應(yīng)的設(shè)置的工作單元中的實(shí)參地址取進(jìn)自己相應(yīng)的

37、形形式單元式單元中，中，過(guò)程（或函數(shù)）體對(duì)形式參數(shù)的任何過(guò)程（或函數(shù)）體對(duì)形式參數(shù)的任何引用或賦值都被處理成為引用或賦值都被處理成為對(duì)形式單元的間接訪問(wèn)對(duì)形式單元的間接訪問(wèn)，形參的值發(fā)生變化，等價(jià)于與之對(duì)應(yīng)實(shí)參發(fā)生變形參的值發(fā)生變化，等價(jià)于與之對(duì)應(yīng)實(shí)參發(fā)生變化?；?在調(diào)用語(yǔ)句執(zhí)行過(guò)程中完成下列操作：在調(diào)用語(yǔ)句執(zhí)行過(guò)程中完成下列操作： 把實(shí)參把實(shí)參x x和和y y的地址分別傳遞到已準(zhǔn)備好（由的地址分別傳遞到已準(zhǔn)備好（由編譯分配）的兩個(gè)單元（編譯分配）的兩個(gè)單元（t1 t1和和t2t2）中；）中； s:=t1 s:=t1 且且 r:= t2r:= t2，使形參得到對(duì)應(yīng)實(shí)參的地，使形參得到對(duì)應(yīng)實(shí)參

38、的地址；址； 將將s s所指向的單元的內(nèi)容（所指向的單元的內(nèi)容（x x）與）與r r所指向的單所指向的單元的內(nèi)容（元的內(nèi)容（y y）相加，完成表達(dá)式）相加，完成表達(dá)式s+rs+r的計(jì)算；的計(jì)算； 將表達(dá)式將表達(dá)式s+rs+r的運(yùn)算結(jié)果送到的運(yùn)算結(jié)果送到s s所指的內(nèi)存單所指的內(nèi)存單元（元（x x）中；）中； 返回主程序。返回主程序。 (2) (2)傳值傳值 把實(shí)在參數(shù)的值計(jì)算出來(lái)傳遞給相應(yīng)的形把實(shí)在參數(shù)的值計(jì)算出來(lái)傳遞給相應(yīng)的形式參數(shù)。式參數(shù)。 v 最簡(jiǎn)單的參數(shù)傳遞方式，工作過(guò)程：最簡(jiǎn)單的參數(shù)傳遞方式，工作過(guò)程：v調(diào)用段（）調(diào)用段（）把實(shí)在參數(shù)的值計(jì)算出來(lái)把實(shí)在參數(shù)的值計(jì)算出來(lái), ,被調(diào)用被調(diào)

39、用段（函數(shù)）段（函數(shù)）能能取取到。到。v 被調(diào)用段被調(diào)用段（函數(shù)）（函數(shù)）開(kāi)始工作時(shí)，首先把這些開(kāi)始工作時(shí)，首先把這些值抄進(jìn)自己的形式單元，然后跟使用值抄進(jìn)自己的形式單元，然后跟使用局部量局部量一樣使用這些形式單元。一樣使用這些形式單元。v在上面關(guān)于傳地址的例子中，如果把過(guò)程add的首部說(shuō)明改為：vprocedure add( s: integer; r: integer);program example(outputprogram example(output); ); var varx,y:integerx,y:integer; ;procedure add(s: integer; var

40、procedure add(s: integer; var r: integer); r: integer); begin begins:=s+rs:=s+r; ; end; end; begin beginx:=0;x:=0;y:=2;y:=2;add(xadd(x, y);, y);writeln(xwriteln(x=,x)=,x) end. end. 傳值方式參數(shù)傳遞傳值方式參數(shù)傳遞 , ,被調(diào)用段無(wú)法改變實(shí)參的值被調(diào)用段無(wú)法改變實(shí)參的值 . .(3) (3) 傳名字傳名字vALGOL語(yǔ)言使用，傳名字參數(shù)的意義：v過(guò)程調(diào)用相當(dāng)于把被調(diào)用段的過(guò)程體抄到調(diào)用出現(xiàn)的地方，但把其中任一出現(xiàn)的形

41、參都替換成相應(yīng)的實(shí)參（文字替換）。v替換時(shí)發(fā)現(xiàn)過(guò)程體中的局部名和實(shí)參中的名字不能重名 。例如，下面的ALGOL過(guò)程：procedure swap(M,N);integer M,N;begininteger L; L:=M; M:=N; N:=L;end;過(guò)程調(diào)用swap(K(I),K(J)采用傳名方式進(jìn)行參數(shù)傳遞，相當(dāng)于執(zhí)行了下面的語(yǔ)句： L:= K(I);K(I):= K(J); K(J):=L; (4) (4)傳結(jié)果傳結(jié)果 每個(gè)形參（函數(shù)頭）對(duì)應(yīng)有每個(gè)形參（函數(shù)頭）對(duì)應(yīng)有兩個(gè)兩個(gè)單元單元，第一個(gè)存放，第一個(gè)存放實(shí)參的地址實(shí)參的地址，第二個(gè)存，第二個(gè)存放放實(shí)參的值實(shí)參的值。 過(guò)程體中對(duì)形參的

42、任何引用都是對(duì)它的過(guò)程體中對(duì)形參的任何引用都是對(duì)它的第第二個(gè)單元的直接訪問(wèn)二個(gè)單元的直接訪問(wèn)。返回前把第二個(gè)單。返回前把第二個(gè)單元的內(nèi)容放到第一個(gè)單元所指的實(shí)參單元元的內(nèi)容放到第一個(gè)單元所指的實(shí)參單元中。中。1.2 編譯過(guò)程概述v編譯器內(nèi)部包括了許多步驟稱為編譯器內(nèi)部包括了許多步驟稱為階段階段，它們執(zhí)行不同的它們執(zhí)行不同的邏輯操作邏輯操作。v將這些階段設(shè)想為編譯器中一個(gè)個(gè)單獨(dú)將這些階段設(shè)想為編譯器中一個(gè)個(gè)單獨(dú)的片斷是很有用的，盡管在應(yīng)用中它們的片斷是很有用的，盡管在應(yīng)用中它們是經(jīng)常組合在一起的，但它們的代碼是是經(jīng)常組合在一起的，但它們的代碼是單獨(dú)來(lái)編寫(xiě)的。單獨(dú)來(lái)編寫(xiě)的。 將編譯過(guò)程劃分成將編譯

43、過(guò)程劃分成詞法分析、語(yǔ)法分析、詞法分析、語(yǔ)法分析、語(yǔ)義分析、中間代碼生成、代碼優(yōu)化和目語(yǔ)義分析、中間代碼生成、代碼優(yōu)化和目標(biāo)代碼標(biāo)代碼生成六個(gè)階段。生成六個(gè)階段。 事實(shí)上某些階段可以組合在一起。事實(shí)上某些階段可以組合在一起。 另外還有兩個(gè)重要的工作：另外還有兩個(gè)重要的工作：表格管理和錯(cuò)表格管理和錯(cuò)誤處理誤處理，它們與編譯各個(gè)階段都有聯(lián)系。，它們與編譯各個(gè)階段都有聯(lián)系。詞法分析詞法分析語(yǔ)法分析語(yǔ)法分析語(yǔ)義分析語(yǔ)義分析目標(biāo)代碼生成目標(biāo)代碼生成中間代碼生成中間代碼生成代碼優(yōu)化代碼優(yōu)化目標(biāo)程序目標(biāo)程序源程序源程序出出 錯(cuò)錯(cuò) 處處 理理表表 格格 管管 理理英譯與編譯的比較1. 1.識(shí)別出句子中的單字識(shí)

44、別出句子中的單字- -詞法分析詞法分析2.2.分析句子的語(yǔ)法結(jié)構(gòu)分析句子的語(yǔ)法結(jié)構(gòu)- -語(yǔ)法分析語(yǔ)法分析3.3.初步翻譯句子的含意初步翻譯句子的含意- -語(yǔ)義分析和中間代碼語(yǔ)義分析和中間代碼生成生成4.4.譯文修飾譯文修飾- -優(yōu)化優(yōu)化5.5.寫(xiě)出最后譯文寫(xiě)出最后譯文- -目標(biāo)代碼生成目標(biāo)代碼生成1 1 詞法分析詞法分析 詞法分析階段是編譯過(guò)程的第一個(gè)階段。詞法分析階段是編譯過(guò)程的第一個(gè)階段。 單詞單詞是指邏輯上緊密相連的一組字符，這些字符是指邏輯上緊密相連的一組字符，這些字符具有集體含義具有集體含義. .v比如比如標(biāo)識(shí)符標(biāo)識(shí)符是由字母字符開(kāi)頭，后跟字母、數(shù)字字是由字母字符開(kāi)頭，后跟字母、數(shù)字

45、字符的字符序列組成的一種單詞符的字符序列組成的一種單詞; ;v保留字保留字（也稱關(guān)鍵詞或基本字）是一種單詞（也稱關(guān)鍵詞或基本字）是一種單詞; ;v此外還有此外還有算符、常數(shù)和界符算符、常數(shù)和界符（標(biāo)點(diǎn)符號(hào)、左右括號(hào)（標(biāo)點(diǎn)符號(hào)、左右括號(hào)等）等等。等）等等。 輸入：源程序輸入：源程序輸出：標(biāo)準(zhǔn)單詞輸出：標(biāo)準(zhǔn)單詞任務(wù)：從左到右一個(gè)字符一個(gè)字符的讀入源程任務(wù)：從左到右一個(gè)字符一個(gè)字符的讀入源程序，對(duì)構(gòu)成源程序的字符串進(jìn)行掃描和分解，序，對(duì)構(gòu)成源程序的字符串進(jìn)行掃描和分解，從而識(shí)別出一個(gè)個(gè)單詞（也稱單詞符號(hào)）。從而識(shí)別出一個(gè)個(gè)單詞（也稱單詞符號(hào)）。方法：狀態(tài)圖；方法：狀態(tài)圖；DFADFA；NFANFA

46、詞法分析程序詞法分析程序示例示例FOR K := 1 TO 100FOR K := 1 TO 100 M := I + 10 M := I + 10 * * K K N := J + 10 N := J + 10 * * K KNEXT KNEXT KTOTONEXTNEXTFORFOR K KN NM MI IJ JK KK KK K:=:=100100:=:=:=:=1 110101010+ +* * *+ +保留字保留字標(biāo)識(shí)符標(biāo)識(shí)符分界符分界符運(yùn)算符運(yùn)算符常數(shù)常數(shù)C源程序片斷： int a; a = a + 2;詞法分析后可能返回:單詞類(lèi)型單詞類(lèi)型 單詞值單詞值保留字 int標(biāo)識(shí)符(變量

47、名) a界符 ;標(biāo)識(shí)符(變量名) a算符(賦值) =標(biāo)識(shí)符(變量名) a 算符(加) +整數(shù) 2界符 ；有關(guān)術(shù)語(yǔ)v詞法分析(lexical analysis or scanning) -The stream of characters making up a source program is read from left to right and grouped into tokens, which are sequences of characters that have a collective meaning.v單詞-tokenv保留字-reserved wordv標(biāo)識(shí)符 -ident

48、ifier(user-defined name)2 2 語(yǔ)法分析語(yǔ)法分析 在編譯程序的實(shí)際實(shí)現(xiàn)中語(yǔ)法分析和語(yǔ)義處在編譯程序的實(shí)際實(shí)現(xiàn)中語(yǔ)法分析和語(yǔ)義處理常常是組合在一起的。稱為語(yǔ)法制導(dǎo)翻譯。理常常是組合在一起的。稱為語(yǔ)法制導(dǎo)翻譯。 輸入：標(biāo)準(zhǔn)單詞輸入：標(biāo)準(zhǔn)單詞輸出：各類(lèi)語(yǔ)法短語(yǔ)輸出：各類(lèi)語(yǔ)法短語(yǔ)任務(wù)：在詞法分析的基礎(chǔ)上將單詞序列任務(wù)：在詞法分析的基礎(chǔ)上將單詞序列分解成分解成各各類(lèi)語(yǔ)法單位，如類(lèi)語(yǔ)法單位，如“表達(dá)式表達(dá)式”、 “ “語(yǔ)句語(yǔ)句”、“程程序序”等等。等等。 方法：遞歸子程序法、方法：遞歸子程序法、LRLR分析法、優(yōu)先分析法。分析法、優(yōu)先分析法。v語(yǔ)法分析所依據(jù)的是語(yǔ)言的語(yǔ)法規(guī)則語(yǔ)言的

49、語(yǔ)法規(guī)則，即描述程序結(jié)構(gòu)的規(guī)則。通過(guò)語(yǔ)法分析確定源程序是否構(gòu)成一個(gè)語(yǔ)法上正確語(yǔ)法上正確的程序。v程序的結(jié)構(gòu)通常是用遞歸規(guī)則遞歸規(guī)則表示的，例如我們可以用下面的規(guī)則來(lái)定義表達(dá)式表達(dá)式：v（1）任何標(biāo)識(shí)符是表達(dá)式；v（2）任何常數(shù)（整常數(shù)、實(shí)常數(shù)）是表達(dá)式；v（3）若e1和e2都是表達(dá)式，那么，e1+e2 ，e1*e2 ，(e1)也都是表達(dá)式。 語(yǔ)法分析規(guī)則規(guī)則 := “:=”“:=” := “+” := “*” := “(”“)” := := := 賦值語(yǔ)句標(biāo)識(shí)符表達(dá)式表達(dá)式+表達(dá)式表達(dá)式標(biāo)識(shí)符整數(shù)標(biāo)識(shí)符:=表達(dá)式*賦值語(yǔ)句的樹(shù)形結(jié)構(gòu)語(yǔ)句id1:= id2 + id3* 10的語(yǔ)法樹(shù)v類(lèi)似地，語(yǔ)

50、句也可以遞歸定義，如：（1）標(biāo)識(shí)符 := 表達(dá)式 是語(yǔ)句（2）while 表達(dá)式 do 語(yǔ)句 （3）if（表達(dá)式then 語(yǔ)句 else 語(yǔ)句 都是語(yǔ)句。示例示例TOTONEXTNEXTFORFORK KN NM MI IJ JK KK KK K:=:=100100:=:=:=:=1 110101010+ +* * *+ +變量、常數(shù)及其運(yùn)算結(jié)果均是表達(dá)式變量、常數(shù)及其運(yùn)算結(jié)果均是表達(dá)式表達(dá)式表達(dá)式表達(dá)式表達(dá)式表達(dá)式表達(dá)式表達(dá)式表達(dá)式表達(dá)式表達(dá)式表達(dá)式表達(dá)式賦值句的形式為賦值句的形式為“變量：表達(dá)式變量：表達(dá)式”賦值句賦值句賦值句賦值句多個(gè)賦值句可構(gòu)成語(yǔ)句塊多個(gè)賦值句可構(gòu)成語(yǔ)句塊語(yǔ)句塊語(yǔ)句塊表

51、達(dá)式可作為循環(huán)的初值和終值表達(dá)式可作為循環(huán)的初值和終值初值初值終值終值簡(jiǎn)單數(shù)值變量可作為循環(huán)的控制變量簡(jiǎn)單數(shù)值變量可作為循環(huán)的控制變量控制變量控制變量控制變量控制變量此時(shí)可以看出上述結(jié)果符合循環(huán)語(yǔ)句此時(shí)可以看出上述結(jié)果符合循環(huán)語(yǔ)句的語(yǔ)法定義，故語(yǔ)法分析成功完成的語(yǔ)法定義，故語(yǔ)法分析成功完成術(shù)語(yǔ)術(shù)語(yǔ)v語(yǔ)法分析語(yǔ)法分析( (syntax analysissyntax analysis or or parsing parsing)( )(剖析剖析, ,分解）分解） The purpose of syntax analysis is to determine the The purpose of sy

52、ntax analysis is to determine the source programs phrase structure. This process is source programs phrase structure. This process is also called also called parsingparsing. . The source program is parsed to check whether it The source program is parsed to check whether it conforms to the source lan

53、guages syntax, and to conforms to the source languages syntax, and to construct a suitable representation of its phrase construct a suitable representation of its phrase structure.structure.語(yǔ)法樹(shù)語(yǔ)法樹(shù)( (推導(dǎo)樹(shù)推導(dǎo)樹(shù))( )(parse treeparse tree or or derivation treederivation tree) )3 3 語(yǔ)義分析語(yǔ)義分析語(yǔ)義審查語(yǔ)義審查( (靜態(tài)語(yǔ)義靜態(tài)語(yǔ)

54、義) )v按照語(yǔ)法樹(shù)的層次關(guān)系和先后次序，逐個(gè)語(yǔ)句按照語(yǔ)法樹(shù)的層次關(guān)系和先后次序，逐個(gè)語(yǔ)句地進(jìn)行語(yǔ)義處理。地進(jìn)行語(yǔ)義處理。v主要任務(wù)：主要任務(wù)： 進(jìn)行類(lèi)型審查，審查每個(gè)算符是否進(jìn)行類(lèi)型審查，審查每個(gè)算符是否符合語(yǔ)言規(guī)范，不符合時(shí)應(yīng)報(bào)告錯(cuò)誤。符合語(yǔ)言規(guī)范，不符合時(shí)應(yīng)報(bào)告錯(cuò)誤。類(lèi)型匹配類(lèi)型匹配類(lèi)型轉(zhuǎn)換類(lèi)型轉(zhuǎn)換例:Program p(); Var rate:real; procedure initial; position := initial + rate * 60 /* error */ /* error */ /* warning */;v語(yǔ)義分析是在語(yǔ)法分析程序確定出語(yǔ)法單位后，審語(yǔ)義分析是

55、在語(yǔ)法分析程序確定出語(yǔ)法單位后，審查有無(wú)查有無(wú)語(yǔ)義錯(cuò)誤語(yǔ)義錯(cuò)誤，并為代碼生成階段收集類(lèi)型信息。，并為代碼生成階段收集類(lèi)型信息。v例如進(jìn)行例如進(jìn)行類(lèi)型檢查類(lèi)型檢查，檢查每個(gè)算符是否具有語(yǔ)言規(guī)，檢查每個(gè)算符是否具有語(yǔ)言規(guī)范允許的運(yùn)算對(duì)象，當(dāng)不符合語(yǔ)言規(guī)范時(shí)，編譯程范允許的運(yùn)算對(duì)象，當(dāng)不符合語(yǔ)言規(guī)范時(shí)，編譯程序應(yīng)報(bào)告錯(cuò)誤。序應(yīng)報(bào)告錯(cuò)誤。v再如，有的編譯程序不允許實(shí)數(shù)作為數(shù)組下標(biāo)。再如，有的編譯程序不允許實(shí)數(shù)作為數(shù)組下標(biāo)。v又如，某語(yǔ)言規(guī)定可進(jìn)行強(qiáng)制類(lèi)型轉(zhuǎn)換，當(dāng)二目運(yùn)又如，某語(yǔ)言規(guī)定可進(jìn)行強(qiáng)制類(lèi)型轉(zhuǎn)換，當(dāng)二目運(yùn)算施于一整型數(shù)和一實(shí)型數(shù)時(shí)，編譯程序應(yīng)該將整算施于一整型數(shù)和一實(shí)型數(shù)時(shí)，編譯程序應(yīng)該將整型數(shù)

56、轉(zhuǎn)換成實(shí)型數(shù)而不能認(rèn)為源程序發(fā)生類(lèi)型錯(cuò)誤。型數(shù)轉(zhuǎn)換成實(shí)型數(shù)而不能認(rèn)為源程序發(fā)生類(lèi)型錯(cuò)誤。例: Program p(); Var rate:real; Var initial :real; Var position :real ; position := initial + rate * 60 60為整數(shù)，其余量為實(shí)數(shù)。語(yǔ)義分析插入語(yǔ)義處理結(jié)點(diǎn)的語(yǔ)法樹(shù)60:=+*Id1 positionId2 initialId3 rateinttoreal術(shù)語(yǔ)v語(yǔ)義分析(semantic analysis) The parsed program is further analyzed to determine

57、 whether it conforms to the source languages contextual constraints: scope rules, type rulese.g. To relate each applied occurrence of an identifier in the source program to the corresponding declaration. 4 4 中間代碼生成中間代碼生成 中間語(yǔ)言或稱中間代碼，是一種結(jié)構(gòu)簡(jiǎn)單、中間語(yǔ)言或稱中間代碼，是一種結(jié)構(gòu)簡(jiǎn)單、含義明確的記號(hào)系統(tǒng)。是編譯程序使用的內(nèi)含義明確的記號(hào)系統(tǒng)。是編譯程序使用的內(nèi)部表示

58、形式。部表示形式。輸入：句子輸入：句子輸出：中間代碼序列輸出：中間代碼序列任務(wù)：將各類(lèi)語(yǔ)法單位，如任務(wù)：將各類(lèi)語(yǔ)法單位，如“表達(dá)式表達(dá)式”、 “ “語(yǔ)語(yǔ)句句”、“程序程序”等翻譯為中間代碼序列。等翻譯為中間代碼序列。 中間代碼的形式：常見(jiàn)的有四元式、三元式和中間代碼的形式：常見(jiàn)的有四元式、三元式和逆波蘭式等逆波蘭式等 方法：語(yǔ)義子程序；方法：語(yǔ)義子程序；DAGDAG圖，語(yǔ)法制導(dǎo)翻譯圖，語(yǔ)法制導(dǎo)翻譯v四元式的形式為：四元式的形式為：v（算符，運(yùn)算對(duì)象（算符，運(yùn)算對(duì)象1 1，運(yùn)算對(duì)象，運(yùn)算對(duì)象2 2，結(jié)果）；，結(jié)果）；v對(duì)于源程序?qū)τ谠闯绦騭um:= first + count sum:= fir

59、st + count * * 10 10可以生成如下可以生成如下所示的四元式：所示的四元式：（1 1） (inttoreal(inttoreal , 10 , , 10 , , t1), t1)（2 2） ( ( * * , id3 , t1 , t2 ) , id3 , t1 , t2 ) （3 3） ( + , id2 , t2 , t3 )( + , id2 , t2 , t3 )（4 4） ( := , t3 , ( := , t3 , , id1 ) , id1 )vid1id1、id2id2、id3id3分別表示分別表示sumsum、firstfirst、countcount的機(jī)器

60、內(nèi)的機(jī)器內(nèi)部表示；部表示；vt1 t1、t2t2、t3t3是臨時(shí)生成的名字，表示中間運(yùn)算結(jié)果。是臨時(shí)生成的名字，表示中間運(yùn)算結(jié)果。t1 t1，t2t2，t3t3是是臨時(shí)變量臨時(shí)變量id2id2id1id1id3id3中間代碼生成(intermediate code generation) This is where the intermediate representation of the source program is created. We want this representation to be easy to generate, and easy to translate into the target program. Th