編譯課程教學(xué)相關(guān)工具資源分析

摘要：結(jié)合編譯課程教學(xué)特點(diǎn)，收集當(dāng)前常用的編譯資源，并從編程語(yǔ)言和教學(xué)知識(shí)點(diǎn)兩個(gè)角度對(duì)這些資源進(jìn)行歸類(lèi)分析；在此基礎(chǔ)上，探討如何利用這些資源開(kāi)展編譯課程的課堂教學(xué)和實(shí)踐教學(xué)。

關(guān)鍵詞：編譯原理；工具資源；實(shí)踐教學(xué)

1.背景

編譯理論與技術(shù)是計(jì)算機(jī)科學(xué)中發(fā)展最迅速、最成熟的一個(gè)重要分支，程序設(shè)計(jì)語(yǔ)言和編譯的發(fā)展集中體現(xiàn)了計(jì)算機(jī)科學(xué)的重要成果與精華。編譯原理課程是計(jì)算機(jī)科學(xué)與技術(shù)專(zhuān)業(yè)的專(zhuān)業(yè)必修課程，主要講授程序設(shè)計(jì)語(yǔ)言編譯程序構(gòu)造的基本原理和方法。編譯程序的開(kāi)發(fā)堪稱(chēng)經(jīng)典理論和先進(jìn)技術(shù)緊密結(jié)合的典型示范，因此理論學(xué)習(xí)和實(shí)踐的緊密結(jié)合是本課程的突出特色。通過(guò)編譯程序構(gòu)造的問(wèn)題，可以體驗(yàn)到如何從實(shí)際需求中提出理論問(wèn)題、理論研究推動(dòng)技術(shù)進(jìn)步、運(yùn)用技術(shù)工具解決實(shí)際問(wèn)題的過(guò)程。

在經(jīng)典理論的支持下，在編譯程序的研制過(guò)程中，產(chǎn)生了非常豐富的工具資源。在這些工具資源的支持下，編譯程序開(kāi)發(fā)的自動(dòng)化程度得到了顯著提高；相對(duì)其他軟件開(kāi)發(fā)任務(wù)，編譯程序開(kāi)發(fā)在效率和質(zhì)量上的優(yōu)勢(shì)非常明顯。更為重要的是，編譯的理論和技術(shù)對(duì)于計(jì)算機(jī)科學(xué)中的其他領(lǐng)域也有重要的影響。一直以來(lái)，編譯的理論和技術(shù)在程序設(shè)計(jì)語(yǔ)言的實(shí)現(xiàn)、針對(duì)計(jì)算機(jī)體系結(jié)構(gòu)的優(yōu)化、新的計(jì)算機(jī)體系結(jié)構(gòu)的設(shè)計(jì)、自然語(yǔ)言理解、網(wǎng)絡(luò)信息處理、網(wǎng)絡(luò)協(xié)議的分析與實(shí)現(xiàn)等領(lǐng)域都是不可或缺的。國(guó)外著名大學(xué)（如美國(guó)哥倫比亞大學(xué)、哈佛大學(xué)和斯坦福大學(xué)等）的編譯課程教學(xué)都特別重視相關(guān)的課程實(shí)踐項(xiàng)目。以哥倫比亞大學(xué)為例，在編譯原理的課程教學(xué)中開(kāi)展了貫穿整個(gè)學(xué)期的課程實(shí)踐項(xiàng)目。在項(xiàng)目中，學(xué)生分成小組，自主設(shè)計(jì)并實(shí)現(xiàn)一個(gè)小的語(yǔ)言，而這個(gè)語(yǔ)言涉及了豐富的領(lǐng)域，包括量子計(jì)算、音樂(lè)合成、計(jì)算機(jī)圖形學(xué)、游戲、矩陣計(jì)算和很多其他領(lǐng)域。在這些教學(xué)實(shí)踐中，很多編譯開(kāi)發(fā)工具都被應(yīng)用于各種案例中，包括ANTLR、LEX和YACC等編譯領(lǐng)域經(jīng)典的開(kāi)源軟件工具。

通過(guò)收集編譯資源（包括開(kāi)源的編譯器和編譯程序開(kāi)發(fā)工具），以及這些工具在計(jì)算機(jī)科學(xué)各領(lǐng)域中的成功應(yīng)用案例，可以為開(kāi)展案例式教學(xué)改革打下堅(jiān)實(shí)的基礎(chǔ)。筆者收集了編譯領(lǐng)域常用的開(kāi)源軟件工具及其應(yīng)用案例，并對(duì)其進(jìn)行歸類(lèi)分析和整理，以形成支撐編譯課堂教學(xué)和實(shí)踐教學(xué)的資源庫(kù)。基于該資源庫(kù)，在今后的編譯原理課程教學(xué)中，可以通過(guò)采取基于案例的教學(xué)方法，形象地向?qū)W生展示編譯研究中“經(jīng)典理論和先進(jìn)技術(shù)有機(jī)結(jié)合”的突出特點(diǎn)，使學(xué)生能夠通過(guò)具體的案例切實(shí)體驗(yàn)編譯經(jīng)典理論在各領(lǐng)域的重要作用。

2.編譯資源分析

在幾十年的研究過(guò)程中，編譯領(lǐng)域已經(jīng)形成了很多編譯資源，如LEX、YACC、JavaCC為代表的編譯模塊開(kāi)發(fā)工具，以及精簡(jiǎn)語(yǔ)言編譯器、產(chǎn)品級(jí)開(kāi)源編譯器等。這些工具實(shí)現(xiàn)了從Ada、C、Pascal等面向過(guò)程語(yǔ)言到Java、C++等面向?qū)ο笳Z(yǔ)言的編譯程序，覆蓋了文法、詞法分析、語(yǔ)法分析、中間代碼生成、代碼優(yōu)化、目標(biāo)代碼生成等編譯原理教學(xué)中所有的知識(shí)點(diǎn)。基于這些工具也開(kāi)發(fā)了SQL、XML分析等計(jì)算機(jī)科學(xué)其他領(lǐng)域的應(yīng)用。下面，筆者從生成語(yǔ)言、知識(shí)點(diǎn)覆蓋等角度對(duì)互聯(lián)網(wǎng)上的編譯資源進(jìn)行整理分析。

2.1從編程語(yǔ)言的角度分析

從編譯資源所面向的程序語(yǔ)言來(lái)看，從面向特殊領(lǐng)域的Fortran語(yǔ)言、DSP語(yǔ)言，面向過(guò)程的C語(yǔ)言、Pascal語(yǔ)言，到常見(jiàn)的面向?qū)ο蟮腏ava語(yǔ)言、C++、C#語(yǔ)言等，均有種類(lèi)繁多的分析器、生成器、目標(biāo)代碼優(yōu)化器等可用于案例教學(xué)的編譯資源。

1）面向過(guò)程語(yǔ)言的編譯資源。

這方面的編譯資源主要針對(duì)C語(yǔ)言和Pascal語(yǔ)言。C語(yǔ)言作為最被廣泛使用的編程語(yǔ)言，也擁有最多的編譯工具資源，如YACC、LEX、ACCENT、BANSHEE等經(jīng)典工具均可用來(lái)產(chǎn)生C語(yǔ)言編程的分析器、生成器。其中，最知名的C語(yǔ)言解析器生成器YACC已經(jīng)在各種場(chǎng)合得到了廣泛應(yīng)用。YACC也是常用于編譯課程教學(xué)的工具，它采用LALR（1）語(yǔ)法分析方法，最初由AT&T為Unix操作系統(tǒng)開(kāi)發(fā)，在漫長(zhǎng)的演變中產(chǎn)生了如Berkeley YACC、GNU BISON、MKS YACC和Abraxas YACC等變種版本，也出現(xiàn)了AYACC、YACC++等面向ADA、c++其他語(yǔ)言的編譯器。由于所產(chǎn)生的解析器需要詞法分析器配合，因此YACC經(jīng)常和詞法分析器產(chǎn)生器LEX一起使用，目前已有IEEE相關(guān)標(biāo)準(zhǔn)對(duì)YACC和LEX的功能進(jìn)行了標(biāo)準(zhǔn)化描述。此外，ACCENT、BEG、CKIT等面向c語(yǔ)言的編譯資源也可以用于編譯課程教學(xué)。據(jù)我們初步統(tǒng)計(jì)，目前互聯(lián)網(wǎng)上可用的針對(duì)c語(yǔ)言的編譯資源多達(dá)20余種，涵蓋了詞法分析、語(yǔ)法分析、前端、后端生成器、代碼優(yōu)化、程序分析等編譯過(guò)程中的各個(gè)環(huán)節(jié)。

2）面向?qū)ο笳Z(yǔ)言的編譯資源。

面向?qū)ο笳Z(yǔ)言已成為程序開(kāi)發(fā)的主流語(yǔ)言，在應(yīng)用層軟件、網(wǎng)絡(luò)服務(wù)開(kāi)發(fā)上占據(jù)著絕對(duì)優(yōu)勢(shì)地位。因此，目前也相應(yīng)出現(xiàn)了很多針對(duì)面向?qū)ο缶幊陶Z(yǔ)言的編譯資源，特別是C++語(yǔ)言和Java語(yǔ)言。C++語(yǔ)言由于與C語(yǔ)言一脈相承，許多針對(duì)c語(yǔ)言的編譯工具也擴(kuò)展了c++版本，如YACC++、Berkeley YACC、IDC-C等，均可以生成C/C++語(yǔ)言的分析器。

Java語(yǔ)言在最近20年一直是最流行的編程語(yǔ)言。Java語(yǔ)言為了實(shí)現(xiàn)跨平臺(tái)的目標(biāo)，在編譯時(shí)僅生成字節(jié)碼，再由不同平臺(tái)的JVM生成目標(biāo)代碼執(zhí)行；因此，Java語(yǔ)言的編譯執(zhí)行具有明確的前端后端，非常有利于編譯程序的開(kāi)發(fā)和編譯原理知識(shí)點(diǎn)的分解。目前針對(duì)Java語(yǔ)言的編譯資源與工具種類(lèi)繁多，如JavaCC、JastAdd、Jax、Jfront、Soot、PAT等，我們目前已經(jīng)收集到相關(guān)編譯資源20余種，既有JavaCC等綜合編譯環(huán)境，又有Jfront前端工具、PAT正則表達(dá)式分析器、OOPS分析優(yōu)化工具等編譯工具資源。

3）其他專(zhuān)用語(yǔ)言、平臺(tái)的編譯資源。

為了符合特殊應(yīng)用場(chǎng)景的計(jì)算需求，出現(xiàn)了一些針對(duì)特定領(lǐng)域、特定平臺(tái)的程序語(yǔ)言，同樣，在這些領(lǐng)域中對(duì)編譯器往往也存在獨(dú)特的需求，如嵌入式系統(tǒng)、科學(xué)計(jì)算等，如針對(duì)SPARC平臺(tái)的編譯器BEG就能對(duì)Fortran、Modula等專(zhuān)用語(yǔ)言進(jìn)行分析編譯，而Archelon編譯器則針對(duì)DSP芯片為執(zhí)行代碼生成做了專(zhuān)門(mén)的優(yōu)化。ELI是這一類(lèi)編譯資源的典型代表，它除了支持上述流行編程語(yǔ)言及專(zhuān)用語(yǔ)言如c、Fortran外，甚至支持對(duì)用戶(hù)定義的語(yǔ)言生成獨(dú)有的編譯器，從而幫助用戶(hù)快速地實(shí)現(xiàn)一種專(zhuān)業(yè)程序語(yǔ)言。

2.2從知識(shí)點(diǎn)的角度分析

為利于編譯原理課程的教學(xué)，我們更希望從知識(shí)點(diǎn)的角度梳理相關(guān)資源，在講授相關(guān)課程時(shí)，可以介紹這些經(jīng)典的編譯工具。通過(guò)認(rèn)識(shí)真實(shí)編譯系統(tǒng)的工作流程和開(kāi)發(fā)技術(shù)，幫助學(xué)生理解關(guān)鍵知識(shí)點(diǎn)。我們從詞法分析、語(yǔ)法分析、編譯前端、編譯后端、程序分析及優(yōu)化、完整的編譯器平臺(tái)等類(lèi)別對(duì)現(xiàn)有的編譯資源進(jìn)行了梳理和分類(lèi)。

1）詞法分析。

詞法分析器以UNIX/LINUX上的LEX為典型代表，能夠生成c語(yǔ)言描述的詞法分析器；而AFLEX作為L(zhǎng)EX的變種，能生成ADA語(yǔ)言描述的詞法分析器；Quex還能生成C/C++、Python語(yǔ)言描述的詞法分析器；相關(guān)的資源還包括LOLO、FLEX等。

2）語(yǔ)法分析。

支持語(yǔ)法分析的編譯工具最為豐富，從簡(jiǎn)單到復(fù)雜的相關(guān)開(kāi)發(fā)案例也最多，可以很好地用于支撐課程教學(xué)。如前文所述，語(yǔ)法分析器以YACC為典型代表，這一系列的語(yǔ)法分析器還包括AYACC、BISON、BYACC、BEG。CUP、Jell等Java語(yǔ)言開(kāi)發(fā)的語(yǔ)法分析器生成器，可以生成Java語(yǔ)言描述的語(yǔ)法分析器。ANTLR是一種用Java開(kāi)發(fā)的強(qiáng)大的語(yǔ)法分析器生成工具，可以生成各種語(yǔ)言描述的語(yǔ)法分析器，包括Ada、C、C#、Java、JavaScript、Objective-C等，以及Perl、Python和Ruby等較新的互聯(lián)網(wǎng)程序語(yǔ)言和腳本語(yǔ)言，甚至包括SQL、一階邏輯、XPath等應(yīng)用語(yǔ)言等。ACCENT則是一個(gè)包含了詞法分析器和語(yǔ)法分析器的生成工具。JavaCC是當(dāng)前應(yīng)用非常廣的一種語(yǔ)法分析器生成工具，能產(chǎn)生Java語(yǔ)言描述的LL（K）分析程序。值得一提的是，目前已經(jīng)有非常多的利用JavaCC開(kāi)發(fā)的各種語(yǔ)言的分析程序，包括了表達(dá)式等簡(jiǎn)單語(yǔ)言，如DTD、IDL、RTF等應(yīng)用語(yǔ)言，以及PHP等實(shí)用的腳本語(yǔ)言。隨著技術(shù)的發(fā)展，甚至出現(xiàn)了OOPS等面向?qū)ο蟮姆治銎魃晒ぞ摺?/p>

3）編譯前端。

面向c語(yǔ)言的中間代碼生成工具最著名的是Ckit，它支持將c語(yǔ)言程序翻譯譯成SML類(lèi)型的中間語(yǔ)言，也支持用戶(hù)擴(kuò)展C語(yǔ)言語(yǔ)法的前端編譯。EDG則能將C++和Java等語(yǔ)言翻譯成一種高級(jí)的樹(shù)結(jié)構(gòu)中間語(yǔ)言，并具有錯(cuò)誤檢查功能。在面向Java語(yǔ)言方面，比較知名的編譯器前端包括Jfront等。此外，為滿(mǎn)足特定應(yīng)用場(chǎng)景需求，還出現(xiàn)了IDC-C、SUIF等編譯前端及中間代碼優(yōu)化工具。

4）編譯后端。

編譯器后端方面的資源相對(duì)前端來(lái)說(shuō)較少，比較知名的編譯器后端是BEG，以BEGL中間語(yǔ)言為輸入，可用于生成Motorola 68020、SPARC、MIPSl Intel 386、Pentium？Inmos T800和PowerPC等平臺(tái)的目標(biāo)代碼。在Java語(yǔ)言方面，Sable研究小組基于XML提出了JIL中間表示語(yǔ)言，利用XML的特性為執(zhí)行代碼的生成和優(yōu)化提供便利。此外，還有Trimam等針對(duì)并行環(huán)境生成執(zhí)行代碼并優(yōu)化的后端編譯器生成器等工具。

5）程序分析及代碼優(yōu)化。

在程序分析及代碼優(yōu)化方面的編譯工具較多，如BANSHEE、CodeSurfer、Omega、OOPS、PAG、SOOT等。其中BANSHEE、CodeSurfer、Kimwitu、MEMPHIS、PAG等工具針對(duì)C/C++程序進(jìn)行分析，Omega、PAT等工具則可以對(duì)Fortran、Java程序進(jìn)行分析，SOOT、OOPS提供了對(duì)Java等語(yǔ)言編譯器的優(yōu)化，上文中提到的Trimam及SUIF等則針對(duì)并行環(huán)境進(jìn)行了代碼優(yōu)化。

6）編譯器平臺(tái)。

除上述實(shí)現(xiàn)了部分編譯模塊的開(kāi)發(fā)工具之外，還存在著大量實(shí)現(xiàn)了從詞法分析、語(yǔ)法分析直至最后目標(biāo)代碼生成所有環(huán)節(jié)的編譯器平臺(tái)資源，這些資源用于案例教學(xué)可以幫助學(xué)生對(duì)編譯的全過(guò)程進(jìn)行一個(gè)整體的理解和把握。這些平臺(tái)可以分為兩類(lèi)：一類(lèi)是以精簡(jiǎn)語(yǔ)言為源語(yǔ)言的小型編譯器，如PL語(yǔ)言（PASCAL子集）編譯器、與ADA和PASCAL類(lèi)似的TINY編譯器，以及斯坦福大學(xué)開(kāi)發(fā)的COOL（The Classroom ObiectOriented Language）編譯器，這些編譯器都是面向?qū)ｉT(mén)為教學(xué)設(shè)計(jì)的某種精簡(jiǎn)的編程語(yǔ)言，將其翻譯成某種抽象機(jī)代碼，借助抽象機(jī)解釋器執(zhí)行；另一類(lèi)是以GCC、LCC為代表的產(chǎn)品級(jí)開(kāi)源編譯器，面向C/C++這類(lèi)主流的編程語(yǔ)言，提供開(kāi)源、實(shí)用的編譯程序。

3.編譯資源在課程教學(xué)中的應(yīng)用

通過(guò)上面的分析，我們看到編譯開(kāi)發(fā)工具和相關(guān)案例是非常豐富的，但是如何將這些工具和案例很好地結(jié)合到教學(xué)中，則需要做仔細(xì)的選擇和考慮。不論從課程教學(xué)，還是實(shí)踐教學(xué)來(lái)看，編譯原理課程的學(xué)習(xí)可以從局部知識(shí)點(diǎn)和系統(tǒng)整體兩個(gè)層次開(kāi)展。課程教學(xué)需要在掌握編譯各階段的具體知識(shí)點(diǎn)的基礎(chǔ)上，加強(qiáng)各知識(shí)點(diǎn)之間的融會(huì)貫通，并恰當(dāng)及時(shí)地從局部向系統(tǒng)整體引申。

在詞法分析、語(yǔ)法分析、語(yǔ)義分析、優(yōu)化、目標(biāo)代碼生成等知識(shí)點(diǎn)的學(xué)習(xí)過(guò)程中，可以引人相應(yīng)模塊的開(kāi)發(fā)工具作為案例。如在講解詞法分析時(shí)可以結(jié)合LEX、在講解自上而下分析時(shí)結(jié)合JavaCC、講解自下而上分析時(shí)結(jié)合BISON，甚至可以在課堂教學(xué)時(shí)展示這些工具的核心代碼，加深學(xué)生對(duì)相關(guān)算法的印象。也可以在課外安排實(shí)踐作業(yè)，要求學(xué)生選擇這些工具提供的案例資源，以已有的案例為基礎(chǔ)（為調(diào)動(dòng)學(xué)習(xí)興趣，可以有意識(shí)地選擇學(xué)生在其他課程中已經(jīng)熟悉的語(yǔ)言，如數(shù)據(jù)庫(kù)中的SQL、操作系統(tǒng)中的Shell命令語(yǔ)言、離散數(shù)學(xué)中的謂詞邏輯等），實(shí)際生成一個(gè)編譯模塊，閱讀分析生成程序，在此基礎(chǔ)上，可要求學(xué)生擴(kuò)展原有案例。通過(guò)結(jié)合這些工具講解理論知識(shí)，并通過(guò)實(shí)踐作業(yè)，使得學(xué)生能夠理解局部知識(shí)點(diǎn)，并掌握相關(guān)成熟的工具的使用。

在系統(tǒng)開(kāi)發(fā)層面，編譯程序的開(kāi)發(fā)是一個(gè)典型復(fù)雜的軟件開(kāi)發(fā)任務(wù)。如果能在理解局部知識(shí)點(diǎn)的基礎(chǔ)上，為學(xué)生提供一個(gè)理解編譯程序整體全貌的平臺(tái)，以編譯過(guò)程為指導(dǎo)帶動(dòng)課程知識(shí)點(diǎn)的學(xué)習(xí)，也是非常有益的。如何在編譯程序的功能實(shí)用性和教學(xué)可用性?xún)煞矫姹３制胶猓恢笔蔷幾g教學(xué)的難題。開(kāi)展綜合性實(shí)驗(yàn)，是提高學(xué)生對(duì)編譯程序整體理解和開(kāi)發(fā)能力的主要途徑。在這方面，有兩種思路。一種是側(cè)重整體體驗(yàn)，主要是面向一個(gè)為教學(xué)而專(zhuān)門(mén)設(shè)計(jì)的精簡(jiǎn)語(yǔ)言，如前文介紹的PL、TINY和COOL等，這些語(yǔ)言通常包含現(xiàn)代程序設(shè)計(jì)語(yǔ)言典型成分，但更為精簡(jiǎn)，學(xué)生可以通過(guò)課程學(xué)習(xí)，最后為該語(yǔ)言實(shí)現(xiàn)一個(gè)完整的編譯器。按照這種方案開(kāi)展綜合性實(shí)驗(yàn)，有利于學(xué)生體驗(yàn)一個(gè)完整的編譯程序開(kāi)發(fā)過(guò)程。第二種思路側(cè)重實(shí)用性和真實(shí)性，主要以GCC、LCC這類(lèi)實(shí)用的，甚至是產(chǎn)品級(jí)的開(kāi)源編譯器為平臺(tái)開(kāi)展實(shí)踐。由于GCC、LCC這類(lèi)實(shí)用編譯程序代碼量非常大，如何引導(dǎo)學(xué)生在紛繁復(fù)雜的代碼中理清頭緒、找到和教學(xué)知識(shí)點(diǎn)相關(guān)的程序段，需要教師做好充分的準(zhǔn)備。這種思路，對(duì)于將來(lái)從事編譯程序開(kāi)發(fā)的學(xué)生，其收獲可能更大。

4.結(jié)語(yǔ)

理論和實(shí)踐的完美結(jié)合是編譯程序研制的突出特點(diǎn)，也是編譯課程教學(xué)力圖為學(xué)生展示的特色。為了使學(xué)生切實(shí)體驗(yàn)編譯經(jīng)典理論在編譯程序研制以及其他領(lǐng)域發(fā)揮重要作用，我們收集了一批編譯開(kāi)發(fā)工具，并對(duì)這些資源從公開(kāi)程度、開(kāi)發(fā)語(yǔ)言、生成語(yǔ)言、系統(tǒng)平臺(tái)、涉及課程知識(shí)點(diǎn)、應(yīng)用領(lǐng)域和是否提供案例等方面進(jìn)行分析和標(biāo)注。到目前為止，已收集60余項(xiàng)軟件工具資源，并在課程網(wǎng)站上發(fā)布。下一步，我們將繼續(xù)擴(kuò)大收集編譯資源的規(guī)模，并進(jìn)一步提高分析和標(biāo)注的準(zhǔn)確性，積極探索如何結(jié)合這些資源開(kāi)展課堂教學(xué)和實(shí)踐教學(xué)改革，利用這些資源向?qū)W生展示編譯研究中“經(jīng)典理論和先進(jìn)技術(shù)有機(jī)結(jié)合”的突出特點(diǎn)，并使學(xué)生切實(shí)體驗(yàn)編譯經(jīng)典理論在各領(lǐng)域的重要作用，培養(yǎng)學(xué)生的計(jì)算思維，提高課程教學(xué)的效果。