“編譯原理”課程實驗教學(xué)研究與探索

吳海濤

摘要:為促進學(xué)生更好地掌握“編譯原理”課程內(nèi)容,激發(fā)學(xué)生學(xué)習(xí)興趣,并通過實踐對編譯程序的功能有清晰的理解,使教學(xué)既要面向多數(shù)學(xué)生,又要涵蓋更多內(nèi)容,本文提出一種“編譯原理”課程實驗教學(xué)方案,通過讓學(xué)生實現(xiàn)一個非負(fù)整數(shù)四則運算的多遍編譯程序,說明該方案在具體實施后的教學(xué)效果以及在實施過程中應(yīng)注意的問題。

關(guān)鍵詞:編譯原理;實驗教學(xué);課堂教學(xué)

中圖分類號:G642 文獻標(biāo)識碼:B

“編譯原理”課程是高校計算機專業(yè)的一門重要專業(yè)基礎(chǔ)課程,在專業(yè)課程體系中處于一個極其重要的地位。但是,“編譯原理”課程綜合性比較強,涉及的先修課程比較多,包括離散數(shù)學(xué)、程序設(shè)計、數(shù)據(jù)結(jié)構(gòu)、匯編語言等,對學(xué)生專業(yè)知識掌握情況要求比較高,是一門公認(rèn)比較難學(xué)、比較難教的課程。因此,如何使學(xué)生學(xué)好這門課是任課教師要用心解決的問題。

計算機學(xué)科是一門對實踐性要求比較高的學(xué)科,很多東西不能認(rèn)為聽懂看懂就是理解、掌握,需要編程去實現(xiàn)才能說是真正理解、掌握。因此,在考慮如何使學(xué)生學(xué)好“編譯原理”課程時,就考慮著如何把理論和實踐結(jié)合起來,促進學(xué)生對課程的學(xué)習(xí)。國內(nèi)不少學(xué)者對“編譯原理”實踐教學(xué)以及如何把理論與實踐結(jié)合起來提出了自己的觀點、思路,并通過教學(xué)實踐進行探索。國外教材也有不少范例可供參考。Alfred V. Aho等人編著的《編譯原理》先給出一個小的編譯程序范例,給讀者一個對編譯程序的直觀感受,然后再逐步展開來講解編譯的各項原理和技術(shù)。Andrew W. Appel等人編著的《現(xiàn)代編譯原理》將MiniJava語言的實現(xiàn)貫穿于整本書之中。Kenneth C. Louden編著的《編譯原理與實踐》把Tiny語言編譯程序作為范例,在講解每章內(nèi)容后,再講解Tiny語言編譯程序中的相關(guān)部分的實現(xiàn)方法。

但是,在具體實施教學(xué)時,由于授課對象不同,希望達到的教學(xué)目標(biāo)和效果不同,因此在設(shè)計實驗教學(xué)方案時,就有不同的考慮。為了促進學(xué)生更好地掌握課程內(nèi)容,激發(fā)學(xué)生的學(xué)習(xí)興趣,并通過實踐對編譯程序的功能有清晰的理解,既要面向多數(shù)學(xué)生,又要涵蓋更多的教學(xué)內(nèi)容,經(jīng)過考慮,決定讓學(xué)生實現(xiàn)一個非負(fù)整數(shù)四則運算的的多遍編譯程序。這樣的編譯程序雖小,但五臟俱全。

四則運算是“編譯原理”課程的經(jīng)典范例,采用多遍編譯的好處是整個編譯程序的邏輯結(jié)構(gòu)比較清晰,實驗內(nèi)容安排起來比較方便。在設(shè)計具體實驗內(nèi)容時,把課堂教學(xué)內(nèi)容和實驗內(nèi)容緊密結(jié)合起來,這樣一來,課堂教學(xué)內(nèi)容的講解可以為實驗作準(zhǔn)備,而實現(xiàn)實驗內(nèi)容可以進一步加深學(xué)生對課堂教學(xué)內(nèi)容的理解。由于實驗教學(xué)課時有限,為了在有限的時間內(nèi)達到好的教學(xué)效果,盡可能地發(fā)揮實驗教學(xué)的效能,在設(shè)計具體實驗內(nèi)容時,把每個實驗要求學(xué)生做什么、具體完成什么功能、如何去做、需要用到什么數(shù)據(jù)結(jié)構(gòu)、各個模塊間如何銜接都作出了詳細(xì)說明。文獻[8]包含實驗所需的各項技術(shù)。

下面首先介紹實驗教學(xué)方案,然后說明實驗教學(xué)效果以及應(yīng)注意的問題,最后是結(jié)束語。

1實驗教學(xué)方案

實驗總體任務(wù)是,經(jīng)過詞法分析、語法分析、語義分析與中間代碼生成、目標(biāo)代碼生成四個階段,將給定的非負(fù)整數(shù)四則運算表達式翻譯為匯編語言代碼。每個階段設(shè)置一個實驗,共四個實驗。當(dāng)?shù)谒膫€實驗完成時,應(yīng)該得到一個符合實驗總體任務(wù)的編譯程序。

1.1語法和詞法

語法分析部分采用遞歸子程序法。為使學(xué)生在編程時命名方便,非負(fù)整數(shù)四則運算表達式的文法采用如下形式:

::= + | -

|

::= * | /

|

::= () | num

消除左遞歸后的文法如下:

::=

::= +

| - |ε

::=

::= *

| / | ε

::= () | num

在如上文法中,、、、和為非終結(jié)符,+、-、*、/、(、)、num為終結(jié)符。

詞法規(guī)則說明如下:

運算符有+、-、*、/;

界符有(、);

非負(fù)整數(shù)有num。

空白包括空格、換行符和水平制表符,用來分開運算符、界符和非負(fù)整數(shù)?？瞻滓部梢圆话〒Q行符,這時換行符可以作為表達式的終結(jié)標(biāo)志。

1.2詞法分析

需要實現(xiàn)的詞法分析程序的功能是,接受一個表達式,輸出該表達式中的各類單詞符號。測試詞法分析程序時,可以按照一定格式輸出各類單詞符號。

單詞符號的種類和所屬類型可定義如下:

typedef enum Symbol { ERR = -1, END, NUM,

PLUS, MINUS, TIMES, SLASH,

LPAREN, RPAREN } Symbol;

在實現(xiàn)詞法分析程序時,對運算符和界符只需處理種類編碼,而對非負(fù)整數(shù)需要處理其對應(yīng)的具體屬性信息。ERR表示詞法分析錯,END表示表達式分析結(jié)束。例如,測試詞法分析程序時,1+2*(3+4)所對應(yīng)的單詞符號序列的一種輸出形式如下:

NUM: 1

+

NUM: 2

*

(

NUM: 3

+

NUM: 4

)

詞法分析函數(shù)的原型如下:

Symbol gettoken();

實現(xiàn)的具體方法可參考文獻[8]中的44-46頁。另外,可以根據(jù)學(xué)生的具體情況,把一些要求進一步明確。

1.3語法分析

需要實現(xiàn)的語法分析程序的功能是,接受一個表達式,分析該表達式,并根據(jù)輸入正確與否輸出相應(yīng)信息。測試時,如果輸入的表達式分析正確,則輸出表示分析正確的信息;否則,輸出表示分析錯誤的信息。這里對出錯處理不做太高要求,能達到在遇到錯誤時,輸出錯誤提示,然后程序立即終止執(zhí)行就可以了。當(dāng)然,如果學(xué)生能力比較強,可以考慮更加細(xì)致的出錯處理。

語法分析程序由一組遞歸過程組成,文法中每個非終結(jié)符對應(yīng)一個過程。在分析過程中,語法分析程序需要調(diào)用詞法分析實驗中所實現(xiàn)的詞法分析程序,這是個關(guān)鍵。

實現(xiàn)的具體方法可參考文獻[8]中的74-76頁。

1.4語義分析

需要實現(xiàn)的語義分析程序的功能是,接受一個表達式,分析該表達式,并在分析的過程中建立該表達式的抽象語法樹,然后輸出表達式所對應(yīng)的四元式序列。嚴(yán)格來說,非負(fù)整數(shù)四則運算表達式的抽象語法樹是一棵樹,但不嚴(yán)格的說也可以看作是一棵二叉樹,而看作二叉樹時所得到的中序遍歷序列應(yīng)該和輸入的表達式一樣——除了沒有括號之外。因此,可提示學(xué)生,通過輸出中序遍歷序列檢測程序功能是否正確。如果每個分支節(jié)點用一個臨時變量標(biāo)記,則對四則運算表達式的抽象語法樹進行后序遍歷,可以得到輸入表達式所對應(yīng)的四元式序列。例如輸入1+2*(3+4),對應(yīng)的抽象語法樹的中序遍歷序列、四元式序列分別為:

1+2*3+4

和

+ 3 4 T1

* 2 T1T2

+ 1 T2T3

抽象語法樹類型的一種定義為:

typedef int ValType;

typedef struct ASTNode {

Symbol sym;

ValType val;

struct ASTNode * arg1, *arg2;

} ASTNode, *AST;

創(chuàng)建節(jié)點的操作有兩個,對應(yīng)的函數(shù)頭部和功能分別如下:

(1)ASTNode *mknode(Symbol op, ASTNode *arg1, ASTNode *arg2):返回新創(chuàng)建的一個運算節(jié)點,結(jié)點的sym域為op,表示運算,域arg1和arg2分別指向一棵子樹。

(2)ASTNode *mkleaf(Symbol num, ValType val):返回新創(chuàng)建的一個數(shù)節(jié)點,結(jié)點的sym域為num,表示數(shù),域val用于存放數(shù)的值。

建立抽象語法樹的語義規(guī)則為:

E ::= E1 + T E.nptr := mknode( ‘+, E1.nptr, T.nptr )

E ::= E1 – T E.nptr := mknode( ‘-, E1.nptr, T.nptr )

E ::= T E.nptr := T.nptr

T ::= T1 * F T.nptr := mknode( ‘*, T1.nptr, F.nptr )

T ::= T1 / F T.nptr := mknode( ‘/, T1.nptr, F.nptr )

T ::= F T.nptr := F.nptr

F ::= (E) F.nptr := E.nptr

F ::= num F.nptr := mkleaf(num, num.val )

消除左遞歸的翻譯模式為:

E ::= T {E'.i:=T.nptr} E' {E.nptr:=E'.s}

E'::= + T {E'1.i:=mknode(‘+,E'.i,T.nptr)}

E'1 {E'.s:=E1.s}

E'::= - T {E'1.i:=mknode(‘-,E'.i,T.nptr)}

E'1 {E'.s:=E1.s}

E'::= ε {E'.s:= E'.i}

T ::= F {T'.i:=F.nptr} T' {T.nptr:=T'.s}

T'::= * F {T'1.i:=mknode(‘*,T'.i,F.nptr)}

T'1 {T'.s:=T1.s}

T'::= / F {T'1.i:=mknode(‘/,T'.i,F.nptr)}

T'1 {T'.s:=T1.s}

T' ::= ε {T'.s:= T'.i}

F ::= (E) {F.nptr:=E.nptr}

F ::= num {F.nptr:=mkleaf(num,num.val)}

語義分析部分的核心是遞歸下降翻譯器的設(shè)計,可參考文獻[8]中的156-158頁。具體實現(xiàn)時,可以以語法分析實驗中所實現(xiàn)的語法分析程序為基礎(chǔ)進行修改,實現(xiàn)表達式的遞歸下降翻譯器。

1.5代碼生成

需要實現(xiàn)的代碼生成程序的功能是,以語義分析實驗中所實現(xiàn)的語義分析程序的四元式輸出作為輸入,輸出匯編語言程序。例如1+2*(3+4)對應(yīng)的輸出為:

.386

.MODEL FLAT

ExitProcess PROTO NEAR32 stdcall,

dwExitCode:DWORD

INCLUDE io.h ; header file for input/output

cr EQU 0dh ; carriage return character

Lf EQU 0ah ; line feed

.STACK 4096 ; reserve 4096-byte stack

.DATA ; reserve storage for data

t DWORD 40 DUP (?)

label1 BYTE cr, Lf, "The result is "

result BYTE 11 DUP (?)

BYTE cr, Lf, 0

.CODE ; start of main program code

_start:

mov eax, 3

add eax, 4

mov t+0, eax

mov eax, 2

mov ebx, t+0

mul ebx

mov t+4, eax

mov eax, 1

add eax, t+4

mov t+8, eax

mov eax, t+8

dtoa result, eax ; convert to ASCII characters

outputlabel1 ; output label and sum

INVOKE ExitProcess,0 ; exit with

; return code 0

PUBLIC _start ; make entry point public

END ; end of source code

輸出的匯編代碼借鑒了文獻[9]中的格式,并使用了文獻[9]所提供的輸入輸出例程。

在所生成的匯編代碼中,tDWORD40 DUP (?)定義了40個雙字(每個雙字占4字節(jié)大小),用作臨時變量,可根據(jù)需要調(diào)整大小,當(dāng)然更好的方法是在棧中分配臨時變量。

生成代碼時,學(xué)生只需考慮如何生成_start:和dtoaresult, eax之間的匯編碼。開頭到_start:部分和dtoaresult, eax到結(jié)尾部分的匯編碼可以按所給的例子原樣輸出。

翻譯時,采用將四元式直譯為匯編碼的方法。在學(xué)生實現(xiàn)四元式到匯編碼的翻譯時,提示學(xué)生通過分析、對比1+2*(3+4)的四元式序列和匯編碼的對應(yīng)關(guān)系,考慮如何將四元式翻譯為匯編碼。需要特別注意尋址方式、乘法和除法的翻譯問題。

所給匯編程序例子中各個成分的含義,可讓學(xué)生參考文獻[9]。

一般來說,講匯編語言時,通常講的是16位實模式匯編,16位實模式匯編程序在Windows命令提示符下運行有些小問題,文獻[9]中給出的32位匯編程序沒有那些問題,所以在此采用。

2實驗教學(xué)效果及問題

2.1實驗教學(xué)效果

本實驗教學(xué)方案是在本系2008～2009學(xué)年下學(xué)期開設(shè)的編譯原理課程的教學(xué)中開展實施的(使用文獻[8]做教材),學(xué)生的積極性很高,不少學(xué)生開動腦筋,發(fā)揮自己的聰明才智努力完成各個實驗。相對而言,詞法分析和語法分析兩個實驗完成較好,程序有一二十種寫法,但是語義分析和代碼生成兩個實驗就遇到了不少問題。最終能夠獨立完成全部實驗的有五、六位同學(xué),其中有位學(xué)生在剛過一般實驗學(xué)時時就已經(jīng)完成全部實驗。從學(xué)生完成實驗情況來看,學(xué)生的個體能力差異有些偏大。

期末考試卷面成績也在一定程度上體現(xiàn)出實驗教學(xué)的效果。表1是本人所教過的各個年級“編譯原理”課程卷面成績的基本情況,從中可以看出,實驗教學(xué)新方案的實施對學(xué)生成績的提高有明顯作用。這說明,雖然學(xué)生在完成實驗過程中遇到了不少困難,但學(xué)生還是認(rèn)真地考慮了如何完成實驗,因此強化了學(xué)生對相關(guān)內(nèi)容的掌握。

2.2 問題

(1) 雖然在實驗指導(dǎo)書中已經(jīng)詳細(xì)地給出了實驗指導(dǎo),但是有些同學(xué)對一些內(nèi)容還是產(chǎn)生了誤解。例如在詞法分析部分說到測試詞法分析程序時,可以按照一定格式輸出各類單詞符號,但有些學(xué)生把這個要求理解成詞法分析程序本身的功能了。盡管這些學(xué)生能夠完成詞法分析,卻在完成語法分析部分時遇到了麻煩,不知道如何把詞法分析和語法分析銜接起來。

(2) 有些學(xué)生雖然能夠理解各個原理,明白各項技術(shù),并且作業(yè)完成得也比較好,但是,在做實驗時,卻不能熟練編程實現(xiàn)所要求的功能,這反映了理論與實踐脫節(jié)的問題。另外,有些學(xué)生對各個原理理解不清,對各項技術(shù)把握不好,妨礙了實驗的完成。

(3) 不少學(xué)生缺乏實現(xiàn)具有一定規(guī)模程序的能力。按自己實際完成的符合實驗總體任務(wù)的編譯程序估算,學(xué)生完成的最終編譯程序大致應(yīng)該有500行左右的代碼量,這個編程量應(yīng)該基本合適,但現(xiàn)實情況卻有些不太理想。

(4) 學(xué)生運用數(shù)據(jù)結(jié)構(gòu)和算法解決問題的能力方面還有所欠缺。事實上,整個實驗的難點應(yīng)該在語義分析上,那里涉及數(shù)據(jù)結(jié)構(gòu)和算法比較多,學(xué)生容易出現(xiàn)問題。語義分析部分完成得不好也影響到代碼生成部分的完成。

(5) 一些學(xué)生一看到實驗題目,不是想如何自己去完成,而是馬上上網(wǎng)去找答案。在網(wǎng)上通常比較容易找到詞法分析、語法分析程序做參考,但比較難找到符合或接近實驗要求的語義分析、代碼生成程序。因此,學(xué)生在完成詞法分析、語法分析部分時也許還能應(yīng)付,但是在完成語義分析、代碼生成部分時就不知道如何做了,結(jié)果最后實驗不能取得好的效果。

3結(jié)語

這次實驗教學(xué)探索基本達到了預(yù)期目的,雖然在實施過程中遇到了一些問題,但為以后能夠達到更好的教學(xué)效果積累了經(jīng)驗。筆者對實驗方案做進一步改進、完善,以期更好地發(fā)揮實驗教學(xué)效果,提高“編譯原理”課程教學(xué)質(zhì)量。

參考文獻:

[1] 蔣宗禮.“編譯原理”教學(xué)設(shè)計[J]. 計算機教育,2008(3):26-30.

[2] 李冬梅,施海虎.“編譯原理”課程的教學(xué)研究與探索[J]. 計算機教育,2008(8):103-104.

[3] 溫敬和.“編譯原理”課程教學(xué)研究和教材編寫[J]. 計算機教育,2006(5):77-79.

[4] 胡學(xué)聯(lián). 編譯原理課程的調(diào)態(tài)與轉(zhuǎn)型[J]. 計算機教育,2006(11):38-41.

[5] Alfred V.Aho, Ravi Sethi, Jeffrey D.Ullman. 編譯原理 技術(shù)與工具(英文版)[M]. 北京:人民郵電出版社,2002.

[6] Andrew W.Appel, Jens Palsberg. 現(xiàn)代編譯程序?qū)崿F(xiàn)——Java語言(影印版)[M]. 2版. 北京:高等教育出版社,2003.

[7] Kenneth C.Louden. 編譯原理與實踐(英文影印版)[M]. 北京:機械工業(yè)出版社,2002.

[8] 陳火旺,劉春林,譚慶平,等. 程序設(shè)計語言編譯原理 [M]. 3版. 北京:國防工業(yè)出版社,2000.

[9] Richard C. Detmer. 80x86匯編語言與計算機體系結(jié)構(gòu)(英文版)[M]. 北京:機械工業(yè)出版社,2004.