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

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

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

1 抽象機(jī)

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

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

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

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

若所執(zhí)行的指令已修改過ip，則不再修改ip（顯然剛執(zhí)行的指令是一條轉(zhuǎn)移指令）。若所執(zhí)行的指令未修改ip，那么修改ip使之指向下一條指令，即 ip:=ip+1。

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

假設(shè)抽象機(jī)對各種程序設(shè)計(jì)語言所常用的運(yùn)算符（如＋，-，*，/，＞，＜，>=等）都有相應(yīng)的指令與之對應(yīng)。因此，只要知道抽象機(jī)操作的語義，也就知道了語言結(jié)構(gòu)的語義。為了顯示修改ip的內(nèi)容，抽象機(jī)提供兩種特殊的轉(zhuǎn)移指令：無條件轉(zhuǎn)移指令（goto L）和條件轉(zhuǎn)移指令（if B goto L）。

2 語法制導(dǎo)翻譯

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

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

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

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

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

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

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

4 語義模型

（1）單選控制結(jié)構(gòu)語句 if B then S，傳統(tǒng)的流程圖描述語義如圖1所示。

圖1 if B then S語句的流程圖對應(yīng)的控制可以表示為（中間代碼形式）

if B goto B.T

goto S. next

B.T:

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

S.next:

表示為語義模型如圖2所示。

圖2 if B then S語句的語義模型

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

圖3 if B S1else S2 語句的語義模型

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

（2）循環(huán)控制結(jié)構(gòu)語句 while B do S，傳統(tǒng)的流程圖描述語義如圖4所示。

圖4 while B do S語句的流程圖

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

again: if B goto B.T

goto S. next

B.T:

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

goto again

S.next:

表示為語義模型如圖5所示。

圖5 while B do S 語句的語義模型

5 語義子程序

根據(jù)控制語句的語義模型，容易得到分支、循環(huán)控制語句的語義子程序。

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

①M(fèi)→if B then{backpatch（B.T，ip)；

M.CHAIN=B.F；}

②S→M S1{S.CHAIN=merge（S1.CHAIN，M.CHAIN）；}

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

①M(fèi)→if B then{backpatch（B.T，ip)；

M.CHAIN=B.F；}

②N→M S1else{q=ip；

emit（goto 0）；

backpatch（M.CHAIN，ip）；

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

③S→N S2{S.CHAIN=merge（S2.CHAIN，N.CHAIN）；}

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

①D→while B do{backpatch(B.T，ip)；

D.CHAIN=B.F；

D.CODE=B.T；}

②S→D S1{backpatch(S1.CHAIN，D.CODE)；

emit(goto D.CODE)；

S.CHAIN=D.CHAIN；}

6 總結(jié)

采用語義模型的表示，直觀地表達(dá)了控制轉(zhuǎn)移，對文法產(chǎn)生式的改寫和語義子程序的構(gòu)造提供了清晰的思路，實(shí)踐表明，在編譯原理課程的教學(xué)中，有效地幫助學(xué)生理解了語義分析的原理和技術(shù)。

參考文獻(xiàn)：

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

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

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

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

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

（作者單位：四川電子科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院）