編譯器知識拾零

編譯器，是將便于人編寫(xiě)，閱讀，維護的高級計算機語(yǔ)言翻譯為計算機能識別，運行的低級機器語(yǔ)言的程序。編譯器將源程序（Source program）作為輸入，翻譯產(chǎn)生使用目標語(yǔ)言（Target language）的等價(jià)程序。源程序一般為高級語(yǔ)言（High-level language），如Pascal，C++等，而目標語(yǔ)言則是匯編語(yǔ)言或目標機器的目標代碼（Object code），有時(shí)也稱(chēng)作機器代碼（Machine code）。

一個(gè)現代編譯器的主要工作流程如下：

源程序（source code）→預處理器（preprocessor）→編譯器（compiler）→匯編程序（assembler）→目標程序（object code）→連接器（鏈接器，Linker）→可執行程序（executables）

目錄
1 工作原理
2 編譯器種類(lèi)
3 預處理器（preprocessor）
4 編譯器前端（frontend）
5 編譯器后端（backend）
6 編譯語(yǔ)言與解釋語(yǔ)言對比
7 歷史
8 參見(jiàn)



工作原理

翻譯是從源代碼（通常為高級語(yǔ)言）到能直接被計算機或虛擬機執行的目標代碼（通常為低級語(yǔ)言或機器言）。然而，也存在從低級語(yǔ)言到高級語(yǔ)言的編譯器，這類(lèi)編譯器中用來(lái)從由高級語(yǔ)言生成的低級語(yǔ)言代碼重新生成高級語(yǔ)言代碼的又被叫做反編譯器。也有從一種高級語(yǔ)言生成另一種高級語(yǔ)言的編譯器，或者生成一種需要進(jìn)一步處理的的中間代碼的編譯器（又叫級聯(lián)）。

典型的編譯器輸出是由包含入口點(diǎn)的名字和地址以及外部調用（到不在這個(gè)目標文件中的函數調用）的機器代碼所組成的目標文件。一組目標文件，不必是同一編譯器產(chǎn)生，但使用的編譯器必需采用同樣的輸出格式，可以鏈接在一起并生成可以由用戶(hù)直接執行的可執行程序。


編譯器種類(lèi)

編譯器可以生成用來(lái)在與編譯器本身所在的計算機和操作系統（平臺）相同的環(huán)境下運行的目標代碼，這種編譯器又叫做“本地”編譯器。另外，編譯器也可以生成用來(lái)在其它平臺上運行的目標代碼，這種編譯器又叫做交叉編譯器。交叉編譯器在生成新的硬件平臺時(shí)非常有用。“源碼到源碼編譯器”是指用一種高級語(yǔ)言作為輸入，輸出也是高級語(yǔ)言的編譯器。例如: 自動(dòng)并行化編譯器經(jīng)常采用一種高級語(yǔ)言作為輸入，轉換其中的代碼，并用并行代碼注釋對它進(jìn)行注釋?zhuān)ㄈ鏞penMP）或者用語(yǔ)言構造進(jìn)行注釋?zhuān)ㄈ鏔ORTRAN的DOALL指令）。


預處理器（preprocessor）

作用是通過(guò)代入預定義等程序段將源程序補充完整。


編譯器前端（frontend）
前端主要負責解析（parse）輸入的源程序，由詞法分析器和語(yǔ)法分析器協(xié)同工作。詞法分析器負責把源程序中的‘單詞’（Token）找出來(lái),語(yǔ)法分析器把這些分散的單詞按預先定義好的語(yǔ)法組裝成有意義的表達式，語(yǔ)句 ，函數等等。 例如“a = b + c;”前端詞法分析器看到的是“a, =, b , +, c;”，語(yǔ)法分析器按定義的語(yǔ)法，先把他們組裝成表達式“b + c”，再組裝成“a = b + c”的語(yǔ)句。 前端還負責語(yǔ)義（semantic checking）的檢查，例如檢測參與運算的變量是否是同一類(lèi)型的，簡(jiǎn)單的錯誤處理。最終的結果常常是一個(gè)抽象的語(yǔ)法樹(shù)（abstract syntax tree，或 AST），這樣后端可以在此基礎上進(jìn)一步優(yōu)化，處理。


編譯器后端（backend）

編譯器后端主要負責分析，優(yōu)化中間代碼（Intermediate representation）以及生成機器代碼（Code Generation）。


一般說(shuō)來(lái)所有的編譯器分析，優(yōu)化，變型都可以分成兩大類(lèi)： 函數內（intraprocedural）還是函數之間（interprocedural）進(jìn)行。很明顯，函數間的分析，優(yōu)化更準確，但需要更長(cháng)的時(shí)間來(lái)完成。


編譯器分析（compiler analysis）的對象是前端生成并傳遞過(guò)來(lái)的中間代碼，現代的優(yōu)化型編譯器（optimizing compiler）常常用好幾種層次的中間代碼來(lái)表示程序，高層的中間代碼（high level IR）接近輸入的源程序的格式，與輸入語(yǔ)言相關(guān)（language dependent），包含更多的全局性的信息，和源程序的結構；中層的中間代碼（middle level IR）與輸入語(yǔ)言無(wú)關(guān)，低層的中間代碼(Low level IR)與機器語(yǔ)言類(lèi)似。 不同的分析，優(yōu)化發(fā)生在最適合的那一層中間代碼上。


常見(jiàn)的編譯分析有函數調用樹(shù)（call tree），控制流程圖（Control flow graph），以及在此基礎上的 變量定義－使用，使用－定義鏈（define-use/use-define or u-d/d-u chain），變量別名分析（alias analysis），指針?lè )治觯╬ointer analysis），數據依賴(lài)分析（data dependence analysis）等等。


上述的程序分析結果是編譯器優(yōu)化（compiler optimization）和程序變形（compiler transformation）的前提條件。常見(jiàn)的優(yōu)化和變新有：函數內嵌（inlining），無(wú)用代碼刪除（Dead code elimination），標準化循環(huán)結構（loop normalization），循環(huán)體展開(kāi)（loop unrolling），循環(huán)體合并，分裂（loop fusion，loop fission），數組填充（array padding），等等。 優(yōu)化和變形的目的是減少代碼的長(cháng)度，提高內存（memory），緩存（cache）的使用率，減少讀寫(xiě)磁盤(pán)，訪(fǎng)問(wèn)網(wǎng)絡(luò )數據的頻率。更高級的優(yōu)化甚至可以把序列化的代碼（serial code）變成并行運算，多線(xiàn)程的代碼（parallelized，multi-threaded code）。


機器代碼的生成是優(yōu)化變型后的中間代碼轉換成機器指令的過(guò)程?，F代編譯器主要采用生成匯編代碼（assembly code）的策略，而不直接生成二進(jìn)制的目標代碼（binary object code）。即使在代碼生成階段，高級編譯器仍然要做很多分析，優(yōu)化，變形的工作。例如如何分配寄存器（register allocatioin），如何選擇合適的機器指令（instruction selection），如何合并幾句代碼成一句等等。


編譯語(yǔ)言與解釋語(yǔ)言對比

許多人將高級程序語(yǔ)言分為兩類(lèi): 編譯型語(yǔ)言 和 解釋型語(yǔ)言 。然而，實(shí)際上，這些語(yǔ)言中的大多數既可用編譯型實(shí)現也可用解釋型實(shí)現，分類(lèi)實(shí)際上反映的是那種語(yǔ)言常見(jiàn)的實(shí)現方式。（但是，某些解釋型語(yǔ)言，很難用編譯型實(shí)現。比如那些允許 在線(xiàn)代碼更改 的解釋型語(yǔ)言。）


歷史

上世紀50年代，IBM的John Backus帶領(lǐng)一個(gè)研究小組對FORTRAN語(yǔ)言及其編譯器進(jìn)行開(kāi)發(fā)。但由于當時(shí)人們對編譯理論了解不多，開(kāi)發(fā)工作變得既復雜又艱苦。與此同時(shí)，Noam Chomsky開(kāi)始了他對自然語(yǔ)言結構的研究。他的發(fā)現最終使得編譯器的結構異常簡(jiǎn)單，甚至還帶有了一些自動(dòng)化。Chomsky的研究導致了根據語(yǔ)言文法的難易程度以及識別它們所需要的算法來(lái)對語(yǔ)言分類(lèi)。正如現在所稱(chēng)的Chomsky架構（Chomsky Hierarchy），它包括了文法的四個(gè)層次：0型文法、1型文法、2型文法和3型文法，且其中的每一個(gè)都是其前者的特殊情況。2型文法（或上下文無(wú)關(guān)文法）被證明是程序設計語(yǔ)言中最有用的，而且今天它已代表著(zhù)程序設計語(yǔ)言結構的標準方式。分析問(wèn)題（parsing problem，用于上下文無(wú)關(guān)文法識別的有效算法）的研究是在60年代和70年代，它相當完善的解決了這個(gè)問(wèn)題?，F在它已是編譯原理中的一個(gè)標準部分。

有限狀態(tài)自動(dòng)機（Finite Automaton）和正則表達式（Regular Expression）同上下文無(wú)關(guān)文法緊密相關(guān)，它們與Chomsky的3型文法相對應。對它們的研究與Chomsky的研究幾乎同時(shí)開(kāi)始，并且引出了表示程序設計語(yǔ)言的單詞的符號方式。

人們接著(zhù)又深化了生成有效目標代碼的方法，這就是最初的編譯器，它們被一直使用至今。人們通常將其稱(chēng)為優(yōu)化技術(shù)（Optimization Technique），但因其從未真正地得到過(guò)被優(yōu)化了的目標代碼而僅僅改進(jìn)了它的有效性，因此實(shí)際上應稱(chēng)作代碼改進(jìn)技術(shù)（Code Improvement Technique）。

當分析問(wèn)題變得好懂起來(lái)時(shí)，人們就在開(kāi)發(fā)程序上花費了很大的功夫來(lái)研究這一部分的編譯器自動(dòng)構造。這些程序最初被稱(chēng)為編譯器的編譯器（Compiler-compiler），但更確切地應稱(chēng)為分析程序生成器（Parser Generator），這是因為它們僅僅能夠自動(dòng)處理編譯的一部分。這些程序中最著(zhù)名的是Yacc（Yet Another Compiler-compiler），它是由Steve Johnson在1975年為Unix系統編寫(xiě)的。類(lèi)似的，有限狀態(tài)自動(dòng)機的研究也發(fā)展了一種稱(chēng)為掃描程序生成器（Scanner Generator）的工具，Lex（與Yacc同時(shí)，由Mike Lesk為Unix系統開(kāi)發(fā)）是這其中的佼佼者。

在70年代后期和80年代早期，大量的項目都貫注于編譯器其它部分的生成自動(dòng)化，這其中就包括了代碼生成。這些嘗試并未取得多少成功，這大概是因為操作太復雜而人們又對其不甚了解。

編譯器設計最近的發(fā)展包括：首先，編譯器包括了更加復雜算法的應用程序它用于推斷或簡(jiǎn)化程序中的信息；這又與更為復雜的程序設計語(yǔ)言的發(fā)展結合在一起。其中典型的有用于函數語(yǔ)言編譯的Hindley-Milner類(lèi)型檢查的統一算法。其次，編譯器已越來(lái)越成為基于窗口的交互開(kāi)發(fā)環(huán)境（Interactive Development Environment，IDE）的一部分，它包括了編輯器、連接程序、調試程序以及項目管理程序。這樣的IDE標準并沒(méi)有多少，但是對標準的窗口環(huán)境進(jìn)行開(kāi)發(fā)已成為方向。另一方面，盡管近年來(lái)在編譯原理領(lǐng)域進(jìn)行了大量的研究，但是基本的編譯器設計原理在近20年中都沒(méi)有多大的改變，它現在正迅速地成為計算機科學(xué)課程中的中心環(huán)節。

在九十年代，作為GNU項目或其它開(kāi)放源代碼項目的一部分，許多免費編譯器和編譯器開(kāi)發(fā)工具被開(kāi)發(fā)出來(lái)。這些工具可用來(lái)編譯所有的計算機程序語(yǔ)言。它們中的一些項目被認為是高質(zhì)量的，而且對現代編譯理論感性趣的人可以很容易的得到它們的免費源代碼。

大約在1999年，SGI公布了他們的一個(gè)工業(yè)化的并行化優(yōu)化編譯器Pro64的源代碼，后被全世界多個(gè)編譯器研究小組用來(lái)做研究平臺，并命名為Open64。Open64的設計結構好，分析優(yōu)化全面，是編譯器高級研究的理想平臺。

編譯器是一種特殊的程序，它可以把以特定編程語(yǔ)言寫(xiě)成的程序變?yōu)闄C器可以運行的機器碼。我們把一個(gè)程序寫(xiě)好，這時(shí)我們利用的環(huán)境是文本編輯器。這時(shí)我程序把程序稱(chēng)為源程序。在此以后程序員可以運行相應的編譯器，通過(guò)指定需要編譯的文件的名稱(chēng)就可以把相應的源文件（通過(guò)一個(gè)復雜的過(guò)程）轉化為機器碼了。

編譯器工作方法

首先編譯器進(jìn)行語(yǔ)法分析，也就是要把那些字符串分離出來(lái)。然后進(jìn)行語(yǔ)義分析，就是把各個(gè)由語(yǔ)法分析分析出的語(yǔ)法單元的意義搞清楚。最后生成的是目標文件，我們也稱(chēng)為obj文件。再經(jīng)過(guò)鏈接器的鏈接就可以生成最后的可執行代碼了。有些時(shí)候我們需要把多個(gè)文件產(chǎn)生的目標文件進(jìn)行鏈接，產(chǎn)生最后的代碼。我們把一過(guò)程稱(chēng)為交叉鏈接。