編譯原理基本知識

1、編譯原理基本知識l 基本概念n 程序生成過程n 源程序-用匯編語言或高級語言編寫的程序稱為源程序。 n 目標(biāo)程序-用目標(biāo)語言所表示的程序。可以是介于源語言和機(jī)器語言之間的“中間語言”，可以是某種機(jī)器的機(jī)器語言,也可以是某機(jī)器的匯編語言。n 翻譯程序-將源程序轉(zhuǎn)換為目標(biāo)程序的程序稱為翻譯程序。它是指各種語言的翻譯器，包括匯編程序和編譯程序，是匯編程序、編譯程序以及各種變換程序的總稱。l 診斷編譯程序l 優(yōu)化編譯程序l 交叉編譯程序l 可變目標(biāo)編譯程序匯編程序：若源程序用匯編語言書寫，經(jīng)過翻譯程序得到用機(jī)器語言表示的程序，這時(shí)的翻譯程序就稱之為匯編程序，這種翻譯過程稱為“匯編”(Assemble）

2、。編譯程序：若源程序是用高級語言書寫，經(jīng)加工后得到目標(biāo)程序，這種翻譯過程稱“編譯”（Compile)。n 編譯器編譯器就是一個(gè)程序，它讀入用某種語言編寫的源程序，并翻譯成一個(gè)與之等價(jià)的另一種語言編寫的源程序。l 編譯過程的基本階段編譯過程是指將高級語言程序翻譯為等價(jià)的目標(biāo)程序的過程。其一般包含5個(gè)基本階段：n 詞法分析任務(wù)：分析和識別單詞。描述：源程序是由字符序列構(gòu)成的，詞法分析掃描源程序(字符串)，根據(jù)語言的詞法規(guī)則分析并識別單詞，并以某種編碼形式輸出。方法：詞法分析依照詞法規(guī)則，識別出正確的單詞，轉(zhuǎn)換成統(tǒng)一規(guī)格備用。轉(zhuǎn)換： 對基本字，運(yùn)算符，界符的轉(zhuǎn)換 標(biāo)識符的轉(zhuǎn)換 常數(shù)的轉(zhuǎn)換 轉(zhuǎn)換完成后

3、的格式（類號，內(nèi)碼）工具：正規(guī)式和有限自動(dòng)機(jī)例子1：X1 := ( 2.0 + 0.8 ) * C11 2 3 4 5 6 7 8 9例子2：Void jisuan( ) int y, c, d;float x, a, b;x = a + b * 50;y = c + d * ( x + b);基本字：Void,int,float標(biāo)識符：a,b,c,d,x,y,jisuan常數(shù)：50運(yùn)算符：*,+,=,-界限符： ; , ( )例子3：position = initial + rate * 60第一步：識別出單詞（關(guān)鍵字、標(biāo)識符、常數(shù)、算符和界符）。position、=、initial、+ 、

4、rate、*、60第二步：并用記號表示識別出的單詞（記號表示邏輯上相關(guān)的字符序列，常用整數(shù)來表示）。id1、id2、id3表示position、initial、rate第三步：輸出結(jié)果（得到記號流）。id1 = id2 + id3 * 60n 語法分析任務(wù)：根據(jù)語法規(guī)則（即語言的文法），分析并識別出各種語法成分，如表達(dá)式、各種說明、各種語句、過程、函數(shù)等，并進(jìn)行語法正確性檢查。方法：推導(dǎo)（derive)和歸約（reduce)。過程：具體地說，語法分析是在記號流的基礎(chǔ)上建立一個(gè)層次結(jié)構(gòu)建立語法樹。例子1：X1:= ( 2.0 + 0.8 ) * C1賦值語句的文法：<賦值語句><

5、;變量><賦值操作符><表達(dá)式> <變量><簡單標(biāo)識符> <賦值操作符>:= <表達(dá)式> 例子2：id1 = id2 + id3 * 60語法樹 數(shù)據(jù)結(jié)構(gòu)n 語義分析與生成中間代碼任務(wù)：對識別出的各種語法成分進(jìn)行語義分析，并產(chǎn)生相應(yīng)的中間代碼。主要工作包含（1）完成靜態(tài)語義審查和處理；（2）上下文相關(guān)性審查；（3）類型匹配審查；（4）類型轉(zhuǎn)換。中間代碼：一種介于源語言和目標(biāo)語言之間的中間語言形式。編譯程序設(shè)計(jì)者可以自己設(shè)計(jì)，常用的有四元式、三元式、逆波蘭表示等。四元式：四元式實(shí)際上是一種“三地址語句”的等價(jià)表示。它的

6、一般形式為：(op,arg1,arg2,result)其中，op為一個(gè)二元 (也可是一元或零元)運(yùn)算符；arg1,arg2分別為它的兩個(gè)運(yùn)算 (或操作)對象，它們可以是變量、常數(shù)或系統(tǒng)定義的臨時(shí)變量名；運(yùn)算的結(jié)果將放入result中。四元式還可寫為類似于PASCAL語言賦值語句的形式：result = arg1 op arg2。例子1：position = initial + rate * 60例子2：X1:= ( 2.0 + 0.8 ) * C1 運(yùn)算符 左運(yùn)算對象 右運(yùn)算對象 結(jié)果 (1) + 2.0 0.8 T1(2) * T1 C1 T2(3) := X1 T2 其中T1和T2為編譯程

7、序引入的工作單元四元式的語義為： 2.0 + 0.8 T1 T1 * C1 T2 T2 X1這樣所生成的四元式與原來的賦值語句在語言的形式上不同，但語義上等價(jià)。n 目標(biāo)代碼優(yōu)化任務(wù)：目的是為了得到高質(zhì)量的目標(biāo)程序。例子1：目的是為了得到高質(zhì)量的目標(biāo)程序。 優(yōu)化前：（1）2.0 + 0.8 T1 （2）T1 * C1 T2 （3）T2 X1前面的四元式中第一個(gè)四元式是計(jì)算常量表達(dá)式值，該值在編譯時(shí)就可以算出并存放在工作單元中，不必生成目標(biāo)指令來計(jì)算，這樣四元式可優(yōu)化為：2.0 + 0.8 T1 （1) * T1C1 T2 （2) := X1T2n 目標(biāo)代碼生成任務(wù)：把中間代碼變換成特定機(jī)器上的低級語言代碼。目標(biāo)代碼形式：絕對指令代碼匯編指令代碼可重定位的指令代碼。編譯的最后階段，它的工作與硬件系統(tǒng)結(jié)構(gòu)和指令定義有關(guān)，這個(gè)階段的工作很復(fù)雜，涉及到硬件系統(tǒng)功能部件的運(yùn)用、機(jī)器指令的選擇、各種數(shù)據(jù)類型變量的存儲空間分配以及寄存器和后緩寄存器的調(diào)度等。由中間代碼很容易生成目標(biāo)程序（地址指令序列）。這部分工作與機(jī)器關(guān)系密切 ，所以要根據(jù)機(jī)器進(jìn)行。在做這部分工作時(shí)（要注意充分利用累加器），也可以進(jìn)行優(yōu)化處理。例子1：X1 := ( 2.0 + 0.8 ) * C1注意：在翻譯成目標(biāo)程序的過程中，要切記保持語義的等價(jià)性。例子2：position = i