張世奇

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

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

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

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

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

二、編譯系統(tǒng)

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

（一）詞法分析

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

（二）語(yǔ)法分析[1]

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

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

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

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

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

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

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

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

（四）優(yōu)化

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

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

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

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

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

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

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

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

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

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

3）刪除無(wú)用代碼

對(duì)于進(jìn)行復(fù)寫(xiě)傳播的表達(dá)式中的變量以及一些臨時(shí)變量，因?yàn)樵谡麄€(gè)程序中不會(huì)被再次使用，且這些變量的賦值對(duì)程序運(yùn)行的最終結(jié)果沒(méi)有影響。我們可以將其刪除。

4）代碼外提

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

5）強(qiáng)度削減

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

6）刪除歸納變量

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

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

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

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

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

3）匯編語(yǔ)言代碼。

三、對(duì)未來(lái)編譯技術(shù)的展望

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

參考文獻(xiàn)：

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

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

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