編譯原理——引論

1、第一章 引 論編譯原理南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系戴新宇課程概要戴新宇 daixinyu學(xué)時：72學(xué)時(課堂)學(xué)分：4周三: 8-10am，周五 10-12am 計(jì)樓228教材：編譯原理（龍書第二版）講義：/daixinyu/compiler.htm助教: .課程考核：課堂課后作業(yè)實(shí)習(xí)項(xiàng)目 為什么要學(xué)這門課？compiler我們能學(xué)到什么？目標(biāo)：掌握編譯原理理論和技術(shù)形式語言與自動機(jī)，屬性文法等能夠幫助我們更好的理解程序設(shè)計(jì)語言和機(jī)器體系結(jié)構(gòu)幫助我們寫出更加高效的程序什么是編譯器一個編譯器就是一個程序，讀入以某一種語言（源語言）編寫的程序，并把該程序翻譯成為一個等價的、用另一種語言（目標(biāo)語言）編

2、寫的程序。如果翻譯過程發(fā)現(xiàn)源程序有錯，則報(bào)錯狹義： 程序設(shè)計(jì)語言 機(jī)器代碼廣義：程序變換 C+ C 匯編 Python C編譯器源程序目標(biāo)程序編譯器簡介編譯器 vs. 解釋器編譯器的結(jié)構(gòu)編譯的構(gòu)造工具編譯器源程序目標(biāo)程序編譯器編譯器 源程序 目標(biāo)程序效率高，一次編譯，多次運(yùn)行通常目標(biāo)程序是可執(zhí)行的 程序輸出 程序輸入解釋器直接利用用戶提供的輸入，執(zhí)行源程序中指定的操作。不生成目標(biāo)程序，而是根據(jù)源程序的語義直接運(yùn)行。邊解釋，邊執(zhí)行，錯誤診斷效果好。解釋器 源程序 程序輸入 程序輸出編譯器 vs. 解釋器Java結(jié)合了兩者：Javac Hello.javaJava Hello典型語言（如C）的編譯

3、預(yù)處理器匯編器鏈接器加載器CompilerObject file (.o .obj .dcu)LinkerAssemblerlibraries (.lib)assembly file (.a .asm)executable file (.exe)source file (.c .pas )OS (.dll, .so)Loaderprocess編譯器簡介編譯器 vs. 解釋器編譯器的結(jié)構(gòu)編譯的構(gòu)造工具編譯器的結(jié)構(gòu)分析部分（Analysis）源程序 - 語法結(jié)構(gòu) - 中間表示搜集源程序中的相關(guān)信息，放入符號表分析、定位程序中可能存在的錯誤信息（語法、語義錯誤）又稱編譯器的前端（front end）

4、，是于機(jī)器無關(guān)的部分綜合部分（Synthesis）根據(jù)符號表和中間表示構(gòu)造目標(biāo)程序又稱編譯器的后端（back end），是于機(jī)器相關(guān)的部分編譯器中的若干步驟每個步驟把源程序的一種表示方式轉(zhuǎn)換成另一種表示方式。實(shí)踐中，某些中間表示不需要明確的構(gòu)造出來。符號表存放源程序的相關(guān)信息，可由各個步驟使用符號表管理記錄源程序中使用的變量的名字，收集各種屬性名字的存儲分配類型作用域過程名字的參數(shù)數(shù)量、參數(shù)類型等等符號表可由編譯器的各個步驟使用詞法分析（lexical analysis, scanning）詞法分析/掃描讀入源程序的字符流，輸出有意義的詞素(lexeme)基于詞素，產(chǎn)生詞法單元： token-

5、name由語法分析步驟使用attribute-value指向相應(yīng)的符號表?xiàng)l目，由語義分析/代碼生成步驟使用例子position = initial + rate * 60 語法分析（syntax analysis/parsing）詞法分析后，需要得到詞素序列的語法結(jié)構(gòu)語法分析/解析根據(jù)各個詞法單元的第一個分量來創(chuàng)建樹形中間表示形式。通常是語法樹（syntax tree）指出了詞法單元流的語法結(jié)構(gòu)。語義分析(Semantic Analysis)得到語義(meaning)，對于編譯器來說比較難語義分析使用語法樹和符號表中的信息，檢查源程序是否滿足語言定義的語義約束。同時收集類型信息，用于代碼生成。

6、類型檢查，類型轉(zhuǎn)換。語義分析(Interesting examples)Jack said Jerry left his assignment at home.Jack said Jack left his assignment at home?中間代碼生成(Intermediate-Code Generation)根據(jù)語義分析的輸出，生成類機(jī)器語言的中間表示三地址代碼：每個指令最多包含三個運(yùn)算分量t1 = inttofloat(60)； t2 = id3 * t1; t3 = id2 + t2;代碼優(yōu)化(Code Optimization)通過對中間代碼的分析，改進(jìn)中間代碼，得到更好的目標(biāo)代

7、碼運(yùn)行的更快、占用更少的內(nèi)存：少占資源優(yōu)化有具體的設(shè)計(jì)目標(biāo)代碼生成(Code Generation)把中間表示形式映射到目標(biāo)語言寄存器的分配指令選擇內(nèi)存分配編譯器的趟（Pass）趟：以文件為輸入輸出單位的編譯過程的個數(shù)，每趟可由一個或若干個步驟構(gòu)成“步驟”是邏輯組織方式“趟”和具體的實(shí)現(xiàn)相關(guān)編譯器簡介編譯器 vs. 解釋器編譯器的結(jié)構(gòu)編譯的構(gòu)造工具編譯器的構(gòu)造工具掃描器的生成器: lex/flex根據(jù)一個語言的詞法單元的正則表達(dá)式描述生成詞法分析器語法分析器的生成器： yacc/bison根據(jù)一個程序設(shè)計(jì)語言的語法描述自動生成語法分析器語法制導(dǎo)的翻譯引擎生成一組用于遍歷分析樹并生成中間代碼的程

8、序代碼生成器的生成器依據(jù)中間語言的每個運(yùn)算如何翻譯成目標(biāo)機(jī)上機(jī)器語言的一組規(guī)則，生成一個代碼生成器數(shù)據(jù)流分析引擎收集數(shù)據(jù)流信息，用于優(yōu)化編譯器構(gòu)造工具集編譯器源程序目標(biāo)程序編譯器的處理對象-程序語言程序設(shè)計(jì)語言語言的代分類第一代語言：機(jī)器語言第二代語言：匯編語言第三代語言：高級程序設(shè)計(jì)語言Fortran, Pascal, Lisp, Modula, C第四代：特定應(yīng)用語言：NOMAD, SQL, Postscript第五代：基于邏輯和約束的語言，Prolog、OPS5面向?qū)ο笳Z言Simula, Smalltalk, Modula3, C+, Object Pascal, Java, C#數(shù)據(jù)抽

9、象、繼承腳本語言程序設(shè)計(jì)語言和編譯器之間的關(guān)系程序設(shè)計(jì)語言的新發(fā)展向編譯器設(shè)計(jì)者提出新要求設(shè)計(jì)相應(yīng)的算法和表示方法來翻譯和支持新的語言特征通過降低高級語言的執(zhí)行開銷，推動這些高級語言的使用編譯器設(shè)計(jì)者還需要更好地利用新硬件的能力。程序設(shè)計(jì)語言編譯器編譯技術(shù)的應(yīng)用（1）高級程序設(shè)計(jì)語言的實(shí)現(xiàn)高級程序設(shè)計(jì)語言的抽象層次的提高有利于編程，但是直接生成的代碼卻相對低效率聚合類型/高級控制流/面向?qū)ο?垃圾自動收集機(jī)制針對計(jì)算機(jī)體系結(jié)構(gòu)的優(yōu)化并行性：指令級并行，處理器層次并行內(nèi)存層次結(jié)構(gòu)新體系結(jié)構(gòu)的設(shè)計(jì)RISC專用體系結(jié)構(gòu)一個新的體系結(jié)構(gòu)特征能否被充分利用，取決于編譯技術(shù)編譯技術(shù)的應(yīng)用（2）程序翻譯二進(jìn)

10、制翻譯/硬件合成/數(shù)據(jù)查詢解釋器/編譯后模擬軟件生產(chǎn)率工具類型檢查邊界檢查內(nèi)存管理工具程序設(shè)計(jì)語言的基礎(chǔ)概念（1）靜態(tài)/動態(tài)靜態(tài)：語言策略支持編譯器靜態(tài)決定某個問題動態(tài)：只允許在程序運(yùn)行時刻作出決定Java類聲明中的static指明了變量的存放位置可靜態(tài)確定。作用域x的一個聲明的作用域是指程序中的一個區(qū)域，其中對x的使用都指向這個聲明。靜態(tài)作用域：通過靜態(tài)閱讀程序即可確定作用域動態(tài)作用域：程序運(yùn)行時，同一個對x的使用會指向好幾個x的聲明中的一個程序設(shè)計(jì)語言的基礎(chǔ)概念（2）環(huán)境與狀態(tài)環(huán)境：是從名字到存儲位置的映射狀態(tài)：從內(nèi)存位置到它們的值的映射環(huán)境的改變需要遵守語言的作用域規(guī)則程序設(shè)計(jì)語言的基礎(chǔ)概念（3）靜態(tài)作用域和塊結(jié)構(gòu)C族語言使用靜態(tài)作用域。C語言程序由頂層的變量、函數(shù)聲明組成函數(shù)內(nèi)部可以聲明變量（局部變量/參數(shù)），這些聲明的作用域在它出現(xiàn)的函數(shù)內(nèi)一個頂層聲明的作用域包括其后的所有程序。除去那些具有同樣名字的變量聲明的函數(shù)體。作用域規(guī)則基于程序結(jié)構(gòu)，聲明的作用域由它在程序中的位置隱含決定。也通過public、pr