第01講-編譯原理-課程簡介

1、編譯原理編譯原理 Principles of Compiling 大連理工大學軟件學院大連理工大學軟件學院 2021-7-12 2 2021-7-12 3 2021-7-12 4 詞法分析詞法分析語法分析語法分析語義語義分析分析 中間代碼生成中間代碼生成 5 編譯原理課程在計算機科學技術(shù)中的地位：編譯原理課程在計算機科學技術(shù)中的地位： 程序設(shè)計語程序設(shè)計語 言言 離散數(shù)學離散數(shù)學 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 編譯原理編譯原理 操作系統(tǒng)操作系統(tǒng) 系統(tǒng)軟件系統(tǒng)軟件 應(yīng)用軟件應(yīng)用軟件 軟件工程軟件工程 信息系統(tǒng)信息系統(tǒng) 電子商務(wù)電子商務(wù) 6 v編譯理論與方法編譯理論與方法 計算機科學與技術(shù)中理論和實踐相結(jié)合計

2、算機科學與技術(shù)中理論和實踐相結(jié)合 的的最好典范最好典范 ACM ACM 圖靈獎，授予在計算機技術(shù)領(lǐng)域作出圖靈獎，授予在計算機技術(shù)領(lǐng)域作出 突出貢獻的科學家突出貢獻的科學家 程序設(shè)計語言、編譯理論與方法約占程序設(shè)計語言、編譯理論與方法約占1/31/3 7 v課程內(nèi)容課程內(nèi)容 介紹編譯器構(gòu)造的一般原理和基本實現(xiàn)方法介紹編譯器構(gòu)造的一般原理和基本實現(xiàn)方法 介紹的理論知識：形式語言和自動機理論、語介紹的理論知識：形式語言和自動機理論、語 法制導的定義和屬性文法、類型論等法制導的定義和屬性文法、類型論等 v課程特點課程特點 強調(diào)強調(diào)形式化描述技術(shù)形式化描述技術(shù) 強調(diào)對編譯原理和技術(shù)的強調(diào)對編譯原理和技術(shù)

3、的宏觀理解宏觀理解，不把注意，不把注意 力分散到枝節(jié)算法，不偏向于某種源語言或目力分散到枝節(jié)算法，不偏向于某種源語言或目 標機器標機器 8 v學習的意義學習的意義 計算機專業(yè)的核心課程。計算機專業(yè)的核心課程。 深刻的理解編程語言的設(shè)計和實現(xiàn)，有深刻的理解編程語言的設(shè)計和實現(xiàn)，有 利于學習編程語言，知其然知其所以然。利于學習編程語言，知其然知其所以然。 9 v學習的意義學習的意義 從軟件工程看，編譯器是一個很好的實例（基從軟件工程看，編譯器是一個很好的實例（基 本設(shè)計、模塊劃分等），本設(shè)計、模塊劃分等）， 所介紹的概念和技所介紹的概念和技 術(shù)能應(yīng)用到一般的軟件設(shè)計之中。術(shù)能應(yīng)用到一般的軟件設(shè)計之

4、中。 編譯器也許是在本科階段分析最透徹的實例。編譯器也許是在本科階段分析最透徹的實例。 能了解到軟件工程中的一些技術(shù)（如基于事件能了解到軟件工程中的一些技術(shù)（如基于事件 驅(qū)動的編程）。驅(qū)動的編程）。 大多數(shù)程序員同時是語言的設(shè)計者，雖然是一 些簡單的語言（如輸入輸出），本課程的學習 有助于提高對這些語言的設(shè)計水平。 10 v學習的意義學習的意義 可以肯定地說，你們中的可以肯定地說，你們中的95%95%以上的人在以上的人在 一輩子的生涯中都沒有機會去實現(xiàn)一個一輩子的生涯中都沒有機會去實現(xiàn)一個 真正的復雜語言的編譯器。但是每一個真正的復雜語言的編譯器。但是每一個 人都絕對遇到需要使用編譯技術(shù)的項目

5、。人都絕對遇到需要使用編譯技術(shù)的項目。 以下就是一些小的以下就是一些小的“編譯器編譯器”. . 11 v學習的意義學習的意義 12 自動聊天機器人自動聊天機器人 13 14 本講綱要本講綱要 v課程簡介課程簡介 v編譯技術(shù)概述編譯技術(shù)概述 15 虛擬機虛擬機 16 vBASICBASIC年代的解釋器年代的解釋器 功能：它將高級語言的源程序翻譯成一種中間功能：它將高級語言的源程序翻譯成一種中間 語言程序，然后對中間語言程序進行解釋執(zhí)行語言程序，然后對中間語言程序進行解釋執(zhí)行 在那個年代，編譯和解釋兩個功能是合在一個在那個年代，編譯和解釋兩個功能是合在一個 程序中，該程序被稱為解釋器程序中，該程序

6、被稱為解釋器 vJavaJava年代的解釋器年代的解釋器 解釋器的上述兩個功能分在兩個程序中解釋器的上述兩個功能分在兩個程序中 前一個叫做前一個叫做編譯器編譯器，它把源程序翻譯成一種叫，它把源程序翻譯成一種叫 做字節(jié)碼的中間語言程序做字節(jié)碼的中間語言程序 后一個叫做后一個叫做解釋器解釋器，它對字節(jié)碼程序進行解釋，它對字節(jié)碼程序進行解釋 執(zhí)行執(zhí)行 17 18 編程語言演義編程語言演義 v編程語言編程語言 機器語言機器語言 匯編語言匯編語言 高級語言（高級語言（Fortran, C, Java, )Fortran, C, Java, ) 19 編程語言演義編程語言演義 v機器語言特點機器語言特點

7、0,10,1串串 打卡輸入打卡輸入 c7 06 0000 0002 c7 06 0000 0002 mov x, c mov x, c 其中符號其中符號x x的地址是的地址是00000000， c=2c=2 v計算機可以直接理解機器語言程計算機可以直接理解機器語言程 序序 v機器語言缺點機器語言缺點 可讀性差可讀性差 可維護性差可維護性差 20 編程語言演義編程語言演義 v匯編語言形式匯編語言形式 mov x,2mov x,2 c7 06 0000 0002 c7 06 0000 0002 v變量變量x x的地址可以由匯編器維護，的地址可以由匯編器維護， 而不需要固定到某個絕對地址而不需要固定

8、到某個絕對地址 21 編程語言演義編程語言演義 v高級語言形式高級語言形式 賦值語句：賦值語句：x=2x=2 v貼近人類思維方式，貼近實際問貼近人類思維方式，貼近實際問 題描述形式題描述形式 計算機無法直接理解計算機無法直接理解 需要編譯器輔助，將其轉(zhuǎn)換為機器需要編譯器輔助，將其轉(zhuǎn)換為機器 語言形式語言形式 22 v 完成從源語言到目標語言的轉(zhuǎn)換完成從源語言到目標語言的轉(zhuǎn)換 源語言：通常是高級語言（源語言：通常是高級語言（C,Java,C,Java,） 目標語言：匯編語言，或者其他形式的目標語言：匯編語言，或者其他形式的 低級語言（如低級語言（如JavaJava字節(jié)碼）字節(jié)碼） v編譯器實現(xiàn)技

9、術(shù)已經(jīng)發(fā)展成熟，并且編譯器實現(xiàn)技術(shù)已經(jīng)發(fā)展成熟，并且 劃分為功能相對明確的多個功能模塊劃分為功能相對明確的多個功能模塊 23 24 v FORTRAN (FORmula TRANslation) FORTRAN (FORmula TRANslation) 第一個實用的高級語言第一個實用的高級語言 擅長于數(shù)學函數(shù)運算擅長于數(shù)學函數(shù)運算 常用于科學計算中常用于科學計算中 v 第一個編譯器第一個編譯器 歷史上第一個實用的編譯器歷史上第一個實用的編譯器(John Backus)(John Backus)： Fortran compiler for the IBM 704/709/7090/7094 J

10、ohn BackusJohn Backus，引入了編譯器的，引入了編譯器的“階段階段”或稱或稱 為為“遍遍”的概念，是編譯設(shè)計的模塊化的開始的概念，是編譯設(shè)計的模塊化的開始 25 26 27 28 29 30 31 v遍（趟）：遍（趟）： 一遍或或一趟：是指編譯程序在編譯時刻把源程序或源程序的是指編譯程序在編譯時刻把源程序或源程序的 等價物（中間程序）從頭到尾掃描一遍并轉(zhuǎn)換成另一緊鄰的等等價物（中間程序）從頭到尾掃描一遍并轉(zhuǎn)換成另一緊鄰的等 價物的全過程。價物的全過程。 單遍掃描與多遍掃描：每一遍的掃視可完成上述一個階段每一遍的掃視可完成上述一個階段 或多個階段的工作。每一遍的輸入都是上一遍的

11、輸出，第一遍或多個階段的工作。每一遍的輸入都是上一遍的輸出，第一遍 的輸入是源程序正文，最后一遍的輸出是目標代碼。的輸入是源程序正文，最后一遍的輸出是目標代碼。 單遍與多遍的比較： 遍數(shù)多：編譯器結(jié)構(gòu)清晰，但時間效率不高遍數(shù)多：編譯器結(jié)構(gòu)清晰，但時間效率不高 遍數(shù)少：編譯速度快，但對機器的內(nèi)存要求高遍數(shù)少：編譯速度快，但對機器的內(nèi)存要求高 遍數(shù)的確定：主要因素是源程序和機器（目標機）的特征。主要因素是源程序和機器（目標機）的特征。 32 詞法分析器詞法分析器 id, 1 = id, 2 + id, 3 60 position = initial + rate 60 33 34 id, 1 =

12、id, 2 + id, 3 60 35 36 37 38 39 40 詞法分析器詞法分析器 語法分析器語法分析器 語義分析器語義分析器 源程序源程序 中間代碼生成器中間代碼生成器 代碼優(yōu)化器代碼優(yōu)化器 代碼生成器代碼生成器 目標程序目標程序 出錯管理器出錯管理器符號表管理器符號表管理器 后三個階后三個階 段對源程段對源程 序進行綜序進行綜 合合 41 詞法分析器詞法分析器 語法分析器語法分析器 語義分析器語義分析器 源程序源程序 中間代碼生成器中間代碼生成器 代碼優(yōu)化器代碼優(yōu)化器 代碼生成器代碼生成器 目標程序目標程序 出錯管理器出錯管理器符號表管理器符號表管理器 42 43 v前端和后端：前

13、端和后端： 把編譯過程分成前端和后端兩部分把編譯過程分成前端和后端兩部分 前端前端：只依賴于源程序，獨立于目標機器只依賴于源程序，獨立于目標機器 （生成中間代碼）（生成中間代碼） 后端后端：依賴于目標機器，與源程序無關(guān)，只與中間語言：依賴于目標機器，與源程序無關(guān)，只與中間語言 有關(guān)（從中間代碼生成目標代碼）有關(guān)（從中間代碼生成目標代碼） 好處好處：提高開發(fā)編譯器的效率提高開發(fā)編譯器的效率 取一個編譯器的前端，重寫它的后端以產(chǎn)生同一源語言在另一取一個編譯器的前端，重寫它的后端以產(chǎn)生同一源語言在另一 機器上的編譯器機器上的編譯器 不同的前端使用同一個后端，從而得到一個機器上的幾個編譯不同的前端使用

14、同一個后端，從而得到一個機器上的幾個編譯 器（采用同一中間語言）器（采用同一中間語言） 44 45 v高級語言的實現(xiàn) 高級編程語言易于編程，但程序運行較慢 低級語言編程時可實施更有效的控制方式， 得到更有效的代碼，但難編寫、易出錯、 難維護 流行編程語言的大多數(shù)演變都是朝著提高 抽象級別的方向 每一輪編程語言新特征的出現(xiàn)都刺激編譯 器優(yōu)化的新研究 1.2 編譯器技術(shù)的應(yīng)用 46 v程序翻譯 二進制翻譯 編譯器技術(shù)可用于把一種機器的二 進制代碼翻譯成另一種機器的代碼，以運 行原先為別的指令集編譯的代碼 數(shù)據(jù)庫查詢解釋器 數(shù)據(jù)庫查詢由一些謂詞組成，這些謂詞 由包含關(guān)系運算的布爾表達式組成，可以 被

15、解釋執(zhí)行,也可以被編譯成搜索數(shù)據(jù)庫 的命令 1.2 編譯器技術(shù)的應(yīng)用 47 v 提高軟件開發(fā)效率的工具 源于編譯器中代碼優(yōu)化技術(shù)的程序分析一直在改 進軟件開發(fā)效率 類型檢查 類型檢查是一種捕捉程序中前后不一致的成熟 而有效的技術(shù) 邊界檢查 數(shù)據(jù)流分析技術(shù)可用來定位緩沖區(qū)溢出 內(nèi)存管理 自動的內(nèi)存管理刪除內(nèi)存泄漏等內(nèi)存管理錯誤 1.2 編譯器技術(shù)的應(yīng)用 48 語法制導的結(jié)構(gòu)化編輯器語法制導的結(jié)構(gòu)化編輯器 程序格式化工具程序格式化工具 軟件測試工具軟件測試工具 程序理解工具程序理解工具 高級語言的翻譯工具高級語言的翻譯工具 等等。等等。 編譯技術(shù)的應(yīng)用編譯技術(shù)的應(yīng)用 49 本講綱要本講綱要 v課程

16、簡介課程簡介 v編譯技術(shù)概述編譯技術(shù)概述 50 51 Compilers: Principles, Techniques, and Compilers: Principles, Techniques, and Tools Tools http:// “./ “龍書龍書”。 龍書是于龍書是于19861986年出版第一版，年出版第一版，20062006年出版第二版年出版第二版 由于出版年代較早，其中包含部分過時的技術(shù)并且由于出版年代較早，其中包含部分過時的技術(shù)并且 沒有反映一些新的編譯技術(shù)。沒有反

17、映一些新的編譯技術(shù)。 新版的新版的編譯原理編譯原理拋棄諸如算符優(yōu)先分析等過時拋棄諸如算符優(yōu)先分析等過時 技術(shù)，增加面向?qū)ο缶幾g、類型檢查等新技術(shù)。技術(shù)，增加面向?qū)ο缶幾g、類型檢查等新技術(shù)。 52 現(xiàn)代編譯原理現(xiàn)代編譯原理-C-C語言描述語言描述 / Modern Compiler / Modern Compiler Implementation in C Implementation in C （美）安佩爾（美）安佩爾 / 2006-4-1 / / 2006-4-1 / 人民郵電出版社人民郵電出版社 / C/ C 語言描述語言描述 / 45.0 / / 45.0 / 平裝平裝 / / 沈志宇沈

18、志宇 / / 黃春黃春 / / 趙克趙克 佳佳 “虎書虎書”。 虎書出版比較晚，與虎書出版比較晚，與編譯原理編譯原理的知識點差不多，的知識點差不多， 但增加了數(shù)據(jù)流分析、循環(huán)優(yōu)化、內(nèi)存管理等內(nèi)容。但增加了數(shù)據(jù)流分析、循環(huán)優(yōu)化、內(nèi)存管理等內(nèi)容。 與虎書比，與虎書比，編譯原理編譯原理更適合國內(nèi)的編譯原理課更適合國內(nèi)的編譯原理課 程教學。程教學。 本書包括本書包括C C版，還有版，還有javajava版和版和MLML版版 53 高級編譯器設(shè)計與實現(xiàn)高級編譯器設(shè)計與實現(xiàn) / Advanced Compiler / Advanced Compiler Design and Implementation Design and Implementation （美）馬其尼克（美）馬其尼克 / 2005-7-1 / / 2005-7-1 / 機械工業(yè)出版機械工業(yè)出版 社社 / 75.0 / / 75.0 / 平裝平裝 / / 沈志宇沈志宇 / / 趙克佳趙克佳 “鯨書鯨書”。 鯨書側(cè)重在對編譯器后端優(yōu)化的處理。鯨書側(cè)重在對編譯器后端優(yōu)化的處理。 在本科階段的