編譯方法、技術(shù)與實(shí)踐概述

概述?編譯器的結(jié)構(gòu)?編譯過(guò)程?語(yǔ)言特征提綱4?一個(gè)編譯器就是一個(gè)程序，讀入以某一種語(yǔ)言 (源語(yǔ)言)編寫(xiě)的程序，并把該程序翻譯成為一個(gè)等價(jià)的、用另一種語(yǔ)言(目標(biāo)語(yǔ)言)編寫(xiě)的程

序。?如果翻譯過(guò)程發(fā)現(xiàn)源程序有錯(cuò)，則報(bào)錯(cuò)?狹義：程序設(shè)計(jì)語(yǔ)言t

機(jī)器代碼?廣義：程序變換C++t

C

t匯編Pascal

t

C什么是編譯器編譯器目標(biāo)程序源程序5?編譯器vs.

解釋器?編譯器的結(jié)構(gòu)?編譯的構(gòu)造工具編譯器簡(jiǎn)介編譯器目標(biāo)程序源程序6編譯器簡(jiǎn)介7目標(biāo)程序編譯器

效率高，一次編譯，多次運(yùn)行。 通常目標(biāo)程序是可執(zhí)行的。程序輸出程序輸入程序輸入程序輸出源程序編譯器8

直接利用用戶提供的輸入，執(zhí)行源程序中指定的操作。

不生成目標(biāo)程序，而是根據(jù)源程序的語(yǔ)義直接運(yùn)行。 邊解釋，邊執(zhí)行，錯(cuò)誤診斷效果好。程序輸出程序輸入解釋器源程序解釋器9?Java結(jié)合了兩者：O

先編譯成字節(jié)碼，再由Java虛擬機(jī)解釋執(zhí)行O

即時(shí)編譯(Just-in-time

compiling)編譯器

vs.

解釋器10?預(yù)處理器?編譯器?匯編器?鏈接器?加載器典型語(yǔ)言

(如C)

的編譯11?編譯器vs.

解釋器?編譯器的結(jié)構(gòu)?編譯的構(gòu)造工具編譯器簡(jiǎn)介12?分析部分(Analysis)O

源程序-語(yǔ)法結(jié)構(gòu)-中間表示O

搜集源程序中的相關(guān)信息，放入符號(hào)表O

分析、定位程序中可能存在的錯(cuò)誤信息(語(yǔ)法、語(yǔ)義錯(cuò)誤)O

又稱編譯器的前端(front

end)，是與機(jī)器無(wú)關(guān)的部分?綜合部分(Synthesis)O

根據(jù)符號(hào)表和中間表示構(gòu)造目標(biāo)程序O

又稱編譯器的后端(back

end)，是與機(jī)器相關(guān)的部分編譯器的結(jié)構(gòu)13?每個(gè)步驟把源程序的一種表示方式轉(zhuǎn)換成另一種表示方式。?實(shí)踐中，某些中間表示不需要明確的構(gòu)造

出來(lái)。?符號(hào)表可由各個(gè)步驟

使用

編譯器中的若干步驟14O

類型O

作用域O

過(guò)程名字的參數(shù)數(shù)量、參數(shù)類型等等?記錄源程序中使用的變量的名字，收集各種屬性O(shè)

名字的存儲(chǔ)分配?符號(hào)表可由編譯器的各個(gè)步驟使用符號(hào)表管理15?詞法分析：Thislineisalongersentence.?語(yǔ)法分析：?語(yǔ)義分析?Thislineisalongersentence.類比：英語(yǔ)的分析理解過(guò)程16?詞法分析/掃描(lexical

analysis,

scanning)O

讀入源程序的字符流，輸出有意義的詞素(lexeme)O

基于詞素，產(chǎn)生詞法單元：

<token-name,attribute-value>O

token-name由語(yǔ)法分析步驟使用O

attribute-value指向相應(yīng)的符號(hào)表?xiàng)l目，由語(yǔ)義分析/代碼生成步驟使用?例子O

position=initial+rate

*60O

<id,1>

<=,>

<id,2>

<+,>

<id,3>

<*,>

<number,4>詞法分析17?詞法分析后，需要得到詞素序列的語(yǔ)法結(jié)構(gòu)?語(yǔ)法分析/解析(syntax

analysis/parsing)O

根據(jù)各個(gè)詞法單元的第一個(gè)分量來(lái)創(chuàng)建樹(shù)形中間表示形式。通常是語(yǔ)法樹(shù)(syntax

tree)。O

指出了詞法單元流的語(yǔ)法結(jié)構(gòu)。語(yǔ)法分析18?得到語(yǔ)義(meaning)，對(duì)于編譯器來(lái)說(shuō)比較難?語(yǔ)義分析(semantic

analysis)O

使用語(yǔ)法樹(shù)和符號(hào)表中的信息，檢查源程序是否滿足語(yǔ)言定義的語(yǔ)義約束。O

同時(shí)收集類型信息，用于代碼生成。O

類型檢查，類型轉(zhuǎn)換。語(yǔ)義分析19?

根據(jù)語(yǔ)義分析的輸出，生成類機(jī)器語(yǔ)言的中間表示?三地址代碼：O

每個(gè)指令最多包含三個(gè)運(yùn)算分量O

t1=inttofloat(60)；t2=id3*t1;t3=id2+t2;中間代碼生成2021?通過(guò)對(duì)中間代碼的分析，改進(jìn)中間代碼，得到更好的目標(biāo)代碼O

快、短、能耗低?優(yōu)化有具體的設(shè)計(jì)目標(biāo)代碼優(yōu)化?把中間表示形式映射到目標(biāo)語(yǔ)言O(shè)

寄存器的分配指令選擇內(nèi)存分配代碼生成OO22?趟：以文件為輸入輸出單位的編譯過(guò)程的個(gè)數(shù)，每趟可由一個(gè)或若干個(gè)步驟構(gòu)成?“步驟”是邏輯組織方式?“趟”和具體的實(shí)現(xiàn)相關(guān)O

參考LLVM實(shí)現(xiàn)中的Pass編譯器的趟(Pass)23?編譯器vs.

解釋器?編譯器的結(jié)構(gòu)?編譯的構(gòu)造工具編譯器簡(jiǎn)介24?語(yǔ)法分析器的生成器：

yacc/bisonO

根據(jù)一個(gè)程序設(shè)計(jì)語(yǔ)言的語(yǔ)法描述自動(dòng)生成語(yǔ)法分析器?掃描器的生成器:lex/flexO

根據(jù)一個(gè)語(yǔ)言的詞法單元的正則表達(dá)式描述生成詞法分析器?語(yǔ)法制導(dǎo)的翻譯引擎O

生成一組用于遍歷分析樹(shù)并生成中間代碼的程序?代碼生成器的生成器O

把中間語(yǔ)言的每個(gè)運(yùn)算翻譯成目標(biāo)機(jī)上機(jī)器語(yǔ)言的規(guī)則，生成代碼生成器?數(shù)據(jù)流分析引擎O

收集數(shù)據(jù)流信息，用于優(yōu)化?編譯器構(gòu)造工具集編譯器的構(gòu)造工具25?高級(jí)程序設(shè)計(jì)語(yǔ)言的實(shí)現(xiàn)O

高級(jí)程序設(shè)計(jì)語(yǔ)言的抽象層次的提高有利于編程，但是直接生成的代碼卻相對(duì)低效率O

聚合類型/高級(jí)控制流/面向?qū)ο?垃圾自動(dòng)收集機(jī)制?針對(duì)計(jì)算機(jī)體系結(jié)構(gòu)的優(yōu)化O

并行性：指令級(jí)并行，處理器層次并行O

內(nèi)存層次結(jié)構(gòu)?新體系結(jié)構(gòu)的設(shè)計(jì)O

RISCO

專用體系結(jié)構(gòu)O

一個(gè)新的體系結(jié)構(gòu)特征能否被充分利用，取決于編譯技術(shù)編譯技術(shù)的應(yīng)用26?程序翻譯O

二進(jìn)制翻譯/硬件合成/數(shù)據(jù)查詢解釋器/編譯后模擬?軟件生產(chǎn)率工具O

類型檢查O

邊界檢查O

內(nèi)存管理工具編譯技術(shù)的應(yīng)用27編譯器的處理對(duì)象-程序語(yǔ)言編譯器目標(biāo)程序源程序28?語(yǔ)言的代分類O

第一代語(yǔ)言：機(jī)器語(yǔ)言O(shè)

第二代語(yǔ)言：匯編語(yǔ)言O(shè)

第三代語(yǔ)言：高級(jí)程序設(shè)計(jì)語(yǔ)言?Fortran,Pascal,Lisp,Modula,CO

第四代：特定應(yīng)用語(yǔ)言：NOMAD,SQL,PostscriptO

第五代：基于邏輯和約束的語(yǔ)言，Prolog、OPS5?命令式語(yǔ)言/聲明式語(yǔ)言O(shè)

前者指明如何完成，后者指明要完成哪些計(jì)算?馮.諾依曼語(yǔ)言/面向?qū)ο蟮恼Z(yǔ)言/腳本語(yǔ)言?面向?qū)ο笳Z(yǔ)言O(shè)

Simula,Smalltalk,Modula3,C++,ObjectPascal,Java,C#O

數(shù)據(jù)抽象、繼承程序設(shè)計(jì)語(yǔ)言29?程序設(shè)計(jì)語(yǔ)言的新發(fā)展向編譯器設(shè)計(jì)者提出新要求O

設(shè)計(jì)相應(yīng)的算法和表示方法來(lái)翻譯和支持新的語(yǔ)言特征?通過(guò)降低高級(jí)語(yǔ)言的執(zhí)行開(kāi)銷，推動(dòng)這些高級(jí)語(yǔ)言的使用?編譯器設(shè)計(jì)者還需要更好地利用新硬件的能力程序設(shè)計(jì)語(yǔ)言和編譯器之間的關(guān)系30?靜態(tài)/動(dòng)態(tài)O

靜態(tài)：語(yǔ)言策略支持編譯器靜態(tài)決定某個(gè)問(wèn)題O

動(dòng)態(tài)：只允許在程序運(yùn)行時(shí)刻作出決定O

Java類聲明中的static指明了變量的存放位置可靜態(tài)確定?

作用域O

x的一個(gè)聲明的作用域是指程序中的一個(gè)區(qū)域，其中對(duì)x的使用都指向這個(gè)聲明O

靜態(tài)作用域：通過(guò)靜態(tài)閱讀程序決定作用域O

動(dòng)態(tài)作用域程序設(shè)計(jì)語(yǔ)言的基礎(chǔ)概念31?

環(huán)境與狀態(tài)O

環(huán)境：是從名字到存儲(chǔ)位置的映射O

狀態(tài)：從內(nèi)存位置到它們的值的映射?

環(huán)境的改變需要遵守語(yǔ)言的作用于規(guī)則程序設(shè)計(jì)語(yǔ)言的基礎(chǔ)概念32?靜態(tài)作用域和塊結(jié)構(gòu)O

C族語(yǔ)言使用靜態(tài)作用域。?

C語(yǔ)言程序由頂層的變量、函數(shù)聲明組成?函數(shù)內(nèi)部可以聲明變量(局部變量/參數(shù))，這些聲明的作用域在它出現(xiàn)的函數(shù)內(nèi)?一個(gè)頂層聲明的作用域包括其后的所有程序。除去那些具有同樣名字的變量聲明的函數(shù)體。O

作用域規(guī)則基于程序結(jié)構(gòu)，聲明的作用域由它在程序中的位置隱含決定。O

也通過(guò)public

、private

、protected進(jìn)行明確控制程序設(shè)計(jì)語(yǔ)言的基礎(chǔ)概念3334程序設(shè)計(jì)語(yǔ)言的基礎(chǔ)概念?塊作用域?qū)嵗?動(dòng)態(tài)作用域O

對(duì)一個(gè)名字x的使用指向的是最近被調(diào)用但還

沒(méi)有終止且聲明了x的過(guò)程中的這個(gè)聲明。#include<stdio.h>#define

a(x+1)int

x=2;voidc(){printf("%d\n",a);}voidb(){intx=1;printf("%d\n",a);c();}int

main(){b();}#include<stdio.h>#define

a

(x+1)int

x=2;void