[科普中國(guó)]-編譯程序

編譯程序（Compiler，compiling program）也稱為編譯器，是指把用高級(jí)程序設(shè)計(jì)語(yǔ)言書寫的源程序，翻譯成等價(jià)的機(jī)器語(yǔ)言格式目標(biāo)程序的翻譯程序。編譯程序?qū)儆诓捎蒙尚詫?shí)現(xiàn)途徑實(shí)現(xiàn)的翻譯程序。它以高級(jí)程序設(shè)計(jì)語(yǔ)言書寫的源程序作為輸入，而以匯編語(yǔ)言或機(jī)器語(yǔ)言表示的目標(biāo)程序作為輸出。編譯出的目標(biāo)程序通常還要經(jīng)歷運(yùn)行階段，以便在運(yùn)行程序的支持下運(yùn)行，加工初始數(shù)據(jù)，算出所需的計(jì)算結(jié)果。

定義編譯程序詞組可以有兩種認(rèn)識(shí)。

一、編譯程序是一種動(dòng)作，是根據(jù)編譯原理技術(shù)，由高級(jí)程序設(shè)計(jì)語(yǔ)言編譯器翻譯成機(jī)器語(yǔ)言二進(jìn)制代碼行為。

二、編譯程序是動(dòng)名詞，特指生成編譯器的軟件程序。1

簡(jiǎn)介編譯程序compiler

編譯程序的實(shí)現(xiàn)算法較為復(fù)雜。這是因?yàn)樗g的語(yǔ)句與目標(biāo)語(yǔ)言的指令不是一一對(duì)應(yīng)關(guān)系,而是一多對(duì)應(yīng)關(guān)系;同時(shí)也因?yàn)樗幚磉f歸調(diào)用、動(dòng)態(tài)存儲(chǔ)分配、多種數(shù)據(jù)類型，以及語(yǔ)句間的緊密依賴關(guān)系。但是，由于高級(jí)程序設(shè)計(jì)語(yǔ)言書寫的程序具有易讀、易移植和表達(dá)能力強(qiáng)等特點(diǎn)，編譯程序廣泛地用于翻譯規(guī)模較大、復(fù)雜性較高、且需要高效運(yùn)行的高級(jí)語(yǔ)言書寫的源程序。

功能編譯程序的基本功能是把源程序（高級(jí)語(yǔ)言）翻譯成目標(biāo)程序。但是,作為一個(gè)具有實(shí)際應(yīng)用價(jià)值的編譯系統(tǒng),除了基本功能之外，還應(yīng)具備語(yǔ)法檢查、調(diào)試措施、修改手段、覆蓋處理、目標(biāo)程序優(yōu)化、不同語(yǔ)言合用以及人-機(jī)聯(lián)系等重要功能。①語(yǔ)法檢查:檢查源程序是否合乎語(yǔ)法。如果不符合語(yǔ)法，編譯程序要指出語(yǔ)法錯(cuò)誤的部位、性質(zhì)和有關(guān)信息。編譯程序應(yīng)使用戶一次上機(jī)，能夠盡可能多地查出錯(cuò)誤。②調(diào)試措施：檢查源程序是否合乎設(shè)計(jì)者的意圖。為此，要求編譯程序在編譯出的目標(biāo)程序中安置一些輸出指令，以便在目標(biāo)程序運(yùn)行時(shí)能輸出程序動(dòng)態(tài)執(zhí)行情況的信息，如變量值的更改、程序執(zhí)行時(shí)所經(jīng)歷的線路等。這些信息有助于用戶核實(shí)和驗(yàn)證源程序是否表達(dá)了算法要求。③修改手段：為用戶提供簡(jiǎn)便的修改源程序的手段。編譯程序通常要提供批量修改手段（用于修改數(shù)量較大或臨時(shí)不易修改的錯(cuò)誤）和現(xiàn)場(chǎng)修改手段（用于運(yùn)行時(shí)修改數(shù)量較少、臨時(shí)易改的錯(cuò)誤）。④覆蓋處理：主要是為處理程序長(zhǎng)、數(shù)據(jù)量大的大型問(wèn)題程序而設(shè)置的?；舅枷胧亲屢恍┏绦蚨魏蛿?shù)據(jù)公用某些存儲(chǔ)區(qū)，其中只存放當(dāng)前要用的程序或數(shù)據(jù);其余暫時(shí)不用的程序和數(shù)據(jù),先存放在磁盤等輔助存儲(chǔ)器中，待需要時(shí)動(dòng)態(tài)地調(diào)入。⑤目標(biāo)程序優(yōu)化：提高目標(biāo)程序的質(zhì)量,即占用的存儲(chǔ)空間少,程序的運(yùn)行時(shí)間短。依據(jù)優(yōu)化目標(biāo)的不同，編譯程序可選擇實(shí)現(xiàn)表達(dá)式優(yōu)化、循環(huán)優(yōu)化或程序全局優(yōu)化。目標(biāo)程序優(yōu)化有的在源程序級(jí)上進(jìn)行，有的在目標(biāo)程序級(jí)上進(jìn)行。⑥不同語(yǔ)言合用：其功能有助于用戶利用多種程序設(shè)計(jì)語(yǔ)言編寫應(yīng)用程序或套用已有的不同語(yǔ)言書寫的程序模塊。最為常見(jiàn)的是高級(jí)語(yǔ)言和匯編語(yǔ)言的合用。這不但可以彌補(bǔ)高級(jí)語(yǔ)言難于表達(dá)某些非數(shù)值加工操作或直接控制、訪問(wèn)外圍設(shè)備和硬件寄存器之不足，而且還有利于用匯編語(yǔ)言編寫核心部分程序,以提高運(yùn)行效率。⑦人-機(jī)聯(lián)系：確定編譯程序?qū)崿F(xiàn)方案時(shí)達(dá)到精心設(shè)計(jì)的功能。目的是便于用戶在編譯和運(yùn)行階段及時(shí)了解內(nèi)部工作情況，有效地監(jiān)督、控制系統(tǒng)的運(yùn)行。早期編譯程序的實(shí)現(xiàn)方案，是把上述各項(xiàng)功能完全收納在編譯程序之中。然而，習(xí)慣做法是在操作系統(tǒng)的支持下，配置調(diào)試程序、編輯程序和連接裝配程序，用以協(xié)助實(shí)現(xiàn)程序的調(diào)試、修改、覆蓋處理，以及不同語(yǔ)言合用功能。但在設(shè)計(jì)編譯程序時(shí)，仍須精心考慮如何與這些子系統(tǒng)銜接等問(wèn)題。2

特點(diǎn)編譯程序必須分析源程序，然后綜合成目標(biāo)程序。首先，檢查源程序的正確性，并把它分解成若干基本成分；其次，再根據(jù)這些基本成分建立相應(yīng)等價(jià)的目標(biāo)程序部分。為了完成這些工作，編譯程序要在分析階段建立一些表格,改造源程序?yàn)橹虚g語(yǔ)言形式,以便在分析和綜合時(shí)易于引用和加工（圖1）。

數(shù)據(jù)結(jié)構(gòu)分析和綜合時(shí)所用的主要數(shù)據(jù)結(jié)構(gòu)，包括符號(hào)表、常數(shù)表和中間語(yǔ)言程序。符號(hào)表由源程序中所用的標(biāo)識(shí)符連同它們的屬性組成，其中屬性包括種類（如變量、數(shù)組、結(jié)構(gòu)、函數(shù)、過(guò)程等）、類型（如整型、實(shí)型、字符串、復(fù)型、標(biāo)號(hào)等），以及目標(biāo)程序所需的其他信息。常數(shù)表由源程序中用的常數(shù)組成，其中包括常數(shù)的機(jī)內(nèi)表示，以及分配給它們的目標(biāo)程序地址。中間語(yǔ)言程序是將源程序翻譯為目標(biāo)程序前引入的一種中間形式的程序，其表示形式的選擇取決于編譯程序以后如何使用和加工它。常用的中間語(yǔ)言形式有波蘭表示、三元組、四元組以及間接三元組等。

分析部分源程序的分析是經(jīng)過(guò)詞法分析、語(yǔ)法分析和語(yǔ)義分析三個(gè)步驟實(shí)現(xiàn)的。詞法分析由詞法分析程序（又稱為掃描程序）完成，其任務(wù)是識(shí)別單詞（即標(biāo)識(shí)符、常數(shù)、保留字，以及各種運(yùn)算符、標(biāo)點(diǎn)符號(hào)等）、造符號(hào)表和常數(shù)表，以及將源程序換碼為編譯程序易于分析和加工的內(nèi)部形式。語(yǔ)法分析程序是編譯程序的核心部分，其主要任務(wù)是根據(jù)語(yǔ)言的語(yǔ)法規(guī)則，檢查源程序是否合乎語(yǔ)法。如不合乎語(yǔ)法，則輸出語(yǔ)法出錯(cuò)信息；如合乎語(yǔ)法，則分解源程序的語(yǔ)法結(jié)構(gòu)，構(gòu)造中間語(yǔ)言形式的內(nèi)部程序。語(yǔ)法分析的目的是掌握單詞是怎樣組成語(yǔ)句的，以及語(yǔ)句又是如何組成程序的。語(yǔ)義分析程序是進(jìn)一步檢查合法程序結(jié)構(gòu)的語(yǔ)義正確性，其目的是保證標(biāo)識(shí)符和常數(shù)的正確使用，把必要的信息收集和保存到符號(hào)表或中間語(yǔ)言程序中，并進(jìn)行相應(yīng)的語(yǔ)義處理。

工作過(guò)程編譯程序也叫編譯系統(tǒng)，是把用高級(jí)語(yǔ)言編寫的面向過(guò)程的源程序翻譯成目標(biāo)程序的語(yǔ)言處理程序。編譯程序把一個(gè)源程序翻譯成目標(biāo)程序的工作過(guò)程分為五個(gè)階段：詞法分析；語(yǔ)法分析；中間代碼生成；代碼優(yōu)化；目標(biāo)代碼生成。主要是進(jìn)行詞法分析和語(yǔ)法分析，又稱為源程序分析，分析過(guò)程中發(fā)現(xiàn)有語(yǔ)法錯(cuò)誤，給出提示信息。

（1） 詞法分析

詞法分析的任務(wù)是對(duì)由字符組成的單詞進(jìn)行處理，從左至右逐個(gè)字符地對(duì)源程序進(jìn)行掃描，產(chǎn)生一個(gè)個(gè)的單詞符號(hào)，把作為字符串的源程序改造成為單詞符號(hào)串的中間程序。執(zhí)行詞法分析的程序稱為詞法分析程序或掃描器。

源程序中的單詞符號(hào)經(jīng)掃描器分析，一般產(chǎn)生二元式：?jiǎn)卧~種別；單詞自身的值。單詞種別通常用整數(shù)編碼，如果一個(gè)種別只含一個(gè)單詞符號(hào)，那么對(duì)這個(gè)單詞符號(hào)，種別編碼就完全代表它自身的值了。若一個(gè)種別含有許多個(gè)單詞符號(hào)，那么，對(duì)于它的每個(gè)單詞符號(hào)，除了給出種別編碼以外，還應(yīng)給出自身的值。

詞法分析器一般來(lái)說(shuō)有兩種方法構(gòu)造：手工構(gòu)造和自動(dòng)生成。手工構(gòu)造可使用狀態(tài)圖進(jìn)行工作，自動(dòng)生成使用確定的有限自動(dòng)機(jī)來(lái)實(shí)現(xiàn)。

（2） 語(yǔ)法分析

編譯程序的語(yǔ)法分析器以單詞符號(hào)作為輸入，分析單詞符號(hào)串是否形成符合語(yǔ)法規(guī)則的語(yǔ)法單位，如表達(dá)式、賦值、循環(huán)等，最后看是否構(gòu)成一個(gè)符合要求的程序，按該語(yǔ)言使用的語(yǔ)法規(guī)則分析檢查每條語(yǔ)句是否有正確的邏輯結(jié)構(gòu)，程序是最終的一個(gè)語(yǔ)法單位。編譯程序的語(yǔ)法規(guī)則可用上下文無(wú)關(guān)文法來(lái)刻畫。

語(yǔ)法分析的方法分為兩種：自上而下分析法和自下而上分析法。自上而下就是從文法的開(kāi)始符號(hào)出發(fā)，向下推導(dǎo)，推出句子。而自下而上分析法采用的是移進(jìn)歸約法，基本思想是：用一個(gè)寄存符號(hào)的先進(jìn)后出棧，把輸入符號(hào)一個(gè)一個(gè)地移進(jìn)棧里，當(dāng)棧頂形成某個(gè)產(chǎn)生式的一個(gè)候選式時(shí)，即把棧頂?shù)倪@一部分歸約成該產(chǎn)生式的左鄰符號(hào)。

（3） 中間代碼生成

中間代碼是源程序的一種內(nèi)部表示，或稱中間語(yǔ)言。中間代碼的作用是可使編譯程序的結(jié)構(gòu)在邏輯上更為簡(jiǎn)單明確，特別是可使目標(biāo)代碼的優(yōu)化比較容易實(shí)現(xiàn)。中間代碼即為中間語(yǔ)言程序，中間語(yǔ)言的復(fù)雜性介于源程序語(yǔ)言和機(jī)器語(yǔ)言之間。中間語(yǔ)言有多種形式，常見(jiàn)的有逆波蘭記號(hào)、四元式、三元式和樹(shù)。

（4） 代碼優(yōu)化

代碼優(yōu)化是指對(duì)程序進(jìn)行多種等價(jià)變換，使得從變換后的程序出發(fā)，能生成更有效的目標(biāo)代碼。所謂等價(jià)，是指不改變程序的運(yùn)行結(jié)果。所謂有效，主要指目標(biāo)代碼運(yùn)行時(shí)間較短，以及占用的存儲(chǔ)空間較小。這種變換稱為優(yōu)化。

有兩類優(yōu)化：一類是對(duì)語(yǔ)法分析后的中間代碼進(jìn)行優(yōu)化，它不依賴于具體的計(jì)算機(jī)；另一類是在生成目標(biāo)代碼時(shí)進(jìn)行的，它在很大程度上依賴于具體的計(jì)算機(jī)。對(duì)于前一類優(yōu)化，根據(jù)它所涉及的程序范圍可分為局部?jī)?yōu)化、循環(huán)優(yōu)化和全局優(yōu)化三個(gè)不同的級(jí)別。

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

目標(biāo)代碼生成是編譯的最后一個(gè)階段。目標(biāo)代碼生成器把語(yǔ)法分析后或優(yōu)化后的中間代碼變換成目標(biāo)代碼。目標(biāo)代碼有三種形式：

① 可以立即執(zhí)行的機(jī)器語(yǔ)言代碼，所有地址都重定位；

② 待裝配的機(jī)器語(yǔ)言模塊，當(dāng)需要執(zhí)行時(shí)，由連接裝入程序把它們和某些運(yùn)行程序連接起來(lái)，轉(zhuǎn)換成能執(zhí)行的機(jī)器語(yǔ)言代碼；

③ 匯編語(yǔ)言代碼，須經(jīng)過(guò)匯編程序匯編后，成為可執(zhí)行的機(jī)器語(yǔ)言代碼。

目標(biāo)代碼生成階段應(yīng)考慮直接影響到目標(biāo)代碼速度的三個(gè)問(wèn)題：一是如何生成較短的目標(biāo)代碼；二是如何充分利用計(jì)算機(jī)中的寄存器，減少目標(biāo)代碼訪問(wèn)存儲(chǔ)單元的次數(shù)；三是如何充分利用計(jì)算機(jī)指令系統(tǒng)的特點(diǎn)，以提高目標(biāo)代碼的質(zhì)量。3

綜合部分綜合階段必須根據(jù)符號(hào)表和中間語(yǔ)言程序產(chǎn)生出目標(biāo)程序，其主要工作包括代碼優(yōu)化、存儲(chǔ)分配和代碼生成。代碼優(yōu)化是通過(guò)重排和改變程序中的某些操作，以產(chǎn)生更加有效的目標(biāo)程序。存儲(chǔ)分配的任務(wù)是為程序和數(shù)據(jù)分配運(yùn)行時(shí)的存儲(chǔ)單元。代碼生成的主要任務(wù)是產(chǎn)生與中間語(yǔ)言程序符等價(jià)的目標(biāo)程序，順序加工中間語(yǔ)言程序，并利用符號(hào)表和常數(shù)表中的信息生成一系列的匯編語(yǔ)言或機(jī)器語(yǔ)言指令。

結(jié)構(gòu)編譯過(guò)程分為分析和綜合兩個(gè)部分，并進(jìn)一步劃分為詞法分析、語(yǔ)法分析、語(yǔ)義分析、代碼優(yōu)化、存儲(chǔ)分配和代碼生成等六個(gè)相繼的邏輯步驟。這六個(gè)步驟只表示編譯程序各部分之間的邏輯聯(lián)系，而不是時(shí)間關(guān)系。編譯過(guò)程既可以按照這六個(gè)邏輯步驟順序地執(zhí)行，也可以按照平行互鎖方式去執(zhí)行。在確定編譯程序的具體結(jié)構(gòu)時(shí)，常常分若干遍實(shí)現(xiàn)。對(duì)于源程序或中間語(yǔ)言程序，從頭到尾掃視一次并實(shí)現(xiàn)所規(guī)定的工作稱作一遍。每一遍可以完成一個(gè)或相連幾個(gè)邏輯步驟的工作。例如，可以把詞法分析作為第一遍；語(yǔ)法分析和語(yǔ)義分析作為第二遍；代碼優(yōu)化和存儲(chǔ)分配作為第三遍；代碼生成作為第四遍。反之，為了適應(yīng)較小的存儲(chǔ)空間或提高目標(biāo)程序質(zhì)量，也可以把一個(gè)邏輯步驟的工作分為幾遍去執(zhí)行。例如，代碼優(yōu)化可劃分為代碼優(yōu)化準(zhǔn)備工作和實(shí)際代碼優(yōu)化兩遍進(jìn)行。

一個(gè)編譯程序是否分遍,以及如何分遍,根據(jù)具體情況而定。其判別標(biāo)準(zhǔn)可以是存儲(chǔ)容量的大小、源語(yǔ)言的繁簡(jiǎn)、解題范圍的寬窄，以及設(shè)計(jì)、編制人員的多少等。分遍的好處是各遍功能獨(dú)立單純、相互聯(lián)系簡(jiǎn)單、邏輯結(jié)構(gòu)清晰、優(yōu)化準(zhǔn)備工作充分。缺點(diǎn)是各遍之中不可避免地要有些重復(fù)的部分，而且遍和遍之間要有交接工作，因之增加了編譯程序的長(zhǎng)度和編譯時(shí)間。

一遍編譯程序是一種極端情況，整個(gè)編譯程序同時(shí)駐留在內(nèi)存,彼此之間采用調(diào)用轉(zhuǎn)接方式連接在一起(圖2)。當(dāng)語(yǔ)法分析程序需要新符號(hào)時(shí)，它就調(diào)用詞法分析程序；當(dāng)它識(shí)別出某一語(yǔ)法結(jié)構(gòu)時(shí)，它就調(diào)用語(yǔ)義分析程序。語(yǔ)義分析程序?qū)ψR(shí)別出的結(jié)構(gòu)進(jìn)行語(yǔ)義檢查，并調(diào)用“存儲(chǔ)分配”和“代碼生成”程序生成相應(yīng)的目標(biāo)語(yǔ)言指令。

隨著程序設(shè)計(jì)語(yǔ)言在形式化、結(jié)構(gòu)化、直觀化和智能化等方面的發(fā)展，作為實(shí)現(xiàn)相應(yīng)語(yǔ)言功能的編譯程序，也正向自動(dòng)程序設(shè)計(jì)的目標(biāo)發(fā)展，以便提供理想的程序設(shè)計(jì)工具。

參考書目

陳火旺、錢家驊、孫永強(qiáng)編：《編譯原理》，國(guó)防工業(yè)出版社，北京，1980。

A.V.Aho, Principles of Compiler Design,Addison Wes-ley, Reading, Massachusetts, 1977.

動(dòng)態(tài)20世紀(jì)80年代以后，程序設(shè)計(jì)語(yǔ)言在形式化、結(jié)構(gòu)化、直觀化和智能化等方面有了長(zhǎng)足的進(jìn)步和發(fā)展，主要表現(xiàn)兩個(gè)方面：①隨著程序設(shè)計(jì)理論和方法的發(fā)展，相繼推出了一系列新型程序設(shè)計(jì)語(yǔ)言，如結(jié)構(gòu)化程序設(shè)計(jì)語(yǔ)言、并發(fā)程序設(shè)計(jì)語(yǔ)言、分布式程序設(shè)計(jì)語(yǔ)言、函數(shù)式程序設(shè)計(jì)語(yǔ)言、智能化程序設(shè)計(jì)語(yǔ)言、面向?qū)ο蟪绦蛟O(shè)計(jì)語(yǔ)言等；②基于語(yǔ)法、語(yǔ)義和語(yǔ)用方面的研究成果，從不同的角度和層次上深刻地揭示了程序設(shè)計(jì)語(yǔ)言的內(nèi)在規(guī)律和外在表現(xiàn)形式。與此相應(yīng)地，作為實(shí)現(xiàn)程序設(shè)計(jì)語(yǔ)言重要手段之一的編譯程序，在體系結(jié)構(gòu)、設(shè)計(jì)思想、實(shí)現(xiàn)技術(shù)和處理內(nèi)容等方面均有不同程度的發(fā)展、變化和擴(kuò)充。另外，編譯程序已作為實(shí)現(xiàn)編程的重要軟件工具，被納入到軟件支援環(huán)境的基本層軟件工具之中。因此，規(guī)劃編譯程序?qū)崿F(xiàn)方案時(shí)，應(yīng)從所處的具體軟件支援環(huán)境出發(fā)，既要遵循整個(gè)環(huán)境的全局性要求和規(guī)定，又要精心考慮與其他諸層軟件 工具之間的相互支援、配合和銜接關(guān)系。

本詞條內(nèi)容貢獻(xiàn)者為:

李嘉騫 - 博士 - 同濟(jì)大學(xué)