張世奇

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

關(guān)鍵詞：DFA，NFA，句柄，最左素短語

一、編譯技術(shù)發(fā)展歷史

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

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

二、編譯系統(tǒng)

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

（一）詞法分析

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

（二）語法分析[1]

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

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

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

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

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

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

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

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

（四）優(yōu)化

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

1）等價原則。代碼經(jīng)優(yōu)化過后不會影響代碼最終的執(zhí)行結(jié)果。

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

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

代碼優(yōu)化通常使用這幾種方法：

1）刪除公共子表達式

假設(shè)一個表達式S被計算過一次，且在計算之后表達式S之中的變量值為發(fā)生改變，那么我們將S稱之為公共子表達式。我們?yōu)榱吮苊鈱@些公共表達式的重復計算，要將它們刪除，也可以稱為刪除多余運算。

2）復寫傳播[3]

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

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

3）刪除無用代碼

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

4）代碼外提

對于程序之中的循環(huán)結(jié)構(gòu)，若一些代碼在循環(huán)中產(chǎn)生的結(jié)果是不改變的，我們可以將這一部分代碼從循環(huán)內(nèi)部提取出來，將它們放在該循環(huán)結(jié)構(gòu)外面。

5）強度削減

將循環(huán)中的乘除法變?yōu)榧訙p法，因為在計算機中，加減法的運算速度要比乘除法的運算速度快。

6）刪除歸納變量

（五）目標代碼生成

該階段利用經(jīng)語義分析或者優(yōu)化后的中間代碼轉(zhuǎn)化為目標代碼。

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

1）計算機可以立即執(zhí)行的機器代碼

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

3）匯編語言代碼。

三、對未來編譯技術(shù)的展望

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

參考文獻：

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

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

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