編譯實習(xí)課程的創(chuàng)新教學(xué)

摘要：編譯實習(xí)是深入學(xué)習(xí)和理解編譯原理和技術(shù)的重要手段，也是編譯課程的重要組成部分。針對當(dāng)前計算平臺和系統(tǒng)的迅速演進和發(fā)展，北京大學(xué)在編譯實習(xí)的教學(xué)過程中進行創(chuàng)新嘗試，讓學(xué)生面向包括智能手機等在內(nèi)的新型計算平臺開發(fā)一個完整的小型編譯器。文章介紹編譯實習(xí)課程的創(chuàng)新思路，對北京大學(xué)近3年來的實踐情況進行總結(jié)分析并提出展望。

關(guān)鍵詞：編譯原理；編譯實習(xí)；課程創(chuàng)新；移動平臺

0.引言

編譯原理是計算機科學(xué)與技術(shù)專業(yè)本科生的必修課程。國內(nèi)外高校多年的教學(xué)實踐表明，編譯實習(xí)是深入理解編譯原理和技術(shù)的重要途徑，即所有學(xué)生都應(yīng)該能夠自己動手實現(xiàn)一個面向某個簡單語言或語言子集的小型編譯器。編譯實習(xí)可以與編譯原理課程安排在同一個學(xué)期，也可以分開。由于編譯原理課程內(nèi)容較多并且較難，目前北京大學(xué)采用的方法是在學(xué)生上完編譯原理課程的下一個學(xué)期開設(shè)編譯實習(xí)課程。

我們曾經(jīng)嘗試過不同的編譯實習(xí)題目。例如，在20世紀90年代采用的是面向Pascal語言子集Mini-Pascal的編譯器，后來轉(zhuǎn)為實現(xiàn)C語言子集Mini-C的編譯器，隨著Java語言的流行，最近幾年改成了面向Java語言子集MiniJava的編譯器。雖然面向的語言不同，但總體目標都是要實現(xiàn)一個相對完整的編譯過程，包括詞法分析、語法分析、語義分析和類型檢查、中間代碼生成、編譯優(yōu)化、寄存器分配等編譯階段，最后生成面向一種虛擬機的可執(zhí)行目標代碼，編譯器產(chǎn)生的最終結(jié)果可以在虛擬機上執(zhí)行和驗證。

進入21世紀以來，各種新型計算平臺和環(huán)境不斷涌現(xiàn)，特別是在2008年之后，隨著iOS、Android等移動智能計算平臺的流行，許多大學(xué)生都擁有了智能手機并熱衷于開發(fā)智能手機上的應(yīng)用。如果能夠讓學(xué)生面向包括智能手機在內(nèi)的新型計算平臺開發(fā)自己的編譯器，使生成的目標代碼可以在各種實際的計算機硬件和操作系統(tǒng)上運行，那么會激發(fā)學(xué)生對計算機技術(shù)和編譯技術(shù)的更大興趣。

基于此出發(fā)點，作為對編譯實習(xí)課程的創(chuàng)新探索，我們從2010年起在北京大學(xué)設(shè)立編譯實習(xí)實驗班（以下簡稱實驗班），提出把要實現(xiàn)的編譯器運行平臺從課程提供的虛擬機平臺，轉(zhuǎn)移到實際的計算機硬件和操作系統(tǒng)平臺上，如Java虛擬機（JVM）、Windows等傳統(tǒng)平臺以及較新的Android、iPhone等智能手機平臺。通過選修實驗班課程，學(xué)生可以利用編譯基本原理實現(xiàn)一個在實際平臺上運行的編譯器；也可以選擇面向新的語言實現(xiàn)編譯器或解釋器，如Ruby、Scheme等比較新的語言。另外，在編譯器實現(xiàn)過程中，我們通過數(shù)據(jù)流分析等技術(shù)，實現(xiàn)更深入的編譯優(yōu)化功能，提高編譯器生成程序的執(zhí)行效率。

1.設(shè)計目標與理念

1.1設(shè)計目標

在課程的設(shè)計上，實驗班專為編程能力較強、有結(jié)合最新計算平臺開發(fā)真實編譯器意愿的高年級學(xué)生開設(shè)。在編譯實習(xí)普通班上，我們僅僅要求編譯結(jié)果能在模擬器上運行，但這與實際平臺的運行還有一定距離。實驗班要求編譯結(jié)果能在最新出現(xiàn)的平臺上運行，如JVM、Android、Iphone/Ipad等，挑戰(zhàn)性更大，收獲也更大。編譯實習(xí)課的總體目標是培養(yǎng)學(xué)生具有良好的實踐能力，充分發(fā)揮學(xué)生的主動性和積極性，給學(xué)生上講臺的機會，以充分展示自己。

具體來說，實驗班希望學(xué)生達到以下主要目標：（1）深入掌握編譯技術(shù)并將其應(yīng)用到編譯器的實現(xiàn)中；（2）深入掌握運行平臺的細節(jié)，在使用中得到更好的認識；（3）開闊視野，提高學(xué)習(xí)計算機科學(xué)的興趣愛好；（4）培養(yǎng)合作開發(fā)大型軟件能力以及工程實踐能力；（5）培養(yǎng)學(xué)生的演講和溝通能力。

1.2設(shè)計理念與特色

實驗班的主要目的是把要實現(xiàn)的編譯器的運行平臺從課程提供的虛擬機平臺，轉(zhuǎn)移到實際的計算機硬件和操作系統(tǒng)平臺上。實踐證明，雖然面向?qū)嶋H應(yīng)用平臺開發(fā)編譯器原型系統(tǒng)挑戰(zhàn)很大，但是這可以在很大程度上提高學(xué)生對編譯器開發(fā)的興趣，在實際教學(xué)中取得很好的效果。通過近3年的實踐，我們打造了擁有以下特色的實驗班課程。

（1）面對新計算平臺不斷出現(xiàn)的特點，結(jié)合實際的計算平臺實現(xiàn)可用的編譯器。與普通班采用統(tǒng)一虛擬機作為編譯的目標平臺不同，實驗班要求學(xué)生選擇一個實際的計算平臺作為編譯的目標平臺，同時鼓勵學(xué)生選擇包括Android、iOS等移動平臺在內(nèi)的新型計算設(shè)備作為編譯的目標平臺。在實踐中，學(xué)生對新型平臺非常感興趣，如在2011年的編譯實習(xí)實驗板上，4組學(xué)生都選擇面向Android平臺開發(fā)相應(yīng)的編譯器。

（2）鼓勵學(xué)生自主探索相關(guān)領(lǐng)域的最新技術(shù)，如新計算平臺技術(shù)、新程序分析技術(shù)等。由于使用新的平臺需要學(xué)習(xí)許多新的知識，包括該平臺上的體系結(jié)構(gòu)、目標代碼格式、相應(yīng)的運行環(huán)境等內(nèi)容，而這些內(nèi)容無法通過課程講授完全獲得，因此我們鼓勵學(xué)生通過閱讀相關(guān)技術(shù)資料，特別是通過上網(wǎng)查找相應(yīng)的資料以了解新的計算平臺相關(guān)技術(shù)。另外，我們也鼓勵學(xué)生結(jié)合新的計算平臺，采用新的程序分析技術(shù)對目標程序進行優(yōu)化。

（3）鼓勵學(xué)生開展項目小組內(nèi)和項目小組之間的合作。掌握新平臺的知識需要不斷學(xué)習(xí)，因此我們鼓勵小組內(nèi)和小組間展開合作，學(xué)生在課程內(nèi)和課程外通過組間交流互通有無，共同進步。例如，Android采用的Dalvik虛擬機上的DEX程序格式比較復(fù)雜，各小組之間可以通過分工學(xué)習(xí)和深入交流提高掌握的效率。學(xué)生反映組間的合作讓他們受益頗多。

2.教學(xué)實踐情況

從2010年開始的每年秋季學(xué)期，我們都在編譯實習(xí)課程中鼓勵學(xué)有余力的學(xué)生參與到實驗班的探索實踐中。3年來，共有37名學(xué)生分為17個項目小組參與到不同種類自選題目的實習(xí)項目中。2010-2012年實驗班的項目及選題人數(shù)見表1。

2.1第1年：初次嘗試自選題目

我們對編譯實習(xí)課程的改革嘗試始于2010年，共有5個小組10名學(xué)生選擇自選題目的編譯實習(xí)項目。首先有一組學(xué)生在教師的鼓勵下，嘗試面向JVM實現(xiàn)MiniJava編譯器。這個小組由2名學(xué)生組成，編程能力都很強，在跟著普通班上過前面幾次課之后，基本上就能夠自主開發(fā)完成面向JVM的MiniJava編譯器，并且最終實現(xiàn)的編譯器效果很好。

我們還與體系結(jié)構(gòu)實習(xí)課程的任課教師合作，遴選3組學(xué)生面向北京大學(xué)自主研制的眾志處理器UniCore實現(xiàn)MiniC的編譯器，不僅要求他們嘗試面向新的平臺開發(fā)編譯器，而且還把編譯實習(xí)與體系結(jié)構(gòu)實習(xí)有機結(jié)合在一起，進行有益的探索。

除此之外，我們還推薦學(xué)生實現(xiàn)更高級的程序分析技術(shù)，一組學(xué)生在老師的帶領(lǐng)下，實現(xiàn)了Java程序分析中一種非常重要的新的程序分析技術(shù)：污點分析（Taint Analysists）。這組學(xué)生通過自己查閱論文，分析現(xiàn)有的Java編譯器（Soot），自主實現(xiàn)污點分析的技術(shù)和相應(yīng)工具，取得了很好的效果。

2.2第2年：移動平臺大受歡迎

從2011年開始，我們加大對實驗班的宣傳力度，共有19名學(xué)生參加并分為7組，嘗試開發(fā)面向JVM（1組）、Windows（1組）、Android（4組）的MiniJava編譯器，以及面向Unicore的MiniC編譯器（1組）。該年度最大的特點是很多學(xué)生對智能手機的應(yīng)用開發(fā)產(chǎn)生濃厚興趣，北京大學(xué)有許多學(xué)生開發(fā)面向Android和iOS平臺的校園智能應(yīng)用，有12名學(xué)生分為4組分別實現(xiàn)了面向Android平臺的MiniJava編譯器，該編譯器主要有以下特色。

（1）Android是一個相對較新的系統(tǒng)，雖然它采用的主要語言是Java，但是卻專門為移動平臺開發(fā)了新的Dalvik虛擬機，取代了JVM。JVM字節(jié)碼的指令采用的是棧式結(jié)構(gòu)，而Dalvik字節(jié)碼采用的是寄存器風(fēng)格的指令。由于Android系統(tǒng)的資料不是很全，許多信息需要在互聯(lián)網(wǎng)上查找，甚至要自己動手嘗試以分析代碼格式，因此對學(xué)生來講仍存在較大挑戰(zhàn)。

（2）一般來說，Android智能手機上的應(yīng)用是一個APK包，其中除了Dalvik字節(jié)碼的目標碼格式的可執(zhí)行文件之外，還有許多其他的輔助文件。要生成合法的可以在智能手機上安裝的應(yīng)用，還需要在編譯完成之后進行許多復(fù)雜繁瑣的收尾工作。

（3）如果不僅可以生成在Android手機上運行的應(yīng)用，而且還可以讓MiniJava編譯器在Android手機上運行，那就更好了。有一組學(xué)生完成了這個看似很具挑戰(zhàn)性的任務(wù)，即可以直接在手機上運行編譯器。

總的來說，這一年面向Android開發(fā)編譯器的嘗試，不僅對學(xué)生是一個挑戰(zhàn)，而且也讓任課教師收獲頗多。由于參與人數(shù)比較多，項目主要由學(xué)生自主完成，教師期間共組織了多次交流與討論，進行必要的引導(dǎo)與建議。最終的編譯器盡管差異較大，但總體效果非常好，多數(shù)學(xué)生在完成這個項目后，大大增強了開發(fā)大型項目的自信心。

2.3第3年：理性回歸+百花齊放

雖然2011年的嘗試很成功，但是由于參與的學(xué)生較多，難以管理，因此我們在2012年對學(xué)生的自選題目進行了更為嚴格的篩選，最終有8名學(xué)生分別進行了4個不同題目的開發(fā)。我們每年都會鼓勵學(xué)生選擇新的題目，因此2013年只有一組學(xué)生選擇了面向Android平臺的編譯器實現(xiàn)，而其他學(xué)生則分別根據(jù)自己的興趣選擇了不同的項目。

其中，2名學(xué)生在選擇函數(shù)式程序設(shè)計課程時，對Scheme語言產(chǎn)生濃厚興趣，在教師的鼓勵下，決定嘗試編寫Scheme語言的解釋器。作為一種函數(shù)式語言，Scheme的解釋器和C++、Java等命令式語言的編譯過程有較大區(qū)別。最開始2名學(xué)生作為一個小組，但是由于在項目中期出現(xiàn)實現(xiàn)理念上的沖突，因此2名學(xué)生分別實現(xiàn)了2個版本的Scheme解釋器。一個版本的解釋器效率較高，程序執(zhí)行速度較快；另外一個版本的解釋器功能較強，可以支持更復(fù)雜的Scheme語言結(jié)構(gòu)。2名學(xué)生都體現(xiàn)出了非常好的基礎(chǔ)素質(zhì)以及對編譯原理和構(gòu)造技術(shù)的深入理解。

另外2名學(xué)生也對Android等移動平臺感興趣，但是卻另辟蹊徑：編譯器的目標不是生成Dalvik虛擬機上執(zhí)行的APK，而是生成可以在ARM平臺上執(zhí)行的本地（Native）應(yīng)用。由于之前還沒有學(xué)生嘗試過類似項目，因此還需要調(diào)研ARM指令的格式與ARM平臺上Linux相關(guān)庫的實現(xiàn)，以便最終實現(xiàn)的MiniJava編譯器可以生成在Android平板電腦上執(zhí)行的本地程序。

值得一提的是，還有2名學(xué)生選擇實現(xiàn)一個支持Ruby語言子集的解釋器。這也是一個很有挑戰(zhàn)的項目，因為Ruby語言較新，資料不完整。2名學(xué)生雖然在前期表示出很大的信心和決心，也進行了較為詳細的調(diào)研工作，但是由于在中期遇到來自其他項目的壓力，無法投入足夠的時間完成最后的實現(xiàn)工作，很遺憾地選擇了中途退出。這個例子也提醒我們，在課程初期需要更加深入地考察學(xué)生的能力和所選擇項目的難度，盡可能提高每個項目的成功率。

經(jīng)過3年的實踐，我們積累了較多經(jīng)驗，收到的學(xué)生反饋也大多是正面和積極的。我們計劃將實驗班的課程作為一個長期的課程實踐開展下去。目前，2013年秋季的課程也再次列入計劃之中。

3.經(jīng)驗與挑戰(zhàn)

在課程實踐過程中，我們發(fā)現(xiàn)選擇將新出現(xiàn)的計算平臺作為編譯目標平臺，挑戰(zhàn)性比較大。由于平臺新、發(fā)展快，資料更新快，教師提供的信息往往也不全面，因此這就要求學(xué)生有更強的自主解決問題能力。新計算平臺容易吸引學(xué)生，因為許多學(xué)生喜歡新技術(shù)，他們認為新技術(shù)實現(xiàn)空間大，也更能體現(xiàn)自己的能力，還能接受挑戰(zhàn)。這對于激發(fā)學(xué)生的熱情，釋放學(xué)生的創(chuàng)新能力很有意義。然而，在實踐過程中，我們也遇到了一些挑戰(zhàn)和問題。

（1）如何更好地傳承課程經(jīng)驗？學(xué)生在結(jié)束開發(fā)工作后，都會按照要求提交實習(xí)報告，這些報告是課程的寶貴財富。如何充分利用好這些內(nèi)容，值得我們繼續(xù)思考。

（2）如何與普通班進行更好的協(xié)調(diào)？盡管實驗班的題目與普通班有差異，但有些內(nèi)容（如詞法、語法分析工具、編譯器的基本框架等）還是很接近的。這就需要我們在內(nèi)容設(shè)置、評價細節(jié)等方面進行持續(xù)優(yōu)化。

（3）如何設(shè)置更合理的選題？雖然我們鼓勵學(xué)生自選題目，但每年還是會在開課初提供一些選題列表，將前幾年的項目題目作為參考發(fā)給學(xué)生。學(xué)生比較容易被新穎的題目吸引，但還是會綜合考慮創(chuàng)新性和難度。

（4）如何更好地發(fā)揮教師的作用？對于自身編程能力較強的學(xué)生，教師除了為其提供好的題目之外，還應(yīng)如何給予恰當(dāng)?shù)膸椭?？教師指?dǎo)得好既使學(xué)生能夠快速獲取必要的信息而少走彎路，又避免因建議太多而束縛學(xué)生的思路。

（5）如何提高評價的客觀程度？盡管主觀評價是主要手段，但增加可行的客觀手段是非常好的補充，尤其對于相同題目，增加在目標碼的執(zhí)行時間、內(nèi)存開銷、編譯速度等方面的比較，更能激發(fā)學(xué)生優(yōu)化編譯器的熱情。

4.結(jié)語

為了適應(yīng)迅速發(fā)展的計算機硬件和系統(tǒng)平臺，我們在北京大學(xué)信息科學(xué)技術(shù)學(xué)院編譯實習(xí)課程中進行創(chuàng)新探索，并在實踐過程中獲得一些經(jīng)驗，同時還解決實踐過程中出現(xiàn)的問題，希望能與各高校承擔(dān)編譯課程教學(xué)任務(wù)的教師進行廣泛交流，也希望大家多提寶貴意見。