編譯第01章.ppt

1、編譯原理,陳文宇 電子科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院,陳文宇聯(lián)系方式,科A樓514（實(shí)驗(yàn)室） 主樓B1-509（辦公室）,程序設(shè)計(jì)語言與編譯 -語言的設(shè)計(jì)與實(shí)現(xiàn)（4版） 王曉斌 陳文宇 等 編著 龔天富 審 2015 電子工業(yè)出版社,一.教材,二. 參考書,1. 龔天富等 高級程序設(shè)計(jì)語言概論 2. 陳火旺等 編譯原理(3版)2004 3 Alfred V.Aho 等 趙建華 等譯 編譯原理龍書 機(jī)械工業(yè)出版社 4 Andrew W.Appel 等 趙克佳 等譯 現(xiàn)代編譯原理-虎書 人民郵電出版社,1. 課程設(shè)置: 56=48+8 學(xué)時(shí) 2. 先修課程 ,三. 關(guān)于教學(xué)

2、,四. 成績構(gòu)成,平時(shí) 10% 作業(yè)+課堂測驗(yàn) 半期 10% 實(shí)驗(yàn) 10% 期末 70% 課堂點(diǎn)名、測驗(yàn)、作業(yè) 累加到4次： 取消考試資格（教務(wù)處要求）,五. 教學(xué)內(nèi)容,涉及語言及其編譯系統(tǒng)的設(shè)計(jì)要素、設(shè)計(jì)思想、設(shè)計(jì)方法和設(shè)計(jì)技術(shù)等 1)上篇，程序設(shè)計(jì)語言的設(shè)計(jì) 緒論、數(shù)據(jù)類型 控制結(jié)構(gòu)、語言設(shè)計(jì),2)下篇，程序設(shè)計(jì)語言的實(shí)現(xiàn)（編譯） 編譯概述、詞法分析、語法分析 語義分析和中間代碼生成 代碼優(yōu)化和目標(biāo)代碼生成 運(yùn)行時(shí)存儲(chǔ)空間的組織,六.學(xué)習(xí)目標(biāo),掌握設(shè)計(jì)和實(shí)現(xiàn)一個(gè)程序設(shè)計(jì)語言的基本思想和方法。 具有分析、鑒賞、評價(jià)、選擇、學(xué)習(xí)、設(shè)計(jì)和實(shí)現(xiàn)語言的基本能力。,七. 課程的重要性,20世紀(jì)50年代

3、，出現(xiàn)了與機(jī)器無關(guān)的編程語言（高級程序設(shè)計(jì)語言）。 第一個(gè)編譯器是由葛麗絲穆雷霍普（ Grace Murray Hopper ）于1952年為A-0 系統(tǒng)編寫的。 1957年由IBM的約翰巴科斯領(lǐng)導(dǎo)開發(fā)的FORTRAN語言編譯器則是第一個(gè)具備完整功能的編譯器,課程的重要性,編譯技術(shù)已經(jīng)成為計(jì)算機(jī)科學(xué)中發(fā)展最迅速、最成熟的一個(gè)重要分支。 編譯技術(shù)集中體現(xiàn)了計(jì)算機(jī)科學(xué)發(fā)展的重要成果與精華。,課程的重要性,ACM圖靈獎(jiǎng)是授予在計(jì)算機(jī)技術(shù)領(lǐng)域作出突出貢獻(xiàn)的科學(xué)家的最高獎(jiǎng)勵(lì). 自1966年設(shè)立以來，程序設(shè)計(jì)語言、編譯理論的成果約占總數(shù)的1/3。,課程的重要性,從計(jì)算機(jī)應(yīng)用的發(fā)展來看，編譯技術(shù)在其中有著極

4、其重要的和不可替代的作用。 正是在編譯技術(shù)的支持下，程序設(shè)計(jì)才從以繁瑣的低級語言為工具，發(fā)展到以接近自然語言和數(shù)學(xué)語言的高級程序設(shè)計(jì)語言為工具;,課程的重要性,編譯技術(shù)的發(fā)展極大地提高了軟件開發(fā)的效率，深刻地影響著軟件開發(fā)方法的變革。,通過本課程的學(xué)習(xí),1)掌握和理解語言設(shè)計(jì)的理論和方法； 2)掌握和理解編譯系統(tǒng)的各組成部分的設(shè)計(jì)原理和實(shí)現(xiàn)技術(shù)； 3)提高對程序設(shè)計(jì)語言、操作系統(tǒng)、計(jì)算機(jī)組成原理、算法分析和體系結(jié)構(gòu)等課程知識的綜合理解。,結(jié)論,從計(jì)算機(jī)專業(yè)人才的知識結(jié)構(gòu)和專業(yè)素養(yǎng)的培養(yǎng)而言 編譯原理是高等學(xué)校培養(yǎng)計(jì)算機(jī)專業(yè)人才的核心課程,內(nèi)容安排,上篇 程序設(shè)計(jì)語言的設(shè)計(jì) 下篇 程序設(shè)計(jì)語言的

5、實(shí)現(xiàn),第一章 緒論,本章討論程序設(shè)計(jì)語言中的一些重要概念，為深入了解程序設(shè)計(jì)語言打下基礎(chǔ)。 簡介程序設(shè)計(jì)語言的發(fā)展歷史。,1.1 引言,1.程序設(shè)計(jì)語言的產(chǎn)生 語言是人們交流思想的工具。人類在長期的歷史發(fā)展過程中，為了交流思想、表達(dá)感情和交換信息，逐步形成了語言-自然語言。 程序設(shè)計(jì)語言:人工語言,程序設(shè)計(jì)語言programming language,程序設(shè)計(jì)語言是一組規(guī)則，包括： 1）字母表的定義； 2）詞法規(guī)則：單詞符號的形成規(guī)則 C語言單詞符號包括： 關(guān)鍵字、 標(biāo)識符、 運(yùn)算符 常量 、分界符,程序設(shè)計(jì)語言,3）語法規(guī)則：語法單位的形成規(guī)則 C語言語法單位包括： 表達(dá)式、語句、函數(shù)、程序

6、 4）語義規(guī)則： 單詞符號和語法單位的含義規(guī)則；,程序設(shè)計(jì)語言,5)語用規(guī)則：語義規(guī)則的發(fā)展和延伸 強(qiáng)調(diào)在一定的語境中使用單詞和語法單位時(shí)體現(xiàn)出來的具體意義；要根據(jù)上下文（即前、后內(nèi)容）明確單詞和語法單位的具體意義 6）其他規(guī)則：包括類型使用規(guī)則，參數(shù)傳遞規(guī)則，作用域規(guī)則等。,程序設(shè)計(jì)語言,計(jì)算機(jī)程序設(shè)計(jì)語言的發(fā)展，經(jīng)歷了從機(jī)器語言、匯編語言到高級語言的歷程。,2.程序設(shè)計(jì)語言的發(fā)展,機(jī)器語言匯編語言高級語言 用機(jī)器語言編寫的程序由二進(jìn)制指令組成，計(jì)算機(jī)可以直接執(zhí)行。 將機(jī)器語言符號化，產(chǎn)生了匯編語言。,對于機(jī)器語言和匯編語言： 指令的操作碼與功能、指令格式、尋址方式、數(shù)據(jù)格式等，不同的計(jì)算機(jī)

7、有不同的規(guī)定：機(jī)器有關(guān)的語言，通常稱為低級語言。 與機(jī)器無關(guān)的程序設(shè)計(jì)語言，通常稱為高級語言。,直觀、自然、易于理解 易讀，易寫，易于交流、存檔 一般都是獨(dú)立于機(jī)器的,易于移植,3.高級語言的特點(diǎn),翻譯:等價(jià)的變換,計(jì)算機(jī)只可直接執(zhí)行用機(jī)器語言編寫的程序。 而用匯編語言和高級語言編寫的程序，機(jī)器不能直接執(zhí)行 必須將它們翻譯成完全等價(jià)的機(jī)器語言程序才能執(zhí)行,將匯編語言程序翻譯為機(jī)器語言程序的程序稱為匯編程序（匯編器） 將高級語言程序翻譯為低級語言程序的程序稱為編譯程序（編譯器） 編寫一個(gè)高級語言的編譯程序的工作，通常稱為對這個(gè)語言的實(shí)現(xiàn)。,語言另一種執(zhí)行方式：解釋,BASIC是最簡單的高級語言

8、它不是編譯執(zhí)行，而是對源程序進(jìn)行解釋（分析），直接計(jì)算出結(jié)果。 需要解釋程序(解釋器)支持,LISP，ML，Prolog和Smalltalk均是解釋型的語言。 Java被當(dāng)作一種解釋型語言。 翻譯產(chǎn)生字節(jié)碼的中間代碼， 可以在Java虛擬機(jī)上運(yùn)行。,解釋執(zhí)行特別適合于動(dòng)態(tài)語言和交互式環(huán)境，便于人機(jī)對話。 解釋器邊翻譯邊解釋執(zhí)行，重復(fù)執(zhí)行的語句需要重復(fù)翻譯，比編譯執(zhí)行要花去更多的時(shí)間，執(zhí)行效率較低。,4.與編譯有關(guān)的三種語言、三種程序 源語言、工具語言、目標(biāo)語言 源程序、編譯程序、目標(biāo)程序 5.高級語言涉及的三類人 設(shè)計(jì)者、實(shí)現(xiàn)者、使用者,1.2 強(qiáng)制式語言,一.程序設(shè)計(jì)語言的分類 按設(shè)計(jì)的理論

9、基礎(chǔ)分為4類語言: 強(qiáng)制式語言:基礎(chǔ)是馮諾依曼模型 函數(shù)式語言:基礎(chǔ)是數(shù)學(xué)函數(shù)(函數(shù)運(yùn)算) 邏輯式語言:基礎(chǔ)是數(shù)理邏輯、謂詞演算 對象式語言:基礎(chǔ)是抽象數(shù)據(jù)類型,第一代語言（機(jī)器語言） 第二代語言（匯編語言） 第三代語言（高級語言:命令式、過程式） 第四代語言（說明性語言、超高級語言） 新一代語言（函數(shù)式、邏輯式語言）,按語言的發(fā)展進(jìn)程分類:,1.基礎(chǔ) 存儲(chǔ)器,控制器,處理器，ip 2.特點(diǎn) 數(shù)據(jù)、指令以二進(jìn)制形式存儲(chǔ); 存儲(chǔ)程序的工作方式； 程序順序執(zhí)行；可強(qiáng)制修改執(zhí)行順序 存儲(chǔ)器的內(nèi)容可以被修改。,二. 馮.諾依曼體系結(jié)構(gòu)（模型）,ip,代碼存儲(chǔ)器（C）,數(shù)據(jù)存儲(chǔ)器（D）,3.在命令式語言

10、上的表現(xiàn) 變量 存儲(chǔ)單元及名稱由變量的概念代替。變量可以代表一個(gè)或一組單元。 賦值 存儲(chǔ)計(jì)算結(jié)果。 重復(fù) 語句順序執(zhí)行,指令存儲(chǔ)在有限的存儲(chǔ)器中,完成復(fù)雜計(jì)算時(shí)需要重復(fù)執(zhí)行某些指令序列。,馮.諾依曼體系結(jié)構(gòu)(模型),實(shí)體：程序的組成部分，如變量，表達(dá)式、程序單元等。 屬性：實(shí)體具有的特性。 綁定：實(shí)體與其各種屬性建立起聯(lián)系的過程稱為綁定，實(shí)際上就是建立了某種約束。 描述符：描述實(shí)體屬性的表格。,三. 綁定（Binding)概念,編譯時(shí)能確定的特性-靜態(tài)特性 運(yùn)行時(shí)才能確定的特性-動(dòng)態(tài)特性,靜態(tài)和動(dòng)態(tài)特性,若綁定在運(yùn)行之前(即編譯時(shí))完成，且在運(yùn)行時(shí)不會(huì)改變，則稱為靜態(tài)綁定。 若綁定在運(yùn)行時(shí)完成

11、，則稱為動(dòng)態(tài)綁定。,四 變量,變量是對一個(gè)或若干個(gè)存儲(chǔ)單元的抽象 一個(gè)變量至少占用一個(gè)存儲(chǔ)單元；一個(gè)存儲(chǔ)單元至少一個(gè)字節(jié)（也可以為2個(gè)字節(jié)、 4個(gè)字節(jié)） 變量用名字來標(biāo)識 變量也可以不具有名字-匿名變量 賦值是對修改存儲(chǔ)單元內(nèi)容的抽象,變量的4個(gè)屬性： 作用域、生存期、值、類型,1.變量的作用域,可以訪問該變量的程序范圍。 靜態(tài)作用域綁定:按照程序的結(jié)構(gòu)定義變量的作用域（C語言等）。 動(dòng)態(tài)作用域綁定:按照程序的執(zhí)行動(dòng)態(tài)地定義變量的作用域（SNOBL4 語言等） 。,2.變量的生存期,存儲(chǔ)區(qū)綁定于一個(gè)變量的時(shí)間區(qū)間。 編譯階段 數(shù)據(jù)由變量和常量表示 運(yùn)行階段 數(shù)據(jù)由數(shù)據(jù)對象表示 數(shù)據(jù)對象表示存儲(chǔ)

12、區(qū)和它保存的值。 變量獲得存儲(chǔ)區(qū)的活動(dòng)稱為分配。 變量分配的存儲(chǔ)單元的個(gè)數(shù)-變量長度。,運(yùn)行前分配變量存儲(chǔ)區(qū) -靜態(tài)分配（FORTRAN語言） 運(yùn)行時(shí)分配變量存儲(chǔ)區(qū) -動(dòng)態(tài)分配（C 、C+語言） 分配原則，由語言(設(shè)計(jì)者)規(guī)定。,動(dòng)態(tài)分配通過兩種途徑來實(shí)現(xiàn)： 用相關(guān)的語句顯式提出請求(new) 運(yùn)行變量所對應(yīng)的程序單元時(shí)自動(dòng)分配。,3.變量的值,存儲(chǔ)區(qū)單元的內(nèi)容 變量在生存期內(nèi)綁定于一個(gè)存儲(chǔ)區(qū)，該存儲(chǔ)區(qū)中的內(nèi)容以二進(jìn)制編碼方式表示的變量值，并綁定于變量。 值按變量所綁定的類型來進(jìn)行解釋。,訪問匿名變量的基本方法是通過訪問路徑來實(shí)現(xiàn)的。 變量的值在程序運(yùn)行時(shí)可以通過賦值操作來修改，因此，變量與它

13、的值的綁定是動(dòng)態(tài)的。 常數(shù)（量）的值不能修改。,初始值問題,變量獲得所分配的存儲(chǔ)區(qū)，完成變量與存儲(chǔ)區(qū)的綁定。 此時(shí)，該變量綁定的值是什么呢？即變量初始化問題。 不同的語言有不同的規(guī)則： 不初始化則出錯(cuò) 隨機(jī) 缺省值0,4.變量的類型,與變量相關(guān)聯(lián)的值，以及對這些值進(jìn)行的操作的抽象。 類型可用來解釋變量綁定的存儲(chǔ)區(qū)的內(nèi)容(二進(jìn)制編碼)的意義； 語言定義時(shí),類型綁定于值和操作; 語言實(shí)現(xiàn)時(shí),值和操作綁定于某種機(jī)器二進(jìn)制表示。,變量類型可以靜態(tài)或動(dòng)態(tài)地進(jìn)行綁定 靜態(tài)綁定：通過說明語句完成 動(dòng)態(tài)綁定：執(zhí)行時(shí)隱式說明，且動(dòng)態(tài)變化 A 5 整型 A 1 2 51 0 一維數(shù)組 A 0 A2:3 0 二維數(shù)

14、組 ？,動(dòng)態(tài)綁定的語言實(shí)現(xiàn)采用解釋方式處理更合適，因?yàn)閷τ谝粋€(gè)不能確定變量類型的表達(dá)式，在運(yùn)行之前沒有足夠的信息來生成合適的代碼。 語言實(shí)現(xiàn)采用編譯還是解釋方式，受到變量與類型綁定規(guī)則的嚴(yán)重影響。,靜態(tài)綁定語言是面向編譯的語言。 動(dòng)態(tài)綁定語言是面向解釋的語言。 動(dòng)態(tài)類型綁定的語言，往往其作用域也是動(dòng)態(tài)綁定的，因此，這類語言又稱為動(dòng)態(tài)語言。,M1是實(shí)際的機(jī)器， 匯編語言程序要在M1和匯編程序上執(zhí)行， M1+匯編程序=M2 虛擬機(jī)M2的機(jī)器語言是匯編語言 M2+編譯程序=M3 虛擬機(jī)M3以高級語言為機(jī)器語言(對用戶而言),五.虛擬機(jī)：軟件實(shí)現(xiàn)的機(jī)器,虛擬機(jī)是由實(shí)際機(jī)器加軟件實(shí)現(xiàn)的機(jī)器。 若一臺實(shí)際

15、機(jī)器配置上C語言編譯程序，對用戶來說，這臺機(jī)器就是C語言的虛擬機(jī)（C語言機(jī)）。,六. 主要的強(qiáng)制式語言及其關(guān)系,1.(程序)單元:程序執(zhí)行過程中的被獨(dú)立調(diào)用單元：子程序,分程序,過程等 2.單元表示 編譯時(shí)，單元表示為單元的源程序。 運(yùn)行時(shí)，單元表示由一個(gè)代碼段和一個(gè)活動(dòng)記錄組成，稱為單元實(shí)例。,1.3 程序單元,3.活動(dòng)記錄:執(zhí)行單元需要的信息,及該單元的局部變量的存儲(chǔ)區(qū)。 4.非局部變量:一個(gè)程序單元可以引用未被本單元說明而被其它單元說明的變量。 5.全局變量:在一個(gè)程序中，各個(gè)程序單元都可以引用的變量。,6.引用環(huán)境,一個(gè)程序單元U可以引用的局部變量、非局部變量和全局變量。 局部變量綁定

16、于存儲(chǔ)在U的當(dāng)前活動(dòng)記錄中的數(shù)據(jù)對象，稱為局部環(huán)境。,非局部變量綁定于別的(說明該非局部變量)程序單元的活動(dòng)記錄或全局?jǐn)?shù)據(jù)區(qū)中的數(shù)據(jù)對象，稱為非局部環(huán)境,以C語言為例,C程序運(yùn)行時(shí)的存儲(chǔ)空間： （1）程序代碼區(qū)： 存儲(chǔ)程序代碼（編譯后形成的二進(jìn)制機(jī)器指令序列）,（2）數(shù)據(jù)靜態(tài)存儲(chǔ)區(qū)：存儲(chǔ)程序的常量數(shù)據(jù)、全局?jǐn)?shù)據(jù)和static數(shù)據(jù)。 （3）數(shù)據(jù)動(dòng)態(tài)存儲(chǔ)區(qū)： 活動(dòng)記錄(桟)：返回地址、CPU現(xiàn)場、形參、局部變量、臨時(shí)變量 存儲(chǔ)動(dòng)態(tài)內(nèi)存申請數(shù)據(jù)(堆),7.別名,同一單元的引用環(huán)境中有兩個(gè)或多個(gè)變量綁定于同一數(shù)據(jù)對象，稱這些變量具有別名。,8.副作用,對一個(gè)非局部變量的進(jìn)行修改。,隨著計(jì)算機(jī)技術(shù)的發(fā)展

17、,計(jì)算機(jī)應(yīng)用,已經(jīng)滲透到社會(huì)的各個(gè)領(lǐng)域 對程序設(shè)計(jì)語言也提出了新的要求(如可維護(hù)性,可靠性,可移植性等)，從而促進(jìn)了語言的發(fā)展。,1.4 程序設(shè)計(jì)語言發(fā)展簡介,目標(biāo):追求效率 FORTRAN=FORmula TRANslation .主要用于科學(xué)計(jì)算 .子程序獨(dú)立編譯 .COMMON語句實(shí)現(xiàn)了模塊之間的通信,一. 早期的高級語言（50年代）,2. ALGOL 60 ALGOrithmic Language 60 .主要用于科學(xué)計(jì)算 .引入了分程序結(jié)構(gòu)和遞歸過程 .采用BNF形式描述語法,3. COBOL COmmon Business Oriented Language .廣泛應(yīng)用于各種事務(wù)處

18、理領(lǐng)域 .引入了文件和數(shù)據(jù)描述 .類自然語言程序描述,60年代初，不再盲目地追求效率,出現(xiàn)了基于良好刻畫數(shù)學(xué)原則的語言。 1. LISP .具有很強(qiáng)的符號處理能力 .統(tǒng)一的數(shù)據(jù)結(jié)構(gòu) .數(shù)據(jù)和程序統(tǒng)一的表示方法 .其基礎(chǔ)是函數(shù)和函數(shù)作用,二.早期的突破,2. APL .支持函數(shù)式程序設(shè)計(jì)風(fēng)格 .廣泛應(yīng)用于涉及大量矩陣運(yùn)算的科學(xué)計(jì)算中 .具有豐富的操作符,3. SNOBOL 4 .主要用于字符串處理 .給出了一種與機(jī)器無關(guān)的宏功能,增加了程序的可移植性,PL/1 .希望將所有語言概念集成大全 .分程序概念和遞歸過程 .數(shù)據(jù)描述機(jī)能 .動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu) .異常處理 .多任務(wù)機(jī)能 .可用于科學(xué)數(shù)值計(jì)算,數(shù)據(jù)處理等 .難以得到廣泛的應(yīng)用,三. 概念的集成（64年）,引入了許多有趣的概念 1. ALGOL 68 .以零型文法描述形成規(guī)則 .引入正交性和通用性原則,四. 再一次突破(60年代后期),正交性是從幾何中借來的術(shù)語。如果兩條直線相交成直角，它們們就是正交的。用向量術(shù)語來說，這兩條直線互不依賴。 在計(jì)算技術(shù)中，該術(shù)語用于表示某種不相依賴性或者解耦性。如果兩個(gè)或