“編譯原理”課程的教學內(nèi)容選擇的探討

張 昱 陳意云 郭 宇 李兆鵬

摘要:本文根據(jù)國外“編譯原理”教材的演化情況并結(jié)合筆者自己的教學和科研的經(jīng)驗,對國內(nèi)“編譯原理”的教學提出了普通高校本科、重點高校本科和研究生階段三個不同層次的教學目標,并給出了這三個層次的教學內(nèi)容的建議,供國內(nèi)同行參考。

關鍵詞:編譯原理;編程語言;教學目標;教學內(nèi)容

中圖分類號:G642 文獻標識碼:A

1引言

編程語言的“編譯原理”是計算機專業(yè)一門非常有用的核心課程,又是一門需要較大投入的課程。怎樣激發(fā)學生的學習熱情,努力學好本課程?在正確的教學目標下選擇適當?shù)慕虒W內(nèi)容是非常重要的一環(huán)?；诠P者長期承擔“編譯原理”教學的體會,以及多年從事編程語言理論和實現(xiàn)技術研究的積累,本文闡述筆者對該問題的認識。

國外和國內(nèi)分別從二十世紀六十和八十年代開始設置“編譯原理”課程,幾十年來,“編譯原理”課程可以講授的內(nèi)容越來越多,從文獻[1,2]這兩本專著的內(nèi)容看出。和第一版相比,第二版壓縮了編譯原理傳統(tǒng)部分的內(nèi)容,大量增加了新技術內(nèi)容,書的厚度從接近800頁猛增到超過1000頁。第一版中被刪除的部分包括:語法分析中的算符優(yōu)先分析法,語法制導翻譯中的遞歸計算方法、語法制導翻譯的實現(xiàn)細節(jié)和語法制導定義的分析,最后兩章的編譯器自展和一些具體編譯器的介紹。在靜態(tài)檢查一章介紹的類型系統(tǒng)和類型檢查被分散和弱化到中間代碼生成一章中。第二版中增加的內(nèi)容包括:

(1) 堆管理和各種垃圾收集算法。

(2) 獨立于機器的代碼優(yōu)化增加了數(shù)據(jù)流分析的理論基礎,強調(diào)了在一個數(shù)據(jù)流分析的一般框架下解決各種具體數(shù)據(jù)流問題,能使讀者對程序分析和代碼優(yōu)化有更深刻的認識。

(3) 依賴于機器的優(yōu)化,包括現(xiàn)代處理器體系結(jié)構、指令調(diào)度、基本塊調(diào)度、全局調(diào)度和軟件流水等。

(4) 并行性和數(shù)據(jù)局部性優(yōu)化,重點介紹在多處理器系統(tǒng)上,使用數(shù)組作為數(shù)據(jù)結(jié)構,并且以簡單而有序模式訪問這些數(shù)據(jù)的計算密集型程序的優(yōu)化問題。

(5) 過程間的分析,包括調(diào)用圖、上下文敏感分析和指針分析等。

國外另一本著名的專著是Appel的《Modern Compiler Implementation in C(3rd. Edition)》(還有Java語言描述和ML語言描述的版本)。全書21章,表明它涉及的內(nèi)容廣泛,比Aho第二版覆蓋的范圍還要廣,包括了面向?qū)ο缶幊陶Z言和函數(shù)式編程語言的實現(xiàn)方法。但是全書不到550頁。因為Appel強調(diào)編譯原理的學習離不開具體的實踐,他精心設計了一個“學生項目編譯器”的框架和模塊接口,每章的結(jié)尾給出與該章內(nèi)容相關的編譯器模塊的設計任務,要求學生逐步實現(xiàn)一個編譯器。對相關的理論,該書的介紹都比較粗略;對相關算法,除了直接用代碼表達的以外,大多數(shù)只通過例子表達思想。

從這兩本教材可以看出國際教材的變化趨勢是壓縮僅和編譯器前端有關的部分,增加獨立于機器的優(yōu)化和依賴于機器的優(yōu)化等內(nèi)容。

國內(nèi)的編譯原理教材基本上都是根據(jù)國外教材編寫的,在跟蹤過程中,總顯得有些滯后。例如,國外2000年以后出版的教材已經(jīng)不介紹算符優(yōu)先分析法,而國內(nèi)2004年和2005年出版的一些較有影響的教材仍然介紹算符優(yōu)先分析法。在增加新內(nèi)容方面,國內(nèi)教材也相對落后,筆者力圖克服這一缺點,在新近改版的教材(詳見文獻[5])中,加入了依賴于機器的優(yōu)化內(nèi)容。

真正從事主流編程語言編譯器設計的雖然只是極少數(shù)一部分人,但是編譯技術在計算機體系結(jié)構設計、提高軟件開發(fā)效率與質(zhì)量的工具開發(fā)等方面有著重要的應用,這是學習編譯原理的主要理由。在編譯原理所涉及的知識越來越多,而“編譯原理”課程的課時數(shù)不足的情況下,如何選擇編譯原理的教學內(nèi)容是一件值得探討的事情。

2教學目標

筆者認為,雖然編譯原理和技術對計算機專業(yè)的學生來說是重要的基礎知識之一,但是對不同層次的高校,應該編寫不同深度的教材,講授不同的內(nèi)容,以達到不同的教學目標。

可以將教學目標分成三個層次:普通高校本科的目標、重點高校本科的目標和研究生階段的目標。下面概述的這些目標中,后者包括了前者,并且邊界不是絕對的。

(1) 普通高校本科的目標是:通過編程語言實現(xiàn)技術的學習,提高學習編程語言及在程序開發(fā)中應用編程語言的能力,具體解釋如下:

提高學習、理解和使用編程語言的能力;

提高程序排錯的能力,即快速理解、定位和解決在程序開發(fā)與程序運行中碰到的問題的能力;

提高編寫高質(zhì)量代碼的能力。

(2) 重點高校本科的目標是:通過對與編程語言相關的理論和技術的學習,提高在軟件工程中應用這些理論和技術的能力。和編程語言有關的理論和技術包括:

形式語言和自動機理論、語法制導的翻譯技術、類型論和類型系統(tǒng)、數(shù)據(jù)流分析的理論基礎等,可以選擇一部分作為教學內(nèi)容;

LR分析和語法制導翻譯等技術,代碼生成和代碼優(yōu)化中的一些重要算法。

(3) 研究生階段的目標是:通過對與編程語言密切相關的、更寬泛的理論和技術的學習,提高在科研工作中應用相關理論和技術的能力。這些理論和技術列舉如下:

依賴于機器的各種優(yōu)化技術;

其它范型的編程語言的理論和實現(xiàn)技術;

程序分析的理論和技術;

并行編譯理論和技術。

3教學內(nèi)容的選擇

本節(jié)探討在三種不同教學目標下的教學內(nèi)容。不管怎樣選擇教學內(nèi)容,都要有恰當?shù)恼n程實踐作為課堂教學的非常重要的補充。筆者已另外行文專門介紹在課程實踐方面的經(jīng)驗和體會,因此本文不再討論課程實踐。

3.1普通高校本科

根據(jù)前面提到的目標,筆者認為,教學內(nèi)容應強調(diào)對編譯原理和技術的宏觀理解及全局把握,而不要把學生的注意力分散到一些枝節(jié)的算法上,如計算開始符號集合和后繼符號集合的算法、回填技術等。另一方面,教學內(nèi)容和習題要包括一些從實際碰到的問題中抽象出來的例題和習題,鼓勵學生用所學的知識去分析和解決實際問題。筆者在這方面已經(jīng)有所嘗試(詳見文獻[6, 7]),教材中主要各章都有配合該章內(nèi)容的C語言小程序作為例題或習題。

針對編譯的各邏輯階段,筆者建議的教學內(nèi)容如下。

(1) 詞法分析

正規(guī)式、不確定的有限自動機、確定的有限自動機及其最小化是主線;同時要有用C語言寫的一個簡單語言的詞法分析器,并介紹詞法分析器的生成器。

有限自動機是一種經(jīng)常用得著的概念和工具,放在編譯原理課程中介紹最為合適。詞法分析器的生成器是上述主線的自然產(chǎn)物,由于它比較簡單,讓學生通過它來開始理解程序生成的概念和工具較為合適。

(2) 語法分析

上下文無關文法是必備的基礎知識。LL(1)文法和遞歸下降分析方法比較直觀,便于學生接受,應首先介紹,并伴有一個簡單語言的遞歸下降分析程序作為例子。在介紹自下而上分析的一般概念和使用LR分析表進行移進?歸約分析后,直接介紹分析器的自動生成器,并介紹歸約時的語義動作,為下面階段語義工作的描述奠定基礎。

算符優(yōu)先分析法沒有必要講,因為編譯器的語法分析已不再使用這種方法。LR分析方法固然很重要,但由于SLR(1)分析、規(guī)范LR(1)分析和向前看LR(1)分析的介紹需要占用較多課時,因此以不介紹這幾種LR分析表的生成算法而直接介紹LR分析表的使用為好。

(3) 靜態(tài)語義檢查

概述靜態(tài)語義檢查包括哪些方面,然后重點放在類型檢查上。類型系統(tǒng)在編程語言的設計中占據(jù)重要位置,可以先介紹一下類型系統(tǒng)在編程語言中的作用,然后用語義動作來表達類型檢查算法。

(4) 運行時存儲空間的組織和管理

這是最需要搞明白的部分。尤其在用C這樣比較低級的語言時,掌握這部分內(nèi)容對編寫程序和程序排錯都很有幫助。具體應該介紹局部存儲分配策略(即一個活動記錄中各類數(shù)據(jù)的組織),靜態(tài)分配、棧式分配和堆式分配等三種全局存儲分配策略,非局部名字的訪問方式和各種參數(shù)傳遞方式的實現(xiàn)。

(5) 中間代碼生成

主要介紹各種形式的中間語言,把賦值語句和各種控制流語句翻譯成中間代碼的語義動作。對于類型和變量聲明語句,主要關注怎樣按語言的作用域規(guī)則組織符號表。至于符號表中符號的插入和查找方法在數(shù)據(jù)結(jié)構課程中已經(jīng)介紹過,沒有必要在這里重復。

(6) 代碼生成

選擇一種采用簡單的寄存器分配策略的代碼生成算法加以介紹,讓學生對代碼生成有所了解即可。

(7) 代碼優(yōu)化

用實例來介紹各類優(yōu)化,讓學生明白編譯器能完成哪些優(yōu)化,而不要給學生介紹各種優(yōu)化算法。這對編程有用處,例如,在可讀性好的源代碼和優(yōu)化的源代碼兩者之間做選擇時,若知道那些優(yōu)化可以由優(yōu)化編譯完成,則寧可選擇可讀性好的代碼。

(8) 編譯系統(tǒng)和運行系統(tǒng)

通常,除了編譯器外,還需要一些其它工具的幫助,才能得到可執(zhí)行的目標程序,這些工具包括預處理器、匯編器和連接器等。這些工具都較簡單和明顯。了解這些工具有助于掌握從源程序到可執(zhí)行目標程序的實際處理過程,這些知識對于參與大型軟件系統(tǒng)的開發(fā)是很有用的。

這部分主要是讓學生了解預處理、編譯、匯編和連接這個流程,目標文件的格式,連接時的符號解析,靜態(tài)庫和動態(tài)庫等。

3.2重點高校本科

粗略地說,普通高校本科計算機專業(yè)在軟件方面主要培養(yǎng)軟件編程人員,而重點高校本科培養(yǎng)高一個層次的軟件設計和開發(fā)人員。因此需要學生掌握或了解和編程語言有關的理論以及和編程語言實現(xiàn)有關的重要算法。

(1) 形式語言和自動機理論

形式語言理論是用數(shù)學方法研究自然語言和人工語言(如編程語言)的語法的理論,它只研究語言的組成規(guī)則而不研究語言的含義。自動機理論是以研究離散數(shù)學系統(tǒng)的結(jié)構、功能以及兩者之間關系為主要內(nèi)容的數(shù)學理論。形式語言分層的四類文法和圖靈機等某些自動機的對應(接受同樣語言)是形式語言和自動機之間的重要聯(lián)系。形式語言和自動機理論在編程語言的描述和編譯、自然語言的理解和翻譯以及語法制導的模式識別等方面有著廣泛應用。若想給學生介紹一點形式語言和自動機理論,編譯原理課程是最理想的場所。

(2)LR分析方法

LR分析方法是一種高效的、自下而上的語法分析技術,它能適用于一大類上下文無關文法的分析。LR分析方法被廣泛采用,各種分析器的生成器幾乎都是生成LR分析器。因此在全面介紹語法分析方法時,必須把LR分析方法當作重點來介紹。LR分析表的生成算法較復雜,因此還需把該算法當難點來講解。只有能全面把握LR分析方法時,才能說比較好地掌握了語法分析方法。

(3) 語法制導翻譯

語法制導的定義和語法制導的翻譯方案是描述編程語言翻譯的兩種常用形式方法。它們描述嚴格并便于理解,因此大部分有一定深度的教材都用它們來描述靜態(tài)語義檢查和中間代碼生成等。它們易于實現(xiàn),所以編譯器的生成器都要求編譯器的設計者用這樣的方法來表達識別出輸入串中的語法構造時要執(zhí)行的動作。通過對語法制導翻譯的實現(xiàn)技術的學習,會對程序生成器有更多的理解,這在軟件工程中是很有用處的。

(4) 類型論和類型系統(tǒng)

類型論是為了避免集合論悖論而建立起來的數(shù)學理論,主要研究集合的分層、分類方法。類型系統(tǒng)是一種依據(jù)程序短語語義值的種類來對程序短語進行分類的語法方法,它用來防止程序出現(xiàn)某些上下文有關的錯誤。在計算機科學的編程語言理論中,類型論提供了研究、設計和分析類型系統(tǒng)的形式基礎。編程語言的設計現(xiàn)在都是以類型系統(tǒng)的設計為中心來展開的;掌握類型系統(tǒng)知識對學習編程語言有重要的指導作用。此外,類型系統(tǒng)在軟件工程、軟件安全、高性能編譯器的實現(xiàn)和程序分析等領域都有深入的應用。

目前,國內(nèi)編譯原理的教材一般最多從類型系統(tǒng)的實現(xiàn)——類型檢查算法來粗淺地介紹類型系統(tǒng)的知識,缺乏類型系統(tǒng)在編程語言中作用的全面介紹,缺乏對多態(tài)類型這樣的非普通類型及其類型檢查方法的介紹。

形式語言、語法制導翻譯和類型系統(tǒng)知識的學習有助于提高學生的形式描述能力。

(5) 數(shù)據(jù)流分析的理論基礎

國內(nèi)介紹代碼優(yōu)化的編譯原理教材,對各種數(shù)據(jù)流分析問題,分別給出數(shù)據(jù)流方程及其迭代求解算法,也談及它們之間的聯(lián)系,但是沒有把它們作為一個整體來抽象地研究。文獻[2]突出數(shù)據(jù)流分析的理論基礎,強調(diào)在數(shù)據(jù)流分析的一個一般框架下解決各種具體數(shù)據(jù)流問題,使教材能站在更高層面上討論代碼優(yōu)化,給學生一種洞察數(shù)據(jù)流分析本質(zhì)的認識。

通過從半格定義開始的數(shù)據(jù)流分析一般框架的學習和理解,可以提高學生的數(shù)學抽象能力。

(6) 代碼生成和代碼優(yōu)化的算法

簡單的代碼生成算法離實際的代碼生成器相差太遠。寄存器分配的圖著色算法、樹重寫方式的指令選擇方法、為表達式樹產(chǎn)生最優(yōu)代碼的算法、動態(tài)規(guī)劃的代碼生成算法、使表達式的計算次數(shù)最小化的程序變換方法和程序流圖中自然循環(huán)的識別算法等,不僅能讓學生了解代碼生成和代碼優(yōu)化的技術,而且能給學生算法設計方面的啟迪。

隨著嵌入式系統(tǒng)應用越來越廣,自主設計嵌入式系統(tǒng)軟硬件的機會越來越多,要求軟件開發(fā)人員具備這部分知識的場合也不斷出現(xiàn)。

3.3研究生階段

在國內(nèi),就現(xiàn)階段來看,雖然直接參與編譯器的設計和開發(fā)的工程師還是很少,但是編譯器的設計影響著計算機科學的一些其它領域,如針對計算機體系結(jié)構的優(yōu)化、新計算機體系結(jié)構的設計、軟件質(zhì)量、軟件安全、程序翻譯和提高軟件開發(fā)效率的工具等,這些領域的研究和開發(fā)工作都需要編譯原理的知識。

研究生階段學習編譯原理的有關知識,主要是提高在科研和開發(fā)工作中應用相關理論和技術的能力。由于授課對象是本科畢業(yè)于不同學校的研究生,他們在編譯原理方面的知識背景大不一樣,因此可以挑選文獻[5]中第3.2節(jié)和該節(jié)列舉的部分理論和技術作為講課內(nèi)容。

(1) 依賴于機器的各種優(yōu)化技術

計算機體系結(jié)構的迅速演化引起對新的編譯器技術一種不知足的需要,幾乎所有的高性能系統(tǒng)都在利用兩種基本技術:并行化和內(nèi)存分層。并行性可以在指令級和處理器級分別發(fā)掘;內(nèi)存分層針對這樣的基本局限:構造非常快的存儲器或者非常大的存儲器是可能的,但是構造不出既快又大的存儲器。

所有現(xiàn)代微處理器都開拓指令級的并行。這種并行對程序員是隱蔽的,程序員理解為串行執(zhí)行的指令序列,會被硬件動態(tài)地檢查其中的相關性,并盡可能并行發(fā)射這些指令。編譯器對此的配合作用是重新整理指令,使得指令級的并行更有效。

文獻[2]有這些內(nèi)容的較詳細介紹。這部分內(nèi)容也可以在計算機體系結(jié)構的相關課程中介紹。

(2) 其它范型的編程語言的理論和實現(xiàn)技術

對于不同范型的語言,主要是讓學生了解其影響語言實現(xiàn)技術的重要語言特征,以及它們對實現(xiàn)技術的具體影響。

就面向?qū)ο缶幊陶Z言來說,其信息封裝雖是非常重要的特性;但對編譯器來說,實現(xiàn)這些作用域規(guī)則是簡單而明顯的。因此重點是在另一個重要的語言特征——繼承性及其實現(xiàn)上,實現(xiàn)中的關鍵數(shù)據(jù)結(jié)構是虛方法表。

理解函數(shù)式編程語言并不困難,重要的是理解其既允許高階函數(shù)又支持函數(shù)嵌套聲明給實現(xiàn)帶來的影響。重要的是明白此時棧式存儲分配不再適用,活動記錄必須創(chuàng)建在堆上。實現(xiàn)中的一些重要概念是函數(shù)變量的閉包、垃圾收集、逃逸變量、惰性計算和換名調(diào)用等。

其它還有邏輯編程語言,例如Prolog語言,使用這類語言的人很少,無特別需要則不必介紹。

(3) 程序分析的理論和技術

程序分析指的是以程序為對象的靜態(tài)(如編譯時)預測技術,它們可用來預言程序運行時的動態(tài)布局或行為的一種安全(忠實于語義)且有效(所需時空少)的近似(因為一般而言不能期望精確的解答)。除了用于代碼優(yōu)化外,程序分析還用在程序理解、程序測試、程序安全性分析和程序重構等許多方面。

除了代碼優(yōu)化中提到的數(shù)據(jù)流分析外,常用的程序分析技術還有基于約束的分析、抽象解釋、類型和結(jié)果系統(tǒng)、符號執(zhí)行等。

國內(nèi)已經(jīng)有一些高校開設了專門的程序分析課程,相應教材(文獻[8])也已經(jīng)問世。

(4) 并行編譯理論和技術

并行編譯器是指處理并行編程語言或?qū)⒋芯幊陶Z言的程序并行化的編譯器。這樣的編譯器對程序員隱蔽了它發(fā)現(xiàn)程序并行性、把計算分布到多個處理器、極小化處理器之間的同步和通信的詳情。并行化技術已經(jīng)用于自動地把串行科學計算程序翻譯成多處理器代碼。

并行編譯中采用的主要技術是依賴性分析和循環(huán)并行化等。這些內(nèi)容已經(jīng)被寫入國內(nèi)個別編譯原理教材(文獻[9])中。

參考文獻:

[1]Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman. Compilers: principles, techniques, and tools[M]. New York: Addison- Wesley, 1986.

[2]Alfred V. Aho, Monica S. Lam, Ravi Sethi, Jeffrey D. Ullman. Compilers: principles, techniques, and tools[M]. 2nd edition. New York: Addison-Wesley, 2007.

[3]Andrew W. Appel. Modern compiler implementation in C[M]. Cambridge, England: Cambridge University Press, 1998.

[4] 張素琴,呂映芝,蔣維杜,等. 編譯原理[M]. 2版.北京:清華大學出版社,2005.

[5] 陳意云,張昱. 編譯原理[M]. 2版.北京:高等教育出版社,2008.

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

[7] 陳意云,張昱. 編譯原理習題精選與解析[M]. 北京:高等教育出版社,2005.

[8] 劉磊,張晶,單鄲,等. 程序分析技術[M]. 北京:機械工業(yè)出版社,2005.

[9] 陳火旺,劉春林,譚慶平,等. 程序設計語言編譯原理[M]. 3版.北京:電子工業(yè)出版社,2001.

Discuss on Teaching Content of Compiling Principles

ZHANG Yu, CHEN Yi-yun, Guo Yu, LI Zhao-peng

(School of Computer Science & Technology, University of Science & Technology of China, Hefei 230026,China)

Abstracts: By analysing the evolvement of foreign teaching materials on Compiling Principles and combining self- experience in teaching and scientific research, three levels of teaching goals on Compiling Principles are put forward, i.e. goals for undergraduates from common institutions of higher learning or from key institutions of higher learning, and goals for postgraduates. Moreover the teaching contents for those three levels are proposed for your information.

Key words: Compiling Principles; programming language; teaching goals; teaching content