編譯原理--ch1

1、 編譯原理中國(guó)海洋大學(xué)計(jì)算機(jī)系葛 琳引子n你用編程語(yǔ)言（例如你用編程語(yǔ)言（例如C C）寫的程序是）寫的程序是怎樣被計(jì)算機(jī)運(yùn)行的？怎樣被計(jì)算機(jī)運(yùn)行的？通常使用的編程語(yǔ)言n我們通常使用的編程語(yǔ)言（例如C）是高級(jí)語(yǔ)言（high-level language）：n語(yǔ)義清晰，貼近自然語(yǔ)言（即人類使用的語(yǔ)言），易于理解，編程方便。n其程序無(wú)法被計(jì)算機(jī)理解和直接執(zhí)行。計(jì)算機(jī)使用什么語(yǔ)言？n計(jì)算機(jī)使用機(jī)器語(yǔ)言（machine language）：n機(jī)器語(yǔ)言程序本質(zhì)上是一串0，1串，它可以被計(jì)算機(jī)理解并執(zhí)行。n人類理解機(jī)器語(yǔ)言比較困難，因而直接使用機(jī)器語(yǔ)言編程是困難而效率低下的。編譯器的作用n我們用高級(jí)語(yǔ)言編寫

2、的程序只有被轉(zhuǎn)換成機(jī)器語(yǔ)言程序后才能被計(jì)算機(jī)理解和執(zhí)行。n這種轉(zhuǎn)換是由編譯器進(jìn)行的。n在這一過(guò)程中，被轉(zhuǎn)換程序稱為源程序，其編程語(yǔ)言（通常是高級(jí)語(yǔ)言）稱為源語(yǔ)言（source language），而轉(zhuǎn)換后的程序稱為目標(biāo)程序，其語(yǔ)言稱為目標(biāo)語(yǔ)言（target language）。課程要求和教學(xué)目標(biāo)n掌握編譯器構(gòu)造的一般原理和基本實(shí)現(xiàn)方法。n不偏向于某種源語(yǔ)言或目標(biāo)機(jī)器，而是強(qiáng)調(diào)對(duì)編譯原理和技術(shù)的宏觀理解。前驅(qū)課程：n學(xué)習(xí)這門課程之前請(qǐng)確定你有一定計(jì)算機(jī)專業(yè)背景，并且已經(jīng)學(xué)過(guò)下列課程：n至少一門編程語(yǔ)言（比如C）。n數(shù)據(jù)結(jié)構(gòu)、離散數(shù)學(xué)等，并有一定編程經(jīng)驗(yàn)。n擁有下列知識(shí)將對(duì)你學(xué)習(xí)這門課程很有幫助：

3、n計(jì)算機(jī)體系結(jié)構(gòu)n算法和軟件工程n更多編程語(yǔ)言知識(shí)（例如Pascal、Fortran、Java等）教材和參考書(shū)n教材：n編譯原理，陳意云、張昱，第2版，高等教育出版社，2009。n英文參考書(shū)：nCompilers: Principles, Techniques, and Tools. A. V. Aho, M. S. Lam, R. Sethi, and J. D. Ullman, 2nd edition, Addison-Wesley, 2007. （Dragon book）nModern Compiler Implementation in C/Java/ML. Andrew W. App

4、el with Jens Palsberg. 第2版影印版，高教出版社。（Tiger book）nAdvanced compiler design and implementation. Steven S. Muchnick. 影印版，機(jī)械工業(yè)出版社，2003。（Whale book）教材和參考書(shū)（續(xù)）n中文參考書(shū)：n上述英文參考書(shū)的中文翻譯版本。n編譯原理，蔣立源、康慕寧，第3版，西北工業(yè)大學(xué)出版社，2005。n程序設(shè)計(jì)語(yǔ)言編譯原理，陳火旺等，第3版，國(guó)防工業(yè)出版社，2000。授課內(nèi)容：n編譯器概述（第一章）n詞法分析（第二章）n上下文無(wú)關(guān)文法和語(yǔ)法分析（第三章）n語(yǔ)法制導(dǎo)翻譯和類型檢查（第

5、四、五章部分內(nèi)容）n運(yùn)行時(shí)存儲(chǔ)空間的組織和管理（第六章部分內(nèi)容）n中間代碼生成（第七章）n代碼生成（第八章，根據(jù)時(shí)間調(diào)整）課程要求：n本課程共68學(xué)時(shí)，其中講授51學(xué)時(shí)，實(shí)驗(yàn)17學(xué)時(shí)。n由于概念較多，因此要求大家：n認(rèn)真聽(tīng)，理解并牢記各種概念n課后復(fù)習(xí)并加深理解，多看書(shū)和課件。n獨(dú)立認(rèn)真完成作業(yè)。n課程實(shí)驗(yàn)：自己動(dòng)手第一章 引論n什么是編譯器？n為什么要學(xué)習(xí)編譯原理？n編譯過(guò)程可以如何劃分？各階段的作用？n編譯器是如何組織的？n編譯器是如何產(chǎn)生的？n如何構(gòu)造一個(gè)編譯器？什么是編譯器？n翻譯器（translator）：n能夠?qū)⒁环N語(yǔ)言編寫的程序翻譯成語(yǔ)義等價(jià)的另外一種語(yǔ)言的程序的軟件系統(tǒng)。n編譯

6、器（compiler）：n翻譯器的一種，其特點(diǎn)是目標(biāo)語(yǔ)言比源語(yǔ)言低級(jí)（低級(jí)語(yǔ)言：編程語(yǔ)言越接近機(jī)器語(yǔ)言，我們就說(shuō)這種語(yǔ)言越低級(jí)。）什么是編譯器？n直觀上理解的編譯器就是這樣一種程序：編譯器源程序目標(biāo)程序編譯器目標(biāo)程序（機(jī)器語(yǔ)言程序）輸入輸出目標(biāo)程序的運(yùn)行關(guān)于解釋器n解釋器（Interpreter）：不產(chǎn)生目標(biāo)代碼，而是解釋執(zhí)行源程序解釋器輸入輸出源程序編譯器和解釋器的綜合應(yīng)用nJava語(yǔ)言將編譯器和解釋器綜合使用：n先用編譯器把源程序翻譯成一種叫做字節(jié)碼（bytecode）的中間語(yǔ)言程序n再用一個(gè)虛擬機(jī)對(duì)字節(jié)碼程序進(jìn)行解釋執(zhí)行編譯器源程序中間語(yǔ)言程序虛擬機(jī)輸入輸出關(guān)于解釋器nBASIC語(yǔ)言年代

7、解釋器n功能：將高級(jí)語(yǔ)言的源程序翻譯成一種中間語(yǔ)言程序，然后對(duì)中間語(yǔ)言程序進(jìn)行解釋執(zhí)行n在那個(gè)年代，編譯和解釋兩個(gè)功能是合在一個(gè)程序中，該程序被稱為解釋器nJava語(yǔ)言年代解釋器n解釋器的上述兩個(gè)功能分在兩個(gè)程序中n前一個(gè)是編譯器，它把源程序翻譯成一種叫做字節(jié)碼的中間語(yǔ)言程序n后一個(gè)叫做解釋器，它對(duì)字節(jié)碼程序進(jìn)行解釋執(zhí)行源程序如何成為可執(zhí)行程序？n除編譯器外，源程序要想成為可執(zhí)行程序還需要經(jīng)過(guò)下列一些程序的處理：n預(yù)處理器（preprocessor）：先于編譯器執(zhí)行，負(fù)責(zé)收集處于不同文件中的源程序，處理宏等等。n匯編器（assembler）：如果編譯器的目標(biāo)程序不是機(jī)器語(yǔ)言程序而是匯編程序，則

8、需要匯編器將匯編語(yǔ)言程序翻譯成可重定位的機(jī)器語(yǔ)言程序。n鏈接器和裝載器（linker & loader）：鏈接器負(fù)責(zé)將處于不同模塊的可重定位機(jī)器語(yǔ)言程序以及庫(kù)文件等鏈接在一起。裝載器負(fù)責(zé)把鏈接后的程序裝入內(nèi)存準(zhǔn)備執(zhí)行。源程序預(yù)處理器編譯器匯編器鏈接/裝載器經(jīng)過(guò)修改的源程序目標(biāo)匯編程序可重定位的機(jī)器程序目標(biāo)機(jī)器程序關(guān)于交叉編譯源程序P目標(biāo)程序P編譯器C運(yùn)行系統(tǒng)原始數(shù)據(jù)D運(yùn)行結(jié)果S計(jì)算機(jī)A計(jì)算機(jī)B編譯階段運(yùn)行階段A,B是不同類型計(jì)算機(jī)為什么要學(xué)習(xí)編譯原理？n你們中的大部分人在今后的職業(yè)生涯中都不會(huì)去進(jìn)行編譯器的設(shè)計(jì)工作，但是學(xué)習(xí)編譯原理至少有下列一些好處：n能夠確切地知道你所編寫的程序是如

9、何從高級(jí)語(yǔ)言程序變成可執(zhí)行程序的，從而對(duì)編程有更深入的理解；進(jìn)而可以提高糾錯(cuò)能力和編寫高質(zhì)量代碼的能力。n編譯器設(shè)計(jì)中的一些原理和技術(shù)足以應(yīng)用到你今后職業(yè)生涯中的很多領(lǐng)域。例如，我們將涉及到編程語(yǔ)言、體系結(jié)構(gòu)、算法、語(yǔ)言理論、軟件工程等知識(shí)。1.1 編譯器概述n編譯器的工作可以分成若干邏輯階段，每個(gè)階段把源程序從一種表示方式變換成另一種表示方式。n一個(gè)典型的階段劃分如下：編譯器的劃分詞法分析器詞法分析器語(yǔ)法分析器語(yǔ)法分析器語(yǔ)義分析器語(yǔ)義分析器源程序源程序中間代碼生成器中間代碼生成器獨(dú)立于機(jī)器的代碼優(yōu)化器獨(dú)立于機(jī)器的代碼優(yōu)化器代碼生成器代碼生成器依賴于機(jī)器的代碼優(yōu)化器依賴于機(jī)器的代碼優(yōu)化器目標(biāo)機(jī)

10、器代碼目標(biāo)機(jī)器代碼符號(hào)表符號(hào)表1.1.1 詞法分析（lexical analysis）n詞法分析（又稱線性分析或掃描scanning）： 字符流 記號(hào)流（token）n記號(hào)： 二元組詞法規(guī)則共用名稱，表示類別詞法單元的專屬特征值1.1.1 詞法分析（續(xù)）n詞法分析將在課本第二章詳細(xì)介紹。n下面以一個(gè)例子來(lái)說(shuō)明詞法分析階段是如何將字符流轉(zhuǎn)換成記號(hào)流的：n源程序字符流：position = initial + rate * 601.1.1 詞法分析（續(xù)）符 號(hào) 表 positioninitialrate. . . . . . .123詞法分析器 position = initial + rate

11、* 60標(biāo)識(shí)符的總稱position在符號(hào)表中的條目只有一個(gè)實(shí)例，因而省略屬性值本應(yīng)為，簡(jiǎn)化1.1.2 語(yǔ)法分析（parsing）n語(yǔ)法分析（syntax analysis），簡(jiǎn)稱分析（parsing）。 記號(hào)流 樹(shù)型抽象中間表示n語(yǔ)法分析按編程語(yǔ)言的語(yǔ)法規(guī)則檢查記號(hào)流是否滿足這些規(guī)則，從而根據(jù)這些規(guī)則展示各種語(yǔ)言“構(gòu)造”（construct，如函數(shù)、語(yǔ)句、表達(dá)式等）的層次性。語(yǔ)法規(guī)則表達(dá)式的語(yǔ)法規(guī)則n任何一個(gè)標(biāo)識(shí)符都是表達(dá)式n任何一個(gè)數(shù)都是表達(dá)式n如果e1和e2都是表達(dá)式，那么 e1 + e2 e1 * e2 (e1)也都是表達(dá)式表達(dá)式表達(dá)式表達(dá)式表達(dá)式表達(dá)式表達(dá)式標(biāo)識(shí)符標(biāo)識(shí)符表達(dá)式表達(dá)式表

12、達(dá)式表達(dá)式(initial)標(biāo)識(shí)符標(biāo)識(shí)符(rate)數(shù)數(shù)(60)*+initial + rate * * 60的的分析樹(shù)分析樹(shù)1.1.2 語(yǔ)法分析（續(xù)）1.1.2 語(yǔ)法分析（續(xù)）n語(yǔ)法分析中使用的語(yǔ)法規(guī)則可以用上下文無(wú)關(guān)文法CFG（Context-Free Grammars）或Backus-Naur范式（BNF）來(lái)描述。n課本第三章介紹上下文無(wú)關(guān)文法和語(yǔ)法分析。n典型的中間表示是語(yǔ)法樹(shù)1.1.2 語(yǔ)法分析（續(xù)）符 號(hào) 表 positioninitialrate. . . . . . .123語(yǔ)法分析器 語(yǔ)法樹(shù)1.1.3 語(yǔ)義分析n語(yǔ)義分析：分析語(yǔ)法結(jié)構(gòu)的含義和功能；檢查程序語(yǔ)義一致性；為代碼生

13、成階段收集信息。n語(yǔ)義分析的一個(gè)重要部分是類型檢查。n類型是否合法：例，數(shù)組下標(biāo)為整數(shù)（浮點(diǎn)數(shù)）n隱式類型轉(zhuǎn)換（coercion）n目前較流行的是使用“語(yǔ)法制導(dǎo)翻譯”的方法將語(yǔ)法分析和語(yǔ)義分析有機(jī)地組織起來(lái)。n課本第四章介紹語(yǔ)法制導(dǎo)翻譯，第五章介紹類型檢查。1.1.3 語(yǔ)義分析（續(xù)）語(yǔ)義分析器符 號(hào) 表 positioninitialrate. . . . . . .1231.1.4 中間代碼生成n在對(duì)源程序進(jìn)行過(guò)語(yǔ)法和語(yǔ)義分析之后，很多編譯器會(huì)顯式的生成一種比較低級(jí)的中間表示，即中間代碼。n中間表示必須具備特點(diǎn)：n易于產(chǎn)生。n易于翻譯成目標(biāo)程序。1.1.4 中間代碼生成n中間表示有多種形式：

14、逆波蘭表示（后綴表示）、三地址碼（三元式、四元式等）、樹(shù)型結(jié)構(gòu)等。nposition = initial + rate * 60的逆波蘭表示為： position initial rate 60 * + =n一種很常用的中間表示是三地址碼。1.1.4 中間代碼生成（續(xù)）中間代碼生成器t1 = inttofloat(60)t2 = id3 * t1t3 = id2 + t2id1 = t3符 號(hào) 表 positioninitialrate. . . . . . .123特點(diǎn)： 必須先決定運(yùn)算次序 臨時(shí)變量 不一定有三個(gè)運(yùn)算對(duì)象1.1.4 中間代碼生成（續(xù)）n中間代碼的產(chǎn)生與語(yǔ)義分析緊密相連，課本

15、在第七章介紹中間代碼生成。1.1.5 代碼優(yōu)化n為了產(chǎn)生質(zhì)量較高的目標(biāo)代碼，通常在中間代碼生成和目標(biāo)代碼生成兩個(gè)階段之間，插入一個(gè)代碼優(yōu)化階段。n質(zhì)量較高的目標(biāo)代碼：通常指執(zhí)行較快，但也可能指目標(biāo)代碼較短或執(zhí)行時(shí)能耗較低。1.1.5 代碼優(yōu)化（續(xù)）代碼優(yōu)化器t1 = id3 * 60.0id1 = id2 + t1t1 = inttofloat(60)t2 = id3 * t1t3 = id2 + t2id1 = t3符 號(hào) 表 positioninitialrate. . . . . . .1231.1.5 代碼優(yōu)化（續(xù)）n能夠完成大多數(shù)優(yōu)化的編譯器叫做“優(yōu)化編譯器”。（編譯時(shí)空復(fù)雜度增加，

16、可靠性下降）n簡(jiǎn)單優(yōu)化也可使目標(biāo)程序運(yùn)行時(shí)間大大縮短，而編譯速度并未降低太多。n優(yōu)化在課本第九、十章介紹，不作為本課程授課內(nèi)容。1.1.6 目標(biāo)代碼生成n代碼生成階段：由中間代碼生成目標(biāo)代碼（機(jī)器指令或匯編碼）n目標(biāo)代碼生成階段所做的工作：n為變量選擇存儲(chǔ)單元n把中間代碼翻譯成等價(jià)的機(jī)器指令序列。n此階段的關(guān)鍵問(wèn)題是：寄存器分配n代碼生成主要在課本第八章介紹，不作為本課程主要授課內(nèi)容。1.1.6 目標(biāo)代碼生成（續(xù)）代碼生成器t1 = id3 * 60.0id1 = id2 + t1MOVF id3, R2MULF #60.0, R2MOVF id2, R1ADDF R2, R1MOVF R1,

17、 id1符 號(hào) 表 positioninitialrate. . . . . . .1231.1.7 符號(hào)表管理n編譯器的一項(xiàng)重要工作是記錄并收集標(biāo)識(shí)符及其各種屬性，以提供標(biāo)識(shí)符存儲(chǔ)分配、類型、作用域等信息。n符號(hào)表為每個(gè)標(biāo)識(shí)符保存一個(gè)記錄數(shù)據(jù)結(jié)構(gòu)，其中的域是標(biāo)識(shí)符的各個(gè)屬性。n該數(shù)據(jù)結(jié)構(gòu)應(yīng)允許編譯器迅速找到一個(gè)名字的記錄并讀取和存儲(chǔ)數(shù)據(jù)。1.1.7 符號(hào)表管理（續(xù)）n符號(hào)表將在課本第七章討論。符 號(hào) 表 positioninitialrate. . . . . . .1231.1.8 階段的分組n以上將編譯器從邏輯上分成7個(gè)階段：n前四階段完成對(duì)源程序的分析，它們與源語(yǔ)言密切相關(guān)，因此也稱為

18、前端（front-end）n后三階段完成對(duì)源程序的綜合，由于與目標(biāo)機(jī)器更相關(guān)，故也稱后端（back-end）階段的分組詞法分析器詞法分析器語(yǔ)法分析器語(yǔ)法分析器語(yǔ)義分析器語(yǔ)義分析器源程序源程序中間代碼生成器中間代碼生成器獨(dú)立于機(jī)器的代碼優(yōu)化器獨(dú)立于機(jī)器的代碼優(yōu)化器代碼生成器代碼生成器依賴于機(jī)器的代碼優(yōu)化器依賴于機(jī)器的代碼優(yōu)化器目標(biāo)機(jī)器代碼目標(biāo)機(jī)器代碼符號(hào)表符號(hào)表 前端（front-end）分析 后端（back-end）綜合1.1.8 階段的分組（續(xù)）n編譯器劃分前端后端有利于移植C前端Pascal前端中間代碼后端（Intel X86）1.1.8 階段的分組（續(xù)）n編譯器劃分前端后端有利于移植C前

19、端中間代碼后端（Intel X86）后端（MIPS）1.1.8 階段的分組（續(xù)）n在編譯器實(shí)現(xiàn)時(shí)，幾個(gè)階段的活動(dòng)可能被組合起來(lái)形成一“遍”（pass）n每一“遍”都會(huì)讀一個(gè)輸入文件（例如源程序或源程序的中間表示），并寫一個(gè)輸出文件。n例：前端的四個(gè)階段：詞法分析、語(yǔ)法分析、語(yǔ)義分析、中間代碼生成可以組合形成一“遍”。n例：代碼優(yōu)化可以進(jìn)行很多“遍”。1.1.8 階段的分組（續(xù)）n現(xiàn)代高級(jí)語(yǔ)言大都不能通過(guò)一遍掃描就完成從源程序到目標(biāo)代碼的轉(zhuǎn)換，因此一般都需要多遍掃描。1.2 編譯器技術(shù)的應(yīng)用n請(qǐng)自行看課本了解。1.2 編譯器技術(shù)的應(yīng)用 n高級(jí)語(yǔ)言的實(shí)現(xiàn)n高級(jí)編程語(yǔ)言易于編程，但程序運(yùn)行較慢n低級(jí)

20、語(yǔ)言編程時(shí)可實(shí)施更有效的控制方式，得到更有效的代碼，但難編寫、易出錯(cuò)、難維護(hù)n流行編程語(yǔ)言的大多數(shù)演變都是朝著提高抽象級(jí)別的方向n每一輪編程語(yǔ)言新特征的出現(xiàn)都刺激編譯器優(yōu)化的新研究1.2 編譯器技術(shù)的應(yīng)用 n每一輪編程語(yǔ)言新特征的出現(xiàn)都刺激編譯器優(yōu)化的新研究：n支持用戶定義的聚合數(shù)據(jù)類型和高級(jí)控制流，如數(shù)組和記錄、循環(huán)和過(guò)程調(diào)用：C、Fortrann面向?qū)ο蟮闹饕拍钍菙?shù)據(jù)抽象和性質(zhì)繼承，使得程序更加模塊化并易于維護(hù)：Smalltalk、C+、C#、Javan類型安全的語(yǔ)言：Java沒(méi)有指針，也不允許指針?biāo)阈g(shù)。它用無(wú)用單元收集機(jī)制來(lái)自動(dòng)地釋放那些不再使用的變量占據(jù)的內(nèi)存nJava設(shè)計(jì)來(lái)支持代碼

21、移植和代碼移動(dòng)1.2 編譯器技術(shù)的應(yīng)用 n針對(duì)計(jì)算機(jī)體系結(jié)構(gòu)的優(yōu)化n計(jì)算機(jī)體系結(jié)構(gòu)的迅速演化引起對(duì)新的編譯器技術(shù)一種不知足的需要n并行化n編譯器重新整理指令，使得指令級(jí)并行更有效n編譯器從傳統(tǒng)的串行程序自動(dòng)生成并行代碼，使之運(yùn)行于多處理器上n內(nèi)存分層n編譯器優(yōu)化歷來(lái)集中在優(yōu)化處理器的執(zhí)行上，但是現(xiàn)在更強(qiáng)調(diào)要使內(nèi)存分層更有效1.2 編譯器技術(shù)的應(yīng)用 n新計(jì)算機(jī)體系結(jié)構(gòu)的設(shè)計(jì)n現(xiàn)在計(jì)算機(jī)系統(tǒng)的性能不僅僅取決于它的原始速度，還取決于編譯器是否能生成充分利用其特征的代碼n在現(xiàn)代計(jì)算機(jī)體系結(jié)構(gòu)的研究中，在處理器的設(shè)計(jì)階段就開(kāi)發(fā)編譯器，并將編譯生成的代碼在模擬器上運(yùn)行，以評(píng)價(jià)擬采用體系結(jié)構(gòu)的特征n編譯器技術(shù)影響計(jì)算機(jī)體系結(jié)構(gòu)設(shè)計(jì)的一個(gè)著名例子是精簡(jiǎn)指令集計(jì)算機(jī)（RISC）的發(fā)明1.2 編譯器技術(shù)的應(yīng)用 n程序翻譯n二進(jìn)制翻譯 編譯器技術(shù)可用于把一種機(jī)器的二進(jìn)制代碼翻譯成另一種機(jī)器的代碼，以運(yùn)行原先為別的指令集編譯的代碼n數(shù)據(jù)庫(kù)查詢解釋器 數(shù)據(jù)庫(kù)查詢由一些謂詞組成，這些謂詞由包含關(guān)系運(yùn)算的布爾表達(dá)式組成，可以被解釋執(zhí)行,也可以被編譯成搜索數(shù)據(jù)庫(kù)的命令1.2 編譯器技術(shù)的應(yīng)用 n提高軟件開(kāi)發(fā)效率的工具 源于編譯器中代碼優(yōu)化技術(shù)的程序分析一直在改進(jìn)軟件開(kāi)發(fā)效率n類型檢查：類型檢查是一種捕捉程序中前后不一致的成熟而有效的技術(shù)n邊界檢查：數(shù)據(jù)流分析技術(shù)可用來(lái)定位緩沖區(qū)溢出n內(nèi)存管理：自動(dòng)的內(nèi)存管理