基本概念 編譯器是將彙編或高級計算機語言翻譯為二進制機器語言代碼的計算機
程式 。編譯器將
源程式 (source language) 編寫的程式作為
輸入 ,翻譯產生
目標語言 (target language )機器代碼的等價程式。通常地,源程式為
高級語言 (high-level language ),像
C 或C + +、漢語語言程式等,而目標則是機器語言的目標代碼 (object code,有時也稱作機器代碼(machine code )),也就是可以在計算機硬體中運行的機器代碼軟體程式。這一過程可以表示為:
源程式→編譯器 →目標機器代碼程式
編譯原理課程 這門課程關注的是編譯器方面的產生原理和技術問題,似乎和計算機的基礎領域不沾邊,可是編譯原理卻一直作為大學本科的 必修課程,同時也成為了研究生入學考試的必考內容。編譯原理及技術從本質上來講就是一個算法問題而已,當然由於這個問題十分複雜,其解決算法也相對複雜。 我們學的數據結構與算法分析也是講算法的,不過講的基礎算法,換句話說講的是算法導論,而編譯原理這門課程講的就是比較專註解決一種的算法了。在20世紀 50年代,編譯器的編寫一直被認為是十分困難的事情,第一Fortran的編譯器據說花了18年的時間才完成。在人們嘗試編寫編譯器的同時,誕生了許多跟 編譯相關的理論和技術,而這些理論和技術比一個實際的編譯器本身價值更大。就猶如數學家們在解決著名的哥德巴赫猜想一樣,雖然沒有最終解決問題,但是其間 誕生不少名著的相關數論。
發展歷程 在20世紀40年代,由於馮·諾伊曼在存儲-程式計算機方面的先鋒作用,編寫一串代碼或程式已成必要,這樣計算機就可以執行所需的計算。開始時,這些程式都是用
機器語言 (machine language )編寫的。機器語言就是表示機器實際操作的數字代碼,例如:
編譯原理實驗程式 C7 06 0000 0002 表示在IBM PC 上使用的Intel 8x86處理器將數字2移至
地址 0 0 0 0 (
16進制 )的指令。
但編寫這樣的代碼是十分費時和乏味的,這種代碼形式很快就被
彙編語言 (assembly language )代替了。在彙編語言中,都是以符號形式給出指令和存儲地址的。例如,彙編語言指令 MOV X,2 就與前面的機器指令等價(假設符號存儲地址X是0 0 0 0 )。彙編程式(assembler )將彙編語言的符號代碼和存儲地址翻譯成與機器語言相對應的數字代碼。
彙編語言大大提高了編程的速度和準確度,人們至今仍在使用著它,在
編碼 需要極快的
速度 和極高的簡潔程度時尤為如此。但是,彙編語言也有許多缺點:編寫起來也不容易,閱讀和理解很難;而且彙編語言的編寫嚴格依賴於特定的機器,所以為一台計算機編寫的代碼在套用於另一台計算機時必須完全重寫。
發展
編程技術 的下一個重要步驟就是以一個更類似於
數學 定義或自然語言的簡潔形式來編寫程式的操作,它應與任何機器都無關,而且也可由一個程式翻譯為可執行的代碼。例如,前面的彙編語言代碼可以寫成一個簡潔的與機器無關的形式 x = 2。
在1954年至1957年期間,
IBM 的
John Backus 帶領的一個研究小組對
FORTRAN語言 及其編譯器的開發,使得上面的擔憂不必要了。但是,由於當時處理中所涉及到的大多數
程式設計語言 的翻譯並不為人所掌握,所以這個項目的成功也伴隨著巨大的辛勞。幾乎與此同時,人們也在開發著第一個編譯器,
Noam Chomsky 開始了他的自然語言結構的研究。他的發現最終使得編譯器結構異常簡單,甚至還帶有了一些自動化。Chomsky的研究導致了根據語言文法(grammar ,指定其結構的規則)的難易程度以及識別它們所需的
算法 來為語言分類。正如現在所稱的-與喬姆斯基分類結構(Chomsky hierarchy )一樣-包括了文法的4個層次:0型、1型、2型和3型文法,且其中的每一個都是其前者的專門化。2型(或
上下文無關文法 (context-free grammar ))被證明是程式設計語言中最有用的,而且今天它已代表著程式設計語言結構的標準方式。
分析問題( parsing problem ,用於限定上下文無關語言的識別的有效算法)的研究是在20世紀60年代和70年代,它相當完善地解決了這一問題, 現在它已是編譯理論的一個標準部分。它們與喬姆斯基的3型文法相對應。對它們的研究與喬姆斯基的研究幾乎同時開始,並且引出了表示程式設計語言的單詞(或稱為記號)的符號方式。
人們接著又深化了生成有效的目標代碼的方法,這就是最初的編譯器,它們被一直使用至今。人們通常將其誤稱為
最佳化技術 (optimization technique ),但因其從未真正地得到過被最佳化了的目標代碼而僅僅改進了它的有效性,因此實際上應稱作代碼改進技術(code improvement technique )。
這些程式最初被稱為編譯程式-編譯器,但更確切地應稱為
分析程式 生成器 (parser generator ),這是因為它們僅僅能夠自動處理編譯的一部分。這些程式中最著名的是
Yacc (yet another compiler- compiler),它是由
Steve Johnson 在1975年為
Unix系統 編寫的。
類似地,有窮自動機的研究也發展了另一種稱為掃描程式生成器 (scanner generator )的工具,
Lex (與Yacc同時,由Mike Lesk為Unix系統開發的)是這其中的佼佼者。在20世紀70年代後期和80年代早期,大量的項目都關注於編譯器其他部分的生成自動化,這其中就包括代碼生成。這些嘗試並未取得多少成功,這大概是因為操作太複雜而人們又對其不甚了解。
編譯器設計最近的發展包括:首先,編譯器包括了更為複雜的算法的
應用程式 ,它用於推斷或簡化程式中的信息;這又與更為複雜的程式設計語言(可允許此類分析)的發展結合在一起。其中典型的有用於函式語言編譯的Hindle y - Milner類型檢查的統一算法。
其次,編譯器已越來越成為基於視窗的互動開發環境(interactive development environment,IDE )的一部 分,它包括了編輯器、連結程式、調試程式以及項目管理程式。這樣的IDE的標準並沒有多少, 但是已沿著這一方向對標準的視窗環境進行開發了。
相關程式 解釋程式 解釋程式(interpreter): 解釋程式 是如同編譯器的一種語言
翻譯程式 。它與編譯器的不同之處在於:它立即執行源程式而不是生成在翻譯完成之後才執行的目標代碼。從原理上講,任何程式設計語言都可被解釋或被編譯,但是根據所使用的語言和翻譯情況,很可能會選用解釋程式而不用編譯器。例如, 我們經常解釋
BASIC語言 而不是去編譯它。類似地,諸如LISP 的函式語言也常常是被解釋的。
解釋程式也經常用於教育和
軟體 的開發,此處的程式很有可能被翻譯若干次。而另一方面,當執行的速度是最為重要的因素時就使用編譯器,這是因為被編譯的目標代碼比被解釋的
原始碼 要快得多,有時要快10倍或更多。但是,解釋程式具有許多與編譯器共享的操作,而兩者之間也有一些混合之處。
彙編程式 彙編程式(assembler): 彙編程式 是用於特定計算機上的彙編語言的翻譯程式。正如前面所提到的,彙編語言是計算機的機器語言的符號形式,它極易翻譯。有時,編譯器會生成彙編語言以作為其目標語言, 然後再由一個彙編程式將它翻譯成目標代碼。
連線程式 連線程式(linker): 編譯器和彙編程式都經常依賴於
連線程式 ,它將分別在不同的
目標檔案 中編譯或彙編的代碼收集到一個可直接執行的檔案中。在這種情況下,目標代碼,即還未被連線的機器代碼,與可執行的機器代碼之間就有了區別。連線程式還連線目標程式和用於標準
庫函式 的代碼,以及連線目標程式和由計算機的
作業系統 提供的資源(例如,存儲分配程式及輸入與輸出設備)。連線程式現在正在完成編譯器最早的一個主要活動(這也是“編譯”一詞的用法, 即通過收集不同的來源來構造)。連線過程對作業系統和處理器有極大的依賴性。
裝入程式 裝入程式(loader): 編譯器、彙編程式或連線程式生成的代碼經常還不完全適用或不能執行,但是它們的主要
存儲器 訪問卻可以在存儲器的任何位置中且與一個不確定的起始位置相關。這樣的代碼被稱為是可重定位的(relocatable ),而
裝入程式 可處理所有的與指定的基地址或起始地址有關的可
重定位 的地址。裝入程式使得可執行代碼更加靈活,但是裝入處理通常是在
後台 (作為
操作環境 的一部分)或與連線相聯合時才發生,裝入程式極少會是實際的獨立程式。
預處理器 預處理器(preprocessor ): 預處理器 是在真正的翻譯開始之前由編譯器調用的獨立程式。預處理器可以刪除注釋、包含其他檔案以及執行宏(
宏 macro是一段重複文字的簡短描寫)替代。預處理器可由語言(如 C )要求或以後作為提供額外功能(諸如為FORTRAN提供Ratfor預處理器)的附加軟體。
編輯器 編輯器(editor): 編譯器通常接受由任何生成標準檔案(例如
ASCII檔案 )的編輯器編寫的源程式。現在, 編譯器已與另一個編輯器和其他程式捆綁進一個互動的開發環境-IDE中。此時,儘管編輯器仍然生成標準檔案,但會轉向正被討論的程式設計語言的格式或結構。這樣的編輯器稱為基於結構的(structure based ),且它早已包括了編譯器的某些操作;因此,
程式設計師 就會在程式的編寫時而不是在編譯時就得知錯誤了。從編輯器中也可調用編譯器以及與它共用的程式,這樣程式設計師無需離開編輯器就可
執行程式 。
調試程式 調試程式(debugger ): 調試程式 是可在被編譯了的程式中判定執行錯誤的程式,它也經常與編譯器一起放在IDE 中。運行一個帶有調試程式的程式與直接執行不同,這是因為調試程式保存著所有的或大多數原始碼信息(諸如行數、變數名和過程)。它還可以在預先指定的位置(稱為
斷點 (breakpoint )) 暫停執行,並提供有關已調用的函式以及變數的當前值的信息。為了執行這些函式,編譯器必須為調試程式提供恰當的符號信息,而這有時卻相當困難,尤其是在一個要最佳化目標代碼的編譯器中。因此,調試又變成了一個編譯問題。
描述器 描述器(profiler): 描述器是在執行中蒐集目標程式行為統計的程式。程式設計師特別感興趣的統計是每一個過程的調用次數和每一個過程執行時間所占的百分比。這樣的統計對於幫助程式設計師提高程式的執行速度極為有用。有時編譯器也甚至無需程式設計師的干涉就可利用描述器的輸出來自動改進目標代碼。
項目管理程式 項目管理程式(project manager): 軟體項目通常大到需要由一組程式設計師來完成,這時對那些由不同人員操作的檔案進行整理就非常重要了,而這正是
項目管理程式 的任務。例如,項目管理程式應將由不同的程式設計師製作的檔案的各個獨立版本整理在一起,它還應保存一組檔案的更改歷史,這樣就能維持一個正在開發的程式的連貫版本了(這對那些由單個程式設計師管理的項目也很有用)。項目管理程式的編寫可與語言無關,但當其與編譯器捆綁在一起時,它就可以保持有關特定的編譯器和建立一個完整的可執行程式的連結程式操作的信息。在
Unix系統 中有兩個流行的項目管理程式:sccs (source code control system )和
rcs (revision control system )。
步驟 編譯器內部包括了許多步驟或稱為階段原始碼(phase),它們執行不同的邏輯操作。將這些階段構想為編譯器中一個個單獨的片斷是很有用的, 儘管在套用中它們是經常組合在一起的,但它們掃描程式確實是作為單獨的代碼操作來編寫的。
掃描程式 掃描程式(scanner): 在這個階段編譯器實際閱讀源程式(通常以分析程式字元流的形式表示)。掃描程式執行詞法分析注釋樹符號表 (Lexical analysis ):它將字元序列收集到稱作記號錯誤處 (token )的有意義單元中,記號同自然語言,如英原始碼理器語中的字詞相似。因此可以認為掃描程式執行與最佳化程式拼寫相似的任務。中間代碼例如在下面的代碼行(它可以是C程式的一部分)中:代碼生成器 a [index] = 4 + 2 這個代碼包括了1 2個非空字元,但只有 8個目標代碼記號:a
標識符 目標代碼最佳化程式 [ 左括弧 i n d e x 標識符 ] 右括弧 =
賦值 目標代碼 4 數字編譯器的階段 + 加號 2 數字 每一個記號均由一個或多個字元組成,在進一步處理之前它已被收集在一個單元中。掃描程式還可完成與識別記號一起執行的其他操作。例如,它可將標識符輸入到符號表中, 將文字(litral)輸入到文字表中(文字包括諸如3 . 1415926535的數字常量,以及諸如“Hello,world ! ”的引用字元串)。
語法分析 語法分析(parser ): 語法分析程式從掃描程式中獲取記號形式的原始碼,並完成定義程式結構的語法分析 (syntax analysis ),這與自然語言中句子的語法分析類似。語法分析定義了程式的結構元素及其關係。通常將語法分析的結果表示為
分析樹 (parse tree)或
語法樹 (syntax tree)。例如,還是那行C代碼,它表示一個稱為表達式的結構元素,該
表達式 是一個由左邊為下標表達式、右邊為
整型 表達式的
賦值表達式 組成。這個結構可按下面的形式表示為一個分析樹:請注意,分析樹的內部節點均由其表示的結構名標示出,而分析樹的葉子則表示輸入中的記號序列(結構名以不同
字型 表示以示與記號的區別)。分析樹對於顯示程式的語法或程式元素很有幫助,但是對於表示該結構卻顯得力不從心了。分析程式更趨向於生成語法樹,語法樹是分析樹中所含信息的濃縮(有時因為語法樹表示從分析樹中的進一步抽取,所以也被稱為抽象的語法樹(abstract syntax tree ))。下面是一個C
賦值語句 的抽象語法樹的例子:請注意,在語法樹中,許多節點(包括記號節點在內)已經消失。例如,如果知道表達式是一個下標運算,則不再需要用括弧“[”和“]”來表示該操作是在原始輸入中。
語義分析 語義分析(semantic analyzer ): 程式的語義就是它的“意思”,它與語法或結構不同。程式的語義確定程式的運行,但是大多數的程式設計語言都具有在執行之前被確定而不易由語法表示和由分析程式分析的
特徵 。這些特徵被稱作靜態語義(static semantic),而語義分析程式的任務就是分析這樣的語義(程式的“
動態 ”語義具有隻有在程式執行時才能確定的特性,由於編譯器不能執行程式,所以它不能由編譯器來確定)。一般的程式設計語言的典型靜態語義包括聲明和類型檢查。由語義分析程式計算的額外信息(諸如
數據類型 )被稱為
屬性 (attribute),它們通常是作為注釋或“裝 飾”增加到樹中(還可將屬性添加到符號表中)。在正運行的C表達式 a [index] = 4 + 2 中,該行分析之前收集的典型類型信息可能是:a是一個整型值的數組,它帶有來自整型子範圍的下標;index則是一個
整型變數 。接著,語義分析程式將用所有的子表達式類型來標註語法樹,並檢查賦值是否使這些類型有意義了,如若沒有,則聲明一個類型匹配錯誤。在上例中, 所有的類型均有意義,有關語法樹的語義分析結果可用以下注釋了的樹來表示。
最佳化程式 最佳化程式(source code optimizer): 編譯器通常包括許多代碼改進或最佳化步驟。絕大多數最早的最佳化步驟是在語義分析之後完 成的,而此時代碼改進可能只依賴於原始碼。這種可能性是通過將這一操作提供為編譯過程中的單獨階段指出的。每個編譯器不論在已完成的最佳化種類方面還是在最佳化階段的定位中都有很大的差異。在上例中,我們包括了一個原始碼層次的最佳化機會,也就是:表達式4 + 2可由編譯器計算先得到結果6 (這種最佳化稱為常量合併(constant folding ))。當然,還會有更複雜的情況。還是在上例中,通過將根節點右面的子樹合併為它的常量值,這個最佳化就可以直接在(注釋)語法樹上完成:儘管許多最佳化可以直接在樹上完成,但是在很多情況下,最佳化接近於彙編代碼線性化形式的樹更為簡便。這樣
節點 的變形有許多,但是三元式代碼(three-address code )(之所以這樣稱呼是因為它在存儲器中包含了3個(或3個以上)位置的地址)卻是標準選擇。另一個常見的選 擇是P -代碼(P - code ),它常用於Pascal編譯器中。在前面的例子中,原先的C表達式的三元式代碼應是:t = 4 + 2 a [ index] = t (請注意,這裡利用了一個額外的臨時變數t 存放加法的中間值)。這樣,最佳化程式就將這個代碼改進為兩步。首先計算加法的結果:t = 6 a [index] = t 接著,將t替換為該值以得到三元語句 a [index] = 6 ,指出原始碼最佳化程式可能通過將其輸出稱為中間代碼(intermediate code )來使用三元式代碼。中間代碼一直是指一種位於原始碼和目標代碼(例如三元式代碼或類似的線性表示)之間的代碼表示形式。但是,我們可以更概括地認為它是編譯器使用的原始碼的任何一個內部表示。此時,也可將語法樹稱作中間代碼,原始碼最佳化程式則確實能繼續在其輸出中使用這個表示。有時,這箇中間代碼也稱作中間表示(intermediate representation,IR)。
代碼生成 代碼生成(code generator): 代碼生成器 得到中間代碼(IR),並生成目標機器的代碼。正是在編譯的這個階段中,目標機器的特性成為了主要因素。當它存在於目標機器時,使用指令不僅是必須的而且數據的形式表示也起著重要的作用。例如,整型數據類型的
變數 和浮點數據類型的變數在存儲器中所占的位元組數或字數也很重要。在上面的示例中,現在必須決定怎樣存儲整型數來為數組
索引 生成代碼。例如,下面是所給表達式的一個可能的樣本代碼序列(在假設的彙編語言中):
M O V R0,index ;;
value of index -> R0 M U L R0,2 ;;
double value in R0 M O V R1,&a ;;
address of a -> R1 A D D R1,R0 ;;
add R0 to R1 M O V *R1,6 ;;
constant 6 -> address in R1
在以上代碼中,為編址
模式 使用了一個類似C的協定,因此& a是a的地址(也就是數組的基地址),* R1則意味著間接暫存器地址(因此最後一條指令將值6存放在R1包含的地址中)。這個代碼還假設機器執行
位元組 編址,並且整型數占據存儲器的兩個位元組(所以在第2條指令中用2作為
乘數 )。
目標代碼 目標代碼(target code optimizer ): 在這個階段中,編譯器嘗試著改進由代碼生成器生成的目標代碼。這種改進包括選擇編址模式以提高性能、將速度慢的指令更換成速度快的,以及刪除多餘的操作。在上面給出的樣本目標代碼中,還可以做許多更改:在第2條指令中,利用移位指令替代乘法(通常地,乘法很費時間),還可以使用更有效的編址模式(例如用索引地址來執行數組 存儲)。使用了這兩種最佳化後,目標代碼就變成:
MOV R0,index ;;
value of index -> R0 SHL R0 ;;
double value in R0 MOV &a[R0],6 ;;
constant 6 -> address a + R0
到這裡就是編譯原理的簡要描述,但還應特彆強調編譯器在其結構細節上差別很大。
數據結構 編譯原理一直是計算機學習的必修課.
當然,由編譯器的階段使用的算法與支持這些階段的
數據結構 之間的互動是非常強大的。編譯器的編寫者儘可能有效實施這些方法且不引起複雜性。理想的情況是:與程式大小成線性比例的時間內編譯器,換言之就是,在0 ( n )時間內,n是程式大小的度量(通常是字元數)。本節將講述一些主要的數據結構,它們是其操作部分階段所需要的,並用來在階段中交流信息。
記號 記號(token): 當掃描程式將字元收集到一個
記號 中時,它通常是以符號表示這個記號;這也就是說,作為一個枚舉數據類型的值來表示源程式的記號集。有時還必須保留字元串本身或由此派生出的其他信息(例如:與標識符記號相關的名字或數字記號值)。在大多數語言中,掃描程式一次只需要生成一個記號(這稱為單符號先行(single symbol lookahead))。在這種情況下,可以用
全程變數 放置記號信息;而在別的情況(最為明顯的是FORTRAN)下,則可能會需要一個記號數組。
語法樹 語法樹(syntax tree): 如果分析程式確實生成了語法樹,它的構造通常為基於
指針 的標準結構,在進行分析時動態分配該結構,則整棵樹可作為一個指向根節點的單個變數保存。結構中的每一個節點都是一個
記錄 ,它的域表示由分析程式和之後的語義分析程式收集的信息。例如,一個表達式的數據類型可作為表達式的語法樹節點中的域。有時為了節省空間,這些域也是動態分配或存放在諸如符號表的其他數據結構中,這樣就可以有選擇地進行分配和釋放。實際上,根據它所表示的語言結構的類型(例如:表達式節點對於語句節點或聲明節點都有不同的要求),每一個語法樹節點本身都可能要求存儲不同的屬性。在這種情況下,可由不同的記錄表示語法樹中的每個節點,每個節點類型只包含與本身相關的信息。
符號表 符號表(symbol table): 這個數據結構中的信息與標識符有關:
函式 、
變數 、
常量 以及數據類型。符號表幾乎與編譯器的所有階段
互動 :掃描程式、分析程式或將標識符輸入到表格中的語義分析程式;語義分析程式將增加數據類型和其他信息;最佳化階段和代碼生成階段也將利用由符號表提供的信息選 出恰當的代碼。因為對符號表的訪問如此頻繁,所以插入、刪除和訪問操作都必須比常規操作更有效。儘管可以使用各種樹的結構,但雜湊表卻是達到這一要求的標準數據結構。有時在一個列表或棧中可使用若干個表格。
常數表 常數表(literal table): 常數表的功能是存放在程式中用到的常量和字元串,因此快速插入和查找在常數表中也十分重要。但是,在其中卻無需刪除,這是因為它的數據全程套用於程式而且常量或字元串在該表中只出現一次。通過允許重複使用常量和字元串,常數表對於縮小程式在存儲器中的大小顯得非常重要。在代碼生成器中也需要常數表來構造用於常數和在目標代碼檔案中輸入數據定義的符號地址。
中間代碼 中間代碼(intermediate code): 根據中間代碼的類型(例如三元式代碼和P -代碼)和最佳化的類型,該代碼可以是文本串的數組、臨時文本檔案或是結構的連線列表。對於進行複雜最佳化的編譯器,應特別注意選擇允許簡單重組的表示。
臨時檔案 臨時檔案(temporary file): 計算機過去一直未能在編譯器時將整個程式保留在存儲器中。這一問題已經通過使用
臨時檔案 來保存翻譯時中間步驟的結果或通過“匆忙地”編譯(也就是只保留源程式早期部分的足夠信息用以處理翻譯)解決了。存儲器的限制現在也只是一個小問題了,現在可以將整個編譯單元放在存儲器之中,特別是在可以分別編譯的語言中時。但是偶爾還是會發現需要在某些運行步驟中生成中間檔案。其中典型的是代碼生成時需要反填(backpatch)地址。例如,當翻譯如下的條件語句時 if x = 0 then ... else ... 在知道else部分代碼的位置之前必須由文本跳到else部分:
CMP X,0 JNE NEXT ;;
location of NEXT not yet known < code for then-part > NEXT : < code for else-part >
通常,必須為NEXT的值留出一個空格,一旦知道該值後就會將該空格填上,利用臨時檔案可以很容易地做到這一點。
如果想利用上面的編譯原理開發一套屬於自己的程式語言,或者想在一個產品中嵌入程式語言,可以參考zengl開源網開發的zengl程式語言,該程式語言為國人使用C語言開發,裡面包含兩個部分,一個是編譯器,一個是解釋執行中間代碼的虛擬機。編譯器包含了詞法掃描,語法分析,中間代碼輸出等,虛擬機則類似JAVA一樣解釋執行中間代碼。作者將所有的版本都公布出來,好讓讀者可以由淺入深的做研究,並且為了證明該程式語言的實用性,還結合SDL遊戲開發庫開發了一款圖形界面和命令行界面的21點撲克小遊戲。
zengl程式語言目前適用平台為windows和linux (最開始在Linux下使用gcc開發,後來移植到windows平台)
其他問題 可從許多不同的角度來觀察編譯器的結構,還有其他一些可能的觀點:編譯器的
物理結構 、操作的順序等等。由於編譯器的結構對其可靠性、有效性、可用性以及可維護性都有很大的影響,所以編譯器的編寫者應熟悉儘可能多的有關編譯器結構的觀點。
分析和綜合 在這個觀點中,已將分析源程式以計算其特性的編譯器操作歸為編譯器的
分析 (analysis) 部分,而將生成翻譯代碼時所涉及到的操作稱作編譯器的綜合(synthesis )部分。當然,詞法分析、語法分析和語義分析均屬於分析部分,而代碼生成卻是綜合部分。在最佳化步驟中,分析和綜合都有。分析正趨向於易懂和更具有數學性,而綜合則要求更深的專業技術。因此,將分析步驟和綜合步驟兩者區分開來以便發生變化時互不影響是很有用的。
前端和後端 本觀點認為,將編譯器分成了只依賴於源語言(
前端 (front end ))的操作和只依賴於目標語言(
後端 (back end ))的操作兩部分。這與將其分成分析和綜合兩部分是類似的:掃描程式、分析程式和語義分析程式是前端,代碼生成器是後端。但是一些最佳化分析可以依賴於目標語言,這樣就是屬於後端了,然而中間代碼的綜合卻經常與目標語言無關,因此也就屬於前端了。在理想情況下,編譯器被嚴格地分成這兩部分,而中間表示則作為其間的交流媒介。這一結構對於編譯器的
可移植性 (portability)十分重要,此時設計的編譯器既能改變原始碼(它涉及到重寫前端),又能改變目標代碼(它還涉及到重寫後端)。在實際中,這是很難 做到的,而且稱作可移植的編譯器仍舊依賴於源語言和目標語言。其部分原因是程式設計語言和機器構造的快速發展以及根本性的變化,但是有效地保持移植一個新的目標語言所需的信息 或使數據結構普遍地適合改變為一個新的源語言所需的信息卻十分困難。然而人們不斷分離前端和後端的努力會帶來更方便的可移植性。
遍 編譯器發現,在生成代碼之前多次處理整個源程式很方便。這些重複就是
遍 ( pass)。首遍是從源中構造一個語法樹或中間代碼,在它之後的遍是由處理中間表示、向它增加信息、更換結構或生成不同的表示組成。遍可以和階段相應,也可無關-遍中通常含有若干個階段。實際上,根據語言的不同,編譯器可以是一遍(one pass )-所有的階段由一遍完成,其結果是編譯得很好,但(通常)代碼卻不太有效。
Pascal語言 和C 語言均允許單遍編譯。(Modula - 2語言的結構則要求編譯器至少有兩遍)。大多數帶有最佳化的編譯器都需要超過一遍:典型的安排是將一遍用於
掃描 和分析,將另一遍用於語義分析和原始碼層最佳化,第3遍用於代 碼生成和目標層的最佳化。更深層的最佳化則可能需要更多的遍:5遍、6遍、甚至8遍都是可能的。
語言定義和編譯器 程式設計語言的詞法和語法結構通常用形式的術語指定,並
使用正則表達式 和上下文無關文法。但是,程式設計語言的語義通常仍然是由英語(或其他的自然語言)描述的。這些描述(與形式的詞法及語法結構一起)一般是集中在一個語言參考手冊(language reference manual )或語言定義(language definition)之中。因為編譯器的編寫者掌握的技術對於語言的定義有很大的影響,所以在使用了一種新的語言之後,語言的定義和編譯器同時也能夠得到開發。類似地,一種語言的定義對於構造編譯器所需的技術也有很 大的關係。編譯器的編寫者更經常遇到的情況是:正在實現的語言是眾所周知的並已有了語言定義。有時這個語言定義已達到了某個語言標準(language standard )的層次,語言標準是指得到諸如
美國國家標準協會 (American National Standards Institute ,
ANSI )或
國際標準化組織 (International Organization for Standardization,ISO )的官方標準組織批准的標準。FORTRAN、 Pascal和C語言就具有ANSI標準,
Ada 有一個通過了美國政府批准的標準。在這種情況下,編譯器的編寫者必須解釋語言的定義並執行符合語言定義的編譯器。通常做到這一點並不容易, 但是有時由於有了標準測試程式集(測試組(test suite )),就能夠測試編譯器(Ada有這樣一個測試組),這又變得簡單起來了。有時候,一種語言可從
數學術語 的形式定義(formal definition )中得到它的語義。現在人們已經使用了許多方法,儘管一個稱作表示語義(denotational semantics )的方法已經成為較為常用的方法,在函式編程共同體中尤為如此,但現在仍然沒有一種可成為標準的方法。當語言有一個形式定義時,那么在理論上就有可能給出編譯器與該定義一致的
數學證明 ,但是由於這太難了,而幾乎從未有人做過。無論怎樣, 運行時環境的結構和行為是尤其受到語言定義影響的
編譯器構造 的一個方面。