編譯第01章.ppt

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

17、,計算機應(yīng)用,已經(jīng)滲透到社會的各個領(lǐng)域 對程序設(shè)計語言也提出了新的要求(如可維護性,可靠性,可移植性等)，從而促進了語言的發(fā)展。,1.4 程序設(shè)計語言發(fā)展簡介,目標(biāo):追求效率 FORTRAN=FORmula TRANslation .主要用于科學(xué)計算 .子程序獨立編譯 .COMMON語句實現(xiàn)了模塊之間的通信,一. 早期的高級語言（50年代）,2. ALGOL 60 ALGOrithmic Language 60 .主要用于科學(xué)計算 .引入了分程序結(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 .具有很強的符號處理能力 .統(tǒng)一的數(shù)據(jù)結(jié)構(gòu) .數(shù)據(jù)和程序統(tǒng)一的表示方法 .其基礎(chǔ)是函數(shù)和函數(shù)作用,二.早期的突破,2. APL .支持函數(shù)式程序設(shè)計風(fēng)格 .廣泛應(yīng)用于涉及大量矩陣運算的科學(xué)計算中 .具有豐富的操作符,3. SNOBOL 4 .主要用于字符串處理 .給出了一種與機器無關(guān)的宏功能,增加了程序的可移植性,PL/1 .希望將所有語言概念集成大全 .分程序概念和遞歸過程 .數(shù)據(jù)描述機能 .動態(tài)數(shù)據(jù)結(jié)構(gòu) .異常處理 .多任務(wù)機能 .可用于科學(xué)數(shù)值計算,數(shù)據(jù)處理等 .難以得到廣泛的應(yīng)用,三. 概念的集成（64年）,引入了許多有趣的概念 1. ALGOL 68 .以零型文法描述形成規(guī)則 .引入正交性和通用性原則,四. 再一次突破(60年代后期),正交性是從幾何中借來的術(shù)語。如果兩條直線相交成直角，它們們就是正交的。用向量術(shù)語來說，這兩條直線互不依賴。 在計算技術(shù)中，該術(shù)語用于表示某種不相依賴性或者解耦性。如果兩個或