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

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

0.引言

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

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

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

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

1.設(shè)計(jì)目標(biāo)與理念

1.1設(shè)計(jì)目標(biāo)

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2第2年：移動(dòng)平臺大受歡迎

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.結(jié)語

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