編譯原理基本知識

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

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

3、的格式（類號，內碼）工具：正規(guī)式和有限自動機例子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標識符：a,b,c,d,x,y,jisuan常數：50運算符：*,+,=,-界限符： ; , ( )例子3：position = initial + rate * 60第一步：識別出單詞（關鍵字、標識符、常數、算符和界符）。position、=、initial、+ 、

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

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

6、一般形式為：(op,arg1,arg2,result)其中，op為一個二元 (也可是一元或零元)運算符；arg1,arg2分別為它的兩個運算 (或操作)對象，它們可以是變量、常數或系統(tǒng)定義的臨時變量名；運算的結果將放入result中。四元式還可寫為類似于PASCAL語言賦值語句的形式：result = arg1 op arg2。例子1：position = initial + rate * 60例子2：X1:= ( 2.0 + 0.8 ) * C1 運算符 左運算對象 右運算對象 結果 (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這樣所生成的四元式與原來的賦值語句在語言的形式上不同，但語義上等價。n 目標代碼優(yōu)化任務：目的是為了得到高質量的目標程序。例子1：目的是為了得到高質量的目標程序。 優(yōu)化前：（1）2.0 + 0.8 T1 （2）T1 * C1 T2 （3）T2 X1前面的四元式中第一個四元式是計算常量表達式值，該值在編譯時就可以算出并存放在工作單元中，不必生成目標指令來計算，這樣四元式可優(yōu)化為：2.0 + 0.8 T1 （1) * T1C1 T2 （2) := X1T2n 目標代碼生成任務：把中間代碼變換成特定機器上的低級語言代碼。目標代碼形式：絕對指令代碼匯編指令代碼可重定位的指令代碼。編譯的最后階段，它的工作與硬件系統(tǒng)結構和指令定義有關，這個階段的工作很復雜，涉及到硬件系統(tǒng)功能部件的運用、機器指令的選擇、各種數據類型變量的存儲空間分配以及寄存器和后緩寄存器的調度等。由中間代碼很容易生成目標程序（地址指令序列）。這部分工作與機器關系密切 ，所以要根據機器進行。在做這部分工作時（要注意充分利用累加器），也可以進行優(yōu)化處理。例子1：X1 := ( 2.0 + 0.8 ) * C1注意：在翻譯成目標程序的過程中，要切記保持語義的等價性。例子2：position = i