編譯技術綜述

張世奇

摘要：本文通過介紹編譯技術的發展歷史，進而引入編譯系統，通過對編譯系統的五大步驟的系統介紹，使讀者初步認識什么是編譯系統，以及編譯系統各個步驟的主要功能。最后聯系當前人工智能技術，分布式技術，多核技術對編譯技術的影響，對未來的編譯技術的發展進行展望。

關鍵詞：DFA，NFA，句柄，最左素短語

一、編譯技術發展歷史

在二十世紀五十年代，編譯器的開發還是一件非常困難的事情。因為早期大多數的編譯工作是人們手動將算術公式翻譯為機器代碼，當面對復雜的運算公式時，這項工作就變得十分繁瑣。在這個時期，出現了許多高級編程語言，然而第一個Fortran編譯器卻經歷了多年的開發才完成。到二十世紀年代末期，研究人員開始研究能夠自動編譯的工具。從二十世紀六十年代開始，人們開始使用自展技術來構造編譯程序。

近二十年來，隨著計算機技術的迅猛發展，編譯技術也有了長足進步，涌現出了多種優異的編譯技術，如并行編譯技術，交叉編譯技術等等。與此同時，認人們也開發了多種自動生成工具，LEX用于生成詞法分析程序，YACC用于生成語法分析程序等。

二、編譯系統

我們使用高級編程語言邊寫程序，通常是將我們對業務邏輯的理解轉化為程序代碼。編譯則是將我們編寫的源程序通過轉化，成為計算機能夠運行的機器代碼。編譯過程主要分為以下五個階段（如下圖一）。

（一）詞法分析

詞法分析器工作的首要步驟是對輸入的源程序進行預處理，即去除空白符，回車符等編輯性字符，此外還要去除程序中出現的注解。其次，通過超前搜索來對輸入的單詞符號進行識別。最后，構建非確定有限自動機（NFA），并對NFA進行確定化，使其轉換為有限自動機（DFA）來識別字符串。

（二）語法分析[1]

語法分析是建立在詞法分析的基礎之上進行的，它根據文法的產生式來識別輸入的字符串是否可以構成一個句子。下面會介紹兩種語法分析的方法。

自上而下分析法是基于文法進行的，以文法產生式的開始符號作為樹根，自頂向下的構建一棵語法樹。語法分析過程從本質上來講，是一種試探性的分析過程，是一個不斷使用不同的產生式來進行字符串匹配的過程。

自底向上分析法分為算符優先分析法和規范分析法。它們均利用了計算機中的棧，用一個棧區來存儲產生式中的符號，利用棧先進后出的特性，先把符號一個一個移進到棧中。當棧頂出現某一個產生式的候選式時，把棧頂的這一部分進行規約。其中規范規約首先利用產生式規則，對輸入串構建一棵語法樹，根據構建的語法樹尋找句柄，并在符號棧內進行規約。算符優先分析同樣需要根據產生式規則建立一棵語法樹，并尋找最左素短語來進行規約，由于算符優先分析跳過了所有單非產生式對對應的規約步驟，由此可能會出現無法構成句子的輸入串，誤認為是一個句子的錯誤。

（三）語義分析與中間代碼生成[2]

當詞法分析和語法分析完成后，編譯程序就要進行靜態語義檢查和翻譯。所謂靜態語義檢查，即操作符的類型檢查，對控制流語句使用的合法性進行檢查，檢查是否有對象被重復定義，以及相關名字檢查。

在編譯過程中，我們還需要將源程序轉化為中間語言，通常有后綴式、三地址代碼以及DAG圖三種方式。

后綴式表示法，又被人們稱之為逆波蘭表達式。這一種表示方法，其主要作用是將表達式中的操作數寫在表達式前面，將算符寫在表達式的后面。

圖表示法包括兩種表達方式，分別為DAG和抽象語法樹。

（四）優化

優化的目的是為了提高代碼效率，在優化時，對代碼的變換需要遵守以下原則：

1）等價原則。代碼經優化過后不會影響代碼最終的執行結果。

2）有效原則。使代碼優化后，盡可能的降低時間復雜度和空間復雜度，使減少代碼運行時間，占用較小的內存

3）合算原則。盡可能以較小代價取得較好的優化效果。

代碼優化通常使用這幾種方法：

1）刪除公共子表達式

假設一個表達式S被計算過一次，且在計算之后表達式S之中的變量值為發生改變，那么我們將S稱之為公共子表達式。我們為了避免對這些公共表達式的重復計算，要將它們刪除，也可以稱為刪除多余運算。

2）復寫傳播[3]

例如H1：=H2； Z：=X[H1]；

H2將值付給H1，Z=X[H1]；引用了H1的值，我們可以將Z=X[H1]；改為Z=X[H2]；我們稱這種變換方式為復寫傳播。

3）刪除無用代碼

對于進行復寫傳播的表達式中的變量以及一些臨時變量，因為在整個程序中不會被再次使用，且這些變量的賦值對程序運行的最終結果沒有影響。我們可以將其刪除。

4）代碼外提

對于程序之中的循環結構，若一些代碼在循環中產生的結果是不改變的，我們可以將這一部分代碼從循環內部提取出來，將它們放在該循環結構外面。

5）強度削減

將循環中的乘除法變為加減法，因為在計算機中，加減法的運算速度要比乘除法的運算速度快。

6）刪除歸納變量

（五）目標代碼生成

該階段利用經語義分析或者優化后的中間代碼轉化為目標代碼。

目標代碼通常有以下三種形式：

1）計算機可以立即執行的機器代碼

2）待裝配的機器語言模塊

3）匯編語言代碼。

三、對未來編譯技術的展望

隨著人工智能技術的崛起，將人工智能技術應用與編譯技術，為大幅提升編譯效率帶來了希望。如今，雙向長短期神經網絡已經初步運用到了詞法分析當中，使詞法分析效率進一步提高。此外，就目前的分布式技術發展情況來看，并行編譯技術已經使編譯速度大大提高，近年來分布式技術的迅速發展發展，并行運算量將會再上一個臺階，這將極大推動并行編譯技術的發展。從硬件發展的角度來看，隨著多核技術的不斷成熟，編譯技術正逐步從單核編譯技術向多核編譯技術轉變，從而提高編譯執行的效率，我們相信隨著未來技術的不斷進步，編譯技術必將迎來革命性的發展。

參考文獻：

[1]陳火旺，錢家驊，孫永強。著，程序設計語言編譯原理 [M]國防工業出版社，2017.3

[2]Alfred V.Aho ，Monica S.Lam，Ravi Sethi，Jeffrey D.Ullman 著，機械工業出版社，2008.12

[3]趙雄芳，白克明，易忠興，張克強，編譯原理例解析疑。長沙：湖南科技出版社，1991