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

吳海濤

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

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

中圖分類號(hào):G642 文獻(xiàn)標(biāo)識(shí)碼:B

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

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

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

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

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

1實(shí)驗(yàn)教學(xué)方案

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

1.1語法和詞法

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

::= + | -

|

::= * | /

|

::= () | num

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

::=

::= +

| - |ε

::=

::= *

| / | ε

::= () | num

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

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

運(yùn)算符有+、-、*、/;

界符有(、);

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

空白包括空格、換行符和水平制表符,用來分開運(yùn)算符、界符和非負(fù)整數(shù)。空白也可以不包括換行符,這時(shí)換行符可以作為表達(dá)式的終結(jié)標(biāo)志。

1.2詞法分析

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

單詞符號(hào)的種類和所屬類型可定義如下:

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

PLUS, MINUS, TIMES, SLASH,

LPAREN, RPAREN } Symbol;

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

NUM: 1

+

NUM: 2

*

(

NUM: 3

+

NUM: 4

)

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

Symbol gettoken();

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

1.3語法分析

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

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

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

1.4語義分析

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

(1)ASTNode *mknode(Symbol op, ASTNode *arg1, ASTNode *arg2):返回新創(chuàng)建的一個(gè)運(yùn)算節(jié)點(diǎn),結(jié)點(diǎn)的sym域?yàn)閛p,表示運(yùn)算,域arg1和arg2分別指向一棵子樹。

(2)ASTNode *mkleaf(Symbol num, ValType val):返回新創(chuàng)建的一個(gè)數(shù)節(jié)點(diǎn),結(jié)點(diǎn)的sym域?yàn)閚um,表示數(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è)計(jì),可參考文獻(xiàn)[8]中的156-158頁。具體實(shí)現(xiàn)時(shí),可以以語法分析實(shí)驗(yàn)中所實(shí)現(xiàn)的語法分析程序?yàn)榛A(chǔ)進(jìn)行修改,實(shí)現(xiàn)表達(dá)式的遞歸下降翻譯器。

1.5代碼生成

需要實(shí)現(xiàn)的代碼生成程序的功能是,以語義分析實(shí)驗(yàn)中所實(shí)現(xiàn)的語義分析程序的四元式輸出作為輸入,輸出匯編語言程序。例如1+2*(3+4)對(duì)應(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

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

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

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

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

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

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

2實(shí)驗(yàn)教學(xué)效果及問題

2.1實(shí)驗(yàn)教學(xué)效果

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

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

2.2 問題

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

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

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

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

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

3結(jié)語

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

參考文獻(xiàn):

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

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

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

[4] 胡學(xué)聯(lián). 編譯原理課程的調(diào)態(tài)與轉(zhuǎn)型[J]. 計(jì)算機(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. 編譯原理與實(shí)踐(英文影印版)[M]. 北京:機(jī)械工業(yè)出版社,2002.

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

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