引入開源編譯器LLVM的編譯原理課程改革

張 昱，桑榆揚

（中國科學(xué)技術(shù)大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，安徽 合肥 230027）

引入開源編譯器LLVM的編譯原理課程改革

張 昱，桑榆揚

（中國科學(xué)技術(shù)大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，安徽 合肥 230027）

針對計算機及相關(guān)專業(yè)畢業(yè)生在就業(yè)過程中暴露出的對編譯過程理解不足、動手能力差等問題，闡述開源編譯器LLVM的廣泛使用和模塊化設(shè)計的優(yōu)勢，提出結(jié)合LLVM的編譯原理課程實踐新方案，并結(jié)合具體實施情況，總結(jié)該實踐方案的內(nèi)容、方法、效果和經(jīng)驗教訓(xùn)。

編譯原理；實踐；開源編譯器；系統(tǒng)能力

0 引 言

隨著學(xué)術(shù)界和工業(yè)界對計算機人才的要求不斷提高，不少計算機相關(guān)專業(yè)的本科畢業(yè)生暴露出編碼能力弱、對編譯過程理解不足、不能靈活運用常用算法和數(shù)據(jù)結(jié)構(gòu)、不熟悉軟件開發(fā)流程和相關(guān)工具等問題，很大程度上反映出高校專業(yè)實踐教學(xué)方面的不足。

編譯原理作為計算機科學(xué)與技術(shù)專業(yè)的經(jīng)典核心課程，涉及的原理和技術(shù)具有十分普遍的意義，也是培養(yǎng)學(xué)生系統(tǒng)能力（系統(tǒng)的認(rèn)知、分析、開發(fā)與應(yīng)用）和形式化描述能力的一門非常好的課程[1]。然而，隨著高等教育的大眾化，許多高校對計算機專業(yè)是否需要開設(shè)編譯原理課程產(chǎn)生疑問，對該課程采取取消或減少課時、教學(xué)偏重灌輸書本知識、缺乏課程實踐以及理論聯(lián)系實際的講解等，不利于培養(yǎng)學(xué)生的系統(tǒng)能力，也難以向由研究生擔(dān)任助教的高校輸送能勝任編譯課程教學(xué)任務(wù)的助教。

1 課程實踐存在的問題、定位與發(fā)展

在眾多高校中，課程實踐教學(xué)普遍存在以下問題。

（1）課程實踐各自獨立、覆蓋面窄、綜合性不高、難度低且規(guī)模小，不注重對學(xué)生工程實踐能力、工程質(zhì)量規(guī)范、團隊意識等的培養(yǎng)。

（2）課程偏重介紹和考核書本知識，理論與實踐脫節(jié)，學(xué)生感到教學(xué)內(nèi)容抽象、枯燥；實踐占考核的比重不高，學(xué)生不重視實驗且編碼能力的訓(xùn)練不足。

（3）教材和實踐內(nèi)容陳舊且脫離前沿技術(shù)發(fā)展，如教學(xué)實踐中使用的工具和方法在實際工作中已被淘汰或不常用。

（4）助教對課程內(nèi)容不夠熟悉，檢查力度不足，學(xué)生提交實驗時容易蒙混過關(guān)；并且由于課業(yè)繁重等原因，學(xué)生提交內(nèi)容存在互相抄襲的現(xiàn)象。

針對以上問題，我們認(rèn)為要增加實踐占課程考核的比重，改革實踐內(nèi)容；既要提升學(xué)生對編程的重視和興趣，又要科學(xué)公平地制訂評分標(biāo)準(zhǔn)，降低互相抄襲的可能性。編譯原理作為本科高年級的課程，在學(xué)生已具備一定編程能力的前提下開設(shè)，旨在提升學(xué)生對編譯過程的理解，通過構(gòu)建編譯器訓(xùn)練學(xué)生研發(fā)有一定規(guī)模的軟件的能力。

10年前，筆者曾帶領(lǐng)學(xué)生設(shè)計了一套以“源語言—抽象語法樹（AST）—低級中間表示—匯編代碼的內(nèi)部表示—x86/MIPS匯編”為主線搭建的、基于組件的編譯原理實驗體系[2]，編寫了實驗教程[3]，研制了配套的實驗支持庫和課程設(shè)計開發(fā)包。這套實驗體系是一套循序漸進(jìn)、規(guī)模適度、綜觀全局、實現(xiàn)局部且強調(diào)工程質(zhì)量規(guī)范的課程設(shè)計；實踐方案涉及多種編程工具與環(huán)境，包括Java語言及其開發(fā)運行環(huán)境，JFlex、CUP、JavaCC等編譯器的生成工具，Ant編譯工具，GCC、SPIM模擬器等，并且課程實踐的開發(fā)規(guī)模接近工程實際。基于該體系，我們在2007—2010年實施了由學(xué)生獨立完成編譯器前端或后端的綜合性課程實踐方案，許多學(xué)生認(rèn)為這個課程實踐方案設(shè)計得較好，是他們在大學(xué)期間所做的最大實驗，在鞏固編譯原理知識和提高軟件開發(fā)能力上發(fā)揮了很大作用。如果實踐指導(dǎo)力量跟得上，學(xué)生的工程質(zhì)量規(guī)范、綜合運用知識等能力就會有很大提高。不過，由于一些學(xué)生不熟悉Java語言和相關(guān)工具，也導(dǎo)致他們在開展實驗時上手慢，有的甚至出現(xiàn)畏難退縮的現(xiàn)象。

為消除學(xué)生因不了解編程語言而增加的額外負(fù)擔(dān)，2011年起，編譯實驗主要采用C/C++語言編寫，由多個循序漸進(jìn)的小實驗組成。2012年，計算機科學(xué)與技術(shù)學(xué)院將編譯課程分成普通和honor兩個級別，同時開班授課，不同級別的教學(xué)差異體現(xiàn)在課程實驗的量和深度上。honor班（約30人）的課程實踐除了包含多個基礎(chǔ)小實驗外，還包含最后的擴展實驗。由于分級教學(xué)，honor班面臨的問題之一是難以找到能勝任教學(xué)工作的助教。針對這一問題，2014年起，我們嘗試選用前一年學(xué)過honor課的優(yōu)秀大四學(xué)生作為助教，目前已初顯成效。2015年，由于助教非常得力，且開源編譯器LLVM（http://llvm.org/）在學(xué)術(shù)界和工業(yè)界廣泛使用，具有良好的模塊化和文檔化優(yōu)勢，我們將LLVM引入課程實踐，以便讓學(xué)生了解產(chǎn)品級編譯器的實現(xiàn)。

2 引入LLVM的編譯課程實踐方案

新方案由7個基礎(chǔ)實驗和最后的擴展實驗構(gòu)成，普通班的實驗主要從基礎(chǔ)實驗中選取?；A(chǔ)實驗的目標(biāo)是完成一個C1語言的編譯器，涵蓋詞法分析、語法分析、語義檢查和代碼生成；擴展實驗可以是對之前基礎(chǔ)實驗的擴展改進(jìn)，也可以自由選擇其他內(nèi)容進(jìn)行探索。

2.1 C1語言的主要特征

C1語言是C99的子集，包含變量和常量聲明、變量賦值、while、if-else、無參數(shù)無返回值的函數(shù)調(diào)用、算術(shù)運算和比較運算，僅支持int類型，不支持邏輯運算、include和多文件編譯。通過設(shè)計該語言的編譯器，可將課程中涉及的大部分概念帶入實踐中。

2.2 Kaleidoscope和Clang

Kaleidoscope是LLVM提供的一個簡單函數(shù)式語言及其編譯器構(gòu)建的網(wǎng)上教程（http://llvm. org/releases/3.6.0/docs/tutorial），其詞法分析部分使用字符串匹配，語法分析基于LL分析，后端使用LLVM的接口。教程中還穿插講述LLVM后端的一些概念。

Clang是LLVM使用的C/C++編譯器前端。閱讀該源碼旨在讓學(xué)生了解一個產(chǎn)品級編譯器的組成結(jié)構(gòu)，了解Clang如何記錄錯誤、處理運算的優(yōu)先級和結(jié)合性、構(gòu)建靜態(tài)分析等。閱讀源碼不僅可以使學(xué)生了解編譯技術(shù)，還可以使學(xué)生感受一些軟件工程思想，從而嘗試將這些技術(shù)和思想運用到C1編譯器的開發(fā)中。

2.3 基礎(chǔ)實驗的主要任務(wù)

基礎(chǔ)實驗的內(nèi)容及要求詳見https://www. zybuluo.com/clarazhang/note/190166，包含以下7個部分。

（1）預(yù)備階段：熟悉實驗環(huán)境（如Linux、LLVM/Clang、GCC和Makefile）以及C1語言特征。

（2）詞法分析：學(xué)習(xí)Flex并用其為C1語言構(gòu)造詞法分析器，理解Kaleidoscope的詞法分析過程以及Clang詞法分析。

（3）Kaleidoscope語法分析：理解Kaleidoscope的LL語法分析和AST并擴展增加while。

（4）C1語言的語法分析：學(xué)習(xí)用Flex和Bison構(gòu)造C1的LALR分析器。

（5）生成C1程序的AST：理解所提供的案例，為C1構(gòu)造能生成AST的分析器。

（6）Clang語法分析和靜態(tài)檢查：閱讀Clang源碼中指定的源文件，理解其語法分析和靜態(tài)語義檢查的實現(xiàn)機制。學(xué)生可在這個實驗中選做檢查器等附加實驗。

（7）生成LLVM IR：理解LLVM的IR，為C1程序生成LLVM IR并利用LLVM的工具鏈得到可執(zhí)行文件。學(xué)生可以對C1語言作適量擴展并實現(xiàn)對所作擴展的編譯器支持。

教師應(yīng)規(guī)定每個實驗的提交細(xì)則和提交的目錄結(jié)構(gòu)，引導(dǎo)學(xué)生培養(yǎng)工程、質(zhì)量等意識；引入Kaleidoscope教程的閱讀，讓學(xué)生了解其LL分析器的實現(xiàn)機制，彌補單純用Bison構(gòu)造LALR分析器的不足，還希望學(xué)生能基本掌握LLVM IR的接口，而部分沒有涵蓋的內(nèi)容可以通過上網(wǎng)搜索、閱讀文檔、討論交流等形式學(xué)習(xí)。

針對Clang源碼閱讀，首先由助教深入閱讀理解，找出有代表性的源碼段并針對其設(shè)計題目，然后和主講教師一起研討、確定并寫出源碼導(dǎo)讀，指出需要學(xué)生閱讀的源代碼段并回答學(xué)生提問。這樣可以使學(xué)生不至于在面對大規(guī)模代碼時無從下手，大大減輕學(xué)生的壓力，還可以減少一些代碼細(xì)節(jié)，讓學(xué)生將精力集中到對編譯實現(xiàn)技術(shù)的學(xué)習(xí)上。

2.4 擴展實驗的內(nèi)容選擇

擴展實驗一般在開課的第3個月由學(xué)生上報選題，描述擬實現(xiàn)的內(nèi)容。以往的擴展實驗（http://staff.ustc.edu.cn/～yuzhang/compiler/ eprojlist.html#old）要求學(xué)生自擬題目并獨立完成，雖然取得一些有創(chuàng)意的成果，如設(shè)計數(shù)據(jù)流語言、用JS編寫C編譯器等，但是也導(dǎo)致部分學(xué)生選擇無力完成的題目。2015年秋季學(xué)期，我們給學(xué)生提供兩個選擇，即擴展C1或自擬題目。自擬題目要求學(xué)生事先和教師討論，教師對選題的工作量、是否有價值等把關(guān)且部分選題類似的學(xué)生可以合作完成。事實表明，這一嘗試的效果相比以往要好。在31位選課學(xué)生中，20人權(quán)衡課業(yè)負(fù)擔(dān)后，理性地選擇擴展C1；剩余學(xué)生的題目包括：2名學(xué)生合作開展對數(shù)據(jù)流語言StreamIt的調(diào)研并在多核、多節(jié)點機器上進(jìn)行性能評估和分析，3名學(xué)生合作開展對代碼克隆及相似度檢測技術(shù)的調(diào)研和實踐，其他學(xué)生獨立開展宏匯編器的研發(fā)、在LLVM上通過剝離和重組結(jié)構(gòu)體數(shù)組進(jìn)行靜態(tài)內(nèi)存布局的優(yōu)化、Go語言調(diào)研或Python編譯器調(diào)研等。

式中，x1，x2 和S1，S2分別為前后n1年和n2年的均值和標(biāo)準(zhǔn)差；S為合并方差；T為兩組樣本對應(yīng)的統(tǒng)計量。

2.5 考核方法

學(xué)生的成績由平時作業(yè)（占10%）、期中和期末的卷面成績（各占20%）、基礎(chǔ)實驗和擴展實驗、討論課表現(xiàn)以及最后的個人實驗答辯評測（共占50%）這些因素共同決定。

對于平時作業(yè)，僅要求學(xué)生按時交，不考查正確率，希望此舉可以減少學(xué)生互相抄襲和抄答案的行為。期中和期末考試均采用開卷筆試，但不得使用任何電子設(shè)備，每次1～1.5h。采用開卷是希望學(xué)生不要死記硬背，而是主要依據(jù)平時理解的知識答題。

學(xué)院提供專門的長時間在線服務(wù)器，主講教師在開課初期為每位學(xué)生建立只能由其本人和老師訪問的獨立git版本庫。學(xué)生須將平時的實驗及時提交到個人git庫中，由助教批改并將意見提交到git庫中，且不向?qū)W生公布分?jǐn)?shù)。助教在實驗批改中主要考查實驗文檔和程序運行情況，不需費時閱讀代碼細(xì)節(jié)。有的學(xué)生對實驗做了擴展，如進(jìn)行語法檢查時支持較多特性、給C1增加帶參函數(shù)等，助教會酌情加分并反映在批改意見中，借此挖掘?qū)W生的潛力。第6次實驗主要是閱讀Clang語法分析和靜態(tài)檢查代碼，其中給出2個附加題，即編寫Checker插件和閱讀Malloc Checker。這兩項工作都需要學(xué)生投入較多精力，深入到Clang內(nèi)部研究其原理。因此，若學(xué)生完成附加題，則可以獲得更多加分，而實際實踐中約一半的學(xué)生完成了附加題。

對于最后的擴展實驗答辯，將學(xué)生分為4組，每組約8人。評委由所有學(xué)生、助教和主講老師組成，任何人都可以對演講者提問，但整個過程由教師主導(dǎo)，提問主要集中在學(xué)生對代碼的功能、正確性、知識掌握程度等方面。所有評委根據(jù)學(xué)生演講和回答的情況給出組內(nèi)排名，最終成績由分組的綜合排名和教師評分共同確定。

2014年，學(xué)生和教師之間使用google group進(jìn)行交流，但是由于需要翻墻，因此學(xué)生參與度不高。2015年秋季學(xué)期，師生主要通過郵件和QQ群交流，學(xué)生如果有疑問或意見，大多通過郵件向教師反映，教師再將有建設(shè)性的內(nèi)容群發(fā)給所有學(xué)生。此外，關(guān)于實驗的疑惑大多在QQ群內(nèi)交流，學(xué)生參與度較高，許多問題在內(nèi)部就解決了；老師也會在QQ群引導(dǎo)學(xué)生解決部分棘手的問題。

3 實施效果與經(jīng)驗教訓(xùn)

3.1 實施效果

我們收集了2015年秋季學(xué)期31位學(xué)生的git庫提交信息，提交日期分布的統(tǒng)計結(jié)果如圖1所示，提交時間分布的統(tǒng)計結(jié)果如圖2所示。

圖1 學(xué)生git庫提交日期分布

圖2 學(xué)生git庫提交時間分布

從圖1可以清楚地看到有8個明顯的高峰，分別對應(yīng)7次基礎(chǔ)實驗與擴展實驗的提交截止日期：9.12、9.26、10.9、10.31、11.15、12.7、12.29和1.18；表明學(xué)生傾向于到截止時間提交，并且更喜歡在前一天晚上集中突擊。從圖2可以看出，16點至凌晨0點以及6點的提交量較高，凌晨1點到5點的提交量顯著降低，這是因為截止時間定在上午7點前，本科生宿舍晚上斷電，只有少數(shù)學(xué)生可以在實驗室通宵寫代碼。

利用代碼統(tǒng)計工具cloc，得到的學(xué)生提交的平均代碼量見表1，可以看到C++占絕大部分，C和Yacc也有不小的比例，這是因為需要用C++編寫AST節(jié)點的構(gòu)造、遍歷、處理的函數(shù)，產(chǎn)生可執(zhí)行代碼時也要用C++調(diào)用LLVM的后端；C通常作為測試程序出現(xiàn)，也有學(xué)生喜歡寫C代碼；而出現(xiàn)較多Yacc文法描述代碼，是因為需要在產(chǎn)生式后編寫生成AST節(jié)點的操作，部分學(xué)生將一些后續(xù)處理的代碼也放了進(jìn)去，但是我們不提倡這種做法。

表1 學(xué)生提交的平均代碼量統(tǒng)計

3.2 經(jīng)驗教訓(xùn)

（1）和LLVM的結(jié)合。LLVM是一個前景極佳的項目，它的編譯速度遠(yuǎn)超過gcc，同時相對于gcc有更多文檔，也更適合構(gòu)建編譯器。因此，我們希望學(xué)生熟悉LLVM，即使將來不從事編譯相關(guān)的工作，也可以通過課程實踐學(xué)到實用的知識。在基礎(chǔ)實驗中，要求學(xué)生了解LLVM的指令和含義并閱讀Clang源碼，借此學(xué)生可以了解軟件開發(fā)中的代碼規(guī)范、為了避免bug而產(chǎn)生的設(shè)計技巧等，可以將所學(xué)方法應(yīng)用到實驗中。學(xué)生需要用LLVM的編程接口生成LLVM IR，雖然LLVM的教程涉及部分概念，但是也遺漏部分信息，因此，我們鼓勵學(xué)生上網(wǎng)查找和閱讀文檔，并且提供涵蓋大部分接口的樣例代碼，借此培養(yǎng)學(xué)生今后快速自學(xué)的能力。

（2）擴展實驗。擴展實驗分兩類，即改進(jìn)C1編譯器和自擬題目，既允許時間不足的學(xué)生完成作業(yè)，又能讓學(xué)有余力的學(xué)生有機會接觸到更前沿的知識。由教師主導(dǎo)和學(xué)生參與評分的實驗答辯方式可以提高學(xué)生的參與熱情，增加評分的公平性和公開性。

（3）趕截止日期。編譯原理作為本院學(xué)生在本科期間實驗量最大的課程，可以幫助提升學(xué)生的編程能力，提高學(xué)生對編譯鏈的理解，但是由于工作量大，也給學(xué)生帶來較大壓力。許多學(xué)生偏好在提交截止日期前臨時突擊，導(dǎo)致投入時間不夠、完成情況不好甚至無法完成。這是一個無法避免的問題，因此我們盡量將工作任務(wù)細(xì)分，給每個部分規(guī)定截止時間。

（4）工具。本院的教學(xué)傳統(tǒng)是鼓勵學(xué)生研究理論而缺少對實踐的強調(diào)，許多學(xué)生到了大三依然沒用過Linux。本實驗要求學(xué)生在Linix環(huán)境下編程，使用git提交作業(yè)，用make輔助編譯并用shell編寫批量測試程序，此外還要學(xué)習(xí)Lex、Bison、Clang、DOT等工具。由于編譯和調(diào)試過程中整條編譯鏈的工具都需要學(xué)生掌握，學(xué)生需要花較多時間學(xué)習(xí)，而不能將精力集中到編譯技術(shù)上。我們認(rèn)為應(yīng)該重視對學(xué)生基本編程能力的培養(yǎng)，在低年級課程中增加對常用工具的介紹和使用；在編譯原理課程中則可提供簡單的教程和樣例，幫助學(xué)生迅速理解掌握。

（5）使用git。使用git版本管理的好處是方便學(xué)生提交作業(yè)和助教收取作業(yè)，不需要安排固定時間檢查；學(xué)生提交后仍可修改，只要記得常同步，即使本地版本丟失，也可從服務(wù)器上獲得版本繼續(xù)開展實驗。我們發(fā)現(xiàn)有的學(xué)生提交次數(shù)不多，一部分學(xué)生是因為趕在截止日期前完成，另一部分學(xué)生則是喜歡寫完所有代碼后一次性提交，且日志記錄簡單，如使用P5、P5.1之類的日志等。這可能是因為每人負(fù)責(zé)一個git庫，不存在互相合作，所以學(xué)生覺得沒必要寫詳細(xì)的日志，而且學(xué)生缺乏項目實踐經(jīng)驗，沒有多次提交的意識。我們將考慮加入學(xué)生互評機制，充分利用git的協(xié)作性，讓學(xué)生通過評閱他人代碼、閱讀批改意見等，相互促進(jìn)并消化知識。

（6）提供樣例代碼。助教在實驗中多次給出樣例代碼，如在構(gòu)建C1編譯器初期給出僅包含賦值、算數(shù)運算語言的編譯器代碼，包含Lex、Bison、Makefile、類的組織等。不少學(xué)生的代碼是基于此構(gòu)建的，在一定程度上減輕了學(xué)習(xí)和調(diào)試的難度。構(gòu)建C1編譯器末期，許多學(xué)生反映LLVM的接口太難懂，因此助教又給出一份包含大部分接口用法的樣例代碼，并提供根據(jù)一份C1源碼還原出其IR用到的LLVM接口的方法。為學(xué)生提供樣例代碼，可以減輕學(xué)生負(fù)擔(dān)，但如果過于詳細(xì)又會導(dǎo)致學(xué)生無事可干，因此要注意點到為止。

（7）學(xué)生的編碼質(zhì)量?；A(chǔ)實驗之間往往有依賴關(guān)系，這種依賴也帶來弊病，如學(xué)生某次實驗完成得不好，會影響此后與它相關(guān)的其他實驗。部分學(xué)生反映自己的代碼構(gòu)建過于雜亂，導(dǎo)致后期調(diào)試和修改起來非常困難。針對該問題，我們也做了些預(yù)防措施，如在前期提供一個簡單語言編譯器的樣例代碼。到了后期，由于要添加的特性變多，實現(xiàn)策略不同導(dǎo)致工作量差別較大，如有的學(xué)生自定義一個類封裝符號表的操作接口，在遍歷AST時能方便調(diào)用，而有的學(xué)生則直接在每個需要操作符號表的地方進(jìn)行手工處理，導(dǎo)致工作量翻了數(shù)倍。

（8）小班教學(xué)。30人左右的小班教學(xué)優(yōu)于大班教學(xué)，如課堂教學(xué)容易引發(fā)互動、日常實驗容易管理且最終答辯容易實施。在小班課堂中，學(xué)生比較活躍，課間課后的提問較踴躍；老師可以及時了解學(xué)生的學(xué)習(xí)進(jìn)度和學(xué)習(xí)中存在的問題，調(diào)整實驗提交的截止時間，也能在課間和個別學(xué)生交流其學(xué)習(xí)存在的問題及產(chǎn)生原因。

4 結(jié) 語

將產(chǎn)品級編譯器基礎(chǔ)設(shè)施LLVM引入編譯原理課程，可以讓學(xué)生近距離了解產(chǎn)品級編譯器的實現(xiàn)機制、文檔和代碼規(guī)范，有效幫助學(xué)生更好地理解編譯知識并增強系統(tǒng)能力，讓學(xué)生對上規(guī)模軟件的開發(fā)有一定認(rèn)知。LLVM的引入也為部分學(xué)生日后開展程序分析、變換、優(yōu)化等方面的研究奠定了基礎(chǔ)。課程實踐改革的實施過程中暴露出的一些問題，有待我們將來進(jìn)一步改進(jìn)。

[1] 蔣宗禮. “編譯原理”課程與專業(yè)能力培養(yǎng)[J]. 計算機教育, 2009(21): 4-6.

[2] 張昱, 陳意云. 編譯原理課程實踐改革探索[J]. 計算機教育, 2008(8): 24-26.

[3] 張昱, 陳意云. 編譯原理實驗教程[M]. 北京: 高等教育出版社, 2009.

（編輯：宋文婷）

1672-5913(2017)02-0062-06

G642

安徽省2013年省級精品資源共享課程項目“編譯原理和技術(shù)”（2013gxk002）。

張昱，女，副教授，研究方向為程序設(shè)計語言理論與實現(xiàn)技術(shù)、面向多核的可靠高效并行系統(tǒng)軟件的構(gòu)建與評估、軟件安全等，yuzhang@ustc.edu.cn。