編譯原理知識點總結
編譯原理知識點總結
編譯原理是大學計算機專業的必修科目，也是計算機的基礎知識，學好編譯原理，有助於更好的進行程式設計的操作，下面是編譯原理知識點總結，一起來看看吧！
編譯原理知識點總結
一 編譯器
簡單講，編譯器就是將“高階語言”翻譯為“機器語言(低階語言)”的程式。一個現代編譯器的主要工作流程:原始碼 (source code) → 預處理器
(preprocessor) → 編譯器 (compiler) → 彙編程式 (assembler) → 目的碼 (object code) → 連結器(Linker) → 可執行程式 (executables)
二 工作原理
編譯是從原始碼(通常為高階語言)到能直接被計算機或虛擬機器執行的目的碼(通常為低階語言或機器語言)的翻譯過程。然而，也存在從低階語言到高階語言的編譯器，這類編譯器中用來從由高階語言生成的低階語言程式碼重新生成高階語言程式碼的又被叫做反編譯器。
也有從一種高階語言生成另一種高階語言的編譯器，或者生成一種需要進一步處理的的中間程式碼的編譯器(又叫級聯)。
典型的編譯器輸出是由包含入口點的名字和地址， 以及外部呼叫(到不在這個目標檔案中的函式呼叫)的機器程式碼所組成的目標檔案。一組目標檔案，不必是同一編譯器產生，但使用的編譯器必需採用同樣的輸出格式，可以連結在一起並生成可以由使用者直接執行的可執行程式
三 編譯器的發展史
(1) 20世紀50年代
IBM的John Backus帶領一個研究小組對FORTRAN語言及其編譯器進行開發。但由於當時人們對編譯理論瞭解不多，開發工作變得既複雜又艱苦。與此同時，Noam Chomsky開始了他對自然語言結構的研究。他的發現最終使得編譯器的結構異常簡單，甚至還帶有了一些自動化。Chomsky的`研究導致了根據語言文法的難易程度以及識別它們所需要的演算法來對語言分類。正如現在所稱的Chomsky架構(Chomsky Hierarchy)，它包括了文法的四個層次:0型文法、1型文法、2型文法和3型文法，且其中的每一個都是其前者的特殊情況。2型文法(或上下文無關文法)被證明是程式設計語言中最有用的，而且今天它已代表著程式設計語言結構的標準方式。分析問題(parsing problem，用於上下文無關文法識別的有效演算法)的研究是在60年代和70年代，它相當完善的解決了這個問題。現在它已是編譯原理中的一個標準部分。
有限狀態自動機(Finite Automaton)和正則表示式(Regular Expression)同上下文無關文法緊密相關，它們與Chomsky的3型文法相對應。對它們的研究與Chomsky的研究幾乎同時開始，並且引出了表示程式設計語言的單詞的符號方式。
人們接著又深化了生成有效目的碼的方法，這就是最初的編譯器，它們被一直使用至今。人們通常將其稱為最佳化技術(Optimization Technique)，但因其從未真正地得到過被優化了的目的碼而僅僅改進了它的有效性，因此實際上應稱作程式碼改進技術(Code Improvement Technique)。
當分析問題變得好懂起來時，人們就在開發程式上花費了很大的功夫來研究這一部分的編譯器自動構造。這些程式最初被稱為編譯器的編譯器(Compiler-compiler)，但更確切地應稱為分析程式生成器(Parser Generator)，這是因為它們僅僅能夠自動處理編譯的一部分。這些程式中最著名的是Yacc(Yet Another Compiler-compiler)，它是由Steve Johnson在1975年為Unix系統編寫的。類似的，有限狀態自動機的研究也發展了一種稱為掃描程式生成器(Scanner Generator)的工具，Lex(與Yacc同時，由Mike Lesk為Unix系統開發)是這其中的佼佼者。
在70年代後期和80年代早期，大量的專案都貫注於編譯器其它部分的生成自動化，這其中就包括了程式碼生成。這些嘗試並未取得多少成功，這大概是因為操作太複雜而人們又對其不甚瞭解。
(2) 國內編譯器的研發歷史
我國編譯器研發工作起步並不算晚，早在60年代初期，董韞美院士和楊芙清院士就分別在中科院和北大領導研究組開發編譯器，那時面向的高階語言是ALGOL和FORTRAN，目標機是國產機。
在改革開放前，由於國家需要，中科院、國防科大、江南計算所、北大等單位一直在研製國產計算機，包括大型機和高效能計算機(如向量機、並行機)，相應的也在研製高階語言編譯器。中科院計算所以董韞美院士領導的研究組先後開發了119機、109機的類 ALGOL語言編譯器BCY。國防科大開發了向量編譯器和向量識別器。
70年代中科院計算所張兆慶教授研究組(以後稱ACTGroup)開始在國產機上研製FORTRAN語言編譯器，先後參與了眾多的院級和國家級科研攻關專案，主持開發了013，757，KJ8920等國產大型機系統中的FORTRAN語言編譯器，所研製的編譯器支援了數百萬行應用軟體的執行。
90年代以來ACTGroup承擔科學院重大專案，國家攻關專案，863專案，以及國際合作專案，先後開發了共享記憶體多處理機的並行識別器，分散式記憶體多處理機的並行識別器， SIMD晶片和VLIW晶片的並行最佳化C編譯器。將編譯技術與圖形學結合，ACTGroup還推出了整合化、視覺化的並行程式設計環境。ACTGroup在先進編譯技術和並行程式設計環境方面的研究工作獲國內外專家高度評價，國際著名學者評價此研究組居編譯領域的世界先進行列。
(3) 研究現狀
編譯器設計最近的發展包括:首先，編譯器包括了更加複雜演算法的應用程式它用於推斷或簡化程式中的資訊;這又與更為複雜的程式設計語言的發展結合在一起。其中典型的有用於函式語言編譯的Hindley-Milner型別檢查的統一演算法。其次，編譯器已越來越成為基於視窗的互動開發環境(Interactive Development Environment，IDE)的一部分，它包括了編輯器、連線程式、除錯程式以及專案管理程式。這樣的IDE標準並沒有多少，但是對標準的視窗環境進行開發已成為方向。另一方面，儘管近年來在編譯原理領域進行了大量的研究，但是基本的編譯器設計原理在近20年中都沒有多大的改變，它現在正迅速地成為計算機科學課程中的中心環節。
在九十年代，作為GNU專案或其它開放原始碼專案的一部分，許多免費編譯器和編譯器開發工具被開發出來。這些工具可用來編譯所有的計算機程式語言。它們中的一些專案被認為是高質量的，而且對現代編譯理論感性趣的人可以很容易的得到它們的免費原始碼。
大約在1999年，SGI公佈了他們的一個工業化的並行化最佳化編譯器Pro64的原始碼，後被全世界多個編譯器研究小組用來做研究平臺，並命名為Open64。Open64的設計結構好，分析最佳化全面，是編譯器高階研究的理想平臺。
(4)國內編譯器開發的現狀
90年代以來，國內主要以研製並行機為主，相應的並行編譯器研製也在國內開展起來。代表性的成果有:上海復旦大學朱傳琪教授研究組研製的面向共享儲存並行機的並行最佳化編譯器AFT達到世界領先水平。
清華大學湯志忠教授研究組在軟流水最佳化技術上做了很優秀的研究工作。清華大學鄭緯民教授研究組開發了互動式並行化系統 TIPSExplorer，北京大學許卓群教授、李曉明教授研究組在HPF(High Performance Fortran)編譯器方面做了多年工作，取得很好的研究成果。此外，國防科大、江南計算所等單位也都有從事並行編譯技術研究。隨著晶片研製，國內還有若干單位也在開展基於GCC生成面向特定晶片的編譯器工作。