對(duì)編譯原理課程教學(xué)中計(jì)算思維培養(yǎng)的探討

王 挺 李夢(mèng)君 周會(huì)平

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

關(guān)鍵詞:編譯原理;計(jì)算思維;課程改革

中圖分類(lèi)號(hào):G642 文獻(xiàn)標(biāo)識(shí)碼:B

1編譯知識(shí)在計(jì)算機(jī)學(xué)科中的作用

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

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

2編譯原理課程的理論性和技術(shù)性特點(diǎn)

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

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

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

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

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

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

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

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

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

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

(1) 抽象

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

(2) 自動(dòng)化

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

(3) 遞歸

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

(4) 問(wèn)題分解

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

(5) 權(quán)衡

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

5結(jié)束語(yǔ)

計(jì)算思維的培養(yǎng)不是哪一門(mén)課程的教學(xué)能解決的問(wèn)題。對(duì)于計(jì)算機(jī)專(zhuān)業(yè)教育來(lái)說(shuō),應(yīng)當(dāng)關(guān)注在各專(zhuān)業(yè)課程中的計(jì)算思維的培養(yǎng),強(qiáng)調(diào)對(duì)各種原理和方法進(jìn)行提煉,從思維方法的高度培養(yǎng)學(xué)生,使學(xué)生能夠應(yīng)用計(jì)算思維解決問(wèn)題。大學(xué)計(jì)算思維的教育應(yīng)貫穿于整個(gè)大學(xué)教育,做到學(xué)習(xí)期間不斷線(xiàn)。

參考文獻(xiàn):

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

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