遼寧大學編譯原理課件part.ppt

1、2020/12/7,1,編譯原理(Principles of Compiling),主講：周翰遜 QQ：26054036,2020/12/7,2,編譯原理課程簡介,地位 計算機專業(yè)的一門核心課程 編譯程序是計算機的重要系統(tǒng)軟件，是高級程序設計語言的支撐基礎 課程主要介紹設計和構造編譯程序的基本原理和方法,2020/12/7,3,用途與作用,這是本專業(yè)應具備的基本知識，就像其他原理一樣，是基礎。 三大系統(tǒng)軟件： OS、DBMS、Compiling System 開發(fā)大型系統(tǒng)軟件、工具軟件的需要。 看資料、寫論文的需要,2020/12/7,4,編譯原理前導課程,前導課程及涉及內(nèi)容 組成原理計算機組

2、成及結構 微機原理匯編語言與機器語言 離散數(shù)學推理知識及其完備性 數(shù)據(jù)結構樹、表等的表示與實現(xiàn) 操作系統(tǒng)提供虛擬機和系統(tǒng)調(diào)用 高級程序設計語言語言定義和編程,2020/12/7,5,意義: 學習編譯程序構造原理，技術 更好地理解高級語言 編譯的原理和方法有助于構造一些實用的工具,2020/12/7,6,課程特點: 理解性 技術性 考核： 筆試 80% 平時出勤+作業(yè) 20%,2020/12/7,7,學時與參考教材,學時：51學時(15周)，4學時 參考教材： 1、陳火旺等，程序設計語言編譯原理（第3版），國防工業(yè)出版社，2003.8.印刷 2、高仲儀、金茂忠，編譯原理及編譯程序構造，北航出版社

3、。 3、 龍書：Alfred Aho ect.， 編譯原理，李建中等譯，機械工業(yè)出版社，2003.8.(原版-郵電出版社) 4、Kenneth C. Louden，編譯原理及實踐，馮博琴等譯，機械工業(yè)出版社，2001.2.印刷,2020/12/7,8,學時與參考教材,參考教材(續(xù))： 5、金成植，編譯程序構造原理和實現(xiàn)技術，高等教育出版社，2000.7. 6、高仲儀等，編譯技術，西北工業(yè)大學出版社，1985.9 7、何炎祥等，編譯原理，華中理工大學出版社，2000.10. 8、P.M.劉易斯，編譯程序設計理論，科學出版社，1984.5. ,2020/12/7,9,陳火旺生平,陳火旺（1936

4、02.05 - 2008 02.02）福建省安溪縣人。中國工程院院士，國防科學技 術大學計算機學院教授、博士生導師，于2008年2月2日因病醫(yī)治無效，在長沙逝世，72歲。 1956年畢業(yè)于上海復旦大學數(shù)學系，同年加入中國共產(chǎn)黨，留校任助教。曾在北京大學數(shù)理邏輯專業(yè)、英國國家物理所進修。1970年調(diào)長沙工學院（后改名國防科技大學），歷任（電子）計算機系副教授、系副主任、教授、博士生導師、研究生院副院長。1990年被授予少將軍銜。 1997年當選為中國工程院信息與電子工程學部院士。是武漢大學軟件工程國家重點實驗室學術委員會主任，國務院學位委員會計算機學科評議組成員，全國工科院校計算機專業(yè)教學指導委

5、員會主任，國家“863計劃”信息領域第一屆專家委員會委員，中國軟件行業(yè)協(xié)會副主任委員。 成就及榮譽 1991年被授予國家有突出貢獻中青年專家稱號，同年獲光華科學基金一等獎。長期從事計算機軟件和人工智能等方面的教學和研究。建立了有限函數(shù)空間上的能行運算和能行連續(xù)泛函理論；主持國內(nèi)第一個符號匯編語言和宏指令產(chǎn)生器的設計與實現(xiàn)；主持中國第一個FORTRAN編譯程序的設計，獲1978年全國科學大會獎；參與領導中國第一臺巨型計算機銀河I的研制，負責軟件系統(tǒng)總體設計，獲特等國防科技成果獎；主持國內(nèi)最早的一個面向?qū)ο蠹苫浖_發(fā)環(huán)境GWOSE的研制，獲國防科工委科技進步一等獎；領導自然語言處理的研究，研制

6、成功英漢機器編譯系統(tǒng)MATRIX，獲全國優(yōu)秀軟件二等獎；在人工智能方面主持研制的非單調(diào)推理系統(tǒng)1993年獲國防科工委科技進步一等獎。撰有能行連續(xù)泛函、串行運算向量化等論文、研究報告60余篇；主編有數(shù)理邏輯與控制論、程序設計語言編譯原理、程序設計方法學基礎等。 陳火旺院士為我國計算機軟件與理論學科的建立和發(fā)展作出了貢獻，為國家、軍隊和學校人才培養(yǎng)、科學研究作出了貢獻。,2020/12/7,10,主要內(nèi)容,編譯系統(tǒng)及其設計概述(總體結構、設計方法；3) 語言與文法(文法、推導、歸約、分類、分析樹；5) 詞法分析(詞法分析、正規(guī)式與正規(guī)文法、DFA狀態(tài)轉移圖；8) 語法分析(自頂向下：LL(1)、遞

7、歸子程序；自底向上：算符優(yōu)先、LR；15) 語義分析(屬性文法、各種語句的語法制導翻譯；12) 運行環(huán)境(存儲分配、過程調(diào)用、符號表管理；3) 無：代碼優(yōu)化與代碼生成(基本塊與流圖、局部優(yōu)化、馴化優(yōu)化、代碼生成；2) 總結(2),2020/12/7,11,教學目的計算學科是一個寬泛的學科,用戶,多層虛擬系統(tǒng) ,開發(fā)利用,工程實現(xiàn),計算機理,呈現(xiàn)抽象、理論、設計三種學科形態(tài),性能越來越好 使用越來越方便,2020/12/7,12,教學目的計算學科的定義,關鍵：由計算機自動完成/實現(xiàn)自動計算 對信息描述和變換算法的系統(tǒng)研究，主要包括它們的理論、分析、效率、實現(xiàn)和應用 計算學科的根本問題是什么能且如

8、何被有效地自動計算 討論問題求解的“能行性”,2020/12/7,13,教學目的計算學科各有分工,科學,工程,技術,：發(fā)現(xiàn)規(guī)律,：構建系統(tǒng),：實現(xiàn)服務,計算學科,涉及,2020/12/7,14,教學目的學科基本特征,形式化、抽象、邏輯,符號、符號變換,特點,表現(xiàn)形式,2020/12/7,15,教學目的計算學科本科生專業(yè)能力構成,編譯原理的授課涉及上述四種能力的培養(yǎng),計算思維 算法設計 程序?qū)崿F(xiàn) 系統(tǒng)開發(fā),公共基礎系列 基礎理論系列 程序與算法系列 軟件系統(tǒng)系列 (系統(tǒng)級的再認識與再提高) 硬件技術系列,學科基礎能力,工程型 應用型,科學型,2020/12/7,16,教學目的編譯原理是一門非常好

9、的課程,Alfred V.Aho：編寫編譯器的原理和技術具有十分普遍的意義，以至于在每個計算機科學家的研究生涯中，本書中的原理和技術都會反復用到 涉及的是一個比較適當?shù)某橄髮用嫔系臄?shù)據(jù)變換（既抽象，又實際） 既有一些具體的表示和變換算法；又是針對一類問題的求解（自動計算的具體體現(xiàn)）,2020/12/7,17,教學目的編譯原理是一門非常好的課程,一個相當規(guī)模的、邏輯結構清晰系統(tǒng)的設計（含總體結構） “自頂向下”和“自底向上”的系統(tǒng)設計方法（思想、方法、實現(xiàn)） 結論：計算機專業(yè)最恰當、有效的知識載體之一 編譯：掌握“編譯原理”中的基本概念、基本理論、基本方法，在系統(tǒng)級上再認識程序和算法，提升計算機

10、問題求解的水平，增強系統(tǒng)能力，體驗實現(xiàn)自動計算的樂趣,2020/12/7,18,教學要求,知識層面 掌握編譯程序總體結構系統(tǒng)能力基礎 掌握程序變換基本概念、問題描述和處理方法，學習有關的原理、實現(xiàn)方法和技術，掌握典型方法 （自頂向下、自底向上、逐步求精、遞歸求解，目標驅(qū)動，問題分析、問題的抽象與形式化描述，算法設計與實現(xiàn)，系統(tǒng)構建、模塊化 ） 增強理論結合實際能力，獲得更多的“頂峰體驗” 程序?qū)崿F(xiàn)實現(xiàn)能力基礎,2020/12/7,19,教學要求,能力層面 理論與實踐的結合能力：理論指導系統(tǒng)實現(xiàn) 系統(tǒng)能力：在系統(tǒng)級上認識算法、系統(tǒng)的設計，從宏觀到微觀、從微觀到宏觀，提高把握系統(tǒng)的能力 較大規(guī)模程

11、序的設計與實現(xiàn) 形式化描述能力：修養(yǎng)“問題、形式化描述、計算機化”問題求解典型過程，推進從“實例計算”到“類計算”和“模型計算”的跨越 程序語言：兼顧語言描述方法、設計、應用,2020/12/7,20,學習方法,學習是一個過程 上課、讀書、復習、做作業(yè)、討論、做實驗、自己編程序、上機調(diào)試排錯是絕對必要的，不可缺的 上課 課堂是本科教育的主要渠道：不要放棄自己經(jīng)過多年努力爭取到的權利 美國心理學家阿貝爾.梅拉別思： 信息總效果=文字27%+音調(diào)38%+面部表情35%,2020/12/7,21,學習方法,復習、做作業(yè)、討論：勤于思考 博覽、多思（學而不思則罔、思而不學則??；書由厚到薄、由薄到厚）、

12、常實踐 思考由懷疑和答案組成。懷疑是智慧的大門，知道得越多，就越會發(fā)問，而問題就越多。發(fā)問使人進步學問,2020/12/7,22,學習方法,理論：使自己“站到巨人的肩膀上”，并擁有一個“智慧的腦” 增加問題求解和探索的主動性 實踐：用智慧的腦，練就一雙靈巧的手，開創(chuàng)一個新世界希望創(chuàng)新性實踐 在理論指導下實踐，強化理論與實踐相結合能力的培養(yǎng) 讀書：強化基礎 在獨立思考之前，必須先有基礎知識。所謂“獲得基礎知識”并不是形式上讀過某門課程，而是將學過的東西真正弄懂,2020/12/7,23,學習方法,加強實踐 “聽過的會忘記， 看過的能記得， 做過的才理解”,教了什么,學到什么,會做什么,2020/

13、12/7,24,學習方法,輔導答疑 教師是最寶貴的資源 自己要思考，以追求最大收獲：習題、問題 應對困難 不畏懼困難 從教訓到經(jīng)驗親身體驗 要實踐（作業(yè)、實驗），加深理解，探討開拓,2020/12/7,25,學生的體會,向我們展示了一個原先未曾接觸過的世界。我越來越堅信在編譯這個領域里，包含了太多前人的智慧 課中不時的小問題，讓我們?nèi)プ杂伤伎?問題不斷被解決的同時，又有一個個新的問題提了出來，問題的出現(xiàn)恰恰是上一個方案的不足，這個逐漸遞進，逐漸解決問題的過程好像踏著前人研究編譯理論的路線，不斷感覺大師們遇到的問題、解決問題的思路,2020/12/7,26,學生的體會,開闊思路，建立嚴謹?shù)乃伎挤?/p>

14、法,潛移默化地培養(yǎng)形式化描述能力和抽象思維能力, 建立和完善系統(tǒng)觀和全局觀 帶給我的不只是理論知識，更重要的是自動計算的思路,感到了一種“自動計算”的快樂 這門課不僅讓我對編譯器有了一個比較理性的認識與了解，讓我提高了自己的編程能力，還讓我再次體會到了計算機學科的一些基本思想，再次感受到了人類的偉大在于抽象的公理系統(tǒng)以及算法的巧妙,2020/12/7,27,第1章 引論,1.1 計算機語言的發(fā)展 1.2 翻譯系統(tǒng) 1.3 編譯系統(tǒng)的功能分析 1.4 編譯程序總體結構 1.5 編譯程序的生成 1.6 編譯技術的應用,2020/12/7,28,1.1 計算機語言的發(fā)展,機器語言(Machine L

15、anguage) 0、1代碼 匯編語言(Assemble Language) 0、1代碼與助記符：接近計算機硬件指令系統(tǒng) 高級語言(High Level Language) 語句定義數(shù)據(jù)、描述算法（程序） 如：C、FORTRAN、PASCAL、C+、JAVA、SQL(數(shù)據(jù)定義、數(shù)據(jù)操作) 命令語言(Command) 以功能封裝為特征,2020/12/7,29,高級語言的分類,命令式語言(Imperative Language) FORTRAN(段結構)、BASIC、Pascal(嵌套結構)、C、COBOL、ALGOL 函數(shù)(應用)式語言(Functional Language) LISP、ML

16、 邏輯式(基于規(guī)則)語言(Logical Language) Prolog 面向?qū)ο笳Z言(Object-Oriented Language) Smalltalk、 Ada(程序包)、 C+ 、Java,2020/12/7,30,1.2 翻譯系統(tǒng),翻譯程序(Translator) 將某一種語言描述的程序(源程序Source Program)翻譯成等價的另一種語言描述的程序(目標程序Object Program)的程序,翻譯程序,源程序,目標程序,(*.C / *.PAS/*.AS),(*.OBJ / *.EXE/*.*),2020/12/7,31,1.2 翻譯系統(tǒng),解釋程序(Interprete

17、r) 口譯與筆譯（單句提交與整篇提交）,源程序,輸入數(shù)據(jù),計算結果,解釋程序,2020/12/7,32,1.2 翻譯系統(tǒng),編譯程序(Compiler) 高級語言程序匯編/機器語言程序,高級語言源程序,匯編/機器語言目標程序,編譯程序,2020/12/7,33,1.2 翻譯系統(tǒng),支撐環(huán)境、運行庫等,編譯系統(tǒng)(Compiling System) 編譯系統(tǒng)=編譯程序+運行系統(tǒng),SourceProgram,Compiler,ObjectProgram,Input,RunSystem,Output,2020/12/7,34,1.2 翻譯系統(tǒng),其它翻譯系統(tǒng) 診斷編譯程序（Diagnostic Compil

18、er) 優(yōu)化編譯程序（Optimizing Compiler) 交叉編譯程序（Cross Compiler) 可變目標編譯程序（Retargetable Compiler) 并行編譯程序（Parallelizing Compiler） 匯編程序(Assembler)、交叉匯編程序(Cross Assembler)、反匯編程序（Disassembler),2020/12/7,35,1.2 翻譯系統(tǒng)匯總,MLMLP AssemblerDisassembler AL ALP Compiler Data HLHLPInterpreterResult,M-Machine L-Languge P-Prog

19、ram A-Assemble H-High Level,2020/12/7,36,1.3 編譯系統(tǒng)的功能分析,分析 詞法、語法、語義 翻譯 語句的翻譯、代碼生成 例如：標識符左值與右值的綁定(binding) 變量：存儲單元；名字：值 函數(shù)：目標代碼序列；名字；入口地址,2020/12/7,37,上次課主要內(nèi)容,基本概念 翻譯程序、編譯程序、解釋程序、匯編程序、其他 編譯系統(tǒng)：編譯程序+運行系統(tǒng),1.4 編譯程序總體結構,目標代碼生成器,代碼優(yōu)化器,語義分析與中間代碼生成器,語法分析器,2020/12/7,39,1. 詞法分析,例： res=fact *(term1+term2);,結果 ID

20、Nres = IDN fact * ( IDNterm1 + IDN term2 ) ;,在機器的眼里，這只是一個字符串！,走向目標1：變成一個單詞序列！,在機器的眼里，變成一個符號序列！,2020/12/7,40,1、詞法分析,詞法分析器 (Lexical Analyzer)又叫做掃描器(Scanner)，完成詞法分析 功能：詞法分析器從左到右掃描源程序（字符串），并將其轉換成單詞(記號Token)串；同時查詞法錯誤，進行標識符登記符號表管理 輸入：字符串 輸出：(種別碼，屬性值)序?qū)?屬性值token的機內(nèi)表示 數(shù)據(jù)結構？,2020/12/7,41,2. 語法分析,res=fact*(te

21、rm1+term2);,關鍵：讓系統(tǒng)知道“組成規(guī)則”并按照規(guī)則分析！,走向目標2：得到越來越接近要表達內(nèi)容的成分！,2020/12/7,42,2、語法分析,語法分析器(Syntax Analyzer，又叫Parser ) 完成語法分析 功能：實現(xiàn)“組詞成句”，構造分析樹，指出語法錯誤，指導翻譯 輸入：Token序列 輸出：語法成分 數(shù)據(jù)結構？,2020/12/7,43,3. 語義分析,功能：分析由語法分析器給出的語法單位的語義 獲取標識符的屬性：類型、作用域等 語義檢查：運算的合法性、取值范圍等 子程序的靜態(tài)綁定：代碼的相對地址 變量的靜態(tài)綁定：數(shù)據(jù)的相對地址,2020/12/7,44,4.

22、中間代碼生成,中間代碼(intermediate Code) 例:id1+id2*id3,后綴表示(逆波蘭Reverse Polish Notation) id1id2id3 * + 前綴表示(波蘭Polish Notation) + id1*id2id3,四元組表示 (三地址碼) (*,id2,id3,T1) (+,id1 ,T1 ,T2),三地址碼的另一種表示形式 T1=id2*id3 T2=id1*T1,三元組表示 1 (* ,id2,id3) 2 (+,id1,(1),走向目標3：接近機器的表達！,2020/12/7,45,中綴表示(Infix notation): 波蘭表示（Poli

23、sh / Prefix / Parenthesis-free / Lukasiewicz notation）也就是前綴表示 逆波蘭表示(Reverse Polish / Suffix / Postfix notation) 也就是后綴表示,波蘭表示Lukasiewicz發(fā)明,2020/12/7,46,4. 中間代碼生成,其它類型的語句舉例 printf(“hello”) x := s（賦值） param x（參數(shù)） call f（函數(shù)調(diào)用） s 是 hello 的地址 f 是函數(shù) printf 的地址,2020/12/7,47,4. 中間代碼生成,中間代碼的特點 簡單規(guī)范 機器無關 易于優(yōu)化與

24、轉換 輸入？ 輸出？ 數(shù)據(jù)結構？,2020/12/7,48,對中間代碼的優(yōu)化處理:對代碼進行等價變換以求提高執(zhí)行效率提高運行速度和節(jié)省存儲空間 與機器無關的優(yōu)化 與機器有關的優(yōu)化,5. 代碼優(yōu)化,2020/12/7,49,與機器無關的優(yōu)化,局部優(yōu)化 常量合并：常數(shù)運算在編譯期間完成，如8+9*4 公共子表達式的提取:基本塊內(nèi) 循環(huán)優(yōu)化 強度削減 代碼外提,2020/12/7,50,與機器有關的優(yōu)化,寄存器的利用 將常用量放入寄存器，以減少訪問內(nèi)存的次數(shù) 體系結構 MIMD、SIMD、SPMD、向量機、流水機 存儲策略 根據(jù)算法訪存的要求安排：Cache、并行存儲體系減少訪問沖突 任務劃分 按運

25、行的算法即體系結構，劃分子任務(MPMD),走向目標4：更高效地執(zhí)行！,2020/12/7,51,6. 目標代碼生成,將中間代碼轉換成目標機上的機器指令代碼或匯編代碼,走向目標5：實現(xiàn)目標！,2020/12/7,52,7、表格管理,管理各種符號表（常數(shù)、標號、變量、過程、結構） 查、填（登記、查找）源程序中出現(xiàn)的符號和編譯程序生成的符號，為編譯的各個階段提供信息 輔助語法檢查、語義檢查 完成靜態(tài)綁定、管理編譯過程 Hash表、鏈表等各種查、填表技術,2020/12/7,53,8、錯誤處理,進行各種錯誤的檢查、報告、糾正，以及相應的續(xù)編譯處理（如：錯誤的定位與局部化） 詞法：拼寫、定義、 語法：

26、語句結構、表達式結構、 語義：類型不匹配、,2020/12/7,54,模塊分類,編譯程序8項功能對應8個模塊,翻譯,輔助,符號表管理 出錯處理,中間代碼生成 代碼優(yōu)化 目標代碼生成,詞法分析 語法分析 語義分析,分析,例: 一個語句的翻譯,position:= initial + rate * 60,詞法分析器,2020/12/7,56,9 編譯的遍（Pass）,根據(jù)系統(tǒng)資源的狀況、運行目標的要求等，可以將一個編譯程序設計成多遍掃描的形式，在每一遍掃描中，完成不同的任務 遍可以和階段相對應，也可無關 單遍代碼不太優(yōu),2020/12/7,57,10、編譯的前端與后端,前端 與源語言有關、與目標機

27、無關的部分 詞法分析、語法分析、語義分析與中間代碼生成、與機器無關的代碼優(yōu)化 后端 與目標機有關的部分 與機器有關的代碼優(yōu)化、目標代碼生成,2020/12/7,58,1.5 編譯程序的生成,設計目標 OP 目標程序小，執(zhí)行速度快 Compiler 編譯程序小，執(zhí)行速度快 診斷能力強，可靠性高 可移植性好，可擴充性好 如何實現(xiàn)編譯器？直接用可運行的代碼編制太費力！,2020/12/7,59, 形圖,表示語言翻譯的 形圖,源語言,表示語言,目標語言,2020/12/7,60,1.6 編譯技術的應用,把復雜數(shù)據(jù)看作一條語句 數(shù)據(jù)格式的分析 利用詞法分析、語法分析方法 數(shù)據(jù)處理的框架 基于語法制導的語義處理框架 編譯技術可以用于各種復雜數(shù)據(jù)的分析處理,2020/12/7,6