編譯原理：第1章 編譯程序概論

1、1編 譯 原 理學(xué)習(xí)了編譯課，就不能說(shuō)：“某一門(mén)語(yǔ)言沒(méi)有學(xué)過(guò)，所以不會(huì)”。2 課程簡(jiǎn)介課程中文名稱：編譯原理課程英文名稱：Principles of Compiling（ Compiler Principles ）考核方式：閉卷考試開(kāi)課學(xué)期：第三學(xué)年第2學(xué)期總學(xué)時(shí)：56總學(xué)分：3.5前續(xù)課程：程序設(shè)計(jì)語(yǔ)言，數(shù)據(jù)結(jié)構(gòu)3教材：編譯原理，張素琴、呂映芝、蔣維杜、戴桂蘭，清華大學(xué)出版社 2004參考書(shū)1：Compilers: Principles, Techniques, and Tools Alfred V.Aho, Ravi Sethi, Jeffrey D.Ullman, Addison-Wes

2、ley,1986. 影印版：人民郵電出版社，2001參考書(shū)2：（參考書(shū)1 的中譯本） 編譯原理 Alfred V.Aho, Ravi Sethi, Jeffrey D.Ullman, Addison-Wesley 著. 李建中，姜守旭 譯 機(jī)械工業(yè)出版社參考書(shū)3: 編譯原理和技術(shù)， 丁文魁、杜淑敏，電子工業(yè)出版社，2008年3月參考書(shū)4: 編譯原理， 孫悅紅，清華大學(xué)出版社 2005教材及主要參考書(shū)4基本知識(shí)要求掌握課程教學(xué)大綱中規(guī)定的一些基本概念、基本理論和基本方法通過(guò)學(xué)習(xí)，能夠?qū)@些基本概念和理論有更深入的理解，有能力將它們應(yīng)用到一些問(wèn)題的求解中。教學(xué)要求5教學(xué)要求作業(yè)要求每章安排習(xí)題。學(xué)

3、生通過(guò)習(xí)題，復(fù)習(xí)課程內(nèi)容，深入研究有關(guān)問(wèn)題。 另外，會(huì)有一些思考題。根據(jù)實(shí)際情況，將必要的習(xí)題講解安排在理論課的講授中。 6考核形式閉卷重點(diǎn)考查學(xué)生對(duì)基本概念、基本理論、基本方法掌握的程度期末 80%, 平時(shí) 20%。教學(xué)要求7課程性質(zhì)必修，專業(yè)基礎(chǔ)課程所含內(nèi)容既有便于抽象的問(wèn)題，又有較成熟的理論，屬于軟件技術(shù)系列。涉及學(xué)科抽象、理論、設(shè)計(jì)3個(gè)形態(tài)繼程序設(shè)計(jì)、數(shù)據(jù)結(jié)構(gòu)等課程后，從系統(tǒng)級(jí)再認(rèn)識(shí)程序、算法8先修課程要求程序設(shè)計(jì)，數(shù)據(jù)結(jié)構(gòu)等掌握程序、數(shù)據(jù)結(jié)構(gòu)、算法的基本知識(shí)，能夠較熟練地用它們表達(dá)問(wèn)題及求解修過(guò)離散數(shù)學(xué)，對(duì)問(wèn)題的符號(hào)表示、對(duì)符號(hào)表示形式的理解等有良好的基礎(chǔ)。即具有一定的計(jì)算思維能力、

4、程序設(shè)計(jì)與實(shí)現(xiàn)能力、算法設(shè)計(jì)能力修過(guò)形式語(yǔ)言與自動(dòng)機(jī)理論更好 *9編譯是一個(gè)好課程“編譯”是將高級(jí)語(yǔ)言描述的程序變換成與之等價(jià)的另一種語(yǔ)言（面向硬件）表達(dá)的程序在這個(gè)系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)中，用到計(jì)算機(jī)學(xué)科很多基本的技術(shù)、原理和方法Alfred V. Aho：“編寫(xiě)編譯器的原理和技術(shù)具有十分普遍的意義，以至于在每個(gè)計(jì)算機(jī)科學(xué)家的研究生涯中，本書(shū)中的原理和技術(shù)都會(huì)反復(fù)用到。”10瞄準(zhǔn)目標(biāo)編譯：掌握“編譯原理”中的基本概念、基本理論、基本方法，在系統(tǒng)級(jí)上再認(rèn)識(shí)程序和算法，提升計(jì)算機(jī)問(wèn)題求解的水平，增強(qiáng)系統(tǒng)能力，體驗(yàn)實(shí)現(xiàn)自動(dòng)計(jì)算的樂(lè)趣 掌握程序變換基本概念、問(wèn)題描述和處理方法（自頂向下、自底向上、逐步求精

5、、遞歸求解，目標(biāo)驅(qū)動(dòng)，問(wèn)題分析、問(wèn)題的抽象與 形式化描述，算法設(shè)計(jì)與實(shí)現(xiàn)，系統(tǒng)構(gòu)建、模塊化 ）修養(yǎng)“問(wèn)題、形式化描述、計(jì)算機(jī)化”問(wèn)題求解典型過(guò)程，增強(qiáng)理論結(jié)合實(shí)際能力，獲得更多的“頂峰體驗(yàn)”11第一章 編譯概述 1.1 編譯程序的定義 高級(jí)語(yǔ)言程序可看成是符號(hào)序列或稱為字符的序列，而計(jì)算機(jī)能直接接受、理解和運(yùn)行的是由0、1代碼組成的二進(jìn)制指令。 顯然需要一個(gè)系統(tǒng)軟件，能把一個(gè)用面向人的源語(yǔ)言表示的算法轉(zhuǎn)換到一個(gè)等價(jià)的用面向硬件的目標(biāo)語(yǔ)言表示的算法。 121編譯程序的定義 把高級(jí)程序設(shè)計(jì)語(yǔ)言書(shū)寫(xiě)的源程序翻譯成邏輯上等價(jià)的低級(jí)語(yǔ)言形式的目標(biāo)程序的系統(tǒng)軟件稱為編譯程序。 編譯程序的重要性體現(xiàn)在用戶不

6、必考慮與機(jī)器有關(guān)的繁瑣細(xì)節(jié)，編程獨(dú)立于機(jī)器。 132編譯理論和技術(shù)的應(yīng)用 編譯程序作為符號(hào)處理系統(tǒng)，廣泛應(yīng)用到其它的軟件設(shè)計(jì)中。14 查詢解釋器：把含關(guān)系和布爾運(yùn)算的謂詞翻譯成數(shù)據(jù)庫(kù)命令，在數(shù)據(jù)庫(kù)中查詢滿足該謂詞的記錄。數(shù)據(jù)庫(kù)管理系統(tǒng)可看成是一個(gè)編譯系統(tǒng)。硅編輯器： 硅編輯器的輸入是一個(gè)源程序，其書(shū)寫(xiě)的高級(jí)程序設(shè)計(jì)語(yǔ)言類似傳統(tǒng)的程序設(shè)計(jì)語(yǔ)言。但該語(yǔ)言的變量不是內(nèi)存中的地址，而是開(kāi)關(guān)電路中的邏輯符號(hào)（0或1）或符號(hào)組。硅編輯器的輸出是一個(gè)以適當(dāng)語(yǔ)言書(shū)寫(xiě)的電路設(shè)計(jì)。文本格式器：輸入是含有排版命令的字符流，輸出對(duì)應(yīng)排版后的文本。15編譯思想用于通信協(xié)議的轉(zhuǎn)換：與計(jì)算機(jī)高級(jí)程序設(shè)計(jì)語(yǔ)言相比，一次通訊過(guò)

7、程的完整報(bào)文相應(yīng)于一個(gè)程序，而報(bào)文中的一個(gè)幀相當(dāng)于程序中的一個(gè)語(yǔ)句。用編譯原理中識(shí)別程序設(shè)計(jì)語(yǔ)言中的標(biāo)識(shí)符和數(shù)的識(shí)別原理，來(lái)進(jìn)行協(xié)議幀內(nèi)部成分的識(shí)別。利用編譯中的逐層轉(zhuǎn)化思想，轉(zhuǎn)換協(xié)議幀為PC機(jī)內(nèi)部幀。編譯在反病毒中的應(yīng)用：對(duì)于高級(jí)文本語(yǔ)言類的文件（如網(wǎng)頁(yè)類文件），應(yīng)用編譯技術(shù)的詞法分析和語(yǔ)法分析原理，可準(zhǔn)確快速定位病毒代碼，從而可構(gòu)造反病毒程序。編譯在機(jī)器翻譯系統(tǒng)和文本分類中的應(yīng)用：機(jī)器翻譯系統(tǒng)又稱為語(yǔ)言翻譯系統(tǒng)， 輸入是一種語(yǔ)言，輸出是功能上等價(jià)的另外一種語(yǔ)言。例如中文和日文的互翻譯。文本分類是把互聯(lián)網(wǎng)上的海量信息進(jìn)行分類，便于閱讀。它們都離不開(kāi)編譯中的詞法分析和語(yǔ)法分析技術(shù)。16 編譯程

8、序的功能編譯是指將一個(gè)用面向人的源語(yǔ)言表示的算法轉(zhuǎn)換到一個(gè)等價(jià)的用面向硬件的目標(biāo)語(yǔ)言表示的算法Compiler：編譯程序、編譯器源程序（高級(jí)語(yǔ)言） 編譯程序目標(biāo)程序（低級(jí)語(yǔ)言）17T型圖表示編譯程序SL OLWLSL（source language） 可以是Pascal、Fortran、C等高級(jí)語(yǔ)言O(shè)L （object language） 具體機(jī)器上的指令代碼（包括機(jī)器語(yǔ)言、匯編語(yǔ)言）WL or IL （written language or Implementation language） 書(shū)寫(xiě)編譯程序的語(yǔ)言 18為什么要學(xué)習(xí)編譯？（高級(jí)語(yǔ)言的實(shí)現(xiàn)方法）通過(guò)了解編譯程序的構(gòu)造方法及實(shí)現(xiàn)，有利

9、于對(duì)PL（Programming language）的理解，迅速掌握新的語(yǔ)言工具包含了許多軟件技術(shù)蘊(yùn)含了計(jì)算機(jī)學(xué)科解決問(wèn)題的思路 問(wèn)題、形式化描述（實(shí)際問(wèn)題抽象化）、計(jì)算機(jī)化可應(yīng)用于許多實(shí)際的軟件開(kāi)發(fā)工作中，如軟件開(kāi)發(fā)平臺(tái)、軟件自動(dòng)生成、模式匹配等19編譯程序 （語(yǔ)言轉(zhuǎn)換系統(tǒng)）大多數(shù) 計(jì)算機(jī)系統(tǒng)（microcomputer, minicomputer, mainframe, supercomputer）有不止一個(gè)高級(jí)語(yǔ)言的編譯程序。每推出一種高級(jí)語(yǔ)言，都必須配備各自的編譯程序。形式語(yǔ)言20發(fā)展階段1 20世紀(jì)50年代中期，出現(xiàn)了Fortran等高級(jí)語(yǔ)言，相應(yīng)的編譯程序開(kāi)發(fā)成功。 50年代末開(kāi)始

10、研究編譯程序的自動(dòng)生成工具。它的功能是從任一語(yǔ)言的詞法規(guī)則、語(yǔ)法規(guī)則和語(yǔ)義解釋出發(fā)，自動(dòng)產(chǎn)生該語(yǔ)言的編譯程序。2 1972貝爾實(shí)驗(yàn)室在Unix上首次實(shí)現(xiàn)詞法分析程序的生成系統(tǒng)LEX和語(yǔ)法分析程序的生成系統(tǒng)YACC。3 60年代起，開(kāi)始使用自展技術(shù)來(lái)構(gòu)造編譯程序。1971年，PASCAL的編譯程序用自展技術(shù)生成后，影響越來(lái)越大。Compiler的發(fā)展211.2 翻譯程序 高級(jí)語(yǔ)言或匯編語(yǔ)言編制的程序不能直接在計(jì)算機(jī)上執(zhí)行，必須經(jīng)過(guò)“翻譯程序”轉(zhuǎn)化成機(jī)器語(yǔ)言才能執(zhí)行。翻譯程序掃描所輸入的源程序，然后將源程序轉(zhuǎn)換成等價(jià)的目標(biāo)程序。翻譯程序的源程序分高級(jí)語(yǔ)言源程序和匯編語(yǔ)言源程序兩種：1)如果要翻譯的

11、源程序是匯編語(yǔ)言編寫(xiě)的，而目標(biāo)語(yǔ)言是機(jī)器語(yǔ)言，則翻譯程序稱為“匯編程序”；2）若要翻譯的源程序用高級(jí)語(yǔ)言編制，其翻譯后的目標(biāo)程序?yàn)槟撤N具體機(jī)器的機(jī)器語(yǔ)言或匯編語(yǔ)言，那么這種翻譯程序稱為“編譯程序”。 221、編譯程序的目標(biāo)程序是機(jī)器語(yǔ)言在高級(jí)語(yǔ)言程序的編譯和運(yùn)行過(guò)程中，源程序和數(shù)據(jù)是在不同時(shí)間處理的。源程序在編譯階段處理，而數(shù)據(jù)則在程序的運(yùn)行階段處理。有的編譯程序的目標(biāo)程序是機(jī)器語(yǔ)言，則源程序從編譯到被執(zhí)行的過(guò)程如圖1.1所示 。高級(jí)語(yǔ)言源程序 編譯程序 機(jī)器語(yǔ)言目標(biāo)程序 目標(biāo)程序 +運(yùn)行子程序 運(yùn)行結(jié)果 數(shù)據(jù) 編譯階段 執(zhí)行階段 圖1.1 生成機(jī)器語(yǔ)言目標(biāo)程序的編譯方式 語(yǔ)言處理器的類型（l

12、anguage processor）232、編譯程序的目標(biāo)程序是匯編語(yǔ)言如果編譯程序翻譯得到的目標(biāo)程序是匯編語(yǔ)言程序，則還要經(jīng)過(guò)“匯編程序”翻譯成機(jī)器語(yǔ)言程序，這種編譯方式的源程序從編譯到被執(zhí)行的過(guò)程如圖1.2所示。 高級(jí)語(yǔ)言源程序 編譯程序 匯編語(yǔ)言目標(biāo)程序 匯編程序機(jī)器語(yǔ)言目標(biāo)程序 運(yùn)行結(jié)果 目標(biāo)程序 +運(yùn)行子程序 數(shù)據(jù) 編譯階段 匯編階段 運(yùn)行階段 圖1.2 生成匯編語(yǔ)言目標(biāo)程序的編譯方式 語(yǔ)言處理器的類型243、從源程序的編譯到執(zhí)行只有一個(gè)階段解釋執(zhí)行階段如果翻譯程序同時(shí)處理源程序和數(shù)據(jù)，按源程序中語(yǔ)句的動(dòng)態(tài)順序，逐句的進(jìn)行分析解釋，并立即予以執(zhí)行，這種翻譯程序稱為“解釋程序。在解釋方

13、式下，最終并不生成目標(biāo)程序，這是編譯方式與解釋方式的根本區(qū)別。源程序 數(shù)據(jù) 解釋程序 結(jié)果 圖1.3 高級(jí)語(yǔ)言的解釋方式 語(yǔ)言處理器的類型25兩類翻譯程序編譯程序：就是一個(gè)語(yǔ)言翻譯程序，把源語(yǔ)言書(shū)寫(xiě)的程序翻譯成等價(jià)的目標(biāo)語(yǔ)言程序。解釋程序：集編譯與運(yùn)行為一體，同時(shí)處理源程序與數(shù)據(jù)，采取邊分析邊執(zhí)行的方式計(jì)算結(jié)果。提供兩種執(zhí)行方式：編譯方式、解釋方式混合策略 最常執(zhí)行的部分 編譯實(shí)現(xiàn) 其余 解釋實(shí)現(xiàn)26編譯、解釋對(duì)比編譯程序是將全部源程序翻譯成目標(biāo)程序，再執(zhí)行，可反復(fù)執(zhí)行，速度快解釋程序?qū)υ闯绦蛑鹁浞g執(zhí)行，目標(biāo)代碼只執(zhí)行一次，運(yùn)行速度慢但解釋程序容易實(shí)現(xiàn)（與用戶的交互會(huì)話）人機(jī)對(duì)話，局部程序的

14、改動(dòng)不需重新翻譯整個(gè)程序編譯過(guò)程類似筆譯結(jié)果可反復(fù)閱讀解釋過(guò)程類似即席翻譯別人說(shuō)一句話，他就譯一句27編譯C+機(jī)器碼Java（只能在本地機(jī)上運(yùn)行）編譯型：編譯成中間代碼（Byte-code 字節(jié)碼），即JVM代碼。 獨(dú)立于機(jī)器，可在任何具有JVM的機(jī)器上運(yùn)行解釋型：JVM （解釋器）執(zhí)行字節(jié)碼 （JVM虛擬機(jī)，就是一個(gè)解釋程序）區(qū)別：Java一次編譯，（源代碼）平臺(tái)到處運(yùn)行 （JVM）編譯型語(yǔ)言解釋型語(yǔ)言如BASIC, LISP , 數(shù)據(jù)庫(kù)查詢語(yǔ)言SQL, UNIX命令語(yǔ)言shell281.3 編譯程序的組成 按照編譯程序的執(zhí)行過(guò)程和所完成的任務(wù)，編譯分成前后兩個(gè)階段：分析階段和綜合階段。分析

15、階段根據(jù)源語(yǔ)言的定義，分析源程序的結(jié)構(gòu)，檢查源程序是否符合語(yǔ)言的規(guī)定，確定源程序所表示的對(duì)象和規(guī)定的操作，并以某種中間代碼形式表示出來(lái)。分析階段包括詞法分析、語(yǔ)法分析和語(yǔ)義分析。綜合階段根據(jù)分析結(jié)果構(gòu)造所要求的目標(biāo)代碼程序，包括中間代碼生成、代碼優(yōu)化和目標(biāo)代碼生成。為了記錄分析過(guò)程中識(shí)別出的標(biāo)識(shí)符及有關(guān)信息，還需要使用符號(hào)表。如果在編譯過(guò)程中發(fā)現(xiàn)源程序有錯(cuò)誤，不僅要報(bào)告錯(cuò)誤的類型、出錯(cuò)地點(diǎn)，還要進(jìn)行錯(cuò)誤處理，使編譯能繼續(xù)進(jìn)行。 291.3 編譯程序的組成 詞法分析 語(yǔ)法分析 語(yǔ)義分析 分析階段綜合階段 錯(cuò)誤處理符號(hào)表 中間代碼生成目標(biāo)代碼生成代碼優(yōu)化30源程序（字符流）詞法分析中間代碼生成代碼

16、優(yōu)化目標(biāo)代碼生成目標(biāo)程序表格管理出錯(cuò)處理單詞符號(hào)流語(yǔ)法分析語(yǔ)義分析語(yǔ)法樹(shù)語(yǔ)法樹(shù)四元式代碼或三地址碼四元式代碼或三地址碼31a=b+c*20詞法分析中間代碼生成代碼優(yōu)化目標(biāo)代碼生成語(yǔ)法分析語(yǔ)義分析(id,a) (=,=) (id b) (+,+) (id,c) (*,*) (num, 20)=(id,a)(id,b)20*(id,c)+=(id,a)(id,b)20*(id,c)+inttofloatt1=inttofloat(20)t2=c*t1t3=b+t2a=t3t1=c*20.0a=b+t1LDF R2, cMULF R2, #20.0LDF R1, bADDF R1, R2STF a

17、,R1一個(gè)賦值語(yǔ)句的翻譯32（1）詞法分析：識(shí)別單詞。從詞法分析的層面來(lái)看，語(yǔ)言是由字符組成的單詞的集合。進(jìn)行詞法分析的程序稱為掃描器（scanner）。（2）語(yǔ)法分析：分析語(yǔ)法。從語(yǔ)法分析的層面來(lái)看，語(yǔ)言是由單詞組成的句子的集合。進(jìn)行語(yǔ)法分析的程序稱為語(yǔ)法分析器（parser）。（3）語(yǔ)義分析：檢查源程序是否和語(yǔ)言定義的語(yǔ)義一致。 例如類型檢查和類型轉(zhuǎn)換（semantic analyzer)。（4）中間代碼生成：獨(dú)立具體機(jī)器的代碼，便于進(jìn)一步優(yōu)化（intermediate code generator）。（5）代碼優(yōu)化：為生成更有效的目標(biāo)代碼進(jìn)行的修飾工作（code optimizer）。（

18、6）目標(biāo)代碼生成：生成特定機(jī)器上的目標(biāo)代碼（target code generator）。1.3 編譯程序的組成 33編譯程序完成從源程序到目標(biāo)程序的翻譯工作，是分階段進(jìn)行的，每個(gè)階段將源程序的一種表示形式轉(zhuǎn)換成另一種表示形式，各階段的操作在邏輯上是緊密相關(guān)的。根據(jù)源語(yǔ)言的不同，編譯過(guò)程的某些階段也可省略，如：中間代碼生成、代碼優(yōu)化。1.3 編譯程序的組成341.3.1 詞法分析程序 詞法分析又稱掃描器。詞法分析依次讀入源程序中的每個(gè)字符，依據(jù)語(yǔ)言的構(gòu)詞規(guī)則，識(shí)別出一個(gè)個(gè)具有獨(dú)立意義的最小語(yǔ)法單位，即“單詞”，例如：是標(biāo)識(shí)符、還是分界符、還是數(shù)等等。（字符串單詞串 ）可采用整數(shù)碼或有意義的記號(hào)

19、表示單詞詞性。例如，表達(dá)式a=10+c*20經(jīng)詞法分析其結(jié)果如圖所示。整數(shù)碼記號(hào)單詞100IDa21=200NUM1022+100IDc25*200NUM20詞法分析結(jié)果 35詞法分析的數(shù)學(xué)模型是有窮狀態(tài)自動(dòng)機(jī)和正則表達(dá)式a|b|z, =0|1|9(| )* , *1.3.1 詞法分析程序 361.3.2.語(yǔ)法分析程序 語(yǔ)法分析的功能是在詞法分析的基礎(chǔ)上，根據(jù)語(yǔ)言的語(yǔ)法規(guī)則，將一個(gè)個(gè)單詞符號(hào)組成語(yǔ)言的各種語(yǔ)法類。例如：算術(shù)表達(dá)式、賦值語(yǔ)句等。賦值語(yǔ)句的語(yǔ)法結(jié)構(gòu)定義為：賦值語(yǔ)句標(biāo)識(shí)符:=表達(dá)式表達(dá)式的語(yǔ)法結(jié)構(gòu)定義為：表達(dá)式表達(dá)式+表達(dá)式| 表達(dá)式-表達(dá)式| 標(biāo)識(shí)符 | 常數(shù)37單詞的詞性（種別）

20、在語(yǔ)法分析時(shí)使用。單詞的值在語(yǔ)義分析時(shí)使用。在語(yǔ)法分析時(shí)，賦值語(yǔ)句sum := ave+23的語(yǔ)法結(jié)構(gòu)應(yīng)表示為ID:= ID+NUM 1.3.2.語(yǔ)法分析程序 38單詞類別表示的串：ID:= ID+NUM 經(jīng)過(guò)語(yǔ)法分析后，ID:= ID+NUM 被識(shí)別出是賦值語(yǔ)句，識(shí)別過(guò)程相當(dāng)于建立一棵語(yǔ)法樹(shù)。 :=ID (sum) 表達(dá)式賦值語(yǔ)句表達(dá)式表達(dá)式+ID (ave) NUM (23) 1.3.2.語(yǔ)法分析程序 39語(yǔ)法分析的數(shù)學(xué)模型是下推自動(dòng)機(jī)或上下文無(wú)關(guān)文法1.3.2.語(yǔ)法分析程序 401.3.3 語(yǔ)義分析及中間代碼生成程序 語(yǔ)義分析的功能是確定源程序的語(yǔ)義是否正確。語(yǔ)義分析主要能識(shí)別的語(yǔ)義錯(cuò)誤

21、有變量沒(méi)聲明就使用、變量重復(fù)聲明、運(yùn)算對(duì)象類型是否匹配、數(shù)組下標(biāo)是否整數(shù)等。例如分析表達(dá)式A+B時(shí)，當(dāng)分析到+操作時(shí)，語(yǔ)義分析程序就要分析A、B是否已經(jīng)聲明、是否具有兼容的類型、是否已經(jīng)有值。為了識(shí)別出這些語(yǔ)義錯(cuò)誤，語(yǔ)義分析要使用編譯程序中建立的許多表。語(yǔ)義分析程序通常將源程序生成一種中間表示形式，即中間代碼。中間代碼具有易于產(chǎn)生、易于翻譯成目標(biāo)程序的特點(diǎn)，可看成是一種抽象機(jī)的指令代碼 41例如：a=b+c*20假設(shè)a、b、c已經(jīng)被聲明為浮點(diǎn)數(shù)，則語(yǔ)義分析器的類型檢查程序發(fā)現(xiàn)運(yùn)算符*被用于一個(gè)浮點(diǎn)數(shù)和一個(gè)整數(shù)，則整數(shù)20將被轉(zhuǎn)換為浮點(diǎn)數(shù)。語(yǔ)義分析器輸出中會(huì)出現(xiàn)intofloat運(yùn)算。=(id,

22、a)(id,b)20*(id,c)+inttofloat1.3.3 語(yǔ)義分析及中間代碼生成程序 42例如表達(dá)式 (a+b)*(c+d)翻譯成四元式的中間代碼如下：(+ , a , b , t1)(+ , c , d , t2)(* , t1 , t2 , t3)例如表達(dá)式 (a+b)*(c+d)翻譯成三地址碼的中間代碼如下：t1= a +b t2= c + d t3= t1 * t2 1.3.3 語(yǔ)義分析及中間代碼生成程序 43例如表達(dá)式 (a+b)*(c+d)翻譯成四元式的中間代碼如下：(+ , a , b , t1)(+ , c , d , t2)(* , t1 , t2 , t3)LOA

23、D a 將a的內(nèi)容加載到操作數(shù)棧LOAD b 將a的內(nèi)容加載到操作數(shù)棧ADD 將操作數(shù)棧頂?shù)膬蓚€(gè)單元的內(nèi)容相加STO t1 將操作數(shù)棧頂?shù)膬?nèi)容存入單元t1LOAD c 將c的內(nèi)容加載到操作數(shù)棧LOAD d 將d的內(nèi)容加載到操作數(shù)棧ADD 將操作數(shù)棧頂?shù)膬蓚€(gè)單元的內(nèi)容相加STO t2 將操作數(shù)棧頂?shù)膬?nèi)容存入單元t2LOAD t1 將t1的內(nèi)容加載到操作數(shù)棧LOAD t2 將t2的內(nèi)容加載到操作數(shù)棧MULT 將操作數(shù)棧頂?shù)膬蓚€(gè)單元的內(nèi)容相乘 STO t3將操作數(shù)棧頂?shù)膬?nèi)容存入單元t3 翻譯成某個(gè)抽象機(jī)的匯編指令代碼：1.3.3 語(yǔ)義分析及中間代碼生成程序 441.3.4 代碼優(yōu)化 經(jīng)過(guò)語(yǔ)義分析后，

24、編譯程序?qū)⒃闯绦蛏芍虚g代碼，這時(shí)的中間代碼往往有些重復(fù)和冗余。對(duì)代碼進(jìn)行優(yōu)化的目的是提高目標(biāo)程序的執(zhí)行效率。代碼優(yōu)化首先在中間代碼上進(jìn)行。在局部范圍可能做的優(yōu)化有常數(shù)表達(dá)式的計(jì)算或根據(jù)操作符的某些性質(zhì)如可結(jié)合性、可交換性和分配性以及檢測(cè)公共子表達(dá)式進(jìn)行優(yōu)化 有四元式指令代碼如下：(*，3.14，2，t1)(=, t1, _, x)(*, 2, 5, t2)(*, t2, a, t3)(=, t3, _, y)(+, x, 1, t4)(=, t4, _, z) 而優(yōu)化后的代碼如下：(=, 6.28, _, x)(*, 10, a, y)(=, 7.28, _, z) 代碼優(yōu)化不是編譯程序的必

25、要組成部分，不同的編譯程序所進(jìn)行的代碼優(yōu)化程度差別很大，能夠完成代碼優(yōu)化的編譯程序稱為“優(yōu)化編譯程序”。 451.3.5 目標(biāo)代碼生成 編譯的最后一步是將中間代碼生成特定機(jī)器上的低級(jí)語(yǔ)言代碼。這部分與機(jī)器類型有關(guān)，對(duì)程序中的每個(gè)變量指定寄存器或內(nèi)存存貯單元，把中間代碼的指令翻譯成等價(jià)的某種類型機(jī)器的機(jī)器指令代碼或匯編指令代碼。 t1=c*20.0a=b+t1LDF R2, cMULF R2, #20.0LDF R1, bADDF R1, R2STF a ,R1461.3.6 符號(hào)表管理 編譯過(guò)程中要記錄源程序中出現(xiàn)的標(biāo)識(shí)符，并收集每個(gè)標(biāo)識(shí)符的各種屬性信息。在詞法分析中，對(duì)所有的標(biāo)識(shí)符都用一個(gè)統(tǒng)

26、一的符號(hào)表示，那么這個(gè)符號(hào)代表的標(biāo)識(shí)符是變量名、函數(shù)名還是其它對(duì)象名稱呢？如果是變量名，那么變量的類型是什么？如果是函數(shù)名，那么編譯程序怎么知道參數(shù)的個(gè)數(shù)、類型及函數(shù)返回值的類型等信息呢？為此需要建立一個(gè)符號(hào)表記錄有關(guān)標(biāo)識(shí)符的各種信息。標(biāo)識(shí)符的各種屬性是在編譯的不同階段填入符號(hào)表的。詞法分析階段只能分析出標(biāo)識(shí)符名，語(yǔ)法分析階段只能判斷標(biāo)識(shí)符在語(yǔ)句中出現(xiàn)是否合法，只有到了語(yǔ)義分析階段，才能將標(biāo)識(shí)符的各種屬性填入符號(hào)表并使用這些屬性生成中間代碼。 標(biāo)識(shí)符名標(biāo)識(shí)符類型 類型 地址 aaa1（表示變量） 1（表示整型） 0001 471.3.7 錯(cuò)誤處理 編譯的各個(gè)階段都可能發(fā)現(xiàn)源程序中的錯(cuò)誤。詞法分

27、析可以檢測(cè)出源程序中的非法符號(hào)，就好比自然語(yǔ)言語(yǔ)句中的出現(xiàn)的錯(cuò)字、錯(cuò)詞。語(yǔ)法分析能夠發(fā)現(xiàn)程序語(yǔ)句中的各種語(yǔ)法錯(cuò)誤，如括號(hào)不匹配等等。語(yǔ)義分析能判斷運(yùn)算對(duì)象的類型是否匹配、變量是否重復(fù)聲明或沒(méi)聲明就使用等錯(cuò)誤。任意時(shí)刻發(fā)現(xiàn)錯(cuò)誤，都應(yīng)該報(bào)告錯(cuò)誤信息，包括錯(cuò)誤出現(xiàn)的位置、錯(cuò)誤性質(zhì)等，為程序員調(diào)試程序提供方便。481.4 編譯程序的結(jié)構(gòu) 在設(shè)計(jì)和實(shí)現(xiàn)編譯程序時(shí)，要考慮編譯程序分“遍”的問(wèn)題。所謂一“遍”是指編譯程序在編譯時(shí)把源程序或中間形式從頭到尾掃描一遍，并做相關(guān)的處理，生成新的中間形式或目標(biāo)代碼。在一遍掃描中，可完成編譯程序五個(gè)任務(wù)中的一個(gè)或幾個(gè)。采用不同的分遍方式，編譯程序的結(jié)構(gòu)也有所不同。 4

28、91.4.1 單遍編譯程序 詞法分析 源程序 取單詞 目標(biāo)程序 開(kāi)始 語(yǔ)法分析 語(yǔ)義分析及代碼生成 送單詞 圖單遍編譯程序結(jié)構(gòu) 501.4.1 單遍編譯程序 單遍編譯程序只對(duì)源程序進(jìn)行一遍掃描，就完成編譯的各項(xiàng)任務(wù)，產(chǎn)生目標(biāo)代碼。在單遍編譯程序中，往往以語(yǔ)法分析程序?yàn)橹行?，詞法分析和語(yǔ)義分析作為語(yǔ)法分析的子程序。其工作過(guò)程如下：當(dāng)語(yǔ)法分析需要讀進(jìn)一個(gè)新單詞時(shí)，就調(diào)用詞法分析子程序。詞法分析子程序則從源程序中依次讀入字符，組合成單詞符號(hào)，并將單詞符號(hào)返回給語(yǔ)法分析程序。當(dāng)語(yǔ)法分析程序識(shí)別出一個(gè)語(yǔ)法成分時(shí)，就調(diào)用語(yǔ)義分析子程序進(jìn)行語(yǔ)義分析，并生成目標(biāo)程序。當(dāng)源程序處理完后，進(jìn)行善后處理，優(yōu)化目標(biāo)程序。511.4.2 多遍編譯程序詞法分析 語(yǔ)法分析 語(yǔ)義分析 代碼優(yōu)化目標(biāo)代碼生成分