王 挺 李夢君 周會平

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4結合編譯案例的計算思維培養(yǎng)

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

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

(1) 抽象

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

(2) 自動化

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

(3) 遞歸

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

(4) 問題分解

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

(5) 權衡

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

5結束語

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

參考文獻:

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

[2] 何炎祥,伍春香. 計算機專業(yè)不需要編譯原理課程嗎?[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.