編譯原理：第一章編譯程序概論

第一章編譯程序概論學(xué)習(xí)目標：掌握：編譯的各個階段理解：編譯程序的概念了解：解釋器，編譯程序的結(jié)構(gòu)和組合1.1 什么是編譯程序1.2 編譯過程概述1.3 編譯程序的結(jié)構(gòu)1.4 編譯階段的組合1.5 編譯技術(shù)和軟件工具1.1

什么是編譯程序編譯程序（compiler） 將用高級語言（如FORTRAN,PASCAL或C）書寫的程序翻譯成等價的低級語言程序（如匯編語言或機器語言），這種翻譯程序稱為編譯程序(compiler)。

1.1

什么是編譯程序編譯程序（compiler）

編譯程序的輸入對象稱為源程序(Sourceprogram)

輸出對象稱為目標程序（TargetorObjectprogram）高級語言程序編譯程序低級語言程序解釋器(interpreter)與編譯器共同點：都是語言的一個實現(xiàn)系統(tǒng)不同點：解釋器是源程序的一個執(zhí)行系統(tǒng)，工作結(jié)果得到源程序的執(zhí)行結(jié)果；編譯器是源程序的轉(zhuǎn)換系統(tǒng)，工作結(jié)果得到等價于源程序的某種目標程序解釋程序解釋器和編譯器編譯程序源程序源程序數(shù)據(jù)計算結(jié)果目標程序解釋器與編譯器解釋器與編譯器需預(yù)處理的源程序預(yù)處理程序源程序編譯程序目標匯編程序匯編程序可再裝配的機器代碼裝配/連接--編輯程序絕對機器代碼可再裝配目標文件高級語言程序的處理過程需預(yù)處理的源程序預(yù)處理程序源程序編譯程序目標匯編程序匯編程序可再裝配的機器代碼裝配/連接--編輯程序絕對機器代碼可再裝配目標文件高級語言程序的處理過程預(yù)處理程序編譯程序：目標匯編程序編譯程序的發(fā)展20世紀50年代中期，第一個編譯器——FORTARN語言編譯器開發(fā)出來隨著文法出現(xiàn)，20世紀50年代末，開始研究編譯程序的自動生成工具20世紀60年代，研究使用自展技術(shù)20世紀70年代，開發(fā)出目前仍廣泛使用的自動生成工具，lex和Yacc并行編譯技術(shù)1.2編譯程序概述一個編譯程序的整個工作過程是劃分成階段進行的，每個階段將源程序從一種表示形式轉(zhuǎn)換成另一種表示形式。典型的劃分方法：目標程序源程序詞法分析語法分析語義分析中間代碼生成代碼優(yōu)化目標代碼生成表格管理出錯處理編譯的各個階段1詞法分析(lexicalanalysis)任務(wù):從左到右一個字符一個字符地讀入源程序，對構(gòu)成源程序的字符流進行掃描和分解，從而識別出一個個單詞(Token)。邏輯上緊密相連的一組字符，這些字符具有集體含義。單詞：標識符，保留字，算符，界符等例:源程序片斷

beginvarsum,first,count:real;

sum:=first+count*10

end.

r0u;;stliafe,rt:nmuus△acro△v,nigebs*1tnuoct+sirf=:m.

nde

源程序在文件中的表示

(保留字,real)(標識符,first)(冒號,:)(逗號,,)(標識符,count)(分號,;)(保留字,var)(逗號,,)(標識符,sum)(保留字,begin)(賦值號,:=)(乘號,*)(加號,+)(標識符,count)(標識符,first)(標識符,sum)(界符,.)(整數(shù),10)(保留字,end)詞法分析后程序的圖形表示空格換行字符的內(nèi)部表示即ASCII碼單詞表示成二元式（單詞的種別，單詞自身值）2語法分析(syntaxanalysis)任務(wù)單詞符號串(Token串)語法分析語法短語識別規(guī)則：語法規(guī)則(描述程序結(jié)構(gòu)的規(guī)則,通常是由遞歸規(guī)則表示的)注:語法短語又稱語法單位，如“表達式”、“語句”、“分程序”、“程序”等，可以被表示成語法樹結(jié)果:判斷輸入串是否構(gòu)成一個語法上正確的程序,并生成語法樹例:賦值語句sum:=first+count*10

賦值語句規(guī)則<賦值語句>::=<標識符>“:=”<表達式><表達式>::=<表達式>“+”<表達式><表達式>::=<表達式>“*”<表達式><表達式>::=“(”<表達式>“)”<表達式>::=<標識符><表達式>::=<整數(shù)><表達式>::=<實數(shù)>sum賦值語句標識符:=表達式表達式+表達式標識符first表達式*表達式標識符count整數(shù)10語法樹為:3語義分析(semanticanalysis)語義： 程序的語義就是它的意思，決定了程序的運行行為靜態(tài)語義：程序設(shè)計語言某些性質(zhì)可以在運行之前確定，這些特性是靜態(tài)語義動態(tài)語義：只有在運行的時候才能確定的性質(zhì)是動態(tài)語義任務(wù):

審查源程序是否有靜態(tài)語義錯誤，為代碼生成階段收集類型信息靜態(tài)語義包括：聲明的上下文相關(guān)性類型檢查：每個算符是否具有語言規(guī)范允許的運算對象例：programp()varrate:real;procedureinitial;…position := initial + rate*60/*error*//*error*//*warning*/例源程序：Sum:=first+count*10

count是實型,10是整型,語義分析后得到新語法樹為:賦值語句標識符:=表達式sum表達式+表達式標識符first表達式*表達式標識符count實數(shù)10inttoreal4中間代碼生成

(intermediatecodegeneration)任務(wù)：將源程序生成一種內(nèi)部表示形式，這種內(nèi)部表示形式叫中間代碼。中間代碼：結(jié)構(gòu)簡單、含義明確，容易生成并且容易將它翻譯成目標代碼四元式中間代碼: (運算符，運算對象1，運算對象2，結(jié)果)例如：將Sum:=first+count*10翻譯成四元式

(1) (inttoreal10-T1) (2) (*countT1T2) (3) (+firstT2T3) (4) (:=T3-sum)5代碼優(yōu)化(codeoptimization)任務(wù)：對中間代碼進行等價變換，以便使生成的目標代碼更為高效，即省時間和省空間。舉例:

(1) (inttoreal10-T1) (2) (*countT1T2) (3) (+firstT2T3)

(4) (:=T3-sum)

簡化后: (*count10.0T1) (+firstT1sum)6目標代碼生成(codegeneration)任務(wù)：把中間代碼變換成特定機器上的絕對指令代碼或可重定位的指令代碼或匯編指令代碼,它的工作與硬件系統(tǒng)和指令含義有關(guān).例如: (*count10.0T1) (+firstT1sum)

生成匯編代碼如下: MOVFcount,R2 MULF#10.0,R2 MOVFfirst,R1 ADDFR1,R2 MOVR1,sum7表格管理和出錯處理出錯處理：編譯過程中，發(fā)現(xiàn)源程序有錯誤（詞法錯誤、語法錯誤、語義錯誤），編譯程序應(yīng)報告錯誤的性質(zhì)和出錯的地點，并將錯誤所造成的影響限制在盡可能小的范圍內(nèi)，使得源程序的其余部分繼續(xù)被編譯下去。這些工作稱為出錯處理(errorhandling)。編譯過程中源程序的各種信息被保留在種種不同的表格里，編譯各階段的工作涉及到構(gòu)造、查找或更新有關(guān)的表格，因此需要有表格管理工作。1.3編譯程序的結(jié)構(gòu)源程序詞法分析程序語法分析程序語義分析程序中間代碼生成程序代碼優(yōu)化程序目標代碼生成程序表格管理程序出錯處理程序目標程序1.4編譯階段的組合

編譯階段可以從不同的角度來組合：組合方式不同對編譯程序的可靠性、有效性、可用性、可維護性都有影響分析與綜合(analysisandsynthesis)分析階段：詞法分析、語法分析、語義分析，只對程序進行識別和檢查，沒作實質(zhì)翻譯綜合階段：中間代碼的生成，代碼優(yōu)化，目標代碼生成，對源程序進行翻譯，生成目標代碼前端與后端（frontendandbackend）前端(依賴于源語言而與目標機無關(guān))：詞法分析、語法分析、語義分析和中間代碼的生成，中間代碼優(yōu)化;后端(依賴于目標機而一般不依賴源語言)：目標代碼生成;編譯過程的實現(xiàn)：一個編譯過程可以由一遍、兩遍或多遍完成遍(pass)

:對源程序或中間語言程序從頭到尾掃描并完成規(guī)定任務(wù)的過程。一遍的編譯器是通過一遍掃描直接從源程序生成出目標代碼，而多遍的編譯器則通過多遍掃描產(chǎn)生目標代碼。比如第一遍進行詞法分析、語法分析、中間代碼生成和中間代碼優(yōu)化，而第二遍掃描則從中間代碼產(chǎn)生目標代碼影響分遍的因素：源語言結(jié)構(gòu)，目標機資源1.5編譯技術(shù)和軟件工具軟件工具的開發(fā)常用到編譯技術(shù)和方法語言的結(jié)構(gòu)化編輯器(structurebasededitor)

引導(dǎo)用戶在語言的語法制導(dǎo)下編制程序，與語法分析有關(guān)語言程序的調(diào)試工具(debugger)

調(diào)試工具幫助編程人員檢查程序的算法和運行結(jié)果是否符合愿意，與語法分析和語義處理關(guān)系密切。語言程序的測試工具 靜態(tài)分析器：檢查變量的