“編譯原理”課程教學研究和教材編寫

溫敬和

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

教材現狀和問題

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

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

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

當然也不是說國外教材什么都好，包括國外優秀教材在內，也有不足之處。舉一個簡單例子：計算機的內存越來越大，由于引入控件，用戶程序越來越短，是否還有必要將“在詞法分析預處理時，通常將輸入緩沖區分成二個半區互補輪流工作”這一內容寫入教材，我想至少要說明一下。

提高教師自身學術水平

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

現在有越來越多的教師加入了寫書行列，著書立說已不是少數人的專利。但是，如何寫書，如何寫好書，這是每個作者必須面對的問題。尤其是作為一本教材的作者，必須具有一定的學術水平。在自己所涉及的學科領域中要花大功夫，要有自己的見解，要有自己的論文。在一定知識積累的基礎上，才能編寫好教材。

以科研為基礎

“編譯原理”課程是一門實踐性很強的課程。盡管這門學科比較成熟，但仍然存在許多課題，有待我們去探索。比較典型的問題就是上面提及的LEX和YACC類似系統的實現。

本人先后實現了LL(1)分析表自動產生器、LR(0)分析表自動產生器和SLR(1)分析表自動產生器，相當于實現了YACC類似系統。由于有這樣的編程經歷，使得我在上語法分析課時，有一種如魚得水的感覺。

作者曾試圖實現LEX系統，但未獲成功。正規式相當于算術表達式，作者從LR分析法的教學中得到啟示，將LR分析法應用于詞法分析器的自動構造，成功地實現了詞法分析器的自動產生器，所生成的詞法分析器是使用LR分析表來工作的。為了區別LEX系統，該系統簡稱為LR_LEX系統。

在此基礎上，本人進一步實現了匯編程序自動產生器，論文發表于《計算機工程》雜志2005年第12期。

該二項新的編譯技術和方法已寫進《編譯原理實用教程》一書，該書已由清華大學出版社出版發行。

重組教材內容

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

由于面向的學生不同，培養目標不同，如何編寫合適的“編譯原理”課程教材，在很大程度上取決于作者本人所處的教學環境。但是，有一點是共通的，通過“編譯原理”課程教學，使學生掌握編譯基本理論和方法，能夠建立一個較為完整的編譯系統模型。不能由于作者個人因素或者知識難易程度來左右教材的書寫。從國內出版的一部分《編譯原理》課程教材和實際教學內容安排來看，本人認為存在如下問題：

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

（2）語法分析部分過多；

（3）語義分析部分過于簡單；

（4）目標代碼生成部分幾乎是空白；

（5）講授了一些不是很有必要講授的內容（如DFA最小化、中間代碼優化等）。

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

詞法分析相當重要。正是從詞法分析開始，將學生領進編譯系統的大門。并且，作為編譯系統的基礎理論（自動機），也是在詞法分析階段講授的。在授課中，應強調單詞二元式的作用，單詞種別用于語法分析，單詞值用于語義分析。關于“DFA最小化”這一部分教學內容，本人認為應刪除，教育重點應為：DFA的構造和使用。理由為：編譯系統太復雜，首先要解決吃飯問題，然后再解決吃得好問題。

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

語義分析部分應加強，這是學生理解整個編譯系統的關鍵，尤其要著重介紹符號表和常數表在編譯程序中的作用。有了護照，可以周游世界；有了符號表和常數表，可以在編譯系統中暢行無阻，符號表和常數表就是編譯系統的護照。在內存分配時，符號表是變量地址分配的依據。由于符號表的引入，使得代碼生成和變量實際存放地址無關；甚至可在程序運行過程中，對變量地址進行動態分配。

在目標代碼生成部分，可先假設一個匯編語言虛擬機模型，然后介紹從四元式到匯編語言的翻譯。應強調的是：由于符號表和常數表的結構不同，導致變量和常數尋址方式的不同。從匯編語言到機器碼的翻譯, 可將其留作課程實習，詳見下一節。

創建實驗環境

向學生提供一個虛擬裸機，虛擬裸機是用高級語言來實現的，虛擬裸機只接受二進制形式的機器指令。提供虛擬裸機的好處在于：可將與編譯無關的一些硬件特性屏蔽掉，可根據要求來改變虛擬硬件配置。

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

有關這一部分內容，在《編譯原理實用教程》一書中有詳細介紹。

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