編譯原理基本知識

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

2、目標程序，這種翻譯過程稱編譯（Compile）。源程由T值譯程序.目標程序匯編語言T匯編程序T機器語言高級語言T編譯程序T目標程序的源程序程序源程序編譯程序編程序編程序的器編程序v編譯器編譯器就是一個程序，它讀入用某種語言編寫的源程序，并翻譯成一個與之等價的另一種語言編寫的源程序。編譯過程是指將高級語言程序翻譯為等價的目標程序的過程。其一般包含5個基本階段：暫析宜盤析語義分析一呼中間代碼罐I化詞法分析任務(wù)：分析和識別單詞。描述：源程序是由字符序列構(gòu)成的，詞法分析掃描源程序（字符串），根據(jù)語言的詞法規(guī)則分析并識別單詞，并以某種編碼形式輸出。方法：詞法分析依照詞法規(guī)則，識別出正確的單詞，轉(zhuǎn)換成統(tǒng)一

3、規(guī)格備用。轉(zhuǎn)換：對基本字，運算符，界符的轉(zhuǎn)換標識符的轉(zhuǎn)換常數(shù)的轉(zhuǎn)換轉(zhuǎn)換完成后的格式（類號，內(nèi)碼）工具：正規(guī)式和有限自動機例子1：X1:=(2.0+0.8)*C1123456789例子2：Voidjisuan()inty,c,d;floatx,a,b;x=a+b*50;y=c+d*（x+b）;基本字：Void,int,float標識符：a,b,c,d,x,y,jisuan常數(shù)：50運算符：*,+,=,-界限符：；,（）例子3：position=initial+rate*60第一步：識別出單詞（關(guān)鍵字、標識符、常數(shù)、算符和界符）。position、=、initial、+、rate、*、60第二步：

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

5、：id1=id2+id3*60Num|60Num|60語法樹數(shù)據(jù)結(jié)構(gòu)語義分析與生成中間代碼任務(wù)：對識別出的各種語法成分進行語義分析，并產(chǎn)生相應(yīng)的中間代碼。主要工作包含（1）完成靜態(tài)語義審查和處理；（2）上下文相關(guān)性審查；（3）類型匹配審查；（4）類型轉(zhuǎn)換。中間代碼：一種介于源語言和目標語言之間的中間語言形式。編譯程序設(shè)計者可以自己設(shè)計，常用的有四元式、三元式、逆波蘭表示等。四元式：四元式實際上是一種三地址語句的等價表示。它的一般形式為：（op,arg1,arg2,result）其中，op為一個二元（也可是一元或零元）運算符；arg1,arg2分別為它的兩個運算(或操作)對象，它們可以是變量、常

6、數(shù)或系統(tǒng)定義的臨時變量名；運算的結(jié)果將放入result中。四元式還可寫為類似于PASCAL語言賦值語句的形式：result:=argloparg2。例子1：position=initial+rate*60語義分析器例子2：語義分析器例子2：X1:=(2.0+0.8)*C1運算符左運算對象右運算對象結(jié)果+2.00.8T1*T1C1T2:=X1T2其中T1和T2為編譯程序引入的工作單元四元式的語義為：2.0+0.8-T1T1*C1-T2T2一X1這樣所生成的四元式與原來的賦值語句在語言的形式上不同，但語義上等價。目標代碼優(yōu)化任務(wù)：目的是為了得到高質(zhì)量的目標程序。例子1：目的是為了得到高質(zhì)量的目標程

7、序。優(yōu)化前：（1）2.0+0.8-T1T1*C1-T2T2-X1前面的四元式中第一個四元式是計算常量表達式值，該值在編譯時就可以算出并存放在工作單元中，不必生成目標指令來計算，這樣四元式可優(yōu)化為：+0.8tT1*T1C1T2:=X1T2目標代碼生成任務(wù)：把中間代碼變換成特定機器上的低級語言代碼。目標代碼形式：一絕對指令代碼一匯編指令代碼一可重定位的指令代碼。編譯的最后階段，它的工作與硬件系統(tǒng)結(jié)構(gòu)和指令定義有關(guān)，這個階段的工作很復(fù)雜，涉及到硬件系統(tǒng)功能部件的運用、機器指令的選擇、各種數(shù)據(jù)類型變量的存儲空間分配以及寄存器和后緩寄存器的調(diào)度等。由中間代碼很容易生成目標程序（地址指令序列）。這部分工作

8、與機器關(guān)系密切，所以要根據(jù)機器進行。在做這部分工作時（要注意充分利用累加器），也可以進行優(yōu)化處理。例子1：X1:=（2.0+0.8）*C1LOAD2.0ADD0.8STOT1LOADTiMULClLOAD2.0STOT2利用累ADD0,8LOADT2加器的優(yōu)化MULClSTOXIASTOXI注意：在翻譯成目標程序的過程中，要切記保持語義的等價性。例子2：position=initial+rate*60tempi：=id3*60.0idl：=id2+tempi代碼生成器MOVFid3,R2MULF#60。R2MOVFid2,RIADbFR2.RIMOVFRI,idl注：寄存器（R1和R2）編譯程序的邏輯結(jié)構(gòu)按邏輯功能不同，可將編譯過程劃分為五個基本階段，與此相對應(yīng)，我們將實現(xiàn)整個編譯過程的編譯程序劃分為五個邏輯階段（即五個邏