複製鏈接
請複製以下鏈接發送給好友

編譯原理

(計算機專業課程)

編輯 鎖定
編譯原理是計算機專業的一門重要專業課,旨在介紹編譯程序構造的一般原理和基本方法。內容包括語言和文法、詞法分析、語法分析、語法制導翻譯、中間代碼生成、存儲管理、代碼優化和目標代碼生成。 編譯原理是計算機專業設置的一門重要的專業課程。編譯原理課程是計算機相關專業學生的必修課程和高等學校培養計算機專業人才的基礎及核心課程,同時也是計算機專業課程中最難及最挑戰學習能力的課程之一。編譯原理課程內容主要是原理性質,高度抽象 [1] 
中文名
編譯原理 [1] 
外文名
Compilers: Principles, Techniques, and Tools [1] 
領    域
計算機專業的一門重要專業課 [1] 

編譯原理基本概念

編輯
編譯原理即是對高級程序語言進行翻譯的一門科學技術, 我們都知道計算機程序由程序語言編寫而成, 在早期計算機程序語言發展較為緩慢, 因為計算機存儲的數據和執行的程序都是由0、1代碼組合而成的, 那麼在早期程序員編寫計算機程序時必須十分了解計算機的底層指令代碼通過將這些微程序指令組合排列從而完成一個特定功能的程序, 這就對程序員的要求非常高了。人們一直在研究如何如何高效的開發計算機程序, 使編程的門檻降低。 [2] 

編譯原理編譯器

編輯
C語言編譯器是一種現代化的設備, 其需要藉助計算機編譯程序, C語言編譯器的設計是一項專業性比較強的工作, 設計人員需要考慮計算機程序繁瑣的設計流程, 還要考慮計算機用户的需求。計算機的種類在不斷增加, 所以, 在對C語言編譯器進行設計時, 一定要增加其適用性。C語言具有較強的處理能力, 其屬於結構化語言, 而且在計算機系統維護中應用比較多, C語言具有高效率的優點, 在其不同類型的計算機中應用比較多。 [3] 

編譯原理C語言編譯器前端設計

編譯過程一般是在計算機系統中實現的, 是將源代碼轉化為計算機通用語言的過程。編譯器中包含入口點的地址、名稱以及機器代碼。編譯器是計算機程序中應用比較多的工具, 在對編譯器進行前端設計時, 一定要充分考慮影響因素, 還要對詞法、語法、語義進行分析。 [3] 
1 詞法分析 [3] 
詞法分析是編譯器前端設計的基礎階段, 在這一階段, 編譯器會根據設定的語法規則, 對源程序進行標記, 在標記的過程中, 每一處記號都代表着一類單詞, 在做記號的過程中, 主要有標識符、關鍵字、特殊符號等類型, 編譯器中包含詞法分析器、輸入源程序、輸出識別記號符, 利用這些功能可以將字號轉化為熟悉的單詞。 [3] 
2 語法分析 [3] 
語法分析是指利用設定的語法規則, 對記號中的結構進行標識, 這包括句子、短語等方式, 在標識的過程中, 可以形成特殊的結構語法樹。語法分析對編譯器功能的發揮有着重要影響, 在設計的過程中, 一定要保證標識的準確性。 [3] 
3 語義分析 [3] 
語義分析也需要藉助語法規則, 在對語法單元的靜態語義進行檢查時, 要保證語法規則設定的準確性。在對詞法或者語法進行轉化時, 一定要保證語法結構設置的合法性。在對語法、詞法進行檢查時, 語法結構設定不合理, 則會出現編譯錯誤的問題。前端設計對精確性要求比較好, 設計人員能夠要做好校對工作, 這會影響到編譯的準確性, 如果前端設計存在失誤, 則會影響C語言編譯的效果。 [3] 

編譯原理C語言編譯器總體設計

C語言編譯器是一種先進的設備, 其可以將繁瑣複雜的程序轉換為機器語言, 具有化繁為簡的功能, 在對C語言編譯器進行劃分的過程中, 需要了解語法構成原理, 設計人員需要靈活掌握語言語法知識, 還要應用C語言代碼轉化方式, 在對C語言編譯器進行總體設計時, 需要從以下幾個方面入手。 [3] 
1 詞法分析 [3] 
C語言程序具有一定的複雜性, 語法分析是編譯的初級階段, 這一過程主要是對詞法進行掃描, 所以詞法分析階段, 編譯器也被用作是掃描器, 其主要的任務是將源程序中的字符進行連接, 並且對其中的詞語進行識別, 並且對詞彙進行轉化, 將其轉換為內部編碼, 並且對其語法進行分析與標記。單詞符號在編譯的過程中, 一般會被轉化為二元式, 單詞類別主要有二進制、分隔符、單詞等, 計算機在正常工作時, 會通過掃描器自動完成詞法掃描工作, 這一過程也會自動將註釋進行刪除, 會將源程序中的單詞進行自動識別, 還會將其轉換為內部編碼。從工作方式角度來分析, 編譯流程與語法屬於兩種接口方式, 若是從功能上講, 編譯器詞法分分析的過程主要就是將相應的字符源程序進行轉換處理, 從而變成單詞串的形式。 [3] 
2 語義分析 [3] 
將編譯程序轉換為一種內部表現形式後, 我們將該種內部表現形式稱之為中間語言或者是中間代碼, 它含義明確、結構簡單, 屬於一種記號系統。比如一些編譯程序, 基本上沒有中間代碼, 但是為了在實際應用中, 確保機器的獨立運行, 易於實現目標代碼的優化, 在許多的編譯程序中均設置了中間語言。這種中間語言介於機器語言和源程序語言中, 程序相對複雜, 而C語言編譯器卻在很大程度上改變以上現狀, 其語義分析和語法分析相對成熟, 理論和算法比較完善, 可仍舊存在的問題是沒有公認的形式系統, 中間代碼仍舊接近於形式化的方法。 [3] 
3 語法分析 [3] 
語法分析主要是以單詞串形式的源程序作為分析與輸入對象, 其最為根本的目標和任務就是為了以設計語言的語法規則為標準, 對源程序的語法結構進行具體的分析, 根據設計語言的語法規則, 對組成這些源程序的語法成分進行分析, 如函數、下標變量、各種程序語句、各種表達式等等, 並且要通過正確性的語法檢查, 將中間代碼進行階段處理。但是要注意的一點是根據需要進行了歸約處理, 必然存在着相應語法錯誤, 那麼可以將其中全部輸入的符號刪除, 改變上述格局, 進行移進和歸約分析, 並且在此基礎上, 不斷地尋找一個相應的策略, 從而形成有效的語法分析方法。 [3] 

編譯原理編譯原理課程

編輯
《編譯原理》作為計算機專業的一門重要專業課程, 是日後深入研究專業領域知識的基礎。這門課作為計算機科學與技術的專業課, 融合了離散數學、數據結構、操作系統、計算機組成原理等多個學科的知識, 屬於綜合性與理論性較強的一門課, 由於編譯原理課程內容的以上特點, 目前在實驗教學中仍存在一些問題。編譯原理實驗部分若要設計製作完整的編譯器, 實驗週期長, 涉及的模塊較多, 各模塊間銜接較複雜, 不易立即看到整體效果。 [4] 

編譯原理傳統編譯原理課程教學中存在的問題

計算機類專業本科生學習本專業的第一門語言課程是C語言。C語言由於其類型不安全性, 容易出現一些難以捉摸的錯誤, 使得學生難以定位和解決問題。如果能讓學生根據編譯器提供的提示信息, 精確定位程序中的錯誤類型和位置, 把編譯原理中所學用於實際C語言編程需求, 這既完成了課程的教學內容, 也提升了學生的軟件編程和系統分析的能力。 [5] 
從普通高等院校的編譯原理教學實際出發, 其課程覆蓋範圍一般僅限於編譯器的前端, 即詞法分析語法分析和語法制導翻譯等內容。這其中包括大量抽象且邏輯複雜的理論知識點, 如形式語言理論、正規式、有限自動機、上下文無關文法、屬性文法和語法制導翻譯等。傳統的教學方式強調知識點的灌輸, 讓學生解決孤立的單一問題, 缺乏各知識點之間的關聯。這種“只見樹木, 不見森林”的教學方式會極大地削弱學生的學習積極性, 導致整體效果不佳。 [5] 

編譯原理以實踐為導向的互助式編譯原理教學

(一) 理論與實踐相銜接 [6] 
理論知識的來源一般都有其確定的問題背景。脱離實際問題來進行理論教學, 對學生實際能力的提升沒有益處。編譯原理課程中的大量理論知識, 存在一種銜接遞進的關係, 每個知識點的引入和拓展, 都是對於現實遇到問題的解決路徑再現。因此, 整個授課過程就在重現這種解決方案演變的變化歷程。而實現這一目標的關鍵之處, 是教師從之前的“站到講台前”變到現在的“坐在學生中”。這一變化絕不僅僅是簡單地將所有問題留給學生, 從“講授”變成“答疑”, 而是從問題設計、思考啓迪、討論引導到過程管理等各方面都對教師提高了要求。特別是現代高級語言發展日新月異, 各種新問題層出不窮, 如何在面對開放性的未知問題時, 從系統和整體的角度給出學生解決問題的方式方法, 而不是給出具體每個問題的回答, 這是對教師能力的一種新考驗。 [6] 
(二) 編譯器設計實現方案 [6] 
編譯原理課程教學理想情況, 學生應該能夠獨立自主完成小型編譯系統的構造。實際教學中, 學生只需吃透關鍵的幾條原理知識, 如NFA的確定化, LL (1) 文法中FIRST和FOLLOW集合的構造,LR (1) 文法中識別活前綴DFA構造等, 基本上已經滿足了課程考試要求。然而, 僅靠理論學習對實現一個基礎編譯器來説是遠遠不足的。相比較於學生對理論知識的接受程度, 學生自主動手完成編譯系統的能力缺乏就更為明顯。如何面對全體學生, 制定出一套適用的實踐方案, 是課程實際效用的關鍵。 [7] 

編譯原理編譯技術的發展

編輯
在早期馮諾依曼計算機時期 (20世紀40年代) 程序都是以機器語言編寫, 機器語言就是實際存儲的01代碼, 編寫程序是十分枯燥乏味的。後來彙編語言代替機器語言一符號形式該處操作指令和地址編碼。但彙編語言仍有許多缺點, 閲讀理解起來很難, 而且必須依賴於特定的機器, 如果想使編寫好的程序在另一台計算機上運行必須重寫。在20世紀50年代IBM的John Backus帶領一個研究小組對FORTRAN高級語言及其編譯器進行開發。編譯程序的自動生成工具初現端倪, 現在很多自動生成工具已經廣泛使用例如語法分析工具LEX, 語言分析程序YACC等。在20世紀60年代人們不斷的用自編譯技術構造編譯程序, 即用被編譯的語言本身來實現該語言的編譯程序, 但其基本原理和結構大體相同。經過不斷髮展現代編譯技術已經較為成熟, 多種高級語言發展迅速都離不開編譯技術的進步。 [2] 

編譯原理編譯的基本流程

編輯
編譯可以分為五個基本步驟:詞法分析、語法分析、語義分析中間代碼的生成、優化、目標代碼的生成。這是每個編譯器都必須的基本步驟和流程, 從源頭輸入高級語言源程序輸出目標語言代碼。 [2] 
1 詞法分析 [2] 
詞法分析器是通過詞法分析程序對構成源程序的字符串從左到右的掃描, 逐個字符地讀, 識別出每個單詞符號, 識別出的符號一般以二元式形式輸出, 即包含符號種類的編碼和該符號的值。詞法分析器一般以函數的形式存在, 供語法分析器調用。當然也可以一個獨立的詞法分析器程序存在。完成詞法分析任務的程序稱為詞法分析程序或詞法分析器或掃描器。 [2] 
2 語法分析 [2] 
語法分析是編譯過程的第二個階段。這階段的任務是在詞法分析的基礎上將識別出的單詞符號序列組合成各類語法短語, 如“語句”, “表達式”等.語法分析程序的主要步驟是判斷源程序語句是否符合定義的語法規則, 在語法結構上是否正確。而一個語法規則又稱為文法, 喬姆斯基將文法根據施加不同的限制分為0型、1型、2型、3型文法, 0型文法又稱短語文法, 1型稱為上下文有關文法, 2型稱為上下文無關文法, 3型文法稱為正規文法, 限制條件依次遞增。 [2] 
3 語義分析 [2] 
詞法分析注重的是每個單詞是否合法, 以及這個單詞屬於語言中的哪些部分。語法分析的上下文無關文法注重的是輸入語句是否可以依據文法匹配產生式。那麼, 語義分析就是要了解各個語法單位之間的關係是否合法。實際應用中就是對結構上正確的源程序進行上下文有關性質的審查, 進行類型審查等。 [2] 
4 中間代碼生成與優化 [2] 
在進行了語法分析和語義分析階段的工作之後, 有的編譯程序將源程序變成一種內部表示形式, 這種內部表示形式叫做中間語言或中間表示或中間代碼。所謂“中間代碼”是一種結構簡單、含義明確的記號系統, 這種記號系統複雜性介於源程序語言和機器語言之間, 容易將它翻譯成目標代碼。另外, 還可以在中間代碼一級進行與機器無關的優化。 [2] 
5 目標代碼的生成 [2] 
根據優化後的中間代碼, 可生成有效的目標代碼。而通常編譯器將其翻譯為彙編代碼, 此時還需要將彙編代碼經彙編器彙編為目標機器的機器語言。 [2] 
6 出錯處理 [2] 
編譯的各個階段都有可能發現源碼中的錯誤, 尤其是語法分析階段可能會發現大量的錯誤, 因此編譯器需要做出錯處理, 報告錯誤類型及錯誤位置等信息。 [2] 

編譯原理編譯過程概述

編輯
C語言的源程序和對應的可執行程序執行時在內存中的運行結構,實現這一轉換的最主要的過程就是編譯。 [8] 
源程序是給人看的,本質上就是文本文件,可以用Linux中的vi或Windows中的記事本之類的文本編輯程序打開、編寫,但計算機無法直接執行源程序,需要通過一個專門的程序將源程序編譯為計算機可執行程序,這個專門的程序就是編譯器。編譯過程主要分為詞法分析、語法分析、中間代碼生成、目標代碼生成(忽略預處理、語義分析、優化等)。下面我們依次簡要講解編譯的主要過程。 [8] 

編譯原理詞法分析

人眼中看到的源代碼是這樣的: [8] 

int fun(int a,int b);

int m=10;

int main()

{

   int i=4;
  
    int j=5;
   
    m = fun(i,j);
    
    return 0;

}

int fun(int a,int b)

{
 
  int c=0;
  
  c=a+b;
   
  return c;

}

而它在計算機中存儲的形式如圖1-36所示。 [8] 
圖1-36 案例程序的十六進制形式 [8] 
這裏看不出關鍵字、運算符、標識符,甚至看不出哪幾個字符屬於同一個符號。編譯的第一階段是詞法分析,目的就是在連續的字符中識別出一個一個的符號,並儘可能地識別出符號的屬性。 [8] 
人們在看C語言源程序時,藉助空格、括號等一眼就可以看出標識符、關鍵字。與人相比,現在計算機的智能還是相當低的,無法像人那樣同時看多個字符,只能依據一個非常機械的“電子版”詞法,一個字符一個字符地識別。“電子版”詞法是將狀態轉換圖的思路融匯在詞法分析器的代碼中得以體現的。詞法分析器從源程序的字符串中識別出一個個符號(token),並按序保存。 [8] 
詞法分析的結果如圖1-37所示。 [8] 
圖1-37 詞法分析的結果 [8] 
在詞法分析階段能夠識別出一些符號的含義,它們包括關鍵字、數字、字符串、分隔符,這些符號的含義不需要其他符號的輔助就能確定本身的含義。比如,“int”一定代表整數類型,它不可能是一個變量名稱,也不可能是一個運算符。 [8] 
而另外一些符號需要通過前後的其他符號才能確定出準確含義。比如“m”,在詞法階段僅能判斷這是一個標識符,但是如果不對所在的句做分析,就無法得知這個標識符代表一個變量還是一個函數。更多詳細的信息需要對符號所在的句型做分析才能獲得。這部分工作由語法分析來完成。 [8] 

編譯原理語法分析

如果説詞法分析的作用是從連續的字符中識別出標識符、關鍵字、數字、運算符並存儲為符號(token)流,語法分析的作用就是從詞法分析識別出的符號流中識別出符合C語言語法的語句。 [8] 
因為計算機無法像人那樣同時看多個標識符、關鍵字、數字、運算符,無法像人那樣一眼看出這是一個函數聲明,那是一個if語句,只能非常笨拙地一個符號一個符號去識別。與詞法分析器有些類似,語法分析器也是依據用計算機表示的語法,一個符號一個符號地識別出符合C語言語法的語句。語法的計算機表示就是產生式。在語法分析器中把通過產生式產生的C語言語法映射成一套模板,並把這套模板融匯在語法分析器的程序中。語法分析器的作用就是將詞法分析器識別出的符號(token)一個一個地與這套模板進行匹配,匹配上這套模板中的某個語法,就可以識別出一句完整的語句,並確定這條語句的語法。 [8] 
我們以案例中“int fun(int a,int b);”這條函數聲明語句為例描述這個過程,它與語句模板的匹配情景如圖1-38所示。 [8] 
圖1-38 fun函數聲明語句與模板匹配的結果 [8] 
這段token流最終與函數聲明模板相匹配,在匹配成功後,計算機就認為此語句為函數聲明語句,並以語法樹的形式在內存中記錄下來,情景如圖1-39所示。 [8] 
圖1-39 fun函數聲明語句生成的語法樹 [8] 
以樹型結構來記錄分析出的語句是一個非常巧妙、深謀遠慮、通盤考慮的選擇。一方面,樹型結構能夠“記住”源程序全部的“意思”,另一方面,樹型結構更容易對應到運行時結構。 [8] 

編譯原理從語法樹到中間代碼再到目標代碼

至此,語法樹已經承載了源程序的全部信息,後續的轉換工作就和源程序沒關係了。 [8] 
如果希望一步到位,從語法樹轉換為目標代碼,理論上和實際上都是可行的。但計算機存在多種CPU硬件平台,考慮到程序在不同CPU之間的可移植性,先轉換成一個通用的、抽象的“CPU指令”,這就是中間代碼最初的設計思想。然後根據具體選定的CPU,將中間代碼落實到具體CPU的目標代碼。 [8] 
語法樹是個二維結構,中間代碼是準一維結構,語法樹到中間代碼的轉換過程,本質上是將二維結構轉換為準一維結構的過程。中間代碼特別是RTL已經可以和運行時結構一一對應了。如圖1-40所示。 [8] 
圖1-40 中間代碼與目標代碼對應的情景示意 [8] 
運行時結構也是一維的,圖1-40左側部分的轉換結果將更貼近運行時結構。 [8] 
選定具體的CPU、操作系統後,中間代碼就可以轉換為目標代碼——彙編代碼(我們配置的是AT&T彙編),這時操作系統的影響還比較小。然後由彙編器依照選定操作系統的目標文件格式,將.s文件轉換為具體的目標文件,對於Linux而言是.o文件,對於Windows而言是.obj文件。目標文件中已經是選定的CPU的機器指令了。 [8] 
最後鏈接器把一個或多個目標文件(庫文件本質上也是目標文件)鏈接成符合選定操作系統指定格式的可執行文件。 [8] 
通過操作系統,可執行程序就可以被載入內存執行,形成前兩節我們所看到的運行時結構。 [8] 
本書後續內容將詳細講解編譯的主要過程:詞法分析、語法分析、中間代碼到目標代碼,然後是彙編與鏈接,最後講解預處理。 [8] 
參考資料