軟體工程/工具/編譯器簡介

一個典型的多語言、多目標編譯器執行的示意圖。

編譯器是一個計算機程式（或一組程式），它將用程式語言編寫的原始碼（源語言）轉換為另一種計算機語言（目標語言，通常以二進位制形式稱為目的碼）。想要轉換原始碼的最常見原因是建立可執行程式。

“編譯器”這個名字主要用於將原始碼從高階程式語言轉換為低階語言（例如，組合語言或機器程式碼）的程式。如果編譯後的程式可以在其 CPU 或作業系統與編譯器執行的計算機不同的計算機上執行，則編譯器被稱為交叉編譯器。將低階語言轉換為高階語言的程式稱為反編譯器。將高階語言之間進行轉換的程式通常稱為語言翻譯器、源到源翻譯器或語言轉換器。語言重寫器通常是一個程式，它在不改變語言的情況下轉換表示式的形式。

編譯器可能會執行許多或所有以下操作：詞法分析、預處理、解析、語義分析（語法制導翻譯）、程式碼生成和程式碼最佳化。

由編譯器行為不正確引起的程式錯誤可能非常難以追蹤和解決；因此，編譯器實現者投入了大量時間來確保其軟體的正確性。

術語“編譯器編譯器”有時用於指代解析器生成器，這是一種經常用來幫助建立詞法分析器和解析器的工具。

歷史

多年來，早期計算機的軟體主要用匯編語言編寫。直到能夠在不同型別的 CPU 上重用軟體的好處開始明顯大於編寫編譯器的成本，高階程式語言才被髮明。早期計算機的記憶體容量非常有限，這也給編譯器的實現帶來了很多技術問題。

在 20 世紀 50 年代末，機器無關程式語言首次被提出。隨後，開發了幾個實驗性的編譯器。第一個編譯器是由 Grace Hopper 於 1952 年為 A-0 程式語言編寫的。IBM 的 John Backus 領導的 FORTRAN 團隊通常被認為是在 1957 年引入了第一個完整的編譯器。COBOL 是第一個在 1960 年在多個架構上編譯的早期語言。

在許多應用領域，使用高階語言的想法迅速流行起來。由於更新的程式語言支援的功能不斷擴充套件，以及計算機架構的複雜性不斷增加，編譯器變得越來越複雜。

早期的編譯器是用匯編語言編寫的。第一個自託管編譯器——能夠用高階語言編譯自己的原始碼——是由麻省理工學院的 Tim Hart 和 Mike Levin 在 1962 年為 Lisp 建立的。 自 20 世紀 70 年代以來，用它編譯的語言實現編譯器已成為慣例，儘管 Pascal 和 C 都是流行的實現語言。構建自託管編譯器是一個引導問題——針對一種語言的第一個此類編譯器必須透過用另一種語言編寫的編譯器編譯，或者（如 Hart 和 Levin 的 Lisp 編譯器）透過在直譯器中執行編譯器來編譯。

編譯器在教育中的應用

編譯器構造和編譯器最佳化作為計算機科學課程的一部分在大學和學校教授。這些課程通常輔以針對教育性程式語言的編譯器實現。一個有據可查的例子是 Niklaus Wirth 的 PL/0 編譯器，Wirth 在 20 世紀 70 年代用它來教授編譯器構造。 儘管 PL/0 編譯器很簡單，但它為該領域引入了幾個有影響力的概念

1. 逐步求精的程式開發（也是 Wirth 1971 年的一篇論文的標題）
2. 使用遞迴下降解析器
3. 使用 EBNF 指定語言語法
4. 生成可移植 P-code 的程式碼生成器
5. 使用 T-圖 正式描述引導問題

編譯

編譯器促成了機器無關程式的開發。在 20 世紀 50 年代開發出第一種高階語言 FORTRAN（FORmula TRANslator）之前，機器相關的組合語言被廣泛使用。雖然組合語言比在相同架構上的機器程式碼生成更可重用和可重定位的程式，但如果要在不同的硬體架構上執行程式，它必須被修改或重寫。

隨著 FORTRAN 之後不久高階程式語言的發展，如 COBOL、C、BASIC，程式設計師可以編寫機器無關的源程式。編譯器將高階源程式翻譯成針對特定硬體的機器語言的目標程式。目標程式生成後，使用者可以執行該程式。

編譯器的結構

編譯器連線高階語言中的源程式與底層硬體。編譯器需要 1) 確定程式語法上的正確性，2) 生成正確高效的目的碼，3) 執行時組織，以及 4) 根據彙編器和/或連結器的約定格式化輸出。編譯器由三個主要部分組成：前端、中間端和後端。

前端檢查程式在程式語言語法和語義方面是否正確編寫。這裡識別合法和非法程式。如果有錯誤，則以有用的方式報告錯誤。型別檢查也透過收集型別資訊來執行。然後前端為中間端處理生成原始碼的中間表示或IR。

中間端是進行最佳化的部分。最佳化典型的轉換是刪除無用或不可達程式碼，發現和傳播常量值，將計算重新定位到執行頻率較低的地方（例如，迴圈之外），或根據上下文專門化計算。中間端為後面的後端生成另一個 IR。大多數最佳化工作都集中在這個部分。

後端負責將中間端來的 IR 翻譯成彙編程式碼。為每個 IR 指令選擇目標指令。變數也為暫存器選擇。後端利用硬體透過弄清楚如何保持並行 FU 繁忙，填充延遲槽，等等。儘管大多數最佳化演算法都在 NP 中，但啟發式技術已經得到了很好的發展。

編譯器輸出

編譯器的一種分類是根據其生成程式碼執行的平臺。這被稱為目標平臺。

本地或託管編譯器是指其輸出旨在直接執行在與編譯器本身執行的相同型別的計算機和作業系統上的編譯器。交叉編譯器的輸出旨在執行在不同的平臺上。交叉編譯器通常用於為不支援軟體開發環境的嵌入式系統開發軟體。

編譯器生成的虛擬機器（VM）程式碼的輸出，可能或可能不會在與生成該程式碼的編譯器相同的平臺上執行。因此，此類編譯器通常不歸類為原生編譯器或交叉編譯器。

編譯型語言與解釋型語言

為了方便起見，高階程式語言通常被劃分為編譯型語言和解釋型語言。然而，在實踐中，很少有語言會要求它只能被編譯或解釋，儘管可以設計依賴於執行時重新解釋的語言。這種分類通常反映了語言最流行或最廣泛的實現——例如，BASIC有時被稱為解釋型語言，C被稱為編譯型語言，儘管存在BASIC編譯器和C直譯器。

現代趨勢，即即時編譯和位元組碼解釋，有時會模糊編譯器和直譯器的傳統分類。

一些語言規範明確規定實現必須包含編譯功能；例如，Common Lisp。然而，Common Lisp 的定義中並沒有任何固有的東西阻止它被解釋。其他語言具有在直譯器中很容易實現但使編寫編譯器變得更加困難的功能；例如，APL、SNOBOL4 和許多指令碼語言允許程式在執行時使用常規字串操作構造任意原始碼，然後透過將其傳遞給一個特殊的評估函式來執行該程式碼。為了在編譯語言中實現這些功能，程式通常必須與包含編譯器本身版本的執行時庫一起交付。

硬體編譯

一些編譯器的輸出可能會以非常低的級別針對硬體，例如現場可程式設計門陣列（FPGA）或結構化專用積體電路（ASIC）。此類編譯器被稱為硬體編譯器或綜合工具，因為它們編譯的原始碼有效地控制了硬體的最終配置及其操作方式；編譯的輸出不是按順序執行的指令——只是電晶體或查詢表的互連。例如，XST 是用於配置 FPGA 的 Xilinx 綜合工具。Altera、Synplicity、Synopsys 和其他供應商提供了類似的工具。

編譯器構建

在早期，編譯器設計採用的方法會直接受到處理複雜度、設計人員的經驗和可用資源的影響。

由一個人為相對簡單的語言編寫的編譯器可能是一塊單一的、整體的軟體。當源語言龐大而複雜，並且需要高質量的輸出時，設計可能會被分成幾個相對獨立的階段。擁有獨立的階段意味著開發可以被分成小部分，並分配給不同的人。這樣，用改進的階段替換單個階段，或者在後期插入新的階段（例如，額外的最佳化）也變得更加容易。

將編譯過程劃分為階段的做法是由卡內基梅隆大學的產品級編譯器編譯器專案 (PQCC) 提倡的。該專案引入了前端、中間端和後端這些術語。

除最小的編譯器之外，所有編譯器都具有兩個以上的階段。但是，這些階段通常被認為是前端或後端的一部分。這兩個端相遇的點存在爭議。前端通常被認為是在執行語法和語義處理的地方，以及將程式碼轉換為比原始碼更低階的表示形式。

中間端通常被設計用於對除原始碼或機器程式碼之外的形式進行最佳化。這種原始碼/機器程式碼獨立性旨在使通用最佳化能夠在支援不同語言和目標處理器的編譯器版本之間共享。

後端接收來自中間端的輸出。它可能會執行更多針對特定計算機的分析、轉換和最佳化。然後，它會為特定處理器和作業系統生成程式碼。

這種前端/中間/後端方法使得能夠將不同語言的前端與不同 CPU 的後端結合起來。這種方法的實際例子包括 GNU 編譯器集合、LLVM 和阿姆斯特丹編譯器套件，它們具有多個前端、共享分析和多個後端。

單遍編譯器與多遍編譯器

根據遍數對編譯器進行分類，其背景是計算機的硬體資源限制。編譯涉及執行大量工作，早期的計算機沒有足夠的記憶體來容納一個執行所有這些工作的程式。因此，編譯器被分成更小的程式，每個程式對原始碼（或其某種表示）進行一次遍，執行一些必要的分析和轉換。

能夠單遍編譯傳統上被視為一項優勢，因為它簡化了編寫編譯器的任務，並且單遍編譯器通常比多遍編譯器編譯得更快。因此，在一定程度上受早期系統資源限制的驅動，許多早期的語言是專門為單遍編譯而設計的（例如，Pascal）。

在某些情況下，語言特徵的設計可能要求編譯器對原始碼執行多次遍。例如，考慮在原始碼第 20 行出現的宣告，它會影響對第 10 行出現的語句的轉換。在這種情況下，第一遍需要收集有關出現在受其影響的語句之後的宣告的資訊，實際的轉換將在後續遍中進行。

單遍編譯的缺點是無法執行生成高質量程式碼所需的許多複雜最佳化。很難準確計算最佳化編譯器執行的遍數。例如，最佳化的不同階段可能會多次分析一個表示式，但可能只分析另一個表示式一次。

將編譯器分成更小的程式是研究人員感興趣的技術，旨在生成可證明正確的編譯器。證明一組小程式的正確性通常比證明一個更大的、單一的、等效程式的正確性需要更少的努力。

雖然典型的多遍編譯器在其最後一次遍中輸出機器程式碼，但還有幾種其他型別

• “源到源編譯器”是一種編譯器型別，它以高階語言作為輸入，並輸出高階語言。例如，自動並行化編譯器通常會接收高階語言程式作為輸入，然後轉換程式碼並使用並行程式碼註釋（例如 OpenMP）或語言結構（例如 Fortran 的DOALL 語句）對其進行標註。
• 階段式編譯器，編譯為理論機器的組合語言，如一些 Prolog 實現
  • 這種 Prolog 機器也被稱為 Warren 抽象機 (WAM)。
  • Java、Python 和更多語言的位元組碼編譯器也是這種型別的子型別。
• 即時編譯器，用於 Smalltalk 和 Java 系統，以及 Microsoft .NET 的通用中間語言 (CIL)
  • 應用程式以位元組碼的形式交付，該位元組碼在執行之前立即被編譯為本地機器程式碼。

前端

前端分析原始碼以構建程式的內部表示，稱為中間表示或IR。它還管理符號表，這是一種將原始碼中的每個符號對映到相關資訊（如位置、型別和範圍）的資料結構。這在幾個階段內完成，包括以下一些階段

1. 行重建。將關鍵字截斷或允許識別符號中出現任意空格的語言需要在解析之前進行一個階段，該階段將輸入字元序列轉換為解析器可用的規範形式。1960 年代使用的自頂向下、遞迴下降、表驅動的解析器通常一次讀取一個字元，並且不需要單獨的標記化階段。Atlas Autocode 和 Imp（以及 ALGOL 和 Coral 66 的一些實現）是截斷語言的例子，其編譯器將具有行重建階段。
2. 詞法分析將原始碼文字分解成稱為詞法單元的小片段。每個詞法單元是語言的單個原子單元，例如關鍵字、識別符號或符號名稱。詞法單元語法通常是正則語言，因此可以從正則表示式構建的有限狀態自動機用於識別它。此階段也稱為詞法分析或掃描，進行詞法分析的軟體稱為詞法分析器或掃描器。
3. 預處理。某些語言（例如 C）需要預處理階段，該階段支援宏替換和條件編譯。通常，預處理階段發生在語法分析或語義分析之前；例如，在 C 的情況下，預處理器操縱詞法單元而不是語法形式。但是，一些語言（如 Scheme）支援基於語法形式的宏替換。
4. 語法分析涉及解析詞法單元序列以識別程式的語法結構。此階段通常會構建一個解析樹，該解析樹用根據定義語言語法的形式語法的規則構建的樹結構替換詞法單元的線性序列。解析樹通常會被編譯器後面的階段進行分析、增強和轉換。
5. 語義分析是編譯器向解析樹新增語義資訊並構建符號表階段。此階段執行語義檢查，例如型別檢查（檢查型別錯誤）或物件繫結（將變數和函式引用與其定義相關聯）或確定性賦值（要求所有區域性變數在使用前初始化），拒絕不正確的程式或發出警告。語義分析通常需要完整的解析樹，這意味著此階段在邏輯上遵循解析階段，並在邏輯上先於程式碼生成階段，儘管在編譯器實現中通常可以將多個階段摺疊成對程式碼的一次遍歷。

後端

由於生成彙編程式碼的功能重疊，術語後端有時會與程式碼生成器混淆。一些文獻使用中間端來區分後端中的通用分析和最佳化階段與機器相關的程式碼生成器。

後端的主要階段包括以下內容

1. 分析：這是從輸入派生的中間表示中收集程式資訊的過程。典型的分析是資料流分析以構建使用-定義鏈、依賴關係分析、別名分析、指標分析、逃逸分析等。準確的分析是任何編譯器最佳化的基礎。呼叫圖和控制流圖通常也在分析階段構建。
2. 最佳化：中間語言表示被轉換為功能上等效但更快（或更小）的形式。流行的最佳化包括內聯擴充套件、死程式碼消除、常量傳播、迴圈轉換、暫存器分配甚至自動並行化。
3. 程式碼生成：將轉換後的中間語言翻譯成輸出語言，通常是系統的本機機器語言。這涉及資源和儲存決策，例如決定將哪些變數放入暫存器和記憶體，以及選擇和排程適當的機器指令以及它們相關的定址模式（另見 Sethi-Ullman 演算法）。

編譯器分析是任何編譯器最佳化的先決條件，它們緊密地協同工作。例如，依賴關係分析對於迴圈轉換至關重要。

此外，編譯器分析和最佳化的範圍差異很大，從小到一個基本塊到過程/函式級別，甚至整個程式（跨過程最佳化）。顯然，編譯器可以使用更廣闊的視野來更好地完成工作。但這種廣闊的視野並非免費的：大範圍分析和最佳化在編譯時間和記憶體空間方面成本很高；對於跨過程分析和最佳化尤其如此。

跨過程分析和最佳化在來自 HP、IBM、SGI、英特爾、微軟和 Sun Microsystems 的現代商業編譯器中很常見。開源 GCC 長期以來一直因缺乏強大的跨過程最佳化而受到批評，但它在這方面正在發生變化。另一個具有完整分析和最佳化基礎設施的開源編譯器是 Open64，它被許多組織用於研究和商業目的。

由於編譯器分析和最佳化需要額外的時間和空間，因此一些編譯器預設情況下會跳過它們。使用者必須使用編譯選項明確告訴編譯器應啟用哪些最佳化。

編譯器正確性

編譯器正確性是軟體工程的一個分支，它涉及試圖證明編譯器是否按照其語言規範執行。 這些技術包括使用形式化方法開發編譯器，以及對現有編譯器進行嚴格測試（通常稱為編譯器驗證）。

相關技術

組合語言是一種低階語言，編譯它的程式更常被稱為彙編器，而反向程式被稱為反彙編器。

將低階語言翻譯成高階語言的程式稱為反編譯器。

將高階語言相互翻譯的程式通常稱為語言翻譯器、源到源翻譯器、語言轉換器或語言重寫器。最後一個術語通常用於不涉及語言更改的翻譯。

國際會議和組織

每年，歐洲軟體理論與實踐聯合會議（ETAPS）都會贊助國際編譯器構造會議（CC），其中包含來自學術界和工業界的論文。

參考文獻

• 編譯器教科書參考 一系列主流編譯器構建教科書的參考文獻
• Aho，Alfred V.；Sethi，Ravi；Ullman，Jeffrey D.，Compilers: Principles, Techniques and Tools ISBN 0-201-10088-6 連結到出版商。也被稱為“龍書”。
• Allen，Frances E.，"IBM 語言處理器技術的歷史"，IBM 研究與開發雜誌，第 25 卷，第 5 期，1981 年 9 月。
• Allen，Randy；Kennedy，Ken，Optimizing Compilers for Modern Architectures，Morgan Kaufmann 出版社，2001 年。 ISBN 1-55860-286-0
• Appel，Andrew Wilson
  • Modern Compiler Implementation in Java，第二版。劍橋大學出版社，2002 年。 ISBN 0-521-82060-X
  • Modern Compiler Implementation in ML，劍橋大學出版社，1998 年。 ISBN 0-521-58274-1
• Bornat，Richard，理解和編寫編譯器：一個 DIY 指南，Macmillan 出版社，1979 年。 ISBN 0-333-21732-2
• Cooper，Keith D.，和 Torczon，Linda，Engineering a Compiler，Morgan Kaufmann，2004 年，ISBN 1-55860-699-8。
• Leverett；Cattel；Hobbs；Newcomer；Reiner；Schatz；Wulf，An Overview of the Production Quality Compiler-Compiler Project，在Computer 13(8):38-49 (1980 年 8 月)
• McKeeman，William Marshall；Horning，James J.；Wortman，David B.，A Compiler Generator，Englewood Cliffs，N.J.：Prentice-Hall，1970 年。 ISBN 0-13-155077-2
• Muchnick，Steven，高階編譯器設計與實現，Morgan Kaufmann 出版社，1997 年。 ISBN 1-55860-320-4
• Scott，Michael Lee，程式語言實踐，Morgan Kaufmann，2005 年，第二版，912 頁。 ISBN 0-12-633951-1 (本書作者網站).
• Srikant，Y. N.；Shankar，Priti，編譯器設計手冊：最佳化和機器程式碼生成，CRC 出版社，2003 年。 ISBN 0-8493-1240-X
• Terry，Patrick D.，編譯器和編譯器生成器：使用 C++ 的入門，國際湯姆森計算機出版社，1997 年。 ISBN 1-85032-298-8,
• Wirth，Niklaus，編譯器構建 ISBN 0-201-40353-6，Addison-Wesley，1996 年，176 頁。2005 年 11 月修訂。

外部連結

• comp.compilers 新聞組和 RSS 訂閱
• 硬體編譯郵件列表
• "如何建立編譯成 JavaScript 的語言". HackerNoon. 檢索於 2021-12-19.
• 使用 flex 和 yacc 的編譯器構建實踐介紹
• 書籍 "編譯器設計基礎" 作者：Torben Ægidius Mogensen