編譯技術(shù)綜述

張世奇

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

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

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

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

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

二、編譯系統(tǒng)

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

（一）詞法分析

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

（二）語法分析[1]

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

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

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

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

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

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

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

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

（四）優(yōu)化

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

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

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

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

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

1）刪除公共子表達(dá)式

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

2）復(fù)寫傳播[3]

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

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

3）刪除無用代碼

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

4）代碼外提

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

5）強(qiáng)度削減

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

6）刪除歸納變量

（五）目標(biāo)代碼生成

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

目標(biāo)代碼通常有以下三種形式：

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

2）待裝配的機(jī)器語言模塊

3）匯編語言代碼。

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

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

參考文獻(xiàn)：

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

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

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