1、編譯原理課程代碼：課程代碼：05146 05146 課程名稱：編譯原理課程名稱：編譯原理 （ Compiler PrincipleCompiler Principle） 課程面向?qū)I(yè)：計算機科學與技術課程面向?qū)I(yè)：計算機科學與技術 軟件工程、網(wǎng)絡工軟件工程、網(wǎng)絡工程程課程類型：學科基礎課課程類型：學科基礎課 先修課程：離散數(shù)學，程序設計，數(shù)據(jù)結構先修課程：離散數(shù)學，程序設計，數(shù)據(jù)結構 學學 分：分： 3 3總學時：總學時：48 (48 (其中理論學時：其中理論學時：3838 實驗學時：實驗學時：10)10) 教 材：編譯原理（第2版），張素琴 清華大學出版社，十一五國家級規(guī)劃教材參考文獻：參考

2、文獻：程序設計語言編譯原理（第程序設計語言編譯原理（第3 3版）版），陳火旺等，陳火旺等, , 國防工業(yè)出版社，國防工業(yè)出版社，20002000 編譯程序構造原理和實現(xiàn)技術編譯程序構造原理和實現(xiàn)技術，金成植，金成植 高等教育出社高等教育出社, 2000, 2000 編譯原理美 A.V.Aho等著，李建中等譯 機械工業(yè)出版社，2003編譯原理及編譯程序構造，高仲義 北京航空航天大學出版社，2001編譯原理課程網(wǎng)絡教學資源清華大學計算機系編譯原理課程網(wǎng)站清華大學計算機系編譯原理課程網(wǎng)站: :http:/ 武漢大學編譯原理精品課程教學網(wǎng)站武漢大學編譯原理精品課程教學網(wǎng)站: :http:/221.23

3、2.129.83/jpkc2005/byyl/index.html3/jpkc2005/byyl/index.html 重慶工學院計算機學院編譯原理教學網(wǎng)站：重慶工學院計算機學院編譯原理教學網(wǎng)站：http:/ var i,n,s;begin i:=1; s:=0; read(n); while in do begin s:=s+1; i:=i+1; end; write(s);end.001100011111000111001110001111101010110001010001001111110011000010101100111100010000111

4、1000011101110111000010001101011001110001110101111000011110101000100111100(0)int 0 5(1)lit01(2)sto03(3)lit00(4)sto05(5)opr016(6)sto04(7)lod03(8)lod04(9)opr010(10)jpc020(11)lod05(12)lit01(13)opr02(14)sto05(15)lod03(16)lit01(17)opr02(18)sto03(19)jmp07(20)lod05(21)opr014(22)opr015(23)opr00課程教學目標課程教學目標1

5、1 理解并掌握形式語言的基本概念，具理解并掌握形式語言的基本概念，具備基本應用能力；備基本應用能力；2 2 掌握編譯原理中所涉及算法的基本原掌握編譯原理中所涉及算法的基本原理和運用方法；理和運用方法；3 3 了解并掌握將源語言程序翻譯成目標了解并掌握將源語言程序翻譯成目標語言程序的整個過程。語言程序的整個過程。第一章 引論1.1什麼是編譯程序1.2編譯過程和編譯程序的結構1.3 編譯技術的發(fā)展和應用1.4程序設計語言范型 參考書1.1 什么是編譯程序(compiler)編譯程序是現(xiàn)代計算機系統(tǒng)的基本組成部分. 從功能上看，一個編譯程序就是一個語言翻譯程序,它把一種語言(稱作源語言)書寫的程序翻

6、譯成另一種語言(稱作目標語言)的等價的程序. 功能術語術語S:編譯程序的源 (源程序)O:編譯程序的目標 (目標程序)I:編譯程序的實現(xiàn)語言S OI 高級語言書寫的程序 編譯程序低級語言程序S TI分類軟件系統(tǒng)軟件語言處理系統(tǒng)軟件語言操作系統(tǒng)編譯系統(tǒng)裸機分類軟件：計算機系統(tǒng)中的程序及其文檔系統(tǒng)軟件：居于計算機系統(tǒng)中最靠近硬件的一層，其他軟件一般都通過系統(tǒng)軟件發(fā)揮作用。他和具體的應用領域無關，如編譯系統(tǒng)和操作系統(tǒng)等。語言處理系統(tǒng)：把軟件語言書寫的各種程序處理成可在計算機上執(zhí)行的程序。軟件語言：用于書寫軟件的語言。它主要包括需求定義語言，功能性語言，設計性語言，程序設計語言以及文檔語言。預處理器編

7、譯器匯編器裝配連接編輯骨架程序 源程序 目標匯編程序 可重定位機器代碼 絕對機器碼可重定位目標文件庫語言處理過程語言處理過程術語編譯程序：compiler源程序（源語言）：source program (source language)目標程序（目標語言）：object program (object language)編譯程序的實現(xiàn)語言：implementation language語言處理程序：language processor1.2 編譯過程和編譯程序的結構編譯邏輯過程：詞法分析語法分析語義分析中間代碼生成代碼優(yōu)化目標代碼生成出錯處理語法分析程序語義分析程序目標代碼生成程序詞法分析程序

8、中間代碼生成程序代碼優(yōu)化程序表格管理詞法分析：從左至右讀字符流的源程序、識別(拼)單詞。例： position := initial + rate * 60;單詞類型單詞類型單詞值單詞值 標識符1(id1) position 算符(賦值) := 標識符2(id2) initial 算符(加) + 標識符3(id3) rate 算符(乘) * 整數(shù) 60 分號 ；又如一個C源程序片斷： int a; a = a + 2;單詞類型單詞類型單詞值單詞值 保留字 int標識符(變量名) a界符 ;標識符(變量名) a算符(賦值) =標識符(變量名) a 算符(加) +整數(shù) 2界符 ；有關術語：詞法分析

9、lexical analysis （scanning)單詞token保留字reserved word關鍵字key word標識符identifier(user-defined name)語法分析：功能:層次分析依據(jù)依據(jù)源程序的語法規(guī)則語法規(guī)則把源程序的單詞序列組成語法短語(表示成語法樹).position := initial + rate * 60 ;規(guī)則規(guī)則 “:=” “+” “*” “(”“)” 賦值語句標識符表達式表達式+表達式表達式標識符整數(shù)標識符:=表達式*id1:=id2+id3*N:=+N 60*id1: positionid2: initialid3: rate術語：語法分析

10、syntax analysis （parsing)語法樹parse tree 推導樹derivation tree語義分析：語義審查(靜態(tài)語義)上下文相關性類型匹配類型轉(zhuǎn)換例:Program p();Var rate:real;procedure initial;position := initial + rate * 60 /* error */ /* error */ /* warning */;又如: int arr 2,abc; abc = arr * 10;Program p();Var rate:real; Var initial :real; Var position :real

11、 ; position := initial + rate * 60語義分析：60:=+*id1: positionid2: initialid3: rateint to real語義分析(semantic analysis) 語義分析是審查源程序有無語義錯誤，為代碼生成收集類型信息。例如：語義分析的一個工作是進行類型審查，審查每個算符是否具有語言規(guī)范允許的運算對象，當不符合語言規(guī)范時，編譯程序應報告錯誤。 中間代碼生成：源程序的內(nèi)部(中間)表示id1:= id2 + id3 * 60(1)(int to real, 60-t1)(2)(*,id3 t1t2)(3)(+,id2 t2t3)(4

12、)(:=,t3-id1 )中間代碼生成(intermediate code generation)在進行了上述語法分析和語義分析工作之后，有的編譯程序?qū)⒃闯绦蜃兂梢环N內(nèi)部表示形式，這種內(nèi)部表示形式稱為中間語言或中間代碼。這應該是一種結構簡單、含義明確的記號系統(tǒng)，其設計原則： 1. 1.容易生成；容易生成； 2. 2.容易將其翻譯為目標代碼。容易將其翻譯為目標代碼。代碼優(yōu)化：id1:= id2 + id3 * 60(1)(int to real60-t1)(2)( * id3t1t2)(3)( +id2t2t3)(4)( :=t3-id1) 變換變換 （1） ( * id360.0t1) ( 2

13、）（ + id2 t1id1)代碼優(yōu)化：t1 = b* c t1 = b* c t2 = t1+ 0 t2 = t1 + t1t3 = b* c a = t2t4 = t2 + t3a = t4代碼優(yōu)化(code optimization)代碼優(yōu)化的任務是對前階段生成的中間代碼進行變換或改造，其目的是使生成的目標代碼更為高效，即省時間、省空間。目標代碼生成：(*,id360.0t1)(+,id2t1id1)movfid3,R2mulf#60.0,R2movfid2,R1addfR2,R1movfR1,id1目標代碼生成的任務是將中間代碼變換為特定計算機上的絕對指令代碼、可重定位的指令代碼，或匯

14、編指令代碼。這是整個編譯過程的最后階段，與計算機的硬件系統(tǒng)結構以及指令系統(tǒng)直接相關。符號表管理記錄源程序中使用的名字收集每個名字的各種屬性信息類型、作用域、分配存儲信息Const1常量值：35Var1變量類型：實層次：2符號表(symbol table)編譯過程中源程序的各種信息均應保留在符號表中，使得編譯過程的各個階段都必然涉及到構造、查找或更新這些符號表，因此必須有完善的符號表管理功能。出錯處理檢查錯誤、報告出錯信息、排錯、恢復編譯工作。錯誤處理的任務是發(fā)現(xiàn)源程序中的錯誤，報告錯誤的性質(zhì)和錯誤發(fā)生能的位置，并將錯誤所造成的影響限制在盡可能小的范圍之內(nèi)。甚至還可以考慮在檢測到錯誤時能夠自動更

15、正錯誤。編譯程序結構(components)詞法分析程序語法分析程序語義分析程序中間代碼生成程序代碼優(yōu)化程序目標代碼生成程序符號表管理程序出錯處理程序出錯處理語法分析程序語義分析程序目標代碼生成程序詞法分析程序中間代碼生成程序代碼優(yōu)化程序表格管理編譯階段的組合編譯的前端（front end）由那樣一些階段組成： 這些階段的工作主要依賴于源語言而與目標機器無關。編譯的后端（back end）由那樣一些階段組成： 這些階段的工作主要依賴于目標機器而一般不依賴源語言，只與中間代碼有關。遍（趟）遍（趟）( (pass)pass)： 是對源程序或其對等的中間語言程序從是對源程序或其對等的中間語言程序從頭

16、到尾掃視并完成規(guī)定任務的過程。頭到尾掃視并完成規(guī)定任務的過程。高級語言解釋系統(tǒng)(interpreter)功能 讓計算機執(zhí)行高級語言（basic,lisp,prolog)與編譯程序的不同 1）不生成目標代碼 2）能支持交互環(huán)境 （同增量式編譯系統(tǒng)） 源 程 序 初始數(shù)據(jù) 解釋程序計算結果解釋系統(tǒng)直接對源程序中的語句進行分析，執(zhí)行其隱含的操作。如： b := 2 ; a := b+2 ; 編譯程序 write a ; 解釋程序解釋程序直接將4的值輸出（顯示）Int 2St bLd badd 2St a生成代碼 編譯階段和運行階段存儲結構 編譯時 運行時 名字表目標代碼緩沖區(qū)編譯用源程序中間表示各種

17、表格目標代碼區(qū)數(shù)據(jù)區(qū)源程序緩沖區(qū)解釋系統(tǒng)存儲結構解釋系統(tǒng)源程序工作單元名字表標號表緩沖區(qū)(輸入輸出)棧區(qū)1.3 編譯技術的發(fā)展和應用功能：程序 集成環(huán)境實現(xiàn)方式手工機器語言匯編系統(tǒng)程序設計語言自動構造工具lex yaccS OI 編譯程序的發(fā)展Human-orientedlanguageComputer-orientedlanguage計算模式，語言范式語言應用領域編譯程序馮.諾依曼機體系結構并行體系結構嵌入系統(tǒng) 編譯程序的發(fā)展語言范型(paradigms)命令式(imperative language)應用式(applicative)基于規(guī)則的（rule-based）面向?qū)ο蟮模╫bject

18、-oriented）編譯程序執(zhí)行環(huán)境批處理交互環(huán)境嵌入系統(tǒng)環(huán)境 語言范型（支持的計算模式） 命令式：程序特點： 語言執(zhí)行的解釋： 編譯技術發(fā)展快：語句1； 改變機器狀態(tài) 系統(tǒng)語言語句2； 內(nèi)存 自動化生成技術語句3； 各種寄存器 的內(nèi)容 外存 與馮.諾依曼機 體系結構一般 應用式（函數(shù)式）：程序特點： Function n(funetion2(funetion1(data)程序執(zhí)行： 執(zhí)行一個個函數(shù)施用在數(shù)據(jù)上的變換最終得到的結果編譯： 語法分析容易； 語義處理復雜； 基于規(guī)則的語言（prolog,yacc)：程序特點： 使能條件1 動作1 使能條件2 動作2 使能條件3 動作3 面向?qū)ο笳Z言

19、： 抽象數(shù)據(jù)類型，繼承機制編譯： 動態(tài)綁定； 執(zhí)行環(huán)境批處理環(huán)境： 將源程序作為整體處理 排除程序錯誤不能依靠用戶的外部幫助交互環(huán)境： 解釋 增量式編譯嵌入式系統(tǒng)環(huán)境：交叉編譯分布并行環(huán)境： 并行編譯程序創(chuàng)建和測試環(huán)境： 獨立編譯 編譯和調(diào)試同時設計考慮 編譯技術的發(fā)展和應用結構化編譯器程序分析工具 靜態(tài)分析 動態(tài)分析 度量工具 結構度量 模塊接口復雜度 c分析工具(source insight) 廣泛的語言領域 數(shù)據(jù)庫系統(tǒng)查詢 腳本語言 置標語言(SGML.HTML.XML)研究領域并行編譯技術交叉編譯技術硬件描述語言及其編譯技術并行化編譯技術目的：提高并行計算機體系結構的性能。超大規(guī)模計算的日益增長的需求 高性能計算機 并行軟件并行體系結構單機速度 并行體系結構途徑1途徑2 并行體系結構 編譯技術支持 串行程序并行化編譯技術支持 并行程序設計語言編譯 依賴于目標機的優(yōu)化（低層） 性能發(fā)揮 并行算法復雜，難掌握，難編程 開發(fā)并行 軟件的困難 并行程序行為不確定，難調(diào)試，難驗證設計新的并行算法 修改已有串行程序盡量（