“編譯原理”課程教學(xué)研究和教材編寫

溫敬和

由于教育的需求和市場(chǎng)經(jīng)濟(jì)的作用，目前教材出版業(yè)相當(dāng)活躍，新書層出不窮，令人目不暇接。作為一個(gè)使用教材進(jìn)行教學(xué)的教師，最關(guān)心的是教材質(zhì)量，選擇合適的教材是進(jìn)行教學(xué)的第一步。教材與專著不同，教材是教師教學(xué)的工具，教材的主要讀者是學(xué)生。在書寫教材的過(guò)程中，對(duì)學(xué)科的知識(shí)體系要進(jìn)行合理的刪選，使它適合于教學(xué)和知識(shí)的傳授。由于本人長(zhǎng)期從事“編譯原理”課程教學(xué)，所以對(duì)于該課程的教材特別關(guān)注，想就“編譯原理”課程的教學(xué)和教材編寫，發(fā)表一些本人的看法，供同行參考。

教材現(xiàn)狀和問(wèn)題

我上大學(xué)時(shí)，“編譯原理”課程用的是由陳火旺、錢家驊、孫永強(qiáng)三位老師合寫的“編譯原理”一書，這本書可稱之為編譯原理教材的經(jīng)典。該書系統(tǒng)地介紹了編譯基本理論和方法，內(nèi)容充實(shí)，覆蓋面廣。既注重了最經(jīng)典、最廣泛的基本編譯技術(shù)，又力求反映20世紀(jì)70年代以來(lái)一些最重要的新成果。至今，該書仍是我進(jìn)行教育和科研的主要參考書之一。我記得當(dāng)時(shí)上課的王家啟老師（上海計(jì)算技術(shù)研究所）給當(dāng)學(xué)生的我們出了一個(gè)上機(jī)題目：輸入一個(gè)正規(guī)式，輸出該正規(guī)式對(duì)應(yīng)的確定有限自動(dòng)機(jī)，當(dāng)然該題是書中習(xí)題之一。在解題過(guò)程中，我曾經(jīng)有過(guò)這樣的想法，是否可以用LR分析法來(lái)解決這個(gè)問(wèn)題。正是由于這個(gè)20年前的想法，加上自己不斷的努力，在對(duì)編譯理論理解和實(shí)踐不斷加深的同時(shí)，于2001年提出了一個(gè)新的自動(dòng)構(gòu)造詞法分析器的方法，論文發(fā)表于《計(jì)算機(jī)工程》雜志2001年第7期。

在隨后的“編譯原理”課程的教學(xué)中，本人也不斷發(fā)現(xiàn)好書或書中寫得比較好的段落。例如由高仲儀、蔣立源二位老師合寫的《編譯技術(shù)》一書。在該書中，通過(guò)一個(gè)“大象吃花生”的英文句子的語(yǔ)法分析，引入上下無(wú)關(guān)文法的基本概念和定義，這樣的書寫使人特別容易理解。又如由何炎祥老師主編的《編譯原理》一書。在該書中有關(guān)LR分析法基本原理的描述寫得相當(dāng)好，他將活前綴在LR分析法中的作用寫得清清楚楚。另外，盡管有些書不是介紹編譯技術(shù)的，但是這些書對(duì)于“編譯原理”課程的教學(xué)也是相當(dāng)有益。例如由蔣國(guó)南老師翻譯的《PASCAL程序設(shè)計(jì)》一書，書中二個(gè)程序例給了我特別深刻的印象。一個(gè)是去除源程序注釋的程序例，而另一個(gè)是使用自動(dòng)機(jī)的程序例。在以往的《編譯原理》教科書中，只介紹如何構(gòu)造自動(dòng)機(jī)，基本上不介紹使用自動(dòng)機(jī)的控制程序。其結(jié)果是：學(xué)生只知道自動(dòng)機(jī)的構(gòu)造方法，但不知道自動(dòng)機(jī)如何使用。同樣，在以往的詞法分析教學(xué)中，只注重掃描器（單詞識(shí)別程序）的教學(xué)，手工構(gòu)造有狀態(tài)轉(zhuǎn)換圖，自動(dòng)構(gòu)造有DFA；而對(duì)于詞法分析的輸入和預(yù)處理，最多一筆帶過(guò)。實(shí)際上，輸入和預(yù)處理程序是編譯程序和用戶程序的接口。編譯程序首先是從文件讀入源程序，經(jīng)預(yù)處理后，才由掃描器進(jìn)行單詞識(shí)別。適當(dāng)加強(qiáng)這部分內(nèi)容的教學(xué)，有助于學(xué)生對(duì)編譯程序前端的理解。

當(dāng)然，由國(guó)內(nèi)出版社出版的書也有不盡人意的地方。例如現(xiàn)在寫書都要求有創(chuàng)新或標(biāo)異。明明沒有創(chuàng)新或標(biāo)異，為了達(dá)到該指標(biāo)，將一些與“編譯原理”課程無(wú)關(guān)或關(guān)系不大的內(nèi)容寫入書內(nèi)，這些內(nèi)容根本不會(huì)用于教學(xué)，比較典型的是“并行編譯”這部分教材內(nèi)容。個(gè)別作者將國(guó)外教材刪去某些章節(jié)，加上習(xí)題和習(xí)題解答后，就作為一本教材交付某出版社出版。正因?yàn)楸救嗽I到過(guò)這種類型的書，從此改變了本人看到有關(guān)編譯的書就買的習(xí)慣。目前在市場(chǎng)上銷售的有關(guān)編譯的書，基本上都以LEX和YACC系統(tǒng)作為“編譯原理”課程實(shí)習(xí)手段。當(dāng)然LEX和YACC系統(tǒng)有多種版本，可用于不同的操作系統(tǒng)。但LEX和YACC系統(tǒng)畢竟是外國(guó)人編制的，是否適合于國(guó)內(nèi)教學(xué)仍是個(gè)問(wèn)號(hào)。由于本人與他校教師基本無(wú)教學(xué)交流，也不清楚實(shí)際使用效果如何，有關(guān)編譯的書大都由多人合寫，寫編譯理論部分的作者和寫實(shí)驗(yàn)部分的作者往往不是同一人。從書的整體來(lái)看，有明顯的脫節(jié)現(xiàn)象。LEX系統(tǒng)實(shí)際是一個(gè)狀態(tài)轉(zhuǎn)換矩陣產(chǎn)生器，而YACC系統(tǒng)實(shí)際上是一個(gè)LALR(1)分析表產(chǎn)生器。我想，LEX和YACC系統(tǒng)并沒有復(fù)雜到常人不可實(shí)現(xiàn)的程度，為什么作者本人不能動(dòng)手編寫一個(gè)類似系統(tǒng)用于學(xué)生實(shí)驗(yàn)。

當(dāng)然也不是說(shuō)國(guó)外教材什么都好，包括國(guó)外優(yōu)秀教材在內(nèi)，也有不足之處。舉一個(gè)簡(jiǎn)單例子：計(jì)算機(jī)的內(nèi)存越來(lái)越大，由于引入控件，用戶程序越來(lái)越短，是否還有必要將“在詞法分析預(yù)處理時(shí)，通常將輸入緩沖區(qū)分成二個(gè)半?yún)^(qū)互補(bǔ)輪流工作”這一內(nèi)容寫入教材，我想至少要說(shuō)明一下。

提高教師自身學(xué)術(shù)水平

“編譯原理”這門課程涉及的知識(shí)面較廣，一頭是程序設(shè)計(jì)語(yǔ)言，包括文件系統(tǒng)；而另一頭是匯編語(yǔ)言或機(jī)器語(yǔ)言，包括計(jì)算機(jī)的系統(tǒng)結(jié)構(gòu)。編譯系統(tǒng)以形式語(yǔ)言和自動(dòng)機(jī)為基礎(chǔ)理論，構(gòu)造算法復(fù)雜，系統(tǒng)十分龐大。所以，將“程序設(shè)計(jì)語(yǔ)言”、“數(shù)據(jù)結(jié)構(gòu)”、“離散數(shù)學(xué)”和“匯編語(yǔ)言”等課程作為“編譯原理”課程的前驅(qū)課程已成為共識(shí)。作為一個(gè)“編譯原理”課程授課教師，除“編譯原理”課程本身外，還要全面掌握上述這些課程的知識(shí)。尤其是對(duì)于“程序設(shè)計(jì)語(yǔ)言”和“匯編語(yǔ)言”這兩門課程，要有一定的教學(xué)經(jīng)歷，這樣才能把握好“編譯原理”這門課程的教學(xué)。

現(xiàn)在有越來(lái)越多的教師加入了寫書行列，著書立說(shuō)已不是少數(shù)人的專利。但是，如何寫書，如何寫好書，這是每個(gè)作者必須面對(duì)的問(wèn)題。尤其是作為一本教材的作者，必須具有一定的學(xué)術(shù)水平。在自己所涉及的學(xué)科領(lǐng)域中要花大功夫，要有自己的見解，要有自己的論文。在一定知識(shí)積累的基礎(chǔ)上，才能編寫好教材。

以科研為基礎(chǔ)

“編譯原理”課程是一門實(shí)踐性很強(qiáng)的課程。盡管這門學(xué)科比較成熟，但仍然存在許多課題，有待我們?nèi)ヌ剿?。比較典型的問(wèn)題就是上面提及的LEX和YACC類似系統(tǒng)的實(shí)現(xiàn)。

本人先后實(shí)現(xiàn)了LL(1)分析表自動(dòng)產(chǎn)生器、LR(0)分析表自動(dòng)產(chǎn)生器和SLR(1)分析表自動(dòng)產(chǎn)生器，相當(dāng)于實(shí)現(xiàn)了YACC類似系統(tǒng)。由于有這樣的編程經(jīng)歷，使得我在上語(yǔ)法分析課時(shí)，有一種如魚得水的感覺。

作者曾試圖實(shí)現(xiàn)LEX系統(tǒng)，但未獲成功。正規(guī)式相當(dāng)于算術(shù)表達(dá)式，作者從LR分析法的教學(xué)中得到啟示，將LR分析法應(yīng)用于詞法分析器的自動(dòng)構(gòu)造，成功地實(shí)現(xiàn)了詞法分析器的自動(dòng)產(chǎn)生器，所生成的詞法分析器是使用LR分析表來(lái)工作的。為了區(qū)別LEX系統(tǒng)，該系統(tǒng)簡(jiǎn)稱為L(zhǎng)R_LEX系統(tǒng)。

在此基礎(chǔ)上，本人進(jìn)一步實(shí)現(xiàn)了匯編程序自動(dòng)產(chǎn)生器，論文發(fā)表于《計(jì)算機(jī)工程》雜志2005年第12期。

該二項(xiàng)新的編譯技術(shù)和方法已寫進(jìn)《編譯原理實(shí)用教程》一書，該書已由清華大學(xué)出版社出版發(fā)行。

重組教材內(nèi)容

可能有些《編譯原理》教材作者，他寫書的目的并不是完全面向?qū)W生的，可能考慮把它作為這門學(xué)科的大全來(lái)編寫。例如由美國(guó)著名計(jì)算機(jī)科學(xué)家Alfred V.Aho、Ravi Sethit和Jeffrey D.Ullman合著的《Compilers: Principle,Techniques,and Tools》一書，該書已由李建中和姜守旭老師翻譯成中文，中文譯名為《編譯原理》。將這樣的書作為教材，本人認(rèn)為是不合適的，將它作為教師的教學(xué)參考用書，那是最好不過(guò)了。

由于面向的學(xué)生不同，培養(yǎng)目標(biāo)不同，如何編寫合適的“編譯原理”課程教材，在很大程度上取決于作者本人所處的教學(xué)環(huán)境。但是，有一點(diǎn)是共通的，通過(guò)“編譯原理”課程教學(xué)，使學(xué)生掌握編譯基本理論和方法，能夠建立一個(gè)較為完整的編譯系統(tǒng)模型。不能由于作者個(gè)人因素或者知識(shí)難易程度來(lái)左右教材的書寫。從國(guó)內(nèi)出版的一部分《編譯原理》課程教材和實(shí)際教學(xué)內(nèi)容安排來(lái)看，本人認(rèn)為存在如下問(wèn)題：

（1）詞法分析部分偏少；

（2）語(yǔ)法分析部分過(guò)多；

（3）語(yǔ)義分析部分過(guò)于簡(jiǎn)單；

（4）目標(biāo)代碼生成部分幾乎是空白；

（5）講授了一些不是很有必要講授的內(nèi)容（如DFA最小化、中間代碼優(yōu)化等）。

這是造成學(xué)生學(xué)習(xí)“編譯原理”課程感到困惑的主要原因。難怪有些教師寧可使用老教材或者國(guó)外教材，而不愿使用新教材。

詞法分析相當(dāng)重要。正是從詞法分析開始，將學(xué)生領(lǐng)進(jìn)編譯系統(tǒng)的大門。并且，作為編譯系統(tǒng)的基礎(chǔ)理論（自動(dòng)機(jī)），也是在詞法分析階段講授的。在授課中，應(yīng)強(qiáng)調(diào)單詞二元式的作用，單詞種別用于語(yǔ)法分析，單詞值用于語(yǔ)義分析。關(guān)于“DFA最小化”這一部分教學(xué)內(nèi)容，本人認(rèn)為應(yīng)刪除，教育重點(diǎn)應(yīng)為：DFA的構(gòu)造和使用。理由為：編譯系統(tǒng)太復(fù)雜，首先要解決吃飯問(wèn)題，然后再解決吃得好問(wèn)題。

語(yǔ)法分析部分的教材篇幅應(yīng)大幅減少。算符優(yōu)先分析法較簡(jiǎn)單，宜于手工構(gòu)造，特別適合于算術(shù)表達(dá)式的語(yǔ)法分析，在有些程序設(shè)計(jì)語(yǔ)言書中，也能看到它的介紹。由于算符優(yōu)先分析法適用范圍較小，實(shí)用意義不大，在教材中完全可將其刪除。關(guān)于LR分析法，本人認(rèn)為只要介紹LR(0)和SLR(1)分析法即可。理由為：SLR(1)分析法很實(shí)用，分析表又易于構(gòu)造，它可解決大部分語(yǔ)言的識(shí)別問(wèn)題。編譯系統(tǒng)中的事情太多，先解決主要矛盾。

語(yǔ)義分析部分應(yīng)加強(qiáng)，這是學(xué)生理解整個(gè)編譯系統(tǒng)的關(guān)鍵，尤其要著重介紹符號(hào)表和常數(shù)表在編譯程序中的作用。有了護(hù)照，可以周游世界；有了符號(hào)表和常數(shù)表，可以在編譯系統(tǒng)中暢行無(wú)阻，符號(hào)表和常數(shù)表就是編譯系統(tǒng)的護(hù)照。在內(nèi)存分配時(shí)，符號(hào)表是變量地址分配的依據(jù)。由于符號(hào)表的引入，使得代碼生成和變量實(shí)際存放地址無(wú)關(guān)；甚至可在程序運(yùn)行過(guò)程中，對(duì)變量地址進(jìn)行動(dòng)態(tài)分配。

在目標(biāo)代碼生成部分，可先假設(shè)一個(gè)匯編語(yǔ)言虛擬機(jī)模型，然后介紹從四元式到匯編語(yǔ)言的翻譯。應(yīng)強(qiáng)調(diào)的是：由于符號(hào)表和常數(shù)表的結(jié)構(gòu)不同，導(dǎo)致變量和常數(shù)尋址方式的不同。從匯編語(yǔ)言到機(jī)器碼的翻譯, 可將其留作課程實(shí)習(xí)，詳見下一節(jié)。

創(chuàng)建實(shí)驗(yàn)環(huán)境

向?qū)W生提供一個(gè)虛擬裸機(jī)，虛擬裸機(jī)是用高級(jí)語(yǔ)言來(lái)實(shí)現(xiàn)的，虛擬裸機(jī)只接受二進(jìn)制形式的機(jī)器指令。提供虛擬裸機(jī)的好處在于：可將與編譯無(wú)關(guān)的一些硬件特性屏蔽掉，可根據(jù)要求來(lái)改變虛擬硬件配置。

要求學(xué)生根據(jù)虛擬裸機(jī)的機(jī)器指令設(shè)計(jì)匯編語(yǔ)言，然后構(gòu)造匯編程序。用戶用匯編語(yǔ)言編寫程序，由匯編程序?qū)⑺g成機(jī)器指令程序，該機(jī)器指令程序可以在虛擬裸機(jī)上運(yùn)行，這樣就形成了一個(gè)微型編譯系統(tǒng)。這個(gè)微型編譯系統(tǒng)包括了編譯過(guò)程的四個(gè)主要階段，它們是詞法分析、語(yǔ)法分析、語(yǔ)義分析和目標(biāo)代碼生成。在匯編程序構(gòu)造中，要求學(xué)生運(yùn)用在“編譯原理”課程中所學(xué)到的理論和方法。首先根據(jù)機(jī)器指令中所含的地址數(shù)量，將機(jī)器指令劃分為0地址指令（RET）、A型1地址指令（READ）、B型1地址指令（CALL）和2地址（ADD）指令三大類。然后用上下文無(wú)關(guān)文法予以描述，并生成SLR(1)分析表。由于分析表的規(guī)模不大，可由學(xué)生手工構(gòu)造。在有條件的情況下，可向?qū)W生提供SLR(1)分析表產(chǎn)生器，用于驗(yàn)證分析表的正確性。根據(jù)機(jī)器指令的二進(jìn)制位特征，設(shè)計(jì)和構(gòu)造語(yǔ)義分析器。語(yǔ)義分析子程序主要是由二進(jìn)制位運(yùn)算構(gòu)成。當(dāng)然這個(gè)匯編程序是相當(dāng)初步的，它不允許用戶用符號(hào)名來(lái)表示變量地址或標(biāo)號(hào)。

有關(guān)這一部分內(nèi)容，在《編譯原理實(shí)用教程》一書中有詳細(xì)介紹。

“編譯原理”課程是計(jì)算機(jī)專業(yè)本科生必修課程。該課程對(duì)于計(jì)算機(jī)專業(yè)學(xué)生來(lái)說(shuō)，是一門難度較大的專業(yè)課程，不少學(xué)生，就連上課教師也感到頭疼。由于學(xué)生對(duì)該課程意見比較大，有些學(xué)校甚至準(zhǔn)備將“編譯原理”課程從本科教學(xué)計(jì)劃中刪除。實(shí)際上，計(jì)算機(jī)專業(yè)課程大部分都比較難，如計(jì)算機(jī)操作系統(tǒng)、計(jì)算機(jī)組成原理、計(jì)算機(jī)網(wǎng)絡(luò)等。為什么學(xué)生對(duì)“編譯原理”課程教學(xué)意見特別大，可能有多種原因。計(jì)算機(jī)操作系統(tǒng)有五大管理，這些管理可以分別單獨(dú)講授，可不涉及它們之間的聯(lián)系。因?yàn)樵谀撤N狀態(tài)下，計(jì)算機(jī)確實(shí)以這種方式工作。如果要介紹操作系統(tǒng)的整體工作機(jī)制的話，我想操作系統(tǒng)要比編譯系統(tǒng)難得多。更深層次的原因還是應(yīng)從教師自身查找，只有深刻理解編譯系統(tǒng)的工作原理，包括理論和實(shí)踐兩個(gè)方面，才能為人之師。天下無(wú)難事，只怕有心人，只要我們不斷努力，我想一定能搞好“編譯原理”課程的教學(xué)。