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

張 昱，桑榆揚

（中國科學技術大學 計算機科學與技術學院，安徽 合肥 230027）

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

張 昱，桑榆揚

（中國科學技術大學 計算機科學與技術學院，安徽 合肥 230027）

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

編譯原理；實踐；開源編譯器；系統能力

0 引 言

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

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

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

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

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

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

（3）教材和實踐內容陳舊且脫離前沿技術發展，如教學實踐中使用的工具和方法在實際工作中已被淘汰或不常用。

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

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

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

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

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

新方案由7個基礎實驗和最后的擴展實驗構成，普通班的實驗主要從基礎實驗中選取。基礎實驗的目標是完成一個C1語言的編譯器，涵蓋詞法分析、語法分析、語義檢查和代碼生成；擴展實驗可以是對之前基礎實驗的擴展改進，也可以自由選擇其他內容進行探索。

2.1 C1語言的主要特征

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

2.2 Kaleidoscope和Clang

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

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

2.3 基礎實驗的主要任務

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

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

（2）詞法分析：學習Flex并用其為C1語言構造詞法分析器，理解Kaleidoscope的詞法分析過程以及Clang詞法分析。

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

（4）C1語言的語法分析：學習用Flex和Bison構造C1的LALR分析器。

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

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

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

教師應規定每個實驗的提交細則和提交的目錄結構，引導學生培養工程、質量等意識；引入Kaleidoscope教程的閱讀，讓學生了解其LL分析器的實現機制，彌補單純用Bison構造LALR分析器的不足，還希望學生能基本掌握LLVM IR的接口，而部分沒有涵蓋的內容可以通過上網搜索、閱讀文檔、討論交流等形式學習。

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

2.4 擴展實驗的內容選擇

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

式中，x1，x2 和S1，S2分別為前后n1年和n2年的均值和標準差；S為合并方差；T為兩組樣本對應的統計量。

2.5 考核方法

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

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

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

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

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

3 實施效果與經驗教訓

3.1 實施效果

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

圖1 學生git庫提交日期分布

圖2 學生git庫提交時間分布

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

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

表1 學生提交的平均代碼量統計

3.2 經驗教訓

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

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

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

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

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

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

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

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

4 結 語

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

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

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

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

（編輯：宋文婷）

1672-5913(2017)02-0062-06

G642

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

張昱，女，副教授，研究方向為程序設計語言理論與實現技術、面向多核的可靠高效并行系統軟件的構建與評估、軟件安全等，yuzhang@ustc.edu.cn。