編譯原理語義分析的教學探索

[摘要]編譯原理課程是高校計算機類專業的重要的基礎和骨干課程。而語義分析又是編譯原理課程重點中的難點。設計了抽象機模型，使用抽象機的操作行為描述程序設計語言的語義。針對傳統的分支和循環語句，分析了控制結構的抽象，提出了分支和循環控制語句的語義模型。在編譯原理課程的教學中，有效地幫助學生理解了語義分析的原理和技術。

[關鍵詞]編譯原理 控制結構 語法制導翻譯 語義模型

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

1 抽象機

抽象機由一個指令指針ip、一個存儲器、一個控制器和一個運算器組成。

抽象機一旦啟動，由專門的裝入程序將一個要運行的程序裝入代碼存儲器中，并置ip指向該程序的第一條指令。然后依次完成下述工作。

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

(2）修改ip的內容。

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

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

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

2 語法制導翻譯

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

在語法分析過程中，根據每個產生式所對應的語義子程序（語義動作）進行翻譯（生成中間代碼）的方法稱為語法制導翻譯。

3 控制結構的抽象

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

高級語言結構最終還是要翻譯成傳統計算機的條件轉移和無條件轉移機器代碼。將由編譯程序生成有效的中間代碼，而編譯程序必須利用轉移指令將控制抽象進行具體化。

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

循環控制結構允許程序員控制某些語句可以執行0次或多次。

4 語義模型

（1）單選控制結構語句 if B then S，傳統的流程圖描述語義如圖1所示。

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

if B goto B.T

goto S. next

B.T:

┇//語句S對應的中間代碼段

S.next:

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

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

其中，曲線表示語句S1對應的可能的中間出口轉移。

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

其中，曲線表示語句S1和S1對應的可能的中間出口轉移。

（2）循環控制結構語句 while B do S，傳統的流程圖描述語義如圖4所示。

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

對應的控制可以表示為（中間代碼形式）

again: if B goto B.T

goto S. next

B.T:

┇//語句S對應的中間代碼段

goto again

S.next:

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

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

5 語義子程序

根據控制語句的語義模型，容易得到分支、循環控制語句的語義子程序。

（1）單選控制結構語句if B then S1

①M→if B then{backpatch（B.T，ip)；

M.CHAIN=B.F；}

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

（2) 二選一控制結構語句if B S1else S2

①M→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）循環控制結構語句 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 總結

采用語義模型的表示，直觀地表達了控制轉移，對文法產生式的改寫和語義子程序的構造提供了清晰的思路，實踐表明，在編譯原理課程的教學中，有效地幫助學生理解了語義分析的原理和技術。

參考文獻：

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

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

[3]Andrew W.Apple.編譯器的Java實現[M].北京:電子工業出版社，2004.

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

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

（作者單位：四川電子科技大學計算機科學與工程學院）