天津大學(xué)編譯原理講解Part引論

編譯原理引論授課：胡靜第一頁(yè)，共38頁(yè)。2023/2/2編譯原理2教材及參考書(shū)教材：?程序設(shè)計(jì)語(yǔ)言編譯原理〔第3版〕?，國(guó)防工業(yè)出版社，陳火旺等編著主要參考資料編譯原理〔CompilersPrinciples,Techniques,andTools〕出版社：機(jī)械工業(yè)出版社?編譯原理?，清華大學(xué)出版社，呂映芝、張素琴、蔣維杜編著第二頁(yè)，共38頁(yè)。2023/2/2編譯原理3相關(guān)課程課程根底數(shù)據(jù)構(gòu)造計(jì)算機(jī)原理和匯編語(yǔ)言高級(jí)程序設(shè)計(jì)語(yǔ)言后續(xù)課程編譯技術(shù)第三頁(yè)，共38頁(yè)。2023/2/2編譯原理4第一章概論編譯的起源：程序設(shè)計(jì)語(yǔ)言的開(kāi)展根本概念編譯過(guò)程和編譯程序的構(gòu)造第四頁(yè)，共38頁(yè)。2023/2/2編譯原理5程序設(shè)計(jì)語(yǔ)言的開(kāi)展第五頁(yè)，共38頁(yè)。2023/2/2編譯原理6根本概念低級(jí)語(yǔ)言〔LowlevelLanguage)字位碼、機(jī)器語(yǔ)言、匯編語(yǔ)言特點(diǎn)：與特定的機(jī)器有關(guān)，成效高，但使用復(fù)雜、繁瑣、費(fèi)時(shí)、易出錯(cuò)高級(jí)語(yǔ)言Fortran、Pascal、C語(yǔ)言等特點(diǎn)：不依賴(lài)詳細(xì)機(jī)器，移植性好、對(duì)用戶(hù)要求低、易使用、易維護(hù)等。第六頁(yè)，共38頁(yè)。2023/2/2編譯原理7根本概念第七頁(yè)，共38頁(yè)。2023/2/2編譯原理8根本概念第八頁(yè)，共38頁(yè)。2023/2/2編譯原理9源程序的編譯和運(yùn)行第九頁(yè)，共38頁(yè)。2023/2/2編譯原理10源程序的解釋運(yùn)行第十頁(yè)，共38頁(yè)。2023/2/2編譯原理11源程序的編譯-解釋運(yùn)行第十一頁(yè)，共38頁(yè)。2023/2/2編譯原理12編譯器和解釋器編譯器和解釋器的比較一樣點(diǎn)〔執(zhí)行一樣的任務(wù)〕:檢查輸入程序并確定這個(gè)程序是否一個(gè)有效程序建立一個(gè)內(nèi)部模型來(lái)刻畫(huà)輸入程序的構(gòu)造和含義決定在執(zhí)行期間值的存放位置不同點(diǎn)〔執(zhí)行的行為不同〕：編譯器以一個(gè)可執(zhí)行程序的描繪作為輸入，以另一個(gè)等價(jià)的可執(zhí)行程序的描繪作為輸出。解釋器以一個(gè)可執(zhí)行程序的描繪作為輸入，以執(zhí)行這一可執(zhí)行程序描繪的結(jié)果作為輸出。第十二頁(yè)，共38頁(yè)。2023/2/2編譯原理13舉例典型的編譯器：gcc,javac非典型的編譯器：latex(documentcompiler):TransformsaLaTeXdocumentintoDVIprintingcommandsInputinformation=document(notprogram)解釋器：f2c:Fortran-to-Ctranslator(bothhigh-level)latex2html:LaTeX-to-HTML(bothdocuments)第十三頁(yè)，共38頁(yè)。2023/2/2編譯原理14我們?yōu)槭裁葱枰幾g器編寫(xiě)、調(diào)試、維護(hù)和理解用裝配語(yǔ)言(assemblelanguage)編寫(xiě)的程序是很困難的自從第一個(gè)編譯器出現(xiàn)之后，軟件產(chǎn)品的數(shù)量有了宏大的增加。但是仍然有一些情況需要用裝配語(yǔ)言編寫(xiě)例如，訪(fǎng)問(wèn)某些底層的機(jī)器資源〔設(shè)備驅(qū)動(dòng)〕這些代碼規(guī)模一般較小，還是需要編譯器去處理其他的應(yīng)用第十四頁(yè)，共38頁(yè)。2023/2/2編譯原理15編譯器構(gòu)造法的研究目的好的編譯器是計(jì)算機(jī)科學(xué)的縮影包含大量的技術(shù)：貪心算法〔存放器分配〕、啟發(fā)式搜索技術(shù)〔列表調(diào)度〕、圖形算法〔死碼消除〕、動(dòng)態(tài)規(guī)劃〔指令挑選〕、有窮自動(dòng)機(jī)和下推自動(dòng)機(jī)〔掃描和語(yǔ)法分析〕、不動(dòng)點(diǎn)算法〔數(shù)據(jù)流分析〕處理復(fù)雜的問(wèn)題：動(dòng)態(tài)分配、同步、命名、部分化、存儲(chǔ)器分層管理、管道調(diào)度提供完好的解決方案：有機(jī)的結(jié)合算法、軟件體系構(gòu)造和軟件工程的各種理論，對(duì)棘手問(wèn)題給出綜合性的解答方案。第十五頁(yè)，共38頁(yè)。2023/2/2編譯原理16什么是編譯器什么是編譯程序預(yù)處理器編譯器匯編器裝配連接編輯骨架程序

源程序

目標(biāo)匯編程序

可重定位機(jī)器代碼

絕對(duì)機(jī)器碼可重定位目標(biāo)文件庫(kù)第十六頁(yè)，共38頁(yè)。2023/2/2編譯原理17源代碼符合人類(lèi)閱讀習(xí)慣符合人類(lèi)語(yǔ)法定義使用被命名的構(gòu)造，例如變量和過(guò)程第十七頁(yè)，共38頁(yè)。2023/2/2編譯原理18裝配語(yǔ)言機(jī)器代碼符合硬件需求包含機(jī)器指令，使用存放器和沒(méi)有命名的內(nèi)存地址對(duì)人類(lèi)來(lái)說(shuō)很難理解第十八頁(yè)，共38頁(yè)。2023/2/2編譯原理19例子：輸出的裝配代碼沒(méi)有優(yōu)化的代碼優(yōu)化后的代碼第十九頁(yè)，共38頁(yè)。2023/2/2編譯原理20編譯器的根本原那么編譯器是工程對(duì)象，是具有獨(dú)特目的的大型軟件系統(tǒng)，兩個(gè)設(shè)計(jì)原那么必須遵守不違犯原義編譯器必須保持被編譯程序的含義不變這一原那么是編譯器設(shè)計(jì)者與編譯器用戶(hù)之間的契約的核心實(shí)用性原那么編譯器必須用某種明確的方式改進(jìn)輸入程序例如代碼優(yōu)化等對(duì)輸入程序的改進(jìn)第二十頁(yè)，共38頁(yè)。2023/2/2編譯原理21有效的轉(zhuǎn)換目的：產(chǎn)生和源代碼描繪一樣計(jì)算的機(jī)器代碼這種轉(zhuǎn)換是唯一的嘛？有沒(méi)有“完美的轉(zhuǎn)換〞〔速度快，代碼量小〕編譯器優(yōu)化=找到更好的轉(zhuǎn)換第二十一頁(yè)，共38頁(yè)。2023/2/2編譯原理22轉(zhuǎn)換的正確性產(chǎn)生的代碼必須準(zhǔn)確的執(zhí)行和源代碼一樣的計(jì)算正確性很重要用不正確的編譯器調(diào)試程序很難……和開(kāi)發(fā)的本錢(qián)、平安性親密相關(guān)編譯原理這門(mén)課程講述的就是可以保證轉(zhuǎn)換平安性的技術(shù)。第二十二頁(yè)，共38頁(yè)。2023/2/2編譯原理23如何轉(zhuǎn)換轉(zhuǎn)換是一個(gè)很復(fù)雜的過(guò)程源程序語(yǔ)言和目的程序語(yǔ)言是截然不同的我們需要構(gòu)造化這個(gè)轉(zhuǎn)換過(guò)程定義中間階段每個(gè)階段完成特定的功能第二十三頁(yè)，共38頁(yè)。2023/2/2編譯原理24一個(gè)簡(jiǎn)單的編譯器的構(gòu)造第二十四頁(yè)，共38頁(yè)。2023/2/2編譯原理25簡(jiǎn)單的前端構(gòu)造第二十五頁(yè)，共38頁(yè)。2023/2/2編譯原理26Analogy〔ctd〕前端可以通過(guò)類(lèi)比于人類(lèi)理解自然語(yǔ)言的過(guò)程進(jìn)展解釋詞法分析自然語(yǔ)言：Hewrotetheprogram 單詞：‘he’‘wrote’‘the’‘program’編程語(yǔ)言：if(b==0)a=b token:‘if’‘(’‘b’‘==’‘0’‘)’‘a(chǎn)’‘=’‘b’第二十六頁(yè)，共38頁(yè)。2023/2/2編譯原理27Analogy〔ctd〕語(yǔ)法分析自然語(yǔ)言編程語(yǔ)言第二十七頁(yè)，共38頁(yè)。2023/2/2編譯原理28Analogy〔ctd〕語(yǔ)義分析自然語(yǔ)言He wrote the computernoun verb article noun語(yǔ)法正確，語(yǔ)義錯(cuò)誤！編程語(yǔ)言if(b==0) a=foo test assignment假如a是一個(gè)整型變量而foo是一個(gè)過(guò)程，那么語(yǔ)義分析就會(huì)報(bào)錯(cuò)第二十八頁(yè)，共38頁(yè)。2023/2/2編譯原理29詞法分析詞法分析也叫線(xiàn)性分析和掃描。從左到右的讀構(gòu)成源程序的字符流，分組為多個(gè)記號(hào)。詞法分析器position:=initial+rate*60id1:=id2+id3*60第二十九頁(yè)，共38頁(yè)。2023/2/2編譯原理30語(yǔ)法分析語(yǔ)法分析也叫層次分析，把源程序的記號(hào)進(jìn)一步分組，產(chǎn)生被編譯器用于生成代碼的語(yǔ)法短語(yǔ)。程序的語(yǔ)法構(gòu)造常常需要遞歸上下文無(wú)關(guān)文法是遞歸規(guī)那么的一種形式化，可以指導(dǎo)語(yǔ)法分析由于詞法分析不要求遞歸，因此我們通常不明確的界定詞法分析和語(yǔ)法分析的界限。也就是說(shuō)，我們將詞法分析程序當(dāng)成語(yǔ)法分析程序調(diào)用的一個(gè)子程序。第三十頁(yè)，共38頁(yè)。2023/2/2編譯原理31語(yǔ)法分析〔續(xù)〕語(yǔ)法分析器id1:=id2+id3*60id1id3id2:=+*60在本例中，算符優(yōu)先級(jí)可以通過(guò)如下方法定義：1.定義程序語(yǔ)言的語(yǔ)法規(guī)那么表達(dá)算符的優(yōu)先級(jí)2.通過(guò)某些規(guī)那么庫(kù)，例如算符優(yōu)先級(jí)表格等來(lái)定義算符的優(yōu)先級(jí)第三十一頁(yè)，共38頁(yè)。2023/2/2編譯原理32語(yǔ)義分析〔續(xù)〕語(yǔ)義分析器id1id3id2:=+*60id1id3id2:=+*inttoreal60在本例中，幾個(gè)標(biāo)識(shí)符都是實(shí)數(shù)類(lèi)型，而且源程序語(yǔ)言允許整數(shù)向?qū)崝?shù)類(lèi)型的強(qiáng)迫轉(zhuǎn)換第三十二頁(yè)，共38頁(yè)。2023/2/2編譯原理33編譯器的應(yīng)用模型〔邏輯構(gòu)造〕出錯(cuò)處理語(yǔ)法分析程序語(yǔ)義分析程序目的代碼生成程序詞法分析程序中間代碼生成程序代碼優(yōu)化程序表格管理編譯的前端〔FrontEnd〕分析部分與源語(yǔ)言有關(guān)編譯的后端〔BackEnd〕綜合部分與目的語(yǔ)言有關(guān)第三十三頁(yè)，共38頁(yè)。2023/2/2編譯原理34第三十四頁(yè)，共38頁(yè)。2023/2/2編譯原理35第三十五頁(yè)，共38頁(yè)。2023/2/2編譯原理36遍〔PASS〕遍：對(duì)源程序〔包括源程序的中間表示形式〕從頭到尾掃描一次并作有關(guān)的加工處理，生成新的源程序中間形式或目的程序，通常稱(chēng)之為一遍。