第一章 引論,1,第一章：引論,翻譯器的不同形式 編譯器、解釋器、混合編譯器 典型編譯器結(jié)構(gòu) 編譯系統(tǒng) 程序設(shè)計(jì)語言發(fā)展歷程,2,1.1 語言處理器（1.1）,翻譯器 能夠完成從一種語言到另一種語言變換的軟件,源語言,目標(biāo)語言,翻譯器,3,1.1 語言處理器,翻譯器,編譯器,解釋器,混合編譯器,4,編程語言排行榜,TIOBE Index for February 2018,5,1.1 語言處理器,一個(gè)語言處理系統(tǒng)：圖1.5 預(yù)處理器 編譯器 匯編器 連接器/加載器,6,1.1 語言處理器,編譯器 編譯器是一種翻譯器 特點(diǎn)：目標(biāo)語言比源語言低級(jí) 編程語言 傳統(tǒng)程序設(shè)計(jì)語言：Pascal、C+、Java 專用語言：Lisp、Prolog、LaTeX,編程語言,機(jī)器語言,編譯器,7,1.1 語言處理器,編譯器 編譯器是一種翻譯器 特點(diǎn)：目標(biāo)語言比源語言低級(jí) 機(jī)器語言（操作：寄存器BX的內(nèi)容送到AX中) 機(jī)器指令 1000100111011000 匯編指令 mov ax,bx,編程語言,機(jī)器語言,編譯器,8,1.1 語言處理器,編譯器 編譯器是一種翻譯器 特點(diǎn)：目標(biāo)語言比源語言低級(jí),編程語言,機(jī)器語言,編譯器,9,1.2 編譯器結(jié)構(gòu)（1.2）,分析部分 前端：源程序-中間表示 綜合部分 后端：中間表示-目標(biāo)程序,10,1.2 編譯器結(jié)構(gòu),一個(gè)編譯器的各個(gè)步驟 圖1.6 編譯器的工作可以分成若干階段，每個(gè)階段把源程序從一種表示變換成另一種表示。 符號(hào)表管理器 出錯(cuò)管理器,11,1.2 編譯器結(jié)構(gòu),一個(gè)編譯器的各個(gè)步驟 實(shí)例：圖1.7一個(gè)賦值語句的翻譯,12,1.2 編譯器結(jié)構(gòu),前端,后端,13,1.2 編譯器結(jié)構(gòu),編譯器的前端與后端 前端：只依賴于源語言 后端：編譯器中依賴于目標(biāo)機(jī)器的部分，一般獨(dú)立于源語言，而與中間語言有關(guān)。 前端+后端：組合 取一個(gè)編譯器前端，重寫它的后端以產(chǎn)生同一源語言在另一機(jī)器上的編譯器 把幾種不同的語言編譯成同一種中間語言，讓不同的前端使用同一后端，從而得到一臺(tái)機(jī)器上的幾個(gè)編譯器 編譯的幾個(gè)階段常用一趟/遍（pass）掃描來實(shí)現(xiàn)，一趟/遍掃描包括讀一個(gè)輸入文件和寫一個(gè)輸出文件。,14,1.2 編譯器結(jié)構(gòu),詞法分析 逐個(gè)讀構(gòu)成源程序的字符，把它們組成詞法單元(token)流。 實(shí)例：position = initial + rate * 60 （）標(biāo)識(shí)符（position） （）賦值號(hào)（:=） （）標(biāo)識(shí)符（initial） （）加號(hào)（） （）標(biāo)識(shí)符（rate） （）乘號(hào)（） （）數(shù)（60）,15,1.2 編譯器結(jié)構(gòu),詞法分析 逐個(gè)讀構(gòu)成源程序的字符，把它們組成詞法單元(token)流。 實(shí)例： 編譯器的詞法分析也叫做線性分析或掃描。,詞法分析,position = initial + rate * 60,16,1.2 編譯器結(jié)構(gòu),語法分析 把詞法記號(hào)流依照語言的語法結(jié)構(gòu)按層次分組，以形成語法短語。 實(shí)例： position = initial + rate * 60 的語法分析樹,17,1.2 編譯器結(jié)構(gòu),語法分析 表達(dá)式、語句等程序?qū)哟谓Y(jié)構(gòu)通常由遞歸的規(guī)則表示 實(shí)例：表達(dá)式 任何一個(gè)標(biāo)識(shí)符都是表達(dá)式； 任何一個(gè)數(shù)都是表達(dá)式； 如果和都是表達(dá)式，那么 、 、（）、（2）也都是表達(dá)式。,18,1.2 編譯器結(jié)構(gòu),語法分析 表達(dá)式、語句等程序?qū)哟谓Y(jié)構(gòu)通常由遞歸的規(guī)則表示 實(shí)例：語句 如果identifier是標(biāo)識(shí)符，expression是表達(dá)式，那么 identifier := expression是語句。 如果 expression 是表達(dá)式，statement是語句，那么 while (expression) do statement if (expression) then statement 也都是語句。,19,1.2 編譯器結(jié)構(gòu),語法分析 把詞法記號(hào)流依照語言的語法結(jié)構(gòu)按層次分組，以形成語法短語。 實(shí)例：position = initial + rate * 60 的語法樹,20,1.2 編譯器結(jié)構(gòu),語義分析 檢查程序的語義正確性，以保證程序各部分能有意義地結(jié)合在一起，為后面代碼生成階段收集類型信息。 類型轉(zhuǎn)換 類型檢查 語法制導(dǎo)翻譯,real型,21,1.2 編譯器結(jié)構(gòu),中間代碼生成 中間代碼位于高級(jí)編程語言和機(jī)器語言（目標(biāo)程序）之間 后綴表示: 9+5-2 95+2- 抽象語法樹: 三地址碼,22,1.2 編譯器結(jié)構(gòu),代碼優(yōu)化 改進(jìn)代碼，以產(chǎn)生執(zhí)行較快的機(jī)器代碼。,23,1.2 編譯器結(jié)構(gòu),目標(biāo)代碼生成 生成可重定位的機(jī)器代碼或匯編碼 為源程序所用的每個(gè)變量選擇存儲(chǔ)單元，并且把中間代碼翻譯成等價(jià)的機(jī)器指令序列。 關(guān)鍵問題是寄存器分配。,24,1.2 編譯器結(jié)構(gòu),符號(hào)表管理 編譯器的一項(xiàng)重要工作是記錄源程序中使用的標(biāo)識(shí)符，并收集每個(gè)標(biāo)識(shí)符的各種屬性。 這些屬性提供標(biāo)識(shí)符的存儲(chǔ)分配、類型和作用域信息。 如果是過程標(biāo)識(shí)符，還有參數(shù)的個(gè)數(shù)和類型、參數(shù)傳遞方式和返回值類型。 符號(hào)表是為每個(gè)標(biāo)識(shí)符保存一個(gè)記錄的數(shù)據(jù)結(jié)構(gòu)，記錄的域是標(biāo)識(shí)符的屬性。 該數(shù)據(jù)結(jié)構(gòu)允許我們迅速地找到一個(gè)標(biāo)識(shí)符的記錄，在此記錄中存儲(chǔ)和讀取數(shù)據(jù)。,25,1.2 編譯器結(jié)構(gòu),符號(hào)表管理 實(shí)例 語句 position = initial + rate * 60 詞法分析器發(fā)現(xiàn)源程序的標(biāo)識(shí)符時(shí)，把該標(biāo)識(shí)符填入符號(hào)表。但是，詞法分析期間不能確定一個(gè)標(biāo)識(shí)符的屬性。 例如： 其余的階段把標(biāo)識(shí)符的信息填入符號(hào)表，然后以不同的方式使用這些信息,26,1.2 編譯器結(jié)構(gòu),出錯(cuò)管理 每個(gè)階段都可能發(fā)現(xiàn)源程序的錯(cuò)誤。發(fā)現(xiàn)錯(cuò)誤后，該階段必須處理此錯(cuò)誤，使得編譯可以繼續(xù)進(jìn)行，以便進(jìn)一步發(fā)現(xiàn)源程序的其他錯(cuò)誤。 詞法分析：當(dāng)前被掃描的字符串不能形成語言的詞法記號(hào)。 語法分析：記號(hào)流違反語言的語法規(guī)則。 語義分析：編譯器試圖找出語法正確但對(duì)所含的操作來說是無意義的結(jié)構(gòu)，如相加的兩個(gè)標(biāo)識(shí)符，其一是數(shù)組名，另一個(gè)是過程名。,27,1.3 編譯系統(tǒng),除了編譯器外，還需要一些其他工具的幫助，才能得到可執(zhí)行的目標(biāo)程序，這些工具包括預(yù)處理器、匯編器和連接器等 C語言的編譯系統(tǒng) Java語言的編譯系統(tǒng),28,1.3 編譯系統(tǒng),C語言的編譯系統(tǒng) 一個(gè)語言處理系統(tǒng)：圖1.5 設(shè)有兩個(gè)文件 main.c swap.c gccvo swap main.c swap.c -v 可以輸出該編譯系統(tǒng)各步驟執(zhí)行的命令和執(zhí)行結(jié)果 -o 指示生成的可執(zhí)行文件的名字,29,1.3 編譯系統(tǒng),C語言的編譯系統(tǒng) 預(yù)處理器 實(shí)現(xiàn)文件包含 #include 實(shí)現(xiàn)宏展開 #define pi 3.1415926 條件編譯 #if 、#ifdef,30,1.3 編譯系統(tǒng),C語言的編譯系統(tǒng) 匯編器：對(duì)輸入進(jìn)行兩遍掃描 第一遍，匯編器掃描輸入，將表示存儲(chǔ)單元的所有標(biāo)識(shí)符都存入符號(hào)表，并分配地址。 第二遍，匯編器再次掃描輸入，把每個(gè)操作碼翻譯成機(jī)器語言中代表那個(gè)操作的位串，并把代表存儲(chǔ)單元的每個(gè)標(biāo)識(shí)符翻譯成符號(hào)表中為這個(gè)標(biāo)識(shí)符分配的地址。 gcc S main.c as o main.o main.s,31,1.3 編譯系統(tǒng),C語言的編譯系統(tǒng) 連接器：收集、組織程序所需的不同代碼和數(shù)據(jù) 靜態(tài)連接器：將多個(gè)可重定位目標(biāo)文件組成一個(gè)可執(zhí)行目標(biāo)文件（也可以組成一個(gè)可重定位目標(biāo)文件） 動(dòng)態(tài)連接器：支持在內(nèi)存中的可執(zhí)行程序在執(zhí)行時(shí)與共享目標(biāo)文件進(jìn)行動(dòng)態(tài)的連接。,32,1.3 編譯系統(tǒng),Java語言的編譯系統(tǒng) 一般的高級(jí)語言程序如果要在不同的平臺(tái)上運(yùn)行，至少需要編譯成不同的目標(biāo)代碼。 Java虛擬機(jī)技術(shù)是實(shí)現(xiàn)Java平臺(tái)無關(guān)性特點(diǎn)的關(guān)鍵。 Java虛擬機(jī)語言（簡稱JVML） JVML程序只需要與虛擬機(jī)交互，不需要關(guān)心底層的硬件和操作系統(tǒng)。,33,1.3 編譯系統(tǒng),Java語言的編譯系統(tǒng),34,1.4 程序設(shè)計(jì)語言發(fā)展歷程（1.3）,程序設(shè)計(jì)語言發(fā)展歷程 機(jī)器語言（第一代）： 20世紀(jì)40年代 匯編語言（第二代） ：20世紀(jì)50年代早期 高級(jí)語言 ：20世紀(jì)50年代晚期+ 通用（第三代）： Fortran、Cobol、C、C+、C#、Java 專用（第四代）：SQL、Postscript 邏輯（第五代）：Prolog、LISP,35,1.4 程序設(shè)計(jì)語言發(fā)展歷程,C語言的產(chǎn)生 The Development of the C Language：C history Written by Dennis Ritchie BCPL B語言 New B語言 C語言,Ken Thompson (left) with Dennis Ritchie,DEC PDP-7, as used for initial work on C and Unix,36,1.4 程序設(shè)計(jì)語言發(fā)展歷程,第一屆（1966年）圖靈獎(jiǎng)得主：Alan JPerlis 貢獻(xiàn)領(lǐng)域：高級(jí)程序設(shè)計(jì)技巧，編譯器構(gòu)造,37,1.4 程序設(shè)計(jì)語言發(fā)展歷程,1983年圖靈獎(jiǎng)得主：Ken Thompson, Dennis Ritchie 貢獻(xiàn)領(lǐng)域：C語言和Unix操作系統(tǒng),38,1.4 程序設(shè)計(jì)語言發(fā)展歷程,2006年圖靈獎(jiǎng)得主：Frances E. Allen 貢獻(xiàn)領(lǐng)域：優(yōu)化編譯器,39,1.4 程序設(shè)計(jì)語言發(fā)展歷程,編譯性語言、解釋性語言和腳本語言 高級(jí)語言翻譯成機(jī)器語言，計(jì)算機(jī)才能執(zhí)行高級(jí)語言編寫的程序。 翻譯有兩種方式 編譯：一次性編譯成機(jī)器語言文件，不用重新編譯，效率高 解釋：每個(gè)語句都是執(zhí)行的時(shí)候才翻譯，每執(zhí)行一次就翻譯一次，效率比較低 腳本語言 一種解釋性語言：JavaScript，ASP,PHP,PERL Java語言 既要編譯，又要解釋；編譯只有一次，程序執(zhí)行時(shí)解釋執(zhí)行；通過編譯器，把java程序翻譯成一種中間代碼字節(jié)碼，然后通過JVM解釋成相應(yīng)平臺(tái)的語言。,40,1.4 程序設(shè)計(jì)語言發(fā)展歷程,主流編譯理論會(huì)議 PLDI（ACM Symposium on Programming Language Design and Implementation，編程語言設(shè)計(jì)與實(shí)現(xiàn)） POPL（ACM Symposium on Principles of Programming Languages，編程語言原理） PPoPP（ACM Symposium on Principles and Practice of Parallel Programming，并行編程原理與實(shí)踐） OOPSLA（ACM Conference on Object-Oriented Programming Systems, Languages and Applications，面向?qū)ο蟮木幊滔到y(tǒng)、語言和應(yīng)用）,41,第一章：總結(jié),自然語言處理vs編譯原理 詞法分析,42,第一章：總結(jié),自然語言處理vs編譯原理 語法分析,43,第一章：總結(jié),第一章總結(jié)（1.7）,44,作業(yè),給定一個(gè)后綴表示，比如95+2- 求輸出結(jié)果 C+實(shí)現(xiàn),45,重點(diǎn),什么是編譯器？ 編譯器，解釋器的區(qū)別？ 一個(gè)語言處理系統(tǒng)由哪些部分組成？ 編譯器的前端分析由哪些部分構(gòu)成？ 編譯器的后端分析由哪些部分構(gòu)成？ 什么是詞法分析？ 什么是語法分析？ 什么是標(biāo)識(shí)符，表達(dá)式，語句？ 中間代碼有哪三種表達(dá)方式？ 什么是符號(hào)表？ 什么是出錯(cuò)管理？,46,