對編譯原理課程教學中計算思維培養的探討

王 挺 李夢君 周會平

摘要:本文首先回顧了編譯知識在計算機學科中的地位和作用,分析了“編譯原理”課程在理論性和技術性上的特點,然后結合計算思維概念分析了計算思維在編譯理論和技術發展中的作用,并結合編譯課程教學中的知識點,探討了在教學中如何結合具體案例培養計算思維。

關鍵詞:編譯原理;計算思維;課程改革

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

1編譯知識在計算機學科中的作用

自從20世紀50年代中期誕生世界上第一個高級語言編譯器——Fortran語言編譯器以來,編譯技術不斷進步,已經成為計算機科學中發展最迅速、最成熟的一個重要分支。自1966年以來的所有55位圖靈獎獲獎者中,有近1/3的科學家是因為在程序設計語言和編譯方面的成就而獲得該項獎勵,可見程序設計語言和編譯的發展集中體現了計算機科學發展的重要成果與精華。計算機應用能發展到今天,編譯技術的發展有著極其重要的、不可替代的作用。

五十多年以來,隨著編譯技術的發展,有關編譯原理和技術的內容被逐步引入到了計算機專業本科教學中。從早期各階段ACM和IEEE的計算機專業教學計劃,到近年ACM和IEEE聯合制定的CC 2005,再到我國教育部高等學校計算機科學與技術教學指導委員會2006年編制的《高等學校計算機科學與技術專業發展戰略研究報告暨專業規范(試行)》,直至最新的ACM和IEEE聯合制定的CS2008,都把有關編譯原理和技術的知識作為重要教學內容列入。目前,我們編譯原理課程的教學內容覆蓋了CS2008體系中程序設計語言領域、算法和復雜性等領域的多個知識單元。

2編譯原理課程的理論性和技術性特點

編譯程序的構造原理和技術可以說是計算機科學技術中理論和實踐相結合的最好典范。在許多課程的教學中,經典理論和先進技術之間的聯系往往缺乏具體而形象的例證,而“編譯原理”課程在這方面具有得天獨厚的優勢。形式語言和自動機理論為編譯程序的設計提供了堅實的理論基礎,正是在科學理論的保證下,才形成了一系列先進的編譯程序設計方法和工具,使得編譯程序的構造具有很高的系統性和自動化程度。例如,正是有了有限自動機的經典理論,才有了LEX這樣的高度自動化的詞法分析器的自動產生器;正是有了Knuth提出的LR分析方法,才有了YACC這樣的高效的語法分析器產生器,將程序員從繁瑣的代碼編寫中解放出來。編譯課程的教學既要強調經典理論在計算機科學中的重要作用,又要注重介紹利用這些基礎理論來設計和構造編譯程序各模塊的先進方法及工具,可以具體形象地說明經典理論與先進技術的關系。理論和實踐相結合是“編譯原理”課程的鮮明特色。

“編譯原理”課程特別強調運用理論知識進行實踐的能力和素質,以突出計算機專業人才培養的特色。“編譯原理”是每個優秀的計算機專業人員必修的一門課程。通過編譯程序這一具體的案例,學生可以綜合理解和運用計算機的程序語言、操作系統和體系結構等各種軟硬件知識,形成計算機專業人才特有的系統的專業知識結構。在系統學習編譯的理論和技術的過程中,學生一方面對科學理論的基礎作用有了充分的認識,提高了學習經典理論的興趣,形成了較高的理論素養;另一方面,通過課程綜合性的實踐,分析或改進簡單或復雜、原型級或產品級的各種編譯程序或工具,也可以提高靈活運用理論知識、設計較大規模的軟件來解決實際問題的能力。在課程的學習和實踐中,學生可以深刻體會到理論學習的意義和動手實踐的樂趣。

有許多人認為,如果今后不從事編譯器的開發,編譯知識就顯得并不重要了——事實上并非如此。編譯課程鮮明的理論性和技術性特點,使得這些知識對于計算機專業人員來說具有重要作用,甚至可以說是計算機專業人才區別于一般計算機人員的重要知識結構。對于將來從事編譯系統設計工作的學生來說,編譯課程的學習當然可以使他們掌握和理解編譯系統的結構、工作流程以及編譯程序各組成部分的設計原理和實現技術,獲得分析、設計、實現和維護編譯系統的初步能力,打下堅實的能力和知識基礎;而對于那些將來不從事編譯器研制的學生來說,編譯課程的教學對于提高他們對計算機系統總體認識也具有重要的意義。通過學習編譯的理論和方法,學生可以提高對程序設計語言的設計與實現等知識的綜合理解,而這些知識對于準確掌握程序設計語言,學習新的編程范型,理解程序,開發出正確的軟件都是不可缺少的基礎。圖靈獎獲得者Perlis教授的名言“To understand a program you must become both the machine and the program”就精辟地說明了這一點。此外,編譯課程介紹的經典語言分析方法和工具,對于一些實用的工具和軟件,如自然語言理解、網絡信息處理、網絡協議的分析與實現等領域的軟件或工具的研制,都是很好的基礎。更為重要的是,編譯課程中介紹的一些經典的理論和方法,對于傳授計算機科學研究的方法、訓練學生的思維都是難得的生動案例。因此,不能把編譯課程片面地理解成為一個介紹編譯程序的課程,而應當把該課程的教學放在培養專業素質、訓練思維的層面加以認識,特別是應當強調如何在編譯的教學中培養學生的計算思維。

3計算思維及其在編譯理論和技術發展中的作用

計算思維(Computational Thinking)是卡內基梅隆大學計算機科學系Jeannette M. Wing教授在2006年提出來的先進的教育理念,被認為是近十年來產生的最具有基礎性、長期性的學術思想,并將成為21世紀計算機科學研究的熱點。

計算思維是運用計算機科學的基礎概念去求解問題、設計系統和理解人類的行為,它包括了一系列廣泛的計算機科學的思維方法。Wing教授認為,計算思維不僅僅屬于計算機科學家,它將和閱讀、寫作和算術一樣,是21世紀每個人必須具備的基本技能。計算思維已經在其他學科中產生影響,而這種影響在不斷拓展和深入。例如計算生物學、計算博弈理論、納米計算和量子計算等新興研究領域的發展正在深刻改變生物學、經濟學、化學和物理學領域研究的思考方式。

典型的計算思維包括一系列廣泛的計算機科學的思維方法:遞歸、抽象和分解、保護、冗余、容錯、糾錯和恢復,利用啟發式推理來尋求解答,在不確定情況下的規劃、學習和調度等。顯然,這些計算思維方法都可以在許多編譯理論和技術的發展中找到痕跡,很多編譯成果正是運用計算思維的結晶。例如,抽象和自動化是計算思維的兩個重要手段,也是編譯理論和方法產生的基礎。編譯課程中介紹的語法知識描述、詞法分析、語法分析、屬性文法、乃至優化等知識點,都體現了面向具體應用、從實際問題中抽象出科學問題并運用科學的思維方法進行問題求解的思想,其成果根植于堅實的經典理論,并應用于實踐,以推動技術的進步。因此,在編譯課程的教學中,結合編譯理論和技術中經典的案例培養學生的計算思維,是一條值得探索的途徑。

4結合編譯案例的計算思維培養

如何培養“計算思維”,是目前計算機教育界非常關心的問題。例如,在計算機專業的教學中,有些學校在專業核心課程中融入計算思維的培養;在非計算機專業的教學中,對計算機導論類或程序設計類的課程進行改革,針對學科交叉的需求,從教學內容和方法上進行改革,培養學生的計算思維。總體來說,計算思維的培養應該貫穿在大學教育的全過程,甚至在大學之前的教育中。計算思維對于計算機專業的人才培養提出了新的要求,我們必須在專業課程教學中結合計算思維的培養。

編譯課程的知識體系完整,既有經典理論成果奠定的堅實基礎,又有在實踐中發揮巨大作用的先進技術,其中很多知識點都為計算思維提供了很好的詮釋和生動的案例。下面,我們從抽象、自動化、遞歸、問題分解和權衡等典型計算思維方法出發,探討結合編譯案例培養計算思維的可能途徑。

(1) 抽象

“抽象”是科學研究的重要手段,也是計算機科學研究的重要工具。在編譯理論和技術的發展中,正是運用“抽象”這一有力工具,才獲得了一系列的重要成果。例如有限自動機、形式文法等都是重要的抽象工具,有了這些工具,才能夠把握詞法分析和語法分析等問題的本質,發現其中規律,最終形成一系列的自動分析方法。

(2) 自動化

將抽象思維的結果在計算機上實現,是一個將計算思維成果物化的過程,也是將理論成果應用于技術的實踐。有限自動機、預測分析程序、算符優先分析、LR分析等編譯經典方法,都是在抽象的基礎上將知識和控制分離(即分析表加控制程序),從而獲得了經典的分析工具,而這種知識和控制的分離也為分析工具的自動產生提供了可能。自動化的思維方法不僅體現在編譯程序本身的工作機制上,更體現在編譯程序的生成工具的研究和設計上。

(3) 遞歸

許多編譯中的問題都具有明顯的遞歸特征。運用遞歸思維解決復雜的問題,通常是對問題進行逐步化簡,最后得到了一個規模非常小、非常簡單、更容易解決的類似問題,將該問題解決后,再逐層解決上一級問題,最后解決了較復雜的原始問題。編譯中的遞歸下降分析是最直觀的對遞歸思維的運用,此外,基于樹遍歷的屬性計算、語法制導翻譯都是典型的遞歸問題求解。

(4) 問題分解

程序設計中的“自頂向下、逐步求精”的思想就是一種典型的問題分解的計算思維方法。運用問題分解這種思維方法進行問題求解,首先須做出對問題本身的明確描述,并對問題解法做出全局性決策,把問題分解成相對獨立的子問題,再以同樣的方式對每個子問題進一步精確化,直到獲得對問題的明確解答。在編譯程序的設計中,通過引入中間語言,將編譯程序劃分成前端和后端,就是一種典型的分解問題的思路。

(5) 權衡

“編譯原理”課程是一門理論性和技術性都非常強的課程。理論研究重在探尋問題求解的方法,而在編譯程序的設計和實現過程中,對于理論成果的研究運用又需要在能力和運用中做出權衡。這方面一個典型的例子是,我們知道,雖然高級語言的大部機制都可以由上下文無關文法來描述,但是上下文無關文法不能完全刻畫高級程序語言的所有規范,有些語言機制甚至存在二義性。但是上下文無關文法的分析是高效的,所以我們在編譯程序設計中依然采取上下文無關文法來描述高級語言語法,但是在具體實現時,通過改造分析表消除沖突、符號表操作、語義檢查等手段,去實現上下文無關文法分析所不能完成的功能——這正是在具體實踐中結合具體問題進行權衡的結果。

5結束語

計算思維的培養不是哪一門課程的教學能解決的問題。對于計算機專業教育來說,應當關注在各專業課程中的計算思維的培養,強調對各種原理和方法進行提煉,從思維方法的高度培養學生,使學生能夠應用計算思維解決問題。大學計算思維的教育應貫穿于整個大學教育,做到學習期間不斷線。

參考文獻:

[1] Jeannette M. Wing. Computational Thinking[J]. Communications of ACM, 2006,49(3):33-35.

[2] 何炎祥,伍春香. 計算機專業不需要編譯原理課程嗎?[J]. 計算機教育,2009(4):61-62,85.

[3] Alan J. Perlis. Epigram on Programming [J]. GPLAN Notices, 1982,17(9):7-13.

[4] Owen Astrachan, Susanne Hambrusch, Joan Peckham, et al. The Present and Future of Computational Thinking[C]. SIGCSE09, 2009,USA:549-550.