第1章引論--清華大學(xué)出版社(2012)

1、編譯原理編譯原理 武漢理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院編譯原理 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 何九周 教材：編譯原理(第2版)張素琴、呂映芝、蔣維杜、戴桂蘭，清華大學(xué)出版社 參考書：程序設(shè)計(jì)語(yǔ)言編譯原理(第3版)陳火旺、劉春林等，國(guó)防工業(yè)出版社編譯原理學(xué)習(xí)與解題指南伍春香編著 華中科技大學(xué)出版社Compilers: Principles, Technigues, and Tools Alfred V.Aho, Ravi Sethi, Jeffrey D.Ullman, Addison-Wesley,1986. 影印版：人民郵電出版社教材與參考書教材與參考書學(xué)時(shí)學(xué)時(shí) 總學(xué)時(shí)總學(xué)時(shí)48理論學(xué)時(shí)理論學(xué)時(shí)40實(shí)驗(yàn)

2、學(xué)時(shí)實(shí)驗(yàn)學(xué)時(shí)8 在這一學(xué)期里，希望我們能共同努力，學(xué)好這門功課！教學(xué)目的教學(xué)目的 編譯系統(tǒng)是現(xiàn)代計(jì)算機(jī)系統(tǒng)的基本組成之編譯系統(tǒng)是現(xiàn)代計(jì)算機(jī)系統(tǒng)的基本組成之一，編譯程序構(gòu)造的基本原理和技術(shù)不僅應(yīng)一，編譯程序構(gòu)造的基本原理和技術(shù)不僅應(yīng)用于編譯程序的設(shè)計(jì)，也廣泛應(yīng)用于一般軟用于編譯程序的設(shè)計(jì)，也廣泛應(yīng)用于一般軟件的設(shè)計(jì)和實(shí)現(xiàn)。本課程是計(jì)算機(jī)專業(yè)、軟件的設(shè)計(jì)和實(shí)現(xiàn)。本課程是計(jì)算機(jī)專業(yè)、軟件工程專業(yè)的一門十分重要的核心專業(yè)課。件工程專業(yè)的一門十分重要的核心專業(yè)課。 通過(guò)本課程的學(xué)習(xí)，旨在使學(xué)生掌握編譯通過(guò)本課程的學(xué)習(xí)，旨在使學(xué)生掌握編譯的基本理論、原理和技術(shù)，并對(duì)編譯程序有的基本理論、原理和技術(shù)，并對(duì)編

3、譯程序有較為具體的認(rèn)識(shí)。使學(xué)生能運(yùn)用所學(xué)過(guò)的基較為具體的認(rèn)識(shí)。使學(xué)生能運(yùn)用所學(xué)過(guò)的基本知識(shí)、著手開(kāi)發(fā)系統(tǒng)程序，為今后的工作本知識(shí)、著手開(kāi)發(fā)系統(tǒng)程序，為今后的工作（技術(shù)和理論研究）打下基礎(chǔ)。（技術(shù)和理論研究）打下基礎(chǔ)。教學(xué)計(jì)劃教學(xué)計(jì)劃1 引論 2學(xué)時(shí)2 文法和語(yǔ)言 6學(xué)時(shí)3 詞法分析 6學(xué)時(shí)4 自頂向下語(yǔ)法分析方法 4學(xué)時(shí)5 自底向上語(yǔ)法分析法 6學(xué)時(shí)6 語(yǔ)法制導(dǎo)翻譯和中間代碼生成 6學(xué)時(shí)7 符號(hào)表 2學(xué)時(shí)8 目標(biāo)程序運(yùn)行時(shí)的存儲(chǔ)組織 2學(xué)時(shí)9 代碼優(yōu)化 4學(xué)時(shí)10 代碼生成 2學(xué)時(shí)學(xué)習(xí)要求學(xué)習(xí)要求 編譯程序是一個(gè)系統(tǒng)性很強(qiáng)的軟件。在課編譯程序是一個(gè)系統(tǒng)性很強(qiáng)的軟件。在課程中我們按階段進(jìn)行討論，

4、但在學(xué)習(xí)時(shí)心中程中我們按階段進(jìn)行討論，但在學(xué)習(xí)時(shí)心中一定要有系統(tǒng)的概念，把每個(gè)階段放到整個(gè)一定要有系統(tǒng)的概念，把每個(gè)階段放到整個(gè)編譯程序背景中學(xué)習(xí)，才不致將所學(xué)的內(nèi)容編譯程序背景中學(xué)習(xí)，才不致將所學(xué)的內(nèi)容孤立化。通過(guò)課程的學(xué)習(xí)應(yīng)掌握各個(gè)階段的孤立化。通過(guò)課程的學(xué)習(xí)應(yīng)掌握各個(gè)階段的功能和設(shè)計(jì)原則，以及在編譯中的邏輯關(guān)系。功能和設(shè)計(jì)原則，以及在編譯中的邏輯關(guān)系。理解他們?cè)鯓幼鳛橐粋€(gè)整體完成編譯任務(wù)的，理解他們?cè)鯓幼鳛橐粋€(gè)整體完成編譯任務(wù)的，并且或多或少做些實(shí)踐工作更能加深理解。并且或多或少做些實(shí)踐工作更能加深理解。第第1章章 引論引論 本章主要介紹在后面的章節(jié)中將要學(xué)到什么內(nèi)容。第第1章教學(xué)內(nèi)容章

5、教學(xué)內(nèi)容 了解：什么是翻譯程序、編譯程序、解釋程序； 明確編譯程序的功能及其在計(jì)算機(jī)系統(tǒng)中的作用； 了解源語(yǔ)言程序被編譯為目標(biāo)程序的整個(gè)過(guò)程，這個(gè)過(guò)程一般劃分為哪些階段； 知道編譯技術(shù)可用于哪類軟件的設(shè)計(jì)和開(kāi)發(fā)。 一、什么是編譯程序一、什么是編譯程序【翻譯程序】【翻譯程序】將源語(yǔ)言程序轉(zhuǎn)換為目標(biāo)語(yǔ)言將源語(yǔ)言程序轉(zhuǎn)換為目標(biāo)語(yǔ)言程序的程序的等價(jià)等價(jià)的程序稱為翻譯程序。的程序稱為翻譯程序。某一種語(yǔ)言程序某一種語(yǔ)言程序另一種語(yǔ)言程序另一種語(yǔ)言程序轉(zhuǎn)換轉(zhuǎn)換源語(yǔ)言程序源語(yǔ)言程序目標(biāo)語(yǔ)言程序目標(biāo)語(yǔ)言程序編譯程序編譯程序【編譯程序】【編譯程序】將高級(jí)語(yǔ)言源程序翻譯為低級(jí)語(yǔ)將高級(jí)語(yǔ)言源程序翻譯為低級(jí)語(yǔ)言目標(biāo)程序

6、的程序稱為編譯程序。言目標(biāo)程序的程序稱為編譯程序。高級(jí)語(yǔ)言程序高級(jí)語(yǔ)言程序低級(jí)語(yǔ)言程序低級(jí)語(yǔ)言程序編譯程序編譯程序機(jī)器或匯編程序機(jī)器或匯編程序編譯程序的意義：使得多數(shù)計(jì)算機(jī)用戶不必編譯程序的意義：使得多數(shù)計(jì)算機(jī)用戶不必考慮與機(jī)器有關(guān)的繁瑣細(xì)節(jié)，使程序員和程考慮與機(jī)器有關(guān)的繁瑣細(xì)節(jié)，使程序員和程序?qū)＜要?dú)立于機(jī)器。序?qū)＜要?dú)立于機(jī)器。匯編程序匯編程序【匯編程序】【匯編程序】將匯編語(yǔ)言源程序翻譯為機(jī)器語(yǔ)將匯編語(yǔ)言源程序翻譯為機(jī)器語(yǔ)言目標(biāo)程序的程序稱為匯編程序。言目標(biāo)程序的程序稱為匯編程序。匯編語(yǔ)言程序匯編語(yǔ)言程序機(jī)器語(yǔ)言程序機(jī)器語(yǔ)言程序匯編程序匯編程序【反匯編程序】【反匯編程序】將機(jī)器語(yǔ)言源程序翻譯為

7、匯編將機(jī)器語(yǔ)言源程序翻譯為匯編語(yǔ)言目標(biāo)程序的程序稱為反匯編程序。語(yǔ)言目標(biāo)程序的程序稱為反匯編程序。高級(jí)語(yǔ)言有兩種翻譯途徑：高級(jí)語(yǔ)言有兩種翻譯途徑： 編譯方式與解釋方式。編譯方式與解釋方式。它們的主要區(qū)別在于它們的主要區(qū)別在于是否產(chǎn)生目標(biāo)程序是否產(chǎn)生目標(biāo)程序。 解釋程序不產(chǎn)生目標(biāo)程序，而是邊解解釋程序不產(chǎn)生目標(biāo)程序，而是邊解釋邊執(zhí)行源程序本身，是一種釋邊執(zhí)行源程序本身，是一種“會(huì)話型會(huì)話型”語(yǔ)言。語(yǔ)言。編譯程序與解釋程序的異同編譯程序與解釋程序的異同程序設(shè)計(jì)語(yǔ)言的實(shí)現(xiàn)：程序設(shè)計(jì)語(yǔ)言的實(shí)現(xiàn)：有些語(yǔ)言基本通過(guò)解釋程序有些語(yǔ)言基本通過(guò)解釋程序 Java的的Bytecode有些環(huán)境同時(shí)提供編譯程序和解釋

8、系統(tǒng)有些環(huán)境同時(shí)提供編譯程序和解釋系統(tǒng) Lisp 編譯程序低級(jí)語(yǔ)言程序高級(jí)語(yǔ)言程序高級(jí)語(yǔ)言程序 解釋程序計(jì)算結(jié)果編譯程序和解釋系統(tǒng)編譯程序和解釋系統(tǒng)如對(duì)源程序： b := 2 ; a := b+2 ; write a ; 編譯程序編譯程序 解釋程序解釋程序 直接將4的值輸出（顯示）（直接對(duì)源程序中的語(yǔ)句進(jìn)行分析，執(zhí)行其隱含的操作。）Int 2St bLd badd 2St a生成代碼Java編譯器把Java代碼翻譯成獨(dú)立于機(jī)器的Java“字節(jié)代碼”。運(yùn)行時(shí)，目標(biāo)裝置中的校驗(yàn)器便分析這些字節(jié)代碼以確保代碼的安全執(zhí)行。在目標(biāo)裝置中，內(nèi)置一個(gè)JVM（Java虛擬機(jī)）。該虛擬機(jī)用一個(gè)解釋器或一個(gè)JIT

9、（適時(shí)）編譯器把字節(jié)代碼翻譯成目標(biāo)處理器能夠識(shí)別的機(jī)器語(yǔ)言。二、高級(jí)語(yǔ)言程序的處理過(guò)程二、高級(jí)語(yǔ)言程序的處理過(guò)程 需預(yù)處理的源程序預(yù)處理的程序源程序目標(biāo)匯編程序可再裝配的機(jī)器代碼編譯程序匯編程序連接裝配程序可再裝配的目標(biāo)代碼絕對(duì)機(jī)器代碼三、編譯程序的工作過(guò)程三、編譯程序的工作過(guò)程 編譯程序的工作，從輸入源程序開(kāi)始編譯程序的工作，從輸入源程序開(kāi)始到輸出目標(biāo)程序?yàn)橹沟恼麄€(gè)過(guò)程，是非到輸出目標(biāo)程序?yàn)橹沟恼麄€(gè)過(guò)程，是非常復(fù)雜的。但就其過(guò)程而言，它與人們常復(fù)雜的。但就其過(guò)程而言，它與人們進(jìn)行自然語(yǔ)言之間的翻譯有許多相近之進(jìn)行自然語(yǔ)言之間的翻譯有許多相近之處。處。 英漢翻譯與編譯的比較英漢翻譯與編譯的比較

10、【例如】英語(yǔ)句子【例如】英語(yǔ)句子This is a book.This is a book.的的翻譯過(guò)程：翻譯過(guò)程：1 1、識(shí)別單詞、識(shí)別單詞2 2、“組詞成句組詞成句”3 3、分析句子的含義、分析句子的含義4 4、進(jìn)行初步翻譯、進(jìn)行初步翻譯5 5、修飾譯文、修飾譯文6 6、寫出最后譯文、寫出最后譯文編譯程序的翻譯過(guò)程類似：1、詞法分析2、語(yǔ)法分析3、語(yǔ)義分析4 4、中間代碼生成5、代碼優(yōu)化6、目標(biāo)代碼生成編譯程序的編譯程序的6個(gè)階段個(gè)階段 編譯程序的工作過(guò)程一般劃分為六個(gè)階段：編譯程序的工作過(guò)程一般劃分為六個(gè)階段： 詞法分析詞法分析 語(yǔ)法分析語(yǔ)法分析 語(yǔ)義分析語(yǔ)義分析 中間代碼生成中間代碼生

11、成 代碼優(yōu)化代碼優(yōu)化 目標(biāo)代碼生成目標(biāo)代碼生成 1.詞法分析詞法分析任務(wù)：從左至右讀字符流的源程序，識(shí)別(拼)單詞?！締卧~】單詞是具有獨(dú)立意義的最小語(yǔ)法單位。識(shí)別原則：詞法規(guī)則描述工具：正規(guī)式 正規(guī)文法 有窮自動(dòng)機(jī)FA自動(dòng)生成工具：LEX 【例如】某賦值語(yǔ)句如下：例如】某賦值語(yǔ)句如下： yx1x2 * 60；詞法分析階段識(shí)別出的單詞序列為：?jiǎn)卧~類型單詞類型單詞值單詞值標(biāo)識(shí)符(變量名) y算符(賦值) =標(biāo)識(shí)符(變量名) x1算符(加法) +標(biāo)識(shí)符(變量名) x2算符(乘法) *整數(shù) 60界符 ；2.語(yǔ)法分析語(yǔ)法分析任務(wù)：依據(jù)依據(jù)源程序的語(yǔ)法規(guī)則語(yǔ)法規(guī)則把源程序的單詞序列組成更大的語(yǔ)法成分“組詞

12、成句” (表示成語(yǔ)法樹(shù)) 。識(shí)別原則：語(yǔ)法規(guī)則描述工具：上下文無(wú)關(guān)文法 下推自動(dòng)機(jī)PDA自動(dòng)生成工具：YACC賦值語(yǔ)句的語(yǔ)法規(guī)則 := = := + := * :=( ) := := := 賦值語(yǔ)句標(biāo)識(shí)符表達(dá)式表達(dá)式+表達(dá)式表達(dá)式標(biāo)識(shí)符整數(shù)標(biāo)識(shí)符=表達(dá)式*語(yǔ)語(yǔ)法法樹(shù)樹(shù)3.語(yǔ)義分析與中間代碼生成語(yǔ)義分析與中間代碼生成任務(wù)：對(duì)語(yǔ)法分析所識(shí)別出的各類語(yǔ)法范疇，分析其含義，并進(jìn)行初步翻譯（產(chǎn)生中間代碼）。 語(yǔ)義審查(靜態(tài)語(yǔ)義) 上下文相關(guān)性 類型匹配 類型轉(zhuǎn)換識(shí)別原則：語(yǔ)義規(guī)則描述工具：屬性文法實(shí)現(xiàn)方法：語(yǔ)法制導(dǎo)翻譯中間代碼中間代碼 所謂所謂“中間代碼中間代碼”是一種含義明確、便于處理的是一種含義明確

13、、便于處理的記號(hào)系統(tǒng)，它通常獨(dú)立于具體的硬件。這種記號(hào)記號(hào)系統(tǒng)，它通常獨(dú)立于具體的硬件。這種記號(hào)系統(tǒng)或者與現(xiàn)代計(jì)算機(jī)的指令形式有某種程度的系統(tǒng)或者與現(xiàn)代計(jì)算機(jī)的指令形式有某種程度的接近，或者能夠比較容易地把它變換成現(xiàn)代計(jì)算接近，或者能夠比較容易地把它變換成現(xiàn)代計(jì)算機(jī)的機(jī)器指令。機(jī)的機(jī)器指令。 許多編譯程序采用了一種與許多編譯程序采用了一種與“三地址指令三地址指令”非常非常近似的近似的“四元式四元式”作為中間代碼，其形式是：作為中間代碼，其形式是： (算符算符 , 運(yùn)算對(duì)象運(yùn)算對(duì)象1 , 運(yùn)算對(duì)象運(yùn)算對(duì)象2 , 結(jié)果結(jié)果)常用的中間代碼有：四元式，三元式，間接三元式，常用的中間代碼有：四元式，三

14、元式，間接三元式，逆波蘭記號(hào)和樹(shù)形表示等等。逆波蘭記號(hào)和樹(shù)形表示等等。 中間代碼生成示例中間代碼生成示例賦值語(yǔ)句賦值語(yǔ)句 y= x1 + x2* 60對(duì)應(yīng)的四元式是：對(duì)應(yīng)的四元式是： (1) (*,x2,60,t1) (2) (+,x1,t1,t2) (3) (=,t2,-,y)4.代碼優(yōu)化代碼優(yōu)化 任務(wù)：任務(wù)：對(duì)前段產(chǎn)生的中間代碼進(jìn)行加工變換，以期在最后階段能產(chǎn)生出更為高效（省時(shí)間和空間）的目標(biāo)代碼。 主要包括：主要包括：公共子表達(dá)式的提取 循環(huán)優(yōu)化 刪除無(wú)用代碼等等 優(yōu)化所依循的原則：優(yōu)化所依循的原則：程序的等價(jià)變換規(guī)則。 優(yōu)化示例優(yōu)化示例 【例如】程序片斷：【例如】程序片斷： for K

15、：1 to 100 do begin M：I10 * K； N：J 10*K end中間代碼為：( ：, 1, , K ) ( j , 100, K, （9）)( * , 10, K, T1 )( , I, T1 , M )( * , 10, K, T2 )( , J, T2 , N )( , K, 1 , K )( j , , ,（2）)1) 循環(huán)中需做循環(huán)中需做300次加法次加法和和200次乘次乘法法 優(yōu)化后的中間代碼為：( ：, I, , M ) ( ：, J, , N ) ( ：, 1, , K )( j , 100, K, （9）)( , M, 10 , M )( , N, 10 ,

16、 N )( , K, 1 , K )( j , , ,（4）)1) 循環(huán)中只循環(huán)中只需做需做300次次加法加法5.目標(biāo)代碼生成目標(biāo)代碼生成 任務(wù)：把中間代碼（或經(jīng)優(yōu)化處理之后）變換成特定機(jī)器上的低級(jí)語(yǔ)言代碼。生成原則：硬件系統(tǒng)結(jié)構(gòu)和機(jī)器指令含義。目標(biāo)代碼的形式： 絕對(duì)指令代碼 可重定位的指令代碼 匯編指令代碼 目標(biāo)代碼生成示例目標(biāo)代碼生成示例(*,x1 ,60.0,t1)(+,x2 ,t1 ,x1)movfx1,R2mulf#60.0,R2movfx2,R1addfR2,R1movfR1,x1注意注意 上述編譯過(guò)程的階段劃分只是一種典型的分法，上述編譯過(guò)程的階段劃分只是一種典型的分法，事實(shí)上并

17、不是所有的編譯程序都分成這樣幾個(gè)事實(shí)上并不是所有的編譯程序都分成這樣幾個(gè)階段的。階段的。 有些編譯程序?qū)?yōu)化沒(méi)有什么要求，優(yōu)化階段有些編譯程序?qū)?yōu)化沒(méi)有什么要求，優(yōu)化階段就可省去。在某些情況下，為了加快編譯速度，就可省去。在某些情況下，為了加快編譯速度，中間代碼產(chǎn)生階段也可以去掉。有些最簡(jiǎn)單的中間代碼產(chǎn)生階段也可以去掉。有些最簡(jiǎn)單的編譯程序是在語(yǔ)法分析的同時(shí)產(chǎn)生目標(biāo)代碼。編譯程序是在語(yǔ)法分析的同時(shí)產(chǎn)生目標(biāo)代碼。但是，多數(shù)實(shí)用編譯程序的工作過(guò)程大致都像但是，多數(shù)實(shí)用編譯程序的工作過(guò)程大致都像上面所說(shuō)的那六個(gè)階段。上面所說(shuō)的那六個(gè)階段。 其它其它 編譯程序的另外兩個(gè)重要的工作是表格管理和出錯(cuò)處理。

18、 編譯過(guò)程中源程序的各種信息被保留在種種不同的表格里，編譯各階段的工作都涉及到構(gòu)造、查找或更新有關(guān)的表格，因此需要有表格管理的工作；如果編譯過(guò)程中發(fā)現(xiàn)源程序有錯(cuò)誤，編譯程序應(yīng)報(bào)告錯(cuò)誤的性質(zhì)和錯(cuò)誤發(fā)生的地點(diǎn)，并且將錯(cuò)誤所造成的影響限制在盡可能小的范圍內(nèi)，使得源程序的其余部分能繼續(xù)被編譯下去，有些編譯程序還能自動(dòng)校正錯(cuò)誤，這些工作稱之為出錯(cuò)處理。表格與表格管理表格與表格管理 編譯程序在工作過(guò)程中需要保持一系列的編譯程序在工作過(guò)程中需要保持一系列的表格，以登記源程序的各類信息和編譯各表格，以登記源程序的各類信息和編譯各階段的進(jìn)展?fàn)顩r。合理地設(shè)計(jì)和使用表格階段的進(jìn)展?fàn)顩r。合理地設(shè)計(jì)和使用表格是編譯程序

19、構(gòu)造的一個(gè)重要問(wèn)題。是編譯程序構(gòu)造的一個(gè)重要問(wèn)題。 在編譯程序中最重要的一種表格是在編譯程序中最重要的一種表格是符號(hào)表符號(hào)表。 記錄源程序中使用的名字 收集每個(gè)名字的各種屬性信息 類型、作用域、分配存儲(chǔ)信息出錯(cuò)處理出錯(cuò)處理 一個(gè)編譯程序不僅應(yīng)能對(duì)書寫正確的程序進(jìn)一個(gè)編譯程序不僅應(yīng)能對(duì)書寫正確的程序進(jìn)行翻譯，而且應(yīng)能對(duì)出現(xiàn)在源程序中的錯(cuò)誤行翻譯，而且應(yīng)能對(duì)出現(xiàn)在源程序中的錯(cuò)誤進(jìn)行處理。如果源程序有錯(cuò)誤，編譯程序應(yīng)進(jìn)行處理。如果源程序有錯(cuò)誤，編譯程序應(yīng)設(shè)法發(fā)現(xiàn)錯(cuò)誤，把有關(guān)錯(cuò)誤信息報(bào)告給用戶。設(shè)法發(fā)現(xiàn)錯(cuò)誤，把有關(guān)錯(cuò)誤信息報(bào)告給用戶。這部分工作是由專門的一組程序（叫做出錯(cuò)這部分工作是由專門的一組程序（

20、叫做出錯(cuò)處理程序）完成的。處理程序）完成的。 出錯(cuò)處理程序的任務(wù)包括出錯(cuò)處理程序的任務(wù)包括檢查錯(cuò)誤、報(bào)告出檢查錯(cuò)誤、報(bào)告出錯(cuò)信息、排錯(cuò)、恢復(fù)編譯工作錯(cuò)信息、排錯(cuò)、恢復(fù)編譯工作。四、編譯程序的組成四、編譯程序的組成 編譯過(guò)程的五個(gè)階段的任務(wù)，再加上表編譯過(guò)程的五個(gè)階段的任務(wù)，再加上表格管理和出錯(cuò)處理的工作可分別由幾個(gè)格管理和出錯(cuò)處理的工作可分別由幾個(gè)模塊或程序完成，它們分別稱作詞法分模塊或程序完成，它們分別稱作詞法分析程序、語(yǔ)法分析程序、語(yǔ)義分析程序、析程序、語(yǔ)法分析程序、語(yǔ)義分析程序、中間代碼生成程序、代碼優(yōu)化程序、目中間代碼生成程序、代碼優(yōu)化程序、目標(biāo)代碼生成程序、表格管理程序和出錯(cuò)標(biāo)代碼生

21、成程序、表格管理程序和出錯(cuò)處理程序。從而可給出一個(gè)典型的編譯處理程序。從而可給出一個(gè)典型的編譯程序結(jié)構(gòu)框圖，如圖所示。程序結(jié)構(gòu)框圖，如圖所示。出錯(cuò)處理程序語(yǔ)法分析程序語(yǔ)義分析程序目標(biāo)代碼生成程序詞法分析程序中間代碼生成程序代碼優(yōu)化程序表格管理程序編譯程序的組成編譯程序的組成源程序詞法分析器單詞符號(hào)語(yǔ)法分析器語(yǔ)法單位語(yǔ)義分析與中間代碼生成器中間代碼 優(yōu)化器中間代碼目標(biāo)代碼生成器目標(biāo)代碼 表 格 管 理 程 序 出 錯(cuò) 處 理 程 序五、編譯的前端與后端五、編譯的前端與后端o 常把編譯的過(guò)程分為前端和后端。o 前端前端：主要依賴于源語(yǔ)言而與目標(biāo)機(jī)無(wú)關(guān)。通常包括詞法分析、語(yǔ)法分析、語(yǔ)義分析和中間代碼

22、生成這些階段，某些優(yōu)化（中間代碼優(yōu)化），也包括相應(yīng)的出錯(cuò)處理和符號(hào)表管理等工作。o 后端后端：依賴于目標(biāo)機(jī)而一般不依賴源語(yǔ)言。后端包括目標(biāo)代碼生成和目標(biāo)代碼優(yōu)化，以及相關(guān)出錯(cuò)處理和符號(hào)表操作。六、遍（六、遍（pass） 所謂“遍”就是對(duì)源程序或源程序的中間結(jié)果從頭到尾掃描一次，并作有關(guān)的加工處理，生成新的中間結(jié)果或目標(biāo)程序。 Turbo C是一遍完成編譯，以及預(yù)處理和后續(xù)處理。 兩遍編譯： 1.進(jìn)行詞法分析、語(yǔ)法分析、語(yǔ)義分析，生成中間代碼作為文件保留，以及符號(hào)表文件。 2.優(yōu)化后生成目標(biāo)代碼作為文件保留。 三遍編譯： 3.對(duì)目標(biāo)代碼的優(yōu)化。七、編譯程序涉及的三種語(yǔ)言七、編譯程序涉及的三種語(yǔ)言

23、 源語(yǔ)言源語(yǔ)言：要深刻理解源語(yǔ)言(如 FORTRAN、Pascal或 C)結(jié)構(gòu)(語(yǔ)法)和含義(語(yǔ)義)； 目標(biāo)語(yǔ)言目標(biāo)語(yǔ)言：最終的目標(biāo)語(yǔ)言還是機(jī)器語(yǔ)言，則必須搞清楚硬件的系統(tǒng)結(jié)構(gòu)和操作系統(tǒng)的功能； 宿主語(yǔ)言宿主語(yǔ)言：編寫編譯程序的語(yǔ)言。 自編譯程序：宿主語(yǔ)言是源語(yǔ)言。例如PASCAL。八、編譯程序的生成八、編譯程序的生成 q手工手工q機(jī)器語(yǔ)言機(jī)器語(yǔ)言q匯編匯編q系統(tǒng)程序設(shè)計(jì)語(yǔ)言，自編譯，移植，交叉編系統(tǒng)程序設(shè)計(jì)語(yǔ)言，自編譯，移植，交叉編譯等方式譯等方式q自動(dòng)構(gòu)造工具自動(dòng)構(gòu)造工具lex yacc九、九、編譯程序與程序設(shè)計(jì)環(huán)境編譯程序與程序設(shè)計(jì)環(huán)境 編譯程序無(wú)疑是實(shí)現(xiàn)高級(jí)語(yǔ)言的一個(gè)最重要編譯程序無(wú)疑

24、是實(shí)現(xiàn)高級(jí)語(yǔ)言的一個(gè)最重要的工具。但支持程序設(shè)計(jì)人員進(jìn)行程序設(shè)計(jì)開(kāi)的工具。但支持程序設(shè)計(jì)人員進(jìn)行程序設(shè)計(jì)開(kāi)發(fā)通常還需要其它一些工具：如編輯程序、連發(fā)通常還需要其它一些工具：如編輯程序、連接程序、調(diào)試程序等。編譯程序與這些程序設(shè)接程序、調(diào)試程序等。編譯程序與這些程序設(shè)計(jì)工具一起構(gòu)成所謂的計(jì)工具一起構(gòu)成所謂的程序設(shè)計(jì)環(huán)境程序設(shè)計(jì)環(huán)境。 在一個(gè)程序設(shè)計(jì)環(huán)境中，編譯程序起著中心在一個(gè)程序設(shè)計(jì)環(huán)境中，編譯程序起著中心的作用。連接程序、調(diào)試程序、程序分析等工的作用。連接程序、調(diào)試程序、程序分析等工具直接依賴于編譯程序所產(chǎn)生的結(jié)果，而其它具直接依賴于編譯程序所產(chǎn)生的結(jié)果，而其它工具的構(gòu)造也常常要用到編譯的原

25、理、方法和工具的構(gòu)造也常常要用到編譯的原理、方法和技術(shù)。技術(shù)。十、編譯技術(shù)在軟件工具中的應(yīng)用十、編譯技術(shù)在軟件工具中的應(yīng)用 大部分系統(tǒng)軟件與應(yīng)用軟件的開(kāi)發(fā)通常大部分系統(tǒng)軟件與應(yīng)用軟件的開(kāi)發(fā)通常要用到編譯原理和技術(shù)。要用到編譯原理和技術(shù)。 設(shè)計(jì)詞法分析器的串匹配技術(shù)已用于正文編設(shè)計(jì)詞法分析器的串匹配技術(shù)已用于正文編輯器、信息檢索系統(tǒng)和模式識(shí)別程序。輯器、信息檢索系統(tǒng)和模式識(shí)別程序。 上下文無(wú)關(guān)文法和語(yǔ)法制導(dǎo)定義已用于排版、上下文無(wú)關(guān)文法和語(yǔ)法制導(dǎo)定義已用于排版、繪圖系統(tǒng)和語(yǔ)言結(jié)構(gòu)化編輯器。繪圖系統(tǒng)和語(yǔ)言結(jié)構(gòu)化編輯器。 代碼優(yōu)化技術(shù)已用于程序驗(yàn)證器和從非結(jié)構(gòu)代碼優(yōu)化技術(shù)已用于程序驗(yàn)證器和從非結(jié)構(gòu)化

26、的程序產(chǎn)生結(jié)構(gòu)化程序的編程中?；某绦虍a(chǎn)生結(jié)構(gòu)化程序的編程中。十一、處理源程序的軟件工具十一、處理源程序的軟件工具1.語(yǔ)言的結(jié)構(gòu)化編輯器語(yǔ)言的結(jié)構(gòu)化編輯器2.語(yǔ)言程序的調(diào)試工具語(yǔ)言程序的調(diào)試工具3.程序格式化工具程序格式化工具4.語(yǔ)言程序測(cè)試工具語(yǔ)言程序測(cè)試工具5.程序理解工具程序理解工具6.高級(jí)語(yǔ)言之間的轉(zhuǎn)換工具高級(jí)語(yǔ)言之間的轉(zhuǎn)換工具1.語(yǔ)言的結(jié)構(gòu)化編輯器 用戶可使用該編輯器在語(yǔ)言的語(yǔ)法制導(dǎo)下編制出所需的源程序。結(jié)構(gòu)化編輯器不僅具有通常的正文編輯器的正文編輯和修改功能，而且還能像編譯程序那樣對(duì)源程序正文進(jìn)行分析。因此，結(jié)構(gòu)化編輯器能夠執(zhí)行一些對(duì)編制程序有用的附加的任務(wù)。例如，它能夠檢查用戶的

27、輸入是否正確，能夠自動(dòng)地提供關(guān)鍵字,當(dāng)用戶敲入if后，編輯器立即顯示then并將這兩個(gè)關(guān)鍵字之間必須出現(xiàn)的條件留給用戶輸入，并能檢查begin或左括號(hào)與end或右括號(hào)是否相匹配等等。由于結(jié)構(gòu)化編輯器具有上述功能，既可保證編出的源程序無(wú)語(yǔ)法錯(cuò)誤，并有統(tǒng)一的可讀性好的程序格式，這無(wú)疑將會(huì)提高程序的開(kāi)發(fā)效率和質(zhì)量。 商用產(chǎn)品很多如Turbo-Edit,Editplus和Ultraedit等等。很多集成開(kāi)發(fā)環(huán)境中里也都包含這種類似的工具,如Jbuild中就有JAVA程序的結(jié)構(gòu)化編輯器。2.語(yǔ)言程序的調(diào)試工具 調(diào)試是軟件開(kāi)發(fā)過(guò)程中一個(gè)重要環(huán)節(jié)，結(jié)構(gòu)化編輯器只能解決語(yǔ)法錯(cuò)誤的問(wèn)題，而對(duì)一個(gè)已通過(guò)編譯的程序

28、來(lái)說(shuō)，需進(jìn)一步了解的是程序執(zhí)行的結(jié)果與編程人員的意圖是否一致，程序的執(zhí)行是否實(shí)現(xiàn)預(yù)計(jì)的算法和功能。這種對(duì)算法的錯(cuò)誤或程序沒(méi)能反映算法的功能等錯(cuò)誤就需用調(diào)試器來(lái)協(xié)助解決。有一種調(diào)試器允許用戶使用源程序正文和它的符號(hào)來(lái)調(diào)試,即一行一行的跟蹤程序,查看變量和數(shù)據(jù)結(jié)構(gòu)的變化以進(jìn)行調(diào)試工作.當(dāng)然,這些符號(hào)的信息必須由編譯程序提供.調(diào)試器的實(shí)現(xiàn)可以有很多途徑.其中一種是寫一個(gè)解釋器,以交互的方式翻譯和執(zhí)行每一行,它必須維護(hù)其所有的運(yùn)行時(shí)的資源以保證在程序執(zhí)行期間很容易的查詢不同變量的當(dāng)前值.如果不想通過(guò)解釋程序允許編譯了的代碼調(diào)試,編譯程序必須在目標(biāo)代碼(匯編)生成時(shí)同時(shí)生成特定的調(diào)試信息,比如,關(guān)聯(lián)標(biāo)識(shí)

29、符和它表示的地址的信息,用于無(wú)歧義的引用一個(gè)聲明了多次的標(biāo)識(shí)符的信息等等.調(diào)試功能愈強(qiáng)，實(shí)現(xiàn)愈復(fù)雜，它涉及源程序的語(yǔ)法分析和語(yǔ)義處理技術(shù)。3.程序格式化工具程序格式化工具程序格式化工具分析源程序并以使程序結(jié)構(gòu)變得清晰可讀的形式打印出來(lái)。例如，注釋可以以一種專門的字形出現(xiàn)，且語(yǔ)句的嵌套層次結(jié)構(gòu)可以用縮排方式（齒形結(jié)構(gòu)）表示出來(lái)。4.語(yǔ)言程序測(cè)試工具語(yǔ)言程序測(cè)試工具 語(yǔ)言程序的測(cè)試工具有兩種：靜態(tài)分析器和動(dòng)態(tài)測(cè)試器。 靜態(tài)分析器靜態(tài)分析器是在不運(yùn)行程序的情況下對(duì)源程序進(jìn)行靜態(tài)地分析，以發(fā)現(xiàn)程序中潛在的錯(cuò)誤或異常.它對(duì)源程序進(jìn)行語(yǔ)法分析并制定相應(yīng)表格，檢查變量定值與引用的關(guān)系。如某變量未被賦值就被引

30、用，或定值后未被引用，或多余的源代碼等一些編譯程序的語(yǔ)法分析發(fā)現(xiàn)不了的錯(cuò)誤。 動(dòng)態(tài)測(cè)試工具動(dòng)態(tài)測(cè)試工具也是首先對(duì)源程序進(jìn)行分析，在分析基礎(chǔ)上將用于記錄和顯示程序執(zhí)行軌跡的語(yǔ)句或函數(shù)插入到源程序的適當(dāng)位置，并用測(cè)試用例記錄和顯示程序運(yùn)行時(shí)的實(shí)際路徑,將運(yùn)行結(jié)果與期望的結(jié)果進(jìn)行比較分析，幫助編程人員查找問(wèn)題。5.程序理解工具程序理解工具對(duì)程序進(jìn)行分析，確定模塊間的調(diào)用關(guān)系，記錄程序數(shù)據(jù)的靜態(tài)屬性和結(jié)構(gòu)屬性，并畫出控制流程圖，幫助用戶理解程序。6. 高級(jí)語(yǔ)言之間的轉(zhuǎn)換工具高級(jí)語(yǔ)言之間的轉(zhuǎn)換工具 由于計(jì)算機(jī)硬件的不斷更新?lián)Q代，更新更好的程序設(shè)計(jì)語(yǔ)言的推出為提高計(jì)算機(jī)的使用效率提供了良好條件，然而一些已

31、有的非常成熟的軟件如何在新機(jī)器新語(yǔ)言情況下使用呢?為了減少重新編制程序所耗費(fèi)的人力和時(shí)間，就要解決如何把一種高級(jí)語(yǔ)言轉(zhuǎn)換成另一種高級(jí)語(yǔ)言，乃至匯編語(yǔ)言轉(zhuǎn)換成高級(jí)語(yǔ)言的問(wèn)題。這種轉(zhuǎn)換工作要對(duì)被轉(zhuǎn)換的語(yǔ)言進(jìn)行詞法和語(yǔ)法分析，只不過(guò)生成的目標(biāo)語(yǔ)言是另一種高級(jí)語(yǔ)言而已。這與實(shí)現(xiàn)一個(gè)完整的編譯程序相比工作量要少些。 比如：C，PASCAL，F(xiàn)ORTRAN到Ada的翻譯器 IBM 4700匯編到C的轉(zhuǎn)換器 COBOL 到Java 的編譯器 Human-orientedlanguageComputer-orientedlanguage計(jì)算模式，語(yǔ)言范式語(yǔ)言應(yīng)用領(lǐng)域編譯程序馮 諾依曼機(jī)體系結(jié)構(gòu)并行體系結(jié)構(gòu)嵌入

32、系統(tǒng)十二、程序設(shè)計(jì)語(yǔ)言范型十二、程序設(shè)計(jì)語(yǔ)言范型S OI高級(jí)程序語(yǔ)言高級(jí)程序語(yǔ)言v不同的應(yīng)用側(cè)重:數(shù)值計(jì)算 Fortran 系統(tǒng)程序設(shè)計(jì)-C事務(wù)處理-obol VLSI設(shè)計(jì)-VHDL人工智能-rolog大型嵌入式實(shí)時(shí)處理-da 符號(hào)處理-nobol語(yǔ)言范型語(yǔ)言范型（支持的計(jì)算模式）（支持的計(jì)算模式）強(qiáng)制式語(yǔ)言-C,Fortran,Pascal應(yīng)用式(函數(shù)式）語(yǔ)言-ML，Lisp基于規(guī)則(邏輯）的語(yǔ)言-Prolog,Yacc面向?qū)ο笳Z(yǔ)言-Ada,C+,Java強(qiáng)制式語(yǔ)言（強(qiáng)制式語(yǔ)言（Imperative Language）也稱過(guò)程式語(yǔ)言。）也稱過(guò)程式語(yǔ)言。 其特點(diǎn)是命令驅(qū)動(dòng)，面向語(yǔ)句，一個(gè)強(qiáng)制式

33、語(yǔ)言程序由一系列的語(yǔ)句組成，每個(gè)語(yǔ)句的執(zhí)行引起若干存儲(chǔ)單元中的值的改變，這種語(yǔ)言的語(yǔ)法形式通常具有如下形式； 語(yǔ)句1；語(yǔ)句2；語(yǔ)句3；語(yǔ)言執(zhí)行的解釋與萬(wàn)諾曼機(jī)的體系結(jié)構(gòu)對(duì)應(yīng)：改變機(jī)器狀態(tài)（內(nèi)存，各種寄存器和外存的內(nèi)容） 應(yīng)用式（函數(shù)式）：應(yīng)用式語(yǔ)言（Applicative Language）更注重程序所表示的功能，而不是一個(gè)語(yǔ)句接一個(gè)語(yǔ)句地執(zhí)行。程序的開(kāi)發(fā)過(guò)程是從前面已有的函數(shù)出發(fā)構(gòu)造出更復(fù)雜的函數(shù)，對(duì)初始數(shù)據(jù)集進(jìn)行操作直至最終的函數(shù)可以用于從初始數(shù)據(jù)計(jì)算出最終的結(jié)果。程序執(zhí)行： 執(zhí)行一個(gè)個(gè)函數(shù)施用在數(shù)據(jù)上的變換最終得到的結(jié)果Example: 解決八皇后問(wèn)題的一段Haskell98程序：queen 0 = queen (n+1) = x :y | y - queen n, x - 1.8, safe 1 x ysafe n x = Truesafe n x (z :y) = and x/=z, x/=z +n, x/=z -n, safe (n+1) x y-test = que