[摘要]編譯原理課程是高校計(jì)算機(jī)類(lèi)專業(yè)的重要的基礎(chǔ)和骨干課程。而語(yǔ)義分析又是編譯原理課程重點(diǎn)中的難點(diǎn)。它設(shè)計(jì)了抽象機(jī)模型，使用抽象機(jī)的操作行為描述程序設(shè)計(jì)語(yǔ)言的語(yǔ)義。針對(duì)傳統(tǒng)的分支和循環(huán)語(yǔ)句，分析了控制結(jié)構(gòu)的抽象，提出了分支和循環(huán)控制語(yǔ)句的語(yǔ)義模型。在編譯原理課程的教學(xué)中，有效地幫助學(xué)生理解了語(yǔ)義分析的原理和技術(shù)。

[關(guān)鍵詞]編譯原理 控制結(jié)構(gòu) 語(yǔ)法制導(dǎo)翻譯 語(yǔ)義模型

一、引言

編譯原理是計(jì)算機(jī)學(xué)科中少有的從實(shí)踐到理論，再?gòu)睦碚摰綄?shí)踐的一門(mén)專業(yè)課程。編譯技術(shù)不斷進(jìn)步，已經(jīng)成為計(jì)算機(jī)科學(xué)中發(fā)展最迅速、最成熟的一個(gè)重要分支。編譯技術(shù)集中體現(xiàn)了計(jì)算機(jī)科學(xué)發(fā)展的重要成果與精華。程序語(yǔ)言及其編譯的研究在計(jì)算機(jī)科學(xué)中始終處于非常重要的地位。

在語(yǔ)言及編譯理論中，文法(BNF)和語(yǔ)法圖已成為語(yǔ)言語(yǔ)法描述的典型工具，但語(yǔ)義描述至今尚無(wú)人們普遍接受的典型描述工具。采用操作語(yǔ)義學(xué)的方法來(lái)描述語(yǔ)義，即以一個(gè)抽象機(jī)的行為來(lái)描述語(yǔ)言的各個(gè)結(jié)構(gòu)的作用和含義。

二、抽象機(jī)

抽象機(jī)由一個(gè)指令指針ip、一個(gè)存儲(chǔ)器、一個(gè)控制器和一個(gè)運(yùn)算器組成。

抽象機(jī)一旦啟動(dòng)，由專門(mén)的裝入程序?qū)⒁粋€(gè)要運(yùn)行的程序裝入代碼存儲(chǔ)器中，并置ip指向該程序的第一條指令。然后依次完成下述工作：

(1）執(zhí)行ip所指向的指令。

(2）修改ip的內(nèi)容。

若所執(zhí)行的指令已修改過(guò)ip，則不再修改ip；若所執(zhí)行的指令未修改ip，那么修改ip使之指向下一條指令，即 ip:=ip+1。

(3）若ip指向特殊的STOP指令，則終止執(zhí)行，否則轉(zhuǎn)回執(zhí)行（1）。

假設(shè)抽象機(jī)對(duì)各種程序設(shè)計(jì)語(yǔ)言所常用的運(yùn)算符（如＋，-，*，/，＞，＜，>=等）都有相應(yīng)的指令與之對(duì)應(yīng)。因此，只要知道抽象機(jī)操作的語(yǔ)義，也就知道了語(yǔ)言結(jié)構(gòu)的語(yǔ)義。

為了顯示修改ip的內(nèi)容，抽象機(jī)提供兩種特殊的轉(zhuǎn)移指令：無(wú)條件轉(zhuǎn)移指令（goto L）和條件轉(zhuǎn)移指令（if B goto L）。

三、語(yǔ)法制導(dǎo)翻譯

源程序的句子經(jīng)過(guò)詞法分析和語(yǔ)法分析后，已將詞法錯(cuò)誤和語(yǔ)法錯(cuò)誤檢查出來(lái)，并由程序員進(jìn)行了修正，得到語(yǔ)法上正確的句子，下一步對(duì)這些語(yǔ)法上正確的句子，按照句子的語(yǔ)義規(guī)則進(jìn)行語(yǔ)義分析，其目的是生成代碼并實(shí)現(xiàn)其語(yǔ)義。因此，語(yǔ)義分析與代碼生成是緊密相關(guān)的。為便于移植和優(yōu)化，將句子翻譯成抽象機(jī)的指令形式，稱為中間代碼，經(jīng)過(guò)優(yōu)化后再翻譯成目標(biāo)代碼。最終的目標(biāo)代碼質(zhì)量較高，并可以提高執(zhí)行效率。

在語(yǔ)法分析過(guò)程中，根據(jù)每個(gè)產(chǎn)生式所對(duì)應(yīng)的語(yǔ)義子程序（語(yǔ)義動(dòng)作）進(jìn)行翻譯（生成中間代碼）的方法稱為語(yǔ)法制導(dǎo)翻譯。

四、控制結(jié)構(gòu)的抽象

順序、選擇和重復(fù)可以幫助程序員組織語(yǔ)句的控制流程，是基本控制工具。順序是按計(jì)算機(jī)程序計(jì)數(shù)器提供的順序獲得指令的一種抽象。選擇和重復(fù)是對(duì)硬件顯式修改程序計(jì)數(shù)器的值，實(shí)現(xiàn)無(wú)條件轉(zhuǎn)移和條件轉(zhuǎn)移的抽象，這樣的控制既簡(jiǎn)單又有效。抽象控制結(jié)構(gòu)比顯式控制轉(zhuǎn)移修改指令計(jì)數(shù)器的低級(jí)控制機(jī)制更好些，它更面向問(wèn)題，有利于程序設(shè)計(jì)。程序員通過(guò)使用順序、選擇和重復(fù)的一般模式就能較好地表達(dá)他們的意圖。

高級(jí)語(yǔ)言結(jié)構(gòu)最終還是要翻譯成傳統(tǒng)計(jì)算機(jī)的條件轉(zhuǎn)移和無(wú)條件轉(zhuǎn)移機(jī)器代碼。將由編譯程序生成有效的中間代碼，而編譯程序必須利用轉(zhuǎn)移指令將控制抽象進(jìn)行具體化。

分支控制結(jié)構(gòu)允許程序員在某些可選擇的語(yǔ)句中做出一種選擇來(lái)執(zhí)行。有兩種基本的分之控制結(jié)構(gòu)：?jiǎn)芜x控制（if…then…）和二選一控制（if…then…else…）。

循環(huán)控制結(jié)構(gòu)允許程序員控制某些語(yǔ)句可以執(zhí)行0次或多次。

五、語(yǔ)義模型

（1）單選控制結(jié)構(gòu)語(yǔ)句 if B then S

對(duì)應(yīng)的控制可以表示為（中間代碼形式）

if B goto B.T

goto S. next

B.T:

┇//語(yǔ)句S對(duì)應(yīng)的中間代碼段

S.next:

表示為語(yǔ)義模型如圖1所示。

其中，曲線表示語(yǔ)句S1對(duì)應(yīng)的可能的中間出口轉(zhuǎn)移。

（2）二選一控制結(jié)構(gòu)語(yǔ)句if B S1else S2

圖2 if B S1else S2語(yǔ)句的語(yǔ)義模型

對(duì)應(yīng)的控制可以表示為（中間代碼形式）

if B goto B.T

goto B.F

B.T:

┇//語(yǔ)句S1對(duì)應(yīng)的中間代碼段

goto S. next

B.F:

┇//語(yǔ)句S2對(duì)應(yīng)的中間代碼段

S.next:

表示為語(yǔ)義模型如圖2所示。

其中，曲線表示語(yǔ)句S1和S1對(duì)應(yīng)的可能的中間出口轉(zhuǎn)移。

（3）循環(huán)控制結(jié)構(gòu)語(yǔ)句 while B do S

圖3while B do S 語(yǔ)句的語(yǔ)義模型

對(duì)應(yīng)的控制可以表示為（中間代碼形式）

again: if B goto B.T

goto S. next

B.T:

┇//語(yǔ)句S對(duì)應(yīng)的中間代碼段

goto again

S.next:

表示為語(yǔ)義模型如圖3所示。

六、語(yǔ)義子程序

根據(jù)控制語(yǔ)句的語(yǔ)義模型，容易得到分支、循環(huán)控制語(yǔ)句的語(yǔ)義子程序。以二選一控制結(jié)構(gòu)語(yǔ)句為例。

(1)M→if B then{backpatch（B.T，ip)； M.CHAIN=B.F；}

(2)N→M S1 else{q=ip； emit（goto 0）；backpatch（M.CHAIN，ip）；

N.CHAIN=merge（S1.CHAIN，q）；}

(3)S→N S2{S.CHAIN=merge（S2.CHAIN，N.CHAIN）；}

七、總結(jié)

編譯原理中的語(yǔ)義分析是難以理解和掌握的，語(yǔ)義描述的傳統(tǒng)方法是流程圖，但沒(méi)有對(duì)控制轉(zhuǎn)移部分進(jìn)行顯示的標(biāo)注，單憑流程圖進(jìn)行語(yǔ)義子程序的構(gòu)造，學(xué)生普遍難以接收。而采用語(yǔ)義模型的表示，直觀地表達(dá)了控制轉(zhuǎn)移，對(duì)文法產(chǎn)生式的改寫(xiě)和語(yǔ)義子程序的構(gòu)造提供了清晰的思路，實(shí)踐表明，在編譯原理課程的教學(xué)中，有效地幫助學(xué)生理解了語(yǔ)義分析的原理和技術(shù)。

參考文獻(xiàn)：

[1]蔣宗禮，姜守旭.形式語(yǔ)言與自動(dòng)機(jī)理論[M].北京:清華大學(xué)出版社，2007.

[2] 龔天富.語(yǔ)言及編譯[M].北京:電子工業(yè)出版社，2003．

[3]Andrew W.Apple.現(xiàn)代編譯器的Java實(shí)現(xiàn)[M].北京:電子工業(yè)出版社，2004.

[4]Dick Grune etc.Modern Compiler Design[M].JOHN WILEYSONS，LTD，2002.

[5]余勝泉，張建偉.信息時(shí)代的教學(xué)與實(shí)踐[M].北京:高等教育出版社，2005.

（作者單位：四川電子科技大學(xué)）