編譯原理C1-緒論

1、編譯原理第一章：緒論陳飛，南區(qū)943課程簡介及安排課程簡介及安排我能從這門課學(xué)到什么n這門課講什么？q課程問題：課程內(nèi)容面對的科學(xué)問題q課程內(nèi)容n這門課有什么用？q從宏觀、高度概括的學(xué)科層面q從微觀、具體應(yīng)用的實用層面這門課講什么：課程問題n計算機硬件q最重要的計算機硬件是什么？q最基礎(chǔ)的計算機硬件是什么？n計算機軟件q最重要的計算機軟件是什么？q最基礎(chǔ)的計算機軟件是什么？n編譯原理：如何將(使用程序設(shè)計語言編寫的)源代碼，自動、準(zhǔn)確、高效地轉(zhuǎn)換為機器代碼。這門課講什么：課程內(nèi)容n要解決的問題是將使用程序設(shè)計語言編寫的源代碼，自動、準(zhǔn)確、高效地轉(zhuǎn)換為機器代碼。n如何解決這個問題，就是課程內(nèi)容的

2、主線：q文法和語言：如何定義一個語言？包括其單詞、句子q詞法分析：如何準(zhǔn)確、快速識別出符合定義的單詞q語法分析：如何準(zhǔn)確、快速識別出符合定義的句子q語法制導(dǎo)翻譯：如何將源代碼翻譯成機器無關(guān)的中間代碼q優(yōu)化和目標(biāo)代碼生成q符號表這門課有什么用：宏觀遠大n計算學(xué)科特點：本質(zhì)上，任何計算機問題的求解過程，都可轉(zhuǎn)化為語言的轉(zhuǎn)換、翻譯問題。q現(xiàn)實問題 問題描述（書面語言） 求解模型（數(shù)學(xué)語言） 計算方法（程設(shè)語言） 機器指令q現(xiàn)狀 軟件需求規(guī)約 分析設(shè)計模型 源代碼 n課程特點：綜合了計算機理論、程序設(shè)計、軟件工程等方面的內(nèi)容，是理論應(yīng)用于實踐的成功典范。q沒有編譯器之前，開發(fā)一個大型軟件，誰敢先實踐再

3、理論？n專家說法：編譯器原理和技術(shù)具有非常普遍的意義，是從事計算機工作所必不可少的。在計算機從業(yè)人員的職業(yè)生涯中，這些原理和技術(shù)都會反復(fù)用到。這門課有什么用：微觀近前n理論方面理論方面：計算理論的基礎(chǔ)q什么是可計算，什么是不可計算？q可計算里面，什么是P問題，什么是NP問題？q形式語言與自動機理論n思維方面思維方面：理解計算機軟硬件結(jié)合的工作原理q培養(yǎng)嚴(yán)謹(jǐn)?shù)挠嬎闼季S能力n實用方面實用方面：q新型編譯器的設(shè)計：直接改進、應(yīng)用q算法設(shè)計、安全驗證：自動機的一些應(yīng)用q文本處理：源代碼就是文本，處理文本的技術(shù)可通用q數(shù)據(jù)交換：網(wǎng)絡(luò)上傳輸?shù)暮芏鄶?shù)據(jù)，序列化之后，就是普通的文本數(shù)據(jù)這門課怎么學(xué)：學(xué)習(xí)建議n

4、有同學(xué)說：這門課好難，課本都看不懂n也有同學(xué)說：這門課不難啊，上課都聽得明白n這門課，上課聽講很重要，自學(xué)并不容易n聽講：認(rèn)真聽，注意帶紙筆，課堂練習(xí)要思考、動手。實驗：一定要動手，加深對抽象理論知識的理解n貫徹課程內(nèi)容的核心數(shù)據(jù)結(jié)構(gòu)：語法樹這門課怎么學(xué)：教材n蔣立源，康慕寧. 編譯原理. 第3版，西北工業(yè)大學(xué)出版社，2012nhttp:/ etc., Compilers: Principle, Techniques and Tools, Second Edition，人民郵電出版社，2008年。n編譯原理(第2版)，趙建華等譯,機械工業(yè)出版社, 2009年nhttp:/ (D227，第六周開

5、始，雙周實驗)q作業(yè)10%：2次，每次5%n期末60%q大概分布：概論10%、文法20%、詞法30%、語法30%、翻譯10%緒緒論：論：什什么是編譯程序么是編譯程序？程序設(shè)計語言的發(fā)展n低級語言（Low Level Language）q機器語言(Machine Language)q匯編語言(Assemble Language)n高級語言(High Level Language)qC、C+、Java q更多新型語言不斷出現(xiàn)n不是先有編譯器，再有高級設(shè)計語言，例如，現(xiàn)在已經(jīng)有一些生物方面的程序設(shè)計語言qDNA計算、染色體計算、蛋白質(zhì)計算等等q這些計算語言，沒有對應(yīng)的編譯器支持匯編語言或機器代碼n符

6、合硬件需求q包含機器指令，使用寄存器和沒有命名的內(nèi)存地址q對人類來說難理解人難寫，機器易執(zhí)行人難寫，機器易執(zhí)行高級語言編寫的源代碼n符合人類閱讀習(xí)慣q符合人類語法定義q使用被命名的結(jié)構(gòu)，例如變量和過程人易寫，機器難執(zhí)行人易寫，機器難執(zhí)行程序設(shè)計語言發(fā)展產(chǎn)生的問題n機器不能理解高級語言n需要將高級語言，翻譯或解釋為低級語言，機器才能理解、執(zhí)行解釋n解釋程序(Interpreter)源程序源程序輸入數(shù)據(jù)輸入數(shù)據(jù)計算結(jié)果計算結(jié)果解釋程序解釋程序翻譯n翻譯程序(Translator)q信、達、雅q等價、高效翻譯程序翻譯程序源程序源程序目標(biāo)程序目標(biāo)程序編譯特殊的翻譯n編譯程序(Compiler)q高級語

7、言程序(低級）匯編/機器語言程序高級語言編高級語言編寫的源程序?qū)懙脑闯绦虻图壵Z言編寫低級語言編寫的目標(biāo)程序的目標(biāo)程序編譯系統(tǒng)源程序源程序 編譯程序編譯程序 目標(biāo)程序目標(biāo)程序輸入輸入 運行系統(tǒng)運行系統(tǒng) 輸出輸出Compiling System編譯系統(tǒng)預(yù)處理器預(yù)處理器編譯器編譯器匯編器匯編器裝載連接編輯裝載連接編輯骨架程序骨架程序 源程序源程序 目標(biāo)匯編程序目標(biāo)匯編程序 可重定位機器代碼可重定位機器代碼 絕對機器碼絕對機器碼可重定位目標(biāo)文件庫可重定位目標(biāo)文件庫如何翻譯n分析 (Analysis)n綜合 (Synthesis)源程序分析中間表示綜合目標(biāo)程序語法樹語法樹典型編譯器邏輯結(jié)構(gòu)典型編譯器邏輯

8、結(jié)構(gòu)編譯程序的邏輯結(jié)構(gòu)詞法分析程序語法分析程序語義分析程序中間代碼生成代碼優(yōu)化程序目標(biāo)代碼生成信息表管理程序錯誤檢查和處理程序源程序目標(biāo)代碼詞法分析n詞法分析器 (Lexical Analyzer)、掃描器(Scanner)析n輸入：字符串（源程序） n輸出：單詞（Token）串：q有順序的(類別碼，屬性值)二元組q屬性值token的機內(nèi)表示n功能：從左到右掃描源程序，并將其轉(zhuǎn)換成單詞串，同時檢查詞法錯誤，進行標(biāo)識符登記（符號表管理）詞法分析n輸入字符串：“position = initial + rate * 60”，經(jīng)過詞法分析，得到下述單詞串:q（標(biāo)識符：position）q（賦值運算符

9、：=）q（標(biāo)識符：initial）q（加法運算符：+）q（標(biāo)識符：rate）q（乘法運算符：*）q（整數(shù)：60）空格、注釋？語法分析n語法分析器(Syntax Analyzer，又叫Parser ) n輸入：單詞序列n輸出：語法樹n功能：Parser“組詞成句”，構(gòu)造分析樹，指出語法錯誤，指導(dǎo)翻譯語法分析n一個語法定義（BNF）n 定義1：:=n定義2：:= | | | + | * | （ ） position = initial + rate * 60 的語法樹賦值語句標(biāo)識符=表達式+表達式表達式標(biāo)識符*表達式表達式positioninitial標(biāo)識符rate整數(shù)60語法分析語義分析n功能：

10、分析由語法分析器給出的語法單位的語義q獲取標(biāo)識符的屬性：類型、作用域等q語義檢查：運算的合法性、取值范圍等q子程序的靜態(tài)綁定：代碼的相對地址q變量的靜態(tài)綁定：數(shù)據(jù)的相對地址語義分析賦值語句標(biāo)識符=表達式+表達式表達式標(biāo)識符*表達式表達式positioninitial標(biāo)識符rate整數(shù)60int2real轉(zhuǎn)換浮點數(shù)中間代碼生成n抽象機上的程序，如GCC的中間代碼，Java Byte代碼。n重要特性：簡單規(guī)范，機器無關(guān)，容易從語義分析階段產(chǎn)生，并且容易翻譯到目標(biāo)代碼。n中間代碼有多種表示形式。q逆波蘭式（后綴表達式）q四元組三地址碼，最多三個操作數(shù)q三元組兩地址碼，最多兩個操作數(shù)q流控和過程調(diào)用中

11、間代碼生成n例:id1 + id2 * id3n后綴表示(逆波蘭Reverse Polish Notation) qid1id2id3 * +n前綴表示(波蘭Polish Notation) q+ id1*id2id3n四元組表示(三地址碼)q (*,id2,id3,T1) ；(+,id1 ,T1 ,T2) n三元組表示q(* ,id2,id3)；(+,id1,(1)E E + E id1 E * E id2 id3語法樹中間代碼生成其它類型的語句舉例printf(“hello”)x := s（賦值）param x（參數(shù)）call f（函數(shù)調(diào)用）其中s 是hello的地址，f 是printf的

12、地址代碼優(yōu)化n等價變換以提高執(zhí)行效率q省時省空間n與機器無關(guān)的優(yōu)化n與機器有關(guān)的優(yōu)化匯編代碼的優(yōu)化n沒有優(yōu)化的代碼 優(yōu)化后的代碼源代碼與機器無關(guān)的優(yōu)化n優(yōu)化技術(shù)q常量合并：常數(shù)運算在編譯期間完成q公共子表達式的提?。夯緣K內(nèi)q強度削減q代碼外提與機器有關(guān)的優(yōu)化n寄存器的利用q將常用量放入寄存器，以減少訪問內(nèi)存的次數(shù)n體系結(jié)構(gòu)qMIMD、SIMD、SPMD、向量機、流水機n存儲策略q根據(jù)算法訪存的要求安排：Cache、并行存儲體系減少訪問沖突n任務(wù)劃分q按運行的算法即體系結(jié)構(gòu)，劃分子任務(wù)(MPMD)目標(biāo)代碼生成n將中間代碼轉(zhuǎn)換成目標(biāo)機上的機器指令代碼或匯編代碼符號表管理n符號表，記錄符號及與其關(guān)

13、聯(lián)的屬性，如類型、作用域，對于過程名符號，有其參數(shù)個數(shù)和類型、傳值還是傳引用、返回類型。n符號在詞法分析階段進入符號表，而與其關(guān)聯(lián)的屬性要在后繼階段補充。nfloat position, initial, rate;錯誤處理n在遇到錯誤時，應(yīng)盡可能繼續(xù)執(zhí)行相應(yīng)階段。n詞法分析：不成詞的余留串，如3int。n語義分析：語法結(jié)構(gòu)良好，但語義錯誤，如兩個標(biāo)識符相加，但其類型分別為數(shù)組和過程。詞法分析器語法分析器語義分析器中間代碼生成器代碼優(yōu)化器代碼生成器position:= initial + rate * 60idid1 := idid2 + idid3 * 60:=+*idid1idid2idi

14、d360:=+*idid1idid2idid360inttorealinttorealtemp1 := inttoreal(60)temp2 := id3 *temp1temp3 := id2 +temp2id1 := temp3temp1 := id3 *60.0id1 := id2 + temp1MOVF id3, R2MULF #60.0, R2MOVF id2, R1ADDF R2, R1MOVF R1, id1符號表 position initial rate 1234例：例： 一個語句的翻譯一個語句的翻譯編譯器設(shè)計及實現(xiàn)編譯器設(shè)計及實現(xiàn)編譯程序的組織語法分析程序語義分析及代碼生成程

15、序詞法分析程序整理目標(biāo)程序源程序目標(biāo)程序停機開始編譯的前端與后端n前端：與目標(biāo)機無關(guān)的部分n后端：與目標(biāo)機有關(guān)的部分編譯程序的設(shè)計n設(shè)計目標(biāo)q目標(biāo)程序執(zhí)行速度快q編譯程序編譯速度快q編譯程序診斷能力強，可靠性高q可移植性，可擴充性n如何實現(xiàn)編譯器？q直接用可運行的代碼編制太費力！形圖n表示語言翻譯的 形圖源語言表示語言目標(biāo)語言語言語言機器機器A機器機器有一個可在A機器上運行的C語言到A機器語言的編譯器本機編譯器的利用n問題一： A機上有一個C語言編譯器，現(xiàn)要實現(xiàn)一個新語言NEW的編譯器？需要直接用A機器語言編寫嗎？語言語言機器機器A機器機器NEW語言語言A機器機器A機器機器NEW語言語言語語

16、言言A機器機器n用C編寫NEW的編譯，并用C編譯器編譯它交叉編譯(Cross Compiling)/移植n問題二：A機上有一個C語言編譯器，是否可利用此編譯器實現(xiàn)B機上的C語言編譯器？q條件：機有語言的編譯程序(P1)q目的：實現(xiàn)機的語言的編譯(P3)1. (人)用語言編制B機的編譯程序P0(CB)語言語言語語 言言機器機器語言語言機器機器A機器機器語言語言A機器機器機器機器2. (機的C編譯P1)編譯P0，得到在A機上可運行的P2(CB)語言語言語言語言機器機器語言語言機器機器A機器機器語言語言A機器機器機器機器語言語言A機器機器機器機器語言語言語言語言機器機器3. (用機的P2)編譯P0，

17、得到在B機上可運行的P3(CB)語言語言機器機器機器機器編譯程序的自展技術(shù)n問題三：直接在一個新型機器上實現(xiàn)C語言編譯器，還有別的技術(shù)么？n解決：q用匯編語言實現(xiàn)一個子集的編譯程序(P0人)q用匯編程序處理該程序,得到P2(P2:可直接運行)q用子集編制語言的編譯程序(P3人)q用P2編譯P3，得到P41. 用匯編語言實現(xiàn)一個 子集的編譯程序(P0人)2. 用匯編程序(P1)處理該程序,得到P2(P2:可直接運行)3. 用匯編程序(P1)處理該程序,得到P2(P2:可直接運行)4. 用P2編譯P3，得到P4C語言子集語言子集匯編語言匯編語言機器語言機器語言匯編匯編語言語言機器語言機器語言機器語言機器語言C語言子集語言子集機器語言機器語言機器語言機器語言C