Part1編譯原理-引論(天津大學(xué))

編譯原理引論授課：胡靜2/4/20232004年12月28日1編譯原理教材及參考書教材：《程序設(shè)計語言編譯原理（第3版）》，國防工業(yè)出版社，陳火旺等編著主要參考資料編譯原理（CompilersPrinciples,Techniques,andTools）出版社：機械工業(yè)出版社《編譯原理》，清華大學(xué)出版社，呂映芝、張素琴、蔣維杜編著《編譯器工程》——《DesignaCompiler》，機械工業(yè)出版社，KeithD.Cooper、LindaTorczon著；馮速譯2/4/20232編譯原理相關(guān)課程課程基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)計算機原理和匯編語言高級程序設(shè)計語言后續(xù)課程編譯技術(shù)2/4/20233編譯原理第一章概論編譯的起源：程序設(shè)計語言的發(fā)展基本概念編譯過程和編譯程序的構(gòu)造2/4/20234編譯原理程序設(shè)計語言的發(fā)展2/4/20235編譯原理基本概念低級語言（LowlevelLanguage)字位碼、機器語言、匯編語言特點：與特定的機器有關(guān)，功效高，但使用復(fù)雜、繁瑣、費時、易出錯高級語言Fortran、Pascal、C語言等特點：不依賴具體機器，移植性好、對用戶要求低、易使用、易維護等。

2/4/20236編譯原理基本概念2/4/20237編譯原理基本概念2/4/20238編譯原理源程序的編譯和運行2/4/20239編譯原理源程序的解釋運行2/4/202310編譯原理源程序的編譯-解釋運行2/4/202311編譯原理編譯器和解釋器編譯器和解釋器的比較相同點（執(zhí)行相同的任務(wù)）:檢查輸入程序并確定這個程序是否一個有效程序建立一個內(nèi)部模型來刻畫輸入程序的結(jié)構(gòu)和含義決定在執(zhí)行期間值的存放位置不同點（執(zhí)行的行為不同）：編譯器以一個可執(zhí)行程序的描述作為輸入，以另一個等價的可執(zhí)行程序的描述作為輸出。解釋器以一個可執(zhí)行程序的描述作為輸入，以執(zhí)行這一可執(zhí)行程序描述的結(jié)果作為輸出。2/4/202312編譯原理舉例典型的編譯器：gcc,javac非典型的編譯器：latex(documentcompiler):TransformsaLaTeXdocumentintoDVIprintingcommandsInputinformation=document(notprogram)解釋器：f2c:Fortran-to-Ctranslator(bothhigh-level)latex2html:LaTeX-to-HTML(bothdocuments)2/4/202313編譯原理我們?yōu)槭裁葱枰幾g器編寫、調(diào)試、維護和理解用裝配語言(assemblelanguage)編寫的程序是很困難的自從第一個編譯器出現(xiàn)之后，軟件產(chǎn)品的數(shù)量有了巨大的增加。但是仍然有一些情況需要用裝配語言編寫例如，訪問某些底層的機器資源（設(shè)備驅(qū)動）這些代碼規(guī)模一般較小，還是需要編譯器去處理其他的應(yīng)用2/4/202314編譯原理編譯器構(gòu)造法的研究目的好的編譯器是計算機科學(xué)的縮影包含大量的技術(shù)：貪婪算法（寄存器分配）、啟發(fā)式搜索技術(shù)（列表調(diào)度）、圖形算法（死碼消除）、動態(tài)規(guī)劃（指令篩選）、有窮自動機和下推自動機（掃描和語法分析）、不動點算法（數(shù)據(jù)流分析）處理復(fù)雜的問題：動態(tài)分配、同步、命名、局部化、存儲器分層管理、管道調(diào)度提供完整的解決方案：有機的結(jié)合算法、軟件體系結(jié)構(gòu)和軟件工程的各種理論，對棘手問題給出綜合性的解答方案。2/4/202315編譯原理什么是編譯器什么是編譯程序預(yù)處理器編譯器匯編器裝配連接編輯骨架程序

源程序

目標匯編程序

可重定位機器代碼

絕對機器碼可重定位目標文件庫2/4/202316編譯原理源代碼符合人類閱讀習慣符合人類語法定義使用被命名的結(jié)構(gòu)，例如變量和過程2/4/202317編譯原理裝配語言機器代碼符合硬件需求包含機器指令，使用寄存器和沒有命名的內(nèi)存地址對人類來說很難理解2/4/202318編譯原理例子：輸出的裝配代碼沒有優(yōu)化的代碼優(yōu)化后的代碼2/4/202319編譯原理編譯器的基本原則編譯器是工程對象，是具有獨特目標的大型軟件系統(tǒng)，兩個設(shè)計原則必須遵守不違背原義編譯器必須保持被編譯程序的含義不變這一原則是編譯器設(shè)計者與編譯器用戶之間的契約的核心實用性原則編譯器必須用某種明確的方式改進輸入程序例如代碼優(yōu)化等對輸入程序的改進2/4/202320編譯原理有效的轉(zhuǎn)換目標：產(chǎn)生和源代碼描述相同計算的機器代碼這種轉(zhuǎn)換是唯一的嘛？有沒有“完美的轉(zhuǎn)換”（速度快，代碼量?。┚幾g器優(yōu)化=找到更好的轉(zhuǎn)換2/4/202321編譯原理轉(zhuǎn)換的正確性產(chǎn)生的代碼必須精確的執(zhí)行和源代碼相同的計算正確性很重要用不正確的編譯器調(diào)試程序很難……和開發(fā)的成本、安全性密切相關(guān)編譯原理這門課程講述的就是可以保證轉(zhuǎn)換安全性的技術(shù)。2/4/202322編譯原理如何轉(zhuǎn)換轉(zhuǎn)換是一個很復(fù)雜的過程源程序語言和目標程序語言是截然不同的我們需要結(jié)構(gòu)化這個轉(zhuǎn)換過程定義中間階段每個階段完成特定的功能2/4/202323編譯原理一個簡單的編譯器的結(jié)構(gòu)2/4/202324編譯原理簡單的前端結(jié)構(gòu)2/4/202325編譯原理Analogy（ctd）前端可以通過類比于人類理解自然語言的過程進行解釋詞法分析自然語言：Hewrotetheprogram

單詞：‘he’‘wrote’‘the’‘program’編程語言：if(b==0)a=b token:‘if’‘(’‘b’‘==’‘0’‘)’‘a(chǎn)’‘=’‘b’2/4/202326編譯原理Analogy（ctd）語法分析自然語言編程語言2/4/202327編譯原理Analogy（ctd）語義分析自然語言He wrote the computernoun verb article noun語法正確，語義錯誤！編程語言if(b==0) a=foo test assignment如果a是一個整型變量而foo是一個過程，那么語義分析就會報錯2/4/202328編譯原理詞法分析詞法分析也叫線性分析和掃描。從左到右的讀構(gòu)成源程序的字符流，分組為多個記號。詞法分析器position:=initial+rate*60id1:=id2+id3*602/4/202329編譯原理語法分析語法分析也叫層次分析，把源程序的記號進一步分組，產(chǎn)生被編譯器用于生成代碼的語法短語。程序的語法結(jié)構(gòu)常常需要遞歸上下文無關(guān)文法是遞歸規(guī)則的一種形式化，可以指導(dǎo)語法分析由于詞法分析不要求遞歸，因此我們通常不明確的界定詞法分析和語法分析的界限。也就是說，我們將詞法分析程序當成語法分析程序調(diào)用的一個子程序。2/4/202330編譯原理語法分析（續(xù)）語法分析器id1:=id2+id3*60id1id3id2:=+*60在本例中，算符優(yōu)先級可以通過如下方法定義：1.定義程序語言的語法規(guī)則體現(xiàn)算符的優(yōu)先級2.通過某些規(guī)則庫，例如算符優(yōu)先級表格等來定義算符的優(yōu)先級2/4/202331編譯原理語義分析（續(xù)）語義分析器id1id3id2:=+*60id1id3id2:=+*inttoreal60在本例中，幾個標識符都是實數(shù)類型，而且源程序語言允許整數(shù)向?qū)崝?shù)類型的強制轉(zhuǎn)換2/4/202332編譯原理編譯器的應(yīng)用模型（邏輯結(jié)構(gòu)）出錯處理語法分析程序語義分析程序目標代碼生成程序詞法分析程序中間代碼生成程序代碼優(yōu)化程序表格管理編譯的前端（FrontEnd）分析部分與源語言有關(guān)編譯的后端（BackEnd）綜合部分與目標語言有關(guān)2/4/202333編譯原理2/4/202334編譯原理2/4/202335編譯原理遍（PASS）遍：對源程序（包括源程序的中間表示形式）從頭到尾掃描一次并作有關(guān)的加工處理，生成新的源程序中間形式或目標程序，通常