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

源程序

目標匯編程序

可重定位機器代碼

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