編譯原理

基本概念

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

編譯器

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

編譯過程一般是在計算機系統中實現的, 是将源代碼轉化為計算機通用語言的過程。編譯器中包含入口點的地址、名稱以及機器代碼。編譯器是計算機程序中應用比較多的工具, 在對編譯器進行前端設計時, 一定要充分考慮影響因素, 還要對詞法、語法、語義進行分析。

1 詞法分析

詞法分析是編譯器前端設計的基礎階段, 在這一階段, 編譯器會根據設定的語法規則, 對源程序進行标記, 在标記的過程中, 每一處記号都代表着一類單詞, 在做記号的過程中, 主要有标識符、關鍵字、特殊符号等類型, 編譯器中包含詞法分析器、輸入源程序、輸出識别記号符, 利用這些功能可以将字号轉化為熟悉的單詞。

2 語法分析

語法分析是指利用設定的語法規則, 對記号中的結構進行标識, 這包括句子、短語等方式, 在标識的過程中, 可以形成特殊的結構語法樹。語法分析對編譯器功能的發揮有着重要影響, 在設計的過程中, 一定要保證标識的準确性。

3 語義分析

語義分析也需要借助語法規則, 在對語法單元的靜态語義進行檢查時, 要保證語法規則設定的準确性。在對詞法或者語法進行轉化時, 一定要保證語法結構設置的合法性。在對語法、詞法進行檢查時, 語法結構設定不合理, 則會出現編譯錯誤的問題。前端設計對精确性要求比較好, 設計人員能夠要做好校對工作, 這會影響到編譯的準确性, 如果前端設計存在失誤, 則會影響C語言編譯的效果。

C語言編譯器是一種先進的設備, 其可以将繁瑣複雜的程序轉換為機器語言, 具有化繁為簡的功能, 在對C語言編譯器進行劃分的過程中, 需要了解語法構成原理, 設計人員需要靈活掌握語言語法知識, 還要應用C語言代碼轉化方式, 在對C語言編譯器進行總體設計時, 需要從以下幾個方面入手。

1 詞法分析

C語言程序具有一定的複雜性, 語法分析是編譯的初級階段, 這一過程主要是對詞法進行掃描, 所以詞法分析階段, 編譯器也被用作是掃描器, 其主要的任務是将源程序中的字符進行連接, 并且對其中的詞語進行識别, 并且對詞彙進行轉化, 将其轉換為内部編碼, 并且對其語法進行分析與标記。單詞符号在編譯的過程中, 一般會被轉化為二元式, 單詞類别主要有二進制、分隔符、單詞等, 計算機在正常工作時, 會通過掃描器自動完成詞法掃描工作, 這一過程也會自動将注釋進行删除, 會将源程序中的單詞進行自動識别, 還會将其轉換為内部編碼。從工作方式角度來分析, 編譯流程與語法屬于兩種接口方式, 若是從功能上講, 編譯器詞法分分析的過程主要就是将相應的字符源程序進行轉換處理, 從而變成單詞串的形式。

2 語義分析

将編譯程序轉換為一種内部表現形式後, 我們将該種内部表現形式稱之為中間語言或者是中間代碼, 它含義明确、結構簡單, 屬于一種記号系統。比如一些編譯程序, 基本上沒有中間代碼, 但是為了在實際應用中, 确保機器的獨立運行, 易于實現目标代碼的優化, 在許多的編譯程序中均設置了中間語言。這種中間語言介于機器語言和源程序語言中, 程序相對複雜, 而C語言編譯器卻在很大程度上改變以上現狀, 其語義分析和語法分析相對成熟, 理論和算法比較完善, 可仍舊存在的問題是沒有公認的形式系統, 中間代碼仍舊接近于形式化的方法。

3 語法分析

語法分析主要是以單詞串形式的源程序作為分析與輸入對象, 其最為根本的目标和任務就是為了以設計語言的語法規則為标準, 對源程序的語法結構進行具體的分析, 根據設計語言的語法規則, 對組成這些源程序的語法成分進行分析, 如函數、下标變量、各種程序語句、各種表達式等等, 并且要通過正确性的語法檢查, 将中間代碼進行階段處理。但是要注意的一點是根據需要進行了歸約處理, 必然存在着相應語法錯誤, 那麼可以将其中全部輸入的符号删除, 改變上述格局, 進行移進和歸約分析, 并且在此基礎上, 不斷地尋找一個相應的策略, 從而形成有效的語法分析方法。

課程

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

計算機類專業本科生學習本專業的第一門語言課程是C語言。C語言由于其類型不安全性, 容易出現一些難以捉摸的錯誤, 使得學生難以定位和解決問題。如果能讓學生根據編譯器提供的提示信息, 精确定位程序中的錯誤類型和位置, 把編譯原理中所學用于實際C語言編程需求, 這既完成了課程的教學内容, 也提升了學生的軟件編程和系統分析的能力。

從普通高等院校的編譯原理教學實際出發, 其課程覆蓋範圍一般僅限于編譯器的前端, 即詞法分析、語法分析和語法制導翻譯等内容。這其中包括大量抽象且邏輯複雜的理論知識點, 如形式語言理論、正規式、有限自動機、上下文無關文法、屬性文法和語法制導翻譯等。傳統的教學方式強調知識點的灌輸, 讓學生解決孤立的單一問題, 缺乏各知識點之間的關聯。這種“隻見樹木, 不見森林”的教學方式會極大地削弱學生的學習積極性, 導緻整體效果不佳。

(一) 理論與實踐相銜接

理論知識的來源一般都有其确定的問題背景。脫離實際問題來進行理論教學, 對學生實際能力的提升沒有益處。編譯原理課程中的大量理論知識, 存在一種銜接遞進的關系, 每個知識點的引入和拓展, 都是對于現實遇到問題的解決路徑再現。因此, 整個授課過程就在重現這種解決方案演變的變化曆程。而實現這一目标的關鍵之處, 是教師從之前的“站到講台前”變到現在的“坐在學生中”。這一變化絕不僅僅是簡單地将所有問題留給學生, 從“講授”變成“答疑”, 而是從問題設計、思考啟迪、讨論引導到過程管理等各方面都對教師提高了要求。特别是現代高級語言發展日新月異, 各種新問題層出不窮, 如何在面對開放性的未知問題時, 從系統和整體的角度給出學生解決問題的方式方法, 而不是給出具體每個問題的回答, 這是對教師能力的一種新考驗。

(二) 編譯器設計實現方案

編譯原理課程教學理想情況, 學生應該能夠獨立自主完成小型編譯系統的構造。實際教學中, 學生隻需吃透關鍵的幾條原理知識, 如NFA的确定化, LL (1) 文法中FIRST和FOLLOW集合的構造,LR (1) 文法中識别活前綴DFA構造等, 基本上已經滿足了課程考試要求。然而, 僅靠理論學習對實現一個基礎編譯器來說是遠遠不足的。相比較于學生對理論知識的接受程度, 學生自主動手完成編譯系統的能力缺乏就更為明顯。如何面對全體學生, 制定出一套适用的實踐方案, 是課程實際效用的關鍵。

發展

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

基本流程

編譯可以分為五個基本步驟:詞法分析、語法分析、語義分析及中間代碼的生成、優化、目标代碼的生成。這是每個編譯器都必須的基本步驟和流程, 從源頭輸入高級語言源程序輸出目标語言代碼。

1 詞法分析

詞法分析器是通過詞法分析程序對構成源程序的字符串從左到右的掃描, 逐個字符地讀, 識别出每個單詞符号, 識别出的符号一般以二元式形式輸出, 即包含符号種類的編碼和該符号的值。詞法分析器一般以函數的形式存在, 供語法分析器調用。當然也可以一個獨立的詞法分析器程序存在。完成詞法分析任務的程序稱為詞法分析程序或詞法分析器或掃描器。

2 語法分析

語法分析是編譯過程的第二個階段。這階段的任務是在詞法分析的基礎上将識别出的單詞符号序列組合成各類語法短語, 如“語句”, “表達式”等.語法分析程序的主要步驟是判斷源程序語句是否符合定義的語法規則, 在語法結構上是否正确。而一個語法規則又稱為文法, 喬姆斯基将文法根據施加不同的限制分為0型、1型、2型、3型文法, 0型文法又稱短語文法, 1型稱為上下文有關文法, 2型稱為上下文無關文法, 3型文法稱為正規文法, 限制條件依次遞增。

3 語義分析

詞法分析注重的是每個單詞是否合法, 以及這個單詞屬于語言中的哪些部分。語法分析的上下文無關文法注重的是輸入語句是否可以依據文法匹配産生式。那麼, 語義分析就是要了解各個語法單位之間的關系是否合法。實際應用中就是對結構上正确的源程序進行上下文有關性質的審查, 進行類型審查等。

4 中間代碼生成與優化

在進行了語法分析和語義分析階段的工作之後, 有的編譯程序将源程序變成一種内部表示形式, 這種内部表示形式叫做中間語言或中間表示或中間代碼。所謂“中間代碼”是一種結構簡單、含義明确的記号系統, 這種記号系統複雜性介于源程序語言和機器語言之間, 容易将它翻譯成目标代碼。另外, 還可以在中間代碼一級進行與機器無關的優化。

5 目标代碼的生成

根據優化後的中間代碼, 可生成有效的目标代碼。而通常編譯器将其翻譯為彙編代碼, 此時還需要将彙編代碼經彙編器彙編為目标機器的機器語言。

6 出錯處理

編譯的各個階段都有可能發現源碼中的錯誤, 尤其是語法分析階段可能會發現大量的錯誤, 因此編譯器需要做出錯處理, 報告錯誤類型及錯誤位置等信息。

編譯過程

C語言的源程序和對應的可執行程序執行時在内存中的運行結構，實現這一轉換的最主要的過程就是編譯。

源程序是給人看的，本質上就是文本文件，可以用Linux中的vi或Windows中的記事本之類的文本編輯程序打開、編寫，但計算機無法直接執行源程序，需要通過一個專門的程序将源程序編譯為計算機可執行程序，這個專門的程序就是編譯器。編譯過程主要分為詞法分析、語法分析、中間代碼生成、目标代碼生成（忽略預處理、語義分析、優化等）。下面我們依次簡要講解編譯的主要過程。

人眼中看到的源代碼是這樣的：

而它在計算機中存儲的形式如圖1-36所示。



圖1-36 案例程序的十六進制形式

這裡看不出關鍵字、運算符、标識符，甚至看不出哪幾個字符屬于同一個符号。編譯的第一階段是詞法分析，目的就是在連續的字符中識别出一個一個的符号，并盡可能地識别出符号的屬性。

人們在看C語言源程序時，借助空格、括号等一眼就可以看出标識符、關鍵字。與人相比，現在計算機的智能還是相當低的，無法像人那樣同時看多個字符，隻能依據一個非常機械的“電子版”詞法，一個字符一個字符地識别。“電子版”詞法是将狀态轉換圖的思路融彙在詞法分析器的代碼中得以體現的。詞法分析器從源程序的字符串中識别出一個個符号（token），并按序保存。

詞法分析的結果如圖1-37所示。



圖1-37 詞法分析的結果

在詞法分析階段能夠識别出一些符号的含義，它們包括關鍵字、數字、字符串、分隔符，這些符号的含義不需要其他符号的輔助就能确定本身的含義。比如，“int”一定代表整數類型，它不可能是一個變量名稱，也不可能是一個運算符。

而另外一些符号需要通過前後的其他符号才能确定出準确含義。比如“m”，在詞法階段僅能判斷這是一個标識符，但是如果不對所在的句做分析，就無法得知這個标識符代表一個變量還是一個函數。更多詳細的信息需要對符号所在的句型做分析才能獲得。這部分工作由語法分析來完成。

如果說詞法分析的作用是從連續的字符中識别出标識符、關鍵字、數字、運算符并存儲為符号（token）流，語法分析的作用就是從詞法分析識别出的符号流中識别出符合C語言語法的語句。

因為計算機無法像人那樣同時看多個标識符、關鍵字、數字、運算符，無法像人那樣一眼看出這是一個函數聲明，那是一個if語句，隻能非常笨拙地一個符号一個符号去識别。與詞法分析器有些類似，語法分析器也是依據用計算機表示的語法，一個符号一個符号地識别出符合C語言語法的語句。語法的計算機表示就是産生式。在語法分析器中把通過産生式産生的C語言語法映射成一套模闆，并把這套模闆融彙在語法分析器的程序中。語法分析器的作用就是将詞法分析器識别出的符号（token）一個一個地與這套模闆進行匹配，匹配上這套模闆中的某個語法，就可以識别出一句完整的語句，并确定這條語句的語法。

我們以案例中“int fun(int a，int b);”這條函數聲明語句為例描述這個過程，它與語句模闆的匹配情景如圖1-38所示。



圖1-38 fun函數聲明語句與模闆匹配的結果

這段token流最終與函數聲明模闆相匹配，在匹配成功後，計算機就認為此語句為函數聲明語句，并以語法樹的形式在内存中記錄下來，情景如圖1-39所示。



圖1-39 fun函數聲明語句生成的語法樹

以樹型結構來記錄分析出的語句是一個非常巧妙、深謀遠慮、通盤考慮的選擇。一方面，樹型結構能夠“記住”源程序全部的“意思”，另一方面，樹型結構更容易對應到運行時結構。

至此，語法樹已經承載了源程序的全部信息，後續的轉換工作就和源程序沒關系了。

如果希望一步到位，從語法樹轉換為目标代碼，理論上和實際上都是可行的。但計算機存在多種CPU硬件平台，考慮到程序在不同CPU之間的可移植性，先轉換成一個通用的、抽象的“CPU指令”，這就是中間代碼最初的設計思想。然後根據具體選定的CPU，将中間代碼落實到具體CPU的目标代碼。

語法樹是個二維結構，中間代碼是準一維結構，語法樹到中間代碼的轉換過程，本質上是将二維結構轉換為準一維結構的過程。中間代碼特别是RTL已經可以和運行時結構一一對應了。如圖1-40所示。 



圖1-40 中間代碼與目标代碼對應的情景示意

運行時結構也是一維的，圖1-40左側部分的轉換結果将更貼近運行時結構。

選定具體的CPU、操作系統後，中間代碼就可以轉換為目标代碼——彙編代碼（我們配置的是AT&T彙編），這時操作系統的影響還比較小。然後由彙編器依照選定操作系統的目标文件格式，将.s文件轉換為具體的目标文件，對于Linux而言是.o文件，對于Windows而言是.obj文件。目标文件中已經是選定的CPU的機器指令了。

最後鍊接器把一個或多個目标文件（庫文件本質上也是目标文件）鍊接成符合選定操作系統指定格式的可執行文件。

通過操作系統，可執行程序就可以被載入内存執行，形成前兩節我們所看到的運行時結構。

本書後續内容将詳細講解編譯的主要過程：詞法分析、語法分析、中間代碼到目标代碼，然後是彙編與鍊接，最後講解預處理。