編譯實驗課程的教學(xué)研究與實踐

竇 亮 楊宗源 王婷婷

摘要:本文在研究了國內(nèi)外高校編譯實驗課程教學(xué)情況的基礎(chǔ)上,介紹了華東師范大學(xué)計算機(jī)系“編譯原理實踐”課的實施情況。教師從教學(xué)內(nèi)容、教學(xué)方法、教學(xué)手段等方面對該課程進(jìn)行了深入的研究和改革,提高了學(xué)生的動手實踐能力,有助于培養(yǎng)學(xué)生的“計算機(jī)思維能力”。

關(guān)鍵詞:編譯原理;實踐教學(xué);課程改革

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

“編譯原理”是計算機(jī)專業(yè)的一門核心基礎(chǔ)課程,所介紹的知識是計算機(jī)專業(yè)理論知識的重要組成部分,包含了用計算機(jī)解決問題的基本思路和方法。

在教學(xué)中,理論與實踐是相輔相成,互為促進(jìn)的,因此編譯實驗內(nèi)容的合理設(shè)置對搞好整個編譯教學(xué)起著至關(guān)重要的作用。我們一直非常重視編譯實驗的教學(xué),多年來不斷研究國內(nèi)外高校的教學(xué)情況,結(jié)合學(xué)生的實際,對該課程進(jìn)行了深入改革,取得了一定成效。

1國內(nèi)外高校編譯實驗課程的研究

1.1國外高校情況

斯坦福大學(xué)(Stanford University)的編譯課程使用的主要參考教材是業(yè)界經(jīng)典的“龍書”——《Compilers Principles, Techniques and Tools》。課程實驗內(nèi)容分為4部分,在課程的不同階段進(jìn)行布置:①詞法分析(使用Flex);②語法分析(使用Bison);③語義分析;④綜合前面的部分實現(xiàn)一個完整的Decaf編譯器,生成在SPIM模擬器上執(zhí)行的代碼。實驗的后兩部分較前兩部分難度高,因此所給分值不同,分別是50分、60分、125分和125分。整個實驗部分占到了編譯課程總評的70%。

卡內(nèi)基梅隆大學(xué)(Carnegie Mellon University)在編譯技術(shù)領(lǐng)域享有很高的國際聲譽,該校的編譯課程使用的主要參考教材是業(yè)界經(jīng)典的“虎書”——《Modern Compiler Implementation》(ML版本)。實驗題目共有5道:①擴(kuò)展給定的L1語言的編譯器,使之能夠?qū)⒃创a轉(zhuǎn)換成真實的X86匯編代碼;②實現(xiàn)支持L2語言的完整編譯器;③實現(xiàn)支持L3語言的完整編譯器;④實現(xiàn)另一個支持L3語言并生成安全代碼的完整編譯器;⑤兩者選其一,實現(xiàn)L3編譯器的各種代碼優(yōu)化或者實現(xiàn)L3的垃圾收集器。實驗部分量很大,使用的現(xiàn)代編譯器技術(shù)含量高,分?jǐn)?shù)也占到了編譯課程總評的70%。

加州大學(xué)伯克利分校(University of California, Berkeley)的編譯課程使用的參考教材也是“龍書”。課程實驗要求實現(xiàn)一個Python語言編譯器,依次分為3個項目:①完成針對Python語言子集的詞法和語法分析器;②實現(xiàn)靜態(tài)分析;③實現(xiàn)機(jī)器代碼的生成。實驗部分占到編譯課程總評的55%。

華盛頓大學(xué)(Washington University)使用的參考教材是《Engineering a Compiler》(Cooper & Torczon)。課程實驗項目是將一個用Java寫的簡單編譯器完善成一個支持MiniJava(Java語言子集)的功能完整的編譯器。項目分5個階段實施,分別是擴(kuò)展MiniJava編譯器,完成詞法分析、語法分析、類型檢查、中間代碼生成和目標(biāo)代碼生成。實踐部分占編譯課程總評的40%。

總體來看,國外高校的編譯課程非常重視實驗,實驗內(nèi)容量大且要求高,涉及到了面向?qū)ο笳Z言編譯器實現(xiàn)、代碼優(yōu)化等高級內(nèi)容。學(xué)生提交的實驗作業(yè)須遵循嚴(yán)格的學(xué)術(shù)道德,嚴(yán)禁抄襲。課程往往配備2～3名助教,解答學(xué)生疑問,協(xié)助教師檢查實驗作業(yè)。

1.2國內(nèi)高校情況

國防科學(xué)技術(shù)大學(xué)的編譯課程使用的教材是陳火旺院士領(lǐng)銜編著、國內(nèi)高校廣泛使用的《程序設(shè)計語言編譯原理》。課程設(shè)置有兩個實驗:①調(diào)試PL編譯程序,擴(kuò)充PL語言成分,并對相應(yīng)的編譯程序進(jìn)行擴(kuò)充;②了解編譯程序構(gòu)造工具Lex、Yacc和JavaCC的使用。實驗成績占總評的20%。

清華大學(xué)的編譯課程教材選用的是自行編寫的《編譯原理》(呂映芝等著)。實驗內(nèi)容題目由學(xué)生根據(jù)能力自選,分別是:①對PL/0編譯程序進(jìn)行擴(kuò)充,用Lex和Yacc實現(xiàn)一個簡單解釋器;②Deacf編譯程序的設(shè)計和實現(xiàn);③Java實現(xiàn)的Mini-Triangle編譯程序。三個題目難度從低到高,分?jǐn)?shù)所占總評的比例分別是20%、40%和50%。

武漢大學(xué)的編譯原理課程是國家精品課程,教材是自行編寫的《編譯原理》(何炎祥編著)。課程實驗是先在課堂上舉出完整的小語言實現(xiàn)的例子,然后將該小語言擴(kuò)充后作為實習(xí)內(nèi)容;或者提供程序源代碼而空缺關(guān)鍵模塊,讓學(xué)生完成。

吉林大學(xué)的編譯原理課程是教育部—微軟精品課程,教材是自行編寫的《編譯程序構(gòu)造原理和實現(xiàn)技術(shù)》(金成植著)。該校專門開設(shè)了獨立的編譯原理實踐課程,共包含8個實驗:詞法分析程序開發(fā)、遞歸下降分析法、LL(1)語法分析、符號表管理、語義分析、中間代碼生成、中間代碼優(yōu)化和目標(biāo)代碼生成。

以上高校的編譯實驗課程教學(xué)具一定代表性。根據(jù)調(diào)查,國內(nèi)高校編譯實驗課程的教學(xué)大致有以下幾種安排:

(1) 安排多次小型實驗,分別支持編譯程序的各個階段。此種方式是目前國內(nèi)大部分高校采取的形式,由于編譯過程每個階段都有特定的方法和技術(shù),故可以針對各個階段設(shè)計不同的實驗,根據(jù)理論教學(xué)的情況靈活安排。實驗難度相對較低,能夠讓學(xué)生掌握編譯的有關(guān)技術(shù),缺點是不能讓學(xué)生學(xué)習(xí)到一個完整編譯器的開發(fā)運行過程。

(2) 針對某一語言設(shè)計和實現(xiàn)一個相對完整、獨立的編譯器,或者研習(xí)現(xiàn)有的編譯程序,對其進(jìn)行擴(kuò)充。這種方式的難度根據(jù)語言規(guī)模的不同以及學(xué)生擴(kuò)充程度的不同而有差別,彈性較大,有利于加強(qiáng)學(xué)生對編譯程序的整體認(rèn)識,且能充分鍛煉學(xué)生的編程能力。

(3) 借助Lex和Yacc等自動生成工具直接生成編譯程序。這種方式需要學(xué)生花一定量時間研究工具的基本原理及使用方法,對編譯程序前端成熟的理論知識是一個很好的再學(xué)習(xí)過程,但對編程能力鍛煉不多。

(4) 其他涉及編譯技術(shù)的實驗。此類實驗強(qiáng)調(diào)編譯技術(shù)在實際軟件工程中的應(yīng)用,如將詞法分析器的設(shè)計擴(kuò)展為中文網(wǎng)頁分詞的應(yīng)用等,有助于培養(yǎng)學(xué)生理論聯(lián)系實際的能力,靈活性較大。

總體來看,根據(jù)學(xué)生水平層次和培養(yǎng)目標(biāo)的不同,國內(nèi)許多高校實施了不同的實驗,比較強(qiáng)調(diào)編譯器前端的代碼翻譯技術(shù),重視編譯器最基本原理的實踐,以培養(yǎng)學(xué)生的邏輯思維能力、編程和綜合應(yīng)用能力。

2我校編譯原理實驗課程的實踐

2.1教學(xué)簡介

我校計算機(jī)系自1979年建系時就開設(shè)了編譯課程,在理論教學(xué)的同時給出一個精簡的高級語言,要求學(xué)生完成詞法分析和語法分析。為了適應(yīng)我國人才培養(yǎng)標(biāo)準(zhǔn)不斷提高的要求,結(jié)合對國外高校編譯實驗課教學(xué)情況的研究,我們認(rèn)為應(yīng)該更加強(qiáng)調(diào)編譯實驗,適當(dāng)提高難度,結(jié)合軟件工程中的思想培養(yǎng)學(xué)生理論聯(lián)系實際的能力。因此,從2004年起,我們將原來在一學(xué)期同時完成理論和實踐教學(xué)的“編譯原理”課程拆分成在第6學(xué)期先講授理論知識,第7學(xué)期專門開設(shè)“編譯原理實踐”課程,要求學(xué)生獨立設(shè)計和實現(xiàn)一個完整的編譯器,經(jīng)過幾年的實踐探索,收到了良好的效果。

2.1.1課程描述

課程名稱為“編譯原理實踐”,屬專業(yè)必修課。課程選擇了著名計算機(jī)科學(xué)家N.Wirth教授提供的PL/0語言作為實驗語言,該語言是程序設(shè)計語言的典型代表,國內(nèi)較多高校采用其作為編譯教學(xué)使用語言。教師講解PL/0編譯程序構(gòu)建后,要求學(xué)生實現(xiàn)一個完整的PL/X語言編譯程序(教師給出PL/X語言的形式化語法定義),包括詞法分析、語法分析、出錯處理、代碼生成和解釋程序,然后用PL/X語言編若干個程序,用自己開發(fā)的編譯程序進(jìn)行編譯,能指出語法錯誤不中斷,能生成代碼程序,能解釋執(zhí)行代碼程序,最后輸出正確結(jié)果。更重要的是,鼓勵學(xué)生對PL/X語言進(jìn)行定義擴(kuò)展,增加更多功能。教師還演示了使用Lex和Yacc生成PL/0語言編譯器的過程,鼓勵學(xué)生在編程實現(xiàn)PL/X編譯器的基礎(chǔ)上再使用Lex和Yacc構(gòu)建編譯器。

2.1.2組織形式

課程總學(xué)時72學(xué)時,其中教師講課20學(xué)時,學(xué)生上機(jī)52學(xué)時,教師講課集中在前10周完成。教師講授PL/0編譯程序的設(shè)計開發(fā)占16學(xué)時,介紹使用Lex和Yacc生成PL/0語言編譯器占4學(xué)時。

為了充分鍛煉學(xué)生的綜合能力,避免學(xué)生投機(jī)取巧,產(chǎn)生依賴心理,課程不采用分組的形式,而是要求每個學(xué)生都必須獨立實現(xiàn)PL/X語言編譯程序。

2.1.3評分規(guī)則

評分規(guī)則規(guī)定,文檔、程序、測試用例齊全,現(xiàn)場考核通過,成績?yōu)?0分。學(xué)生對PL/X語言進(jìn)行擴(kuò)充的內(nèi)容建議為:①增加運算符定義,如XOR、%等;②擴(kuò)充語句定義,如case、for、continue等;③增加數(shù)據(jù)類型,在現(xiàn)有整型/邏輯型基礎(chǔ)上增加實數(shù)、記錄類型、數(shù)組類型等;④增加函數(shù)調(diào)用功能,進(jìn)一步擴(kuò)充帶參數(shù)、返回值的函數(shù)功能;⑤增加類,補(bǔ)充封裝、繼承、多態(tài)等面向?qū)ο筇匦?。根?jù)擴(kuò)充內(nèi)容的難易進(jìn)行累計,給予2～40分的加分。此外,良好的用戶界面可獲得加分;以Lex和Yacc工具生成編譯器也可獲得加分。

2.2經(jīng)驗總結(jié)

2.2.1突破教學(xué)難點,理論結(jié)合實踐

課程改進(jìn)主要有兩點:一是由于N.Wirth教授采用Pascal語言實現(xiàn)PL/0編譯程序,而學(xué)生不熟悉Pascal語法,因此我們同時提供C語言版本的PL/0編譯程序;二是分階段系統(tǒng)地講授PL/0語言編譯程序各個階段的設(shè)計開發(fā),按順序給出各個版本的范例程序,學(xué)生可以跟著教師的講授進(jìn)度進(jìn)行同步的PL/X編譯程序的開發(fā)。這種方式降低了開發(fā)難度,使學(xué)生可以看到自己的開發(fā)成果不斷完善,增強(qiáng)了信心,提高了繼續(xù)探索的興趣。

對課程的難點,教師也注意講解方法,理論結(jié)合實踐,使用多種教學(xué)手段。比如PL/0編譯器生成的目標(biāo)代碼是一種假想棧式計算機(jī)的匯編語言,而學(xué)生很少直接接觸匯編語言,對目標(biāo)代碼指令感到陌生,且運行時的存儲組織與分配又是編譯原理的一個難點,因此教學(xué)就采用了先易后難的辦法。先給出不含過程調(diào)用的PL/0源程序生成的目標(biāo)代碼,詳細(xì)介紹目標(biāo)代碼執(zhí)行時數(shù)據(jù)棧的變化情況;繼而給出含有過程調(diào)用的PL/0源程序生成的目標(biāo)代碼,再次分步介紹目標(biāo)代碼執(zhí)行時數(shù)據(jù)棧的變化情況,重點講解靜態(tài)鏈、動態(tài)鏈、返回地址3個聯(lián)系單元的作用;接著使用多媒體教學(xué)軟件,以動畫方式完整演示數(shù)據(jù)棧的變化情況,給學(xué)生整體思路;最后復(fù)習(xí)理論教學(xué)中各種運行時的存儲組織與分配情況,讓學(xué)生有深刻的體會。

再如語義分析和代碼生成部分,一直是理論教學(xué)的難點,特別是控制流語句的回填技術(shù)等,在教師詳細(xì)講解了PL/0編譯器中if語句和while語句的語義分析和代碼生成實現(xiàn)后,學(xué)生對此有了實際體會,更進(jìn)一步對for、case語句的實現(xiàn)產(chǎn)生興趣,有動手將理論課上的方法用在作品中的意愿。

2.2.2激發(fā)學(xué)生潛能,延伸第二課堂

課程的實驗內(nèi)容設(shè)計成可擴(kuò)展的,使不同層次學(xué)生都可以接受。由于有了分階段的完整示例,基礎(chǔ)薄弱、編程能力較差的學(xué)生只需在基本理解的情況下就可以模仿PL/0編譯器構(gòu)造PL/X編譯器,消除了畏難心理;對于能力較強(qiáng)的同學(xué),教師羅列出可擴(kuò)展內(nèi)容的建議,激發(fā)學(xué)生積極主動實踐的意愿,拓寬學(xué)生的創(chuàng)新思維視角。

在教學(xué)計劃中,學(xué)生上機(jī)是52學(xué)時,但課程要求實現(xiàn)的是一個完整的編譯器,具有一定工作量,若要實現(xiàn)擴(kuò)展,需要更多時間,大部分學(xué)生難以在課堂內(nèi)完成,這就要充分發(fā)揮第二課堂的作用。課內(nèi)教師把握主要矛盾,對于擴(kuò)展難度較高的部分,則給學(xué)生思路上的啟迪。借助課程網(wǎng)站的功能,給學(xué)生提供編譯技術(shù)文檔、編譯源程序等自學(xué)資料,鼓勵學(xué)生通過各種渠道搜尋相關(guān)資料,并利用網(wǎng)絡(luò)相互討論,助教協(xié)助解答問題,實現(xiàn)第二課堂的功效。

2.2.3考核科學(xué)嚴(yán)格,樹立良好學(xué)風(fēng)

課程要求學(xué)生提交完整規(guī)范的文檔、程序和測試用例。現(xiàn)場考核要求學(xué)生演示程序、回答問題、改寫程序,實現(xiàn)教師提出的特定功能,這樣能夠充分檢驗出學(xué)生的真實水平,并鍛煉學(xué)生的表達(dá)能力和快速解決問題的能力。

在課程開始時,教師重點強(qiáng)調(diào)禁止抄襲,借助程序?qū)Ρ溶浖z查雷同性,無論是抄襲者還是被抄襲者,均不能通過考試。在前兩屆學(xué)生中嚴(yán)格執(zhí)行該規(guī)定后,后續(xù)學(xué)生逐漸形成了良好的學(xué)習(xí)風(fēng)氣。連續(xù)五屆學(xué)生的實踐表明,學(xué)生的潛力是無窮的,許多優(yōu)秀作品充分展示了學(xué)生的創(chuàng)新能力。我們選取了一些優(yōu)秀的作品,將其功能演示的全過程錄制成視頻,放在課程網(wǎng)站上,為下一屆學(xué)生提供參考,也激勵他們創(chuàng)作出更完善、更富創(chuàng)新的作品。

正是由于我們將教學(xué)目標(biāo)定在國內(nèi)外先進(jìn)的水平上,在教學(xué)內(nèi)容、教學(xué)方法上不斷改進(jìn),我校編譯課程始終受到學(xué)生的普遍認(rèn)可,在學(xué)生評教中處于前列。該課程成為華東師范大學(xué)精品課程后,2009年成功成為“上海市精品課程”。當(dāng)然,和國外著名的高校相比,我們還需要進(jìn)一步提高科研水平,不斷跟進(jìn)編譯技術(shù)的發(fā)展,在理論和實踐方面進(jìn)一步增加現(xiàn)代編譯器技術(shù)的教學(xué)內(nèi)容,使學(xué)生在編譯系統(tǒng)方面獲得更大的收獲和提高,有效和國際接

軌。

3結(jié)束語

編譯課程理論難度高,一直是學(xué)生反映難學(xué)的一門課程,因此近年部分高校降低了編譯課程的教學(xué)難度,減少了實驗內(nèi)容,甚至有學(xué)校提出將其從本科教學(xué)計劃中刪除。通過對國內(nèi)外高校編譯課程教學(xué)的研究,我們認(rèn)為,編譯課程在提高學(xué)生“計算機(jī)思維能力”,培養(yǎng)學(xué)生專業(yè)素養(yǎng)方面起著非常重要的作用。要真正做好編譯教學(xué),教師要從教學(xué)內(nèi)容、教學(xué)方法、教學(xué)手段等方面綜合提高,結(jié)合科研,跟進(jìn)編譯技術(shù)的發(fā)展,才能使學(xué)生更好地領(lǐng)會和掌握基本編譯原理,為將來從事軟件開發(fā)工作夯實基礎(chǔ)。

參考文獻(xiàn):

[1] 斯坦福大學(xué). 編譯課程網(wǎng)站[DB/OL]. [2009-9-16]. http://www.stanford.edu/class/cs143/.

[2] 卡內(nèi)基梅隆大學(xué). 編譯課程網(wǎng)站[DB/OL]. [2009-9-16]. http://www.cs.cmu.edu/～fp/courses/15411-f08/.

[3] 加州大學(xué)伯克利分校. 編譯課程網(wǎng)站[DB/OL]. [2009-9-16]. http://www-inst.eecs.berkeley.edu/～cs164/sp09/.

[4] 華盛頓大學(xué). 編譯課程網(wǎng)站[DB/OL]. [2009-9-16]. http://www.cs.washington.edu/education/courses/401/08au/.

[5] 國防科學(xué)技術(shù)大學(xué). 編譯原理精品課程網(wǎng)站[DB/OL]. [2009-9-16]. http://sei.nudt.edu.cn/cp/index.php.

[6] 武漢大學(xué). 編譯原理精品課程教學(xué)網(wǎng)站[DB/OL]. [2009-9-16]. http://jpkc.whu.edu.cn/jpkc2005/byyl/.

[7] 吉林大學(xué). 編譯原理精品課網(wǎng)站[DB/OL]. [2009-9-16]. http://www.jlu-softlab.cn/education/compiler.

[8] 唐仕喜. 編譯技術(shù)可擴(kuò)展式課程設(shè)計改革研究[J]. 計算機(jī)教育,2009(2):40-42.

[9] 斯傳根. 編譯設(shè)計與開發(fā)技術(shù)[M]. 北京:清華大學(xué)出版社,2003.

[10] 何炎祥,伍春香. 計算機(jī)專業(yè)不需要開設(shè)編譯原理課程嗎?[J]. 計算機(jī)教育,2009(4):61-62.

Research and Practice on the Experiment Course of Compiler Principles

DOU Liang, YANG Zong-yuan, WANG Ting-ting

(Department of Computer Science, East China Normal University, Shanghai 200241, China)

Abstract: The paper introduces the teaching of “Practice of Compiler Principles” in Computer Science Depart of ENCU based on the research of the same course in other universities worldwide. We perform in-deep study and reform on all aspects of the course such as teaching contents, teaching methods and course assignments, which greatly improves the students ability of hands-on experience and helps to build the ideation on computer science.

Key words: compiler principles; practice teaching; course reform