“編譯原理”教學(xué)實(shí)踐探究

摘要：教學(xué)需要“教”與“學(xué)”雙方的密切配合。樹(shù)立“學(xué)生為主體、教師為主導(dǎo)”的良好教學(xué)關(guān)系，是成功教學(xué)的關(guān)鍵。本文根據(jù)“編譯原理”課程的特點(diǎn)，提出應(yīng)用啟發(fā)式教學(xué)的思想，提高學(xué)生在學(xué)習(xí)中的主體地位，多方面增強(qiáng)學(xué)生的學(xué)習(xí)興趣。文章結(jié)合筆者17年的“編譯原理”課程教學(xué)實(shí)踐經(jīng)驗(yàn)，總結(jié)了開(kāi)展啟發(fā)教學(xué)、提高教學(xué)質(zhì)量的一些粗淺策略。

關(guān)鍵詞：編譯原理；文法；有窮自動(dòng)機(jī)；下推自動(dòng)機(jī)；啟發(fā)教學(xué)；教學(xué)策略

教書(shū)育人是教師的天職。教學(xué)，顧名思義，包含“教”和“學(xué)”兩個(gè)方面。教師需要“教”給學(xué)生知識(shí)和方法；而學(xué)生是學(xué)習(xí)的主體。我們要取得好的教學(xué)效果，首先要激發(fā)學(xué)生的學(xué)習(xí)興趣。

良好的開(kāi)端是成功的一半。開(kāi)課伊始就讓學(xué)生產(chǎn)生學(xué)習(xí)熱情、學(xué)習(xí)興趣是非常重要的。兩千多年前，孔子曾說(shuō)過(guò)：“知之者不如好之者，好之者不如樂(lè)之者。”意思是懂得它的人，不如愛(ài)好它的人；愛(ài)好它的人，又不如以它為樂(lè)的人。愛(ài)因斯坦也說(shuō)過(guò)：“興趣是最好的老師。”學(xué)生感興趣了，教學(xué)就成功了一大半。

1.“編譯原理”課程概述

“編譯原理”課程是計(jì)算機(jī)科學(xué)專(zhuān)業(yè)的一門(mén)重要核心課程。計(jì)算機(jī)語(yǔ)言之所以能由單一的機(jī)器語(yǔ)言發(fā)展到今天的數(shù)千種高級(jí)語(yǔ)言，是因?yàn)橛辛司幾g技術(shù)。自從20世紀(jì)50年代早期第一個(gè)編譯器出現(xiàn)以來(lái)，編譯技術(shù)成為計(jì)算機(jī)科學(xué)中發(fā)展最迅速、最成熟的重要分支。自1966年設(shè)立圖靈獎(jiǎng)以來(lái)，程序設(shè)計(jì)語(yǔ)言、編譯理論與方法方面的得獎(jiǎng)成果約占總數(shù)的1/3。可見(jiàn)，程序語(yǔ)言及其編譯的研究在計(jì)算機(jī)科學(xué)中始終處于非常重要的地位。

“編譯”是將高級(jí)語(yǔ)言描述的程序轉(zhuǎn)換成與之等價(jià)的低級(jí)語(yǔ)言表達(dá)的程序。在編譯系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)中，用到計(jì)算學(xué)科的很多基本原理、技術(shù)和方法。Alfred V Aho編寫(xiě)的編譯教材作為編譯課程方面的經(jīng)典教材，被奉為“龍書(shū)”。他在該書(shū)第一章的第一句話提到：“編寫(xiě)編譯器的原理和技術(shù)具有十分普遍的意義，以至于在每個(gè)計(jì)算機(jī)科學(xué)家的研究生涯中，本書(shū)中的原理和技術(shù)都會(huì)反復(fù)用到。”北京工業(yè)大學(xué)的蔣宗禮教授認(rèn)為，編譯課程是計(jì)算機(jī)專(zhuān)業(yè)最為恰當(dāng)、有效的知識(shí)載體之一。

2.“編譯原理”課程在整個(gè)課程體系中的地位和作用

從計(jì)算機(jī)應(yīng)用的發(fā)展來(lái)看，編譯技術(shù)在其中發(fā)揮著極其重要且不可替代的作用。正是在編譯技術(shù)的支持下，程序設(shè)計(jì)才從以繁瑣的低級(jí)語(yǔ)言為工具，發(fā)展到以接近自然語(yǔ)言和數(shù)學(xué)語(yǔ)言的高級(jí)程序設(shè)計(jì)語(yǔ)言為工具，軟件開(kāi)發(fā)也從模塊化的軟件開(kāi)發(fā)方法發(fā)展到了面向?qū)ο蟮拈_(kāi)發(fā)方法。編譯技術(shù)的發(fā)展極大地提高了軟件開(kāi)發(fā)的效率，深刻地影響著軟件開(kāi)發(fā)方法的變革，推動(dòng)著計(jì)算機(jī)應(yīng)用不斷地向社會(huì)的方方面面延伸。

編譯程序作為符號(hào)處理系統(tǒng)，廣泛應(yīng)用到其他軟件的設(shè)計(jì)中。

例如，編譯在反病毒中的應(yīng)用：對(duì)于高級(jí)文本語(yǔ)言類(lèi)的文件（如網(wǎng)頁(yè)類(lèi)文件），應(yīng)用編譯技術(shù)的詞法分析和語(yǔ)法分析原理，可準(zhǔn)確快速地定位病毒代碼，從而構(gòu)造反病毒程序。編譯在機(jī)器翻譯系統(tǒng)和文本分類(lèi)中的應(yīng)用：機(jī)器翻譯系統(tǒng)又稱為語(yǔ)言翻譯系統(tǒng)，輸入是一種語(yǔ)言，輸出是功能上等價(jià)的另外一種語(yǔ)言。例如，中文和日文的相互翻譯。文本分類(lèi)是把互聯(lián)網(wǎng)上的海量信息進(jìn)行分類(lèi)，便于閱讀。它們都離不開(kāi)編譯中的詞法分析和語(yǔ)法分析技術(shù)。

“編譯原理”課程含有基本問(wèn)題求解的典型思路和方法，通過(guò)本課程的學(xué)習(xí)，使學(xué)生容易理解和掌握“問(wèn)題、形式化描述、自動(dòng)化（計(jì)算機(jī)化）”的解題思路，培養(yǎng)學(xué)生的形式化描述和抽象思維能力。繼程序設(shè)計(jì)、數(shù)據(jù)結(jié)構(gòu)與算法等課程后，該課程使學(xué)生從系統(tǒng)層面上對(duì)算法和程序進(jìn)行再認(rèn)識(shí)，提高學(xué)生對(duì)“程序設(shè)計(jì)語(yǔ)言”、“操作系統(tǒng)”、“計(jì)算機(jī)原理和體系結(jié)構(gòu)”等課程知識(shí)的綜合理解。

該課程理論的學(xué)習(xí)不應(yīng)僅局限在構(gòu)造高級(jí)程序設(shè)計(jì)語(yǔ)言編譯器方面，還應(yīng)把教學(xué)的重點(diǎn)放在培養(yǎng)專(zhuān)業(yè)素質(zhì)、訓(xùn)練抽象思維的層面上。在編譯課程的教學(xué)中，結(jié)合編譯理論和技術(shù)中的經(jīng)典案例，培養(yǎng)學(xué)生的計(jì)算思維。

例如，抽象計(jì)算思維方法運(yùn)用自動(dòng)機(jī)和形式語(yǔ)言文法的形式化工具，把詞法分析和語(yǔ)法分析問(wèn)題的本質(zhì)抽象出來(lái)，從而可以發(fā)現(xiàn)解決該問(wèn)題的自動(dòng)化方法。自動(dòng)化計(jì)算思維方法在計(jì)算機(jī)上實(shí)現(xiàn)抽象的結(jié)果，詞法分析環(huán)節(jié)的有窮狀態(tài)自動(dòng)機(jī)、語(yǔ)法分析環(huán)節(jié)的LR分析法都是經(jīng)典的編譯方法，它們是在抽象的基礎(chǔ)上對(duì)分析表進(jìn)行處理的算法。編譯器的自動(dòng)生成工具的設(shè)計(jì)正是體現(xiàn)了自動(dòng)化的思維方法。

3.啟發(fā)式教學(xué)的設(shè)計(jì)及實(shí)施

師者，傳道授業(yè)解惑也。“傳道”就是體會(huì)學(xué)生在想什么，能夠啟發(fā)、引誘學(xué)生提高興趣；“解惑”并非簡(jiǎn)單地解答疑惑，好老師會(huì)幫助學(xué)生知道什么是“惑”，引導(dǎo)學(xué)生一步步地去探究，真正調(diào)動(dòng)學(xué)生的學(xué)習(xí)興趣，發(fā)揮個(gè)人的潛能，從而達(dá)到“解惑”的目的。

愛(ài)因斯坦曾經(jīng)說(shuō)過(guò)，一個(gè)人的成功不是解決問(wèn)題，最重要的是提出問(wèn)題。教師是教學(xué)的組織者和實(shí)施者，如何激勵(lì)學(xué)生的學(xué)習(xí)積極性、幫助學(xué)生積極地獲取知識(shí)和技能，使學(xué)生獲得綜合運(yùn)用知識(shí)能力等，這些對(duì)教師來(lái)說(shuō)更具挑戰(zhàn)性。

在計(jì)算機(jī)學(xué)科中，“編譯原理”是公認(rèn)較難也是非常重要的一門(mén)專(zhuān)業(yè)課程。如形式語(yǔ)言、自動(dòng)機(jī)理論、LR分析、語(yǔ)法制導(dǎo)翻譯等理論，內(nèi)容相對(duì)抽象。但若方法應(yīng)用得當(dāng)，也會(huì)化難為易，使學(xué)生非常輕松地掌握看似艱澀的編譯原理和相關(guān)技術(shù)。

在教學(xué)中，教師要以人為本，把學(xué)生的潛能挖掘出來(lái)，同時(shí)培養(yǎng)學(xué)生還要因材施教，根據(jù)學(xué)生的能力給予不同的指導(dǎo)方式，充分發(fā)揮學(xué)生的潛力，這樣才能使學(xué)生很快成長(zhǎng)起來(lái)。

課堂教學(xué)是實(shí)現(xiàn)素質(zhì)教育的主渠道。筆者在長(zhǎng)期的教學(xué)實(shí)踐中，習(xí)慣了從學(xué)生的角度出發(fā)，換位思考，回想自己學(xué)習(xí)新知識(shí)的困惑，設(shè)想學(xué)生初次接觸編譯這門(mén)課程，會(huì)有什么疑問(wèn)，又會(huì)對(duì)什么特別感興趣？如果一開(kāi)始，就能從學(xué)生的關(guān)注點(diǎn)出發(fā)，一步步引領(lǐng)他們解開(kāi)心中的疑惑，樹(shù)立起學(xué)習(xí)的信心，而不是一味地照本宣科，讓學(xué)生興趣寡然，則后面的教學(xué)過(guò)程可能就是柳暗花明，得到事半功倍的效果。

開(kāi)學(xué)第一課是至關(guān)重要的。學(xué)生借此認(rèn)識(shí)教師并了解這門(mén)課程。教師通常在第一課上要概括介紹學(xué)習(xí)“編譯原理”的目的，編譯是“干什么用的？”“編譯”就是將各種高級(jí)程序設(shè)計(jì)語(yǔ)言書(shū)寫(xiě)的源程序翻譯成等價(jià)的目標(biāo)程序（低級(jí)語(yǔ)言）的過(guò)程，因此編譯程序就是一個(gè)語(yǔ)言轉(zhuǎn)換器。換言之，有了編譯程序，計(jì)算機(jī)就能“讀懂”用戶書(shū)寫(xiě)的高級(jí)語(yǔ)言程序。實(shí)際上，編譯程序充當(dāng)了一個(gè)“翻譯者”的角色，在人和計(jì)算機(jī)之間架起了一座橋梁。有了編譯器，用戶不必關(guān)心或掌握計(jì)算機(jī)內(nèi)部的繁瑣細(xì)節(jié)（如指令系統(tǒng)、機(jī)器代碼），只需要掌握某種高級(jí)語(yǔ)言（如C語(yǔ)言），就可以給計(jì)算機(jī)下達(dá)指令，讓它為自己服務(wù)。

接著，教師可以引導(dǎo)學(xué)生思考。既然編譯程序完成的是程序設(shè)計(jì)語(yǔ)言的翻譯工作，那么它和我們生活中的哪些常識(shí)有共通之處呢？學(xué)生當(dāng)然接觸過(guò)自然語(yǔ)言的翻譯，會(huì)聯(lián)想到英漢對(duì)譯。英譯漢通常需要幾個(gè)過(guò)程：識(shí)別單詞、語(yǔ)法分析、理解含義、寫(xiě)出譯文。與此類(lèi)似，編譯程序也要經(jīng)過(guò)詞法分析（識(shí)別單詞）、語(yǔ)法分析、語(yǔ)義分析（理解含義）、目標(biāo)代碼生成，才能最終將源語(yǔ)言（source Language，SL）程序翻譯成等價(jià)的目標(biāo)語(yǔ)言（Object Language，OL）程序。此時(shí)，教師可以自然地引入編譯程序的“T”型圖描述，它非常形象地反映了編譯程序的三個(gè)要素：源語(yǔ)言、目標(biāo)語(yǔ)言、書(shū)寫(xiě)編譯程序的語(yǔ)言。

既然編譯程序要分析源語(yǔ)言，自然要了解語(yǔ)言的定義機(jī)制，從而自然地進(jìn)入到文法的學(xué)習(xí)。文法是語(yǔ)言的定義裝置，它可以用有窮的規(guī)則定義無(wú)窮的語(yǔ)言（使用遞歸規(guī)則就可定義無(wú)窮語(yǔ)言）。這時(shí)我們可以讓學(xué)生瀏覽“編譯原理”教材的目錄，讓學(xué)生發(fā)現(xiàn)全書(shū)實(shí)際上是按照編譯程序的實(shí)現(xiàn)步驟設(shè)立所有章節(jié)的。首先是概述（了解編譯的整體過(guò)程），接著介紹文法和語(yǔ)言（了解源程序是如何定義的），然后依次闡述編譯的各個(gè)階段：詞法分析、語(yǔ)法分析、語(yǔ)義分析和中間代碼生成、代碼優(yōu)化、目標(biāo)代碼生成。編譯原理的學(xué)習(xí)過(guò)程中，會(huì)涉及許多看似抽象的概念和原理，其實(shí)，都是為“一個(gè)中心”（實(shí)現(xiàn)翻譯）服務(wù)的。

在編譯的學(xué)習(xí)過(guò)程中，引導(dǎo)學(xué)生把自己想象成設(shè)計(jì)者。例如學(xué)習(xí)詞法分析時(shí)，怎樣完成單詞的識(shí)別？學(xué)生們經(jīng)過(guò)思考后，會(huì)按照從左向右的掃描順序，一一解讀每個(gè)字符；如何分辨出不同的單詞符號(hào)？尋找規(guī)律，發(fā)現(xiàn)不同單詞，其開(kāi)始符號(hào)各不相同；因此，按照開(kāi)始符的不同，識(shí)別不同單詞，拼寫(xiě)單詞直到遇到非法符號(hào)即可終止。至此，引入有窮自動(dòng)機(jī)（Finite Automata，F(xiàn)A）的定義，即詞法分析程序的數(shù)學(xué)模型，并畫(huà)出FA的狀態(tài)轉(zhuǎn)換圖：一種非常直觀的表達(dá)方式。學(xué)生們由于參與了這一過(guò)程，會(huì)感到興趣盎然，很有成就感。與此同時(shí)，我們可以給出現(xiàn)實(shí)生活中的實(shí)例，如一個(gè)人帶著一頭狼、一棵白菜和一只山羊過(guò)橋，要求每次人只能帶一樣?xùn)|西，如何保證在羊不被狼吃掉，而且白菜也不被羊吃掉的前提下全部過(guò)橋呢。拋出這個(gè)問(wèn)題，讓學(xué)生們?cè)噲D應(yīng)用有窮自動(dòng)機(jī)來(lái)解決這一問(wèn)題。模擬這一問(wèn)題實(shí)現(xiàn)的有窮自動(dòng)機(jī)如圖1所示。（注：m代表人；g代表山羊；w代表狼；c代表白菜。）

進(jìn)一步引申，我們發(fā)現(xiàn)有窮自動(dòng)機(jī)更是實(shí)時(shí)系統(tǒng)的一般建模工具，可以解決大量實(shí)際問(wèn)題。所以，構(gòu)造詞法分析程序僅僅是有窮自動(dòng)機(jī)的一個(gè)應(yīng)用。掌握有窮自動(dòng)機(jī)這種形式化描述工具，對(duì)于計(jì)算機(jī)學(xué)科的學(xué)生來(lái)說(shuō)具有極其重要的意義，它可以提高學(xué)生計(jì)算思維的能力，讓學(xué)生了解計(jì)算機(jī)解決問(wèn)題的思路。

語(yǔ)法分析的學(xué)習(xí)也是難點(diǎn)。難點(diǎn)知識(shí)在高校計(jì)算機(jī)教育中，不僅對(duì)于學(xué)生是學(xué)習(xí)難點(diǎn)，對(duì)于教師也是講授難點(diǎn)。教師應(yīng)該對(duì)知識(shí)點(diǎn)特別熟悉，并能和相關(guān)應(yīng)用案例聯(lián)系起來(lái)。首先應(yīng)該了解它與詞法分析有何不同，為何不能延用有窮自動(dòng)機(jī)來(lái)分析，而必須采用新的分析方法和技術(shù)。由于編程語(yǔ)言的嵌套性質(zhì)，使得編程語(yǔ)言的語(yǔ)法描述通常要采用上下文無(wú)關(guān)文法（ComeXt Free Grammar，CFG），如描述左右括號(hào)配對(duì)的情形，用如下文法來(lái)描述。

G[S]：S→SSI（S）|ε

這類(lèi)文法描述的是2型語(yǔ)言，而有窮自動(dòng)機(jī)僅能分析3型語(yǔ)言，即線性（一般為右線性）語(yǔ)言，沒(méi)有記憶功能，即無(wú)法記住前面讀了多少個(gè)“（”，當(dāng)然也無(wú)法確定“（”與“）”是否匹配。教師可以提示學(xué)生：學(xué)過(guò)的何種數(shù)據(jù)結(jié)構(gòu)具有記憶功能呢？有人可能會(huì)想起棧，其“后進(jìn)先出”的特性使其具有一定的“記憶”能力。因此，語(yǔ)法分析的數(shù)學(xué)模型就是帶有下推棧的有窮自動(dòng)機(jī)，即下推自動(dòng)機(jī)（Push Down Automata，PDA）。因此，下推自動(dòng)機(jī)的引入，也是出于語(yǔ)法分析的需求，這是由于上下文無(wú)關(guān)文法CFG具有有別于3型文法的一個(gè)本質(zhì)特征：自嵌入特性。

不論是用于“自上而下”分析的LL分析器，還是“自下而上”分析的LR分析器，都是下推自動(dòng)機(jī)的特例，它們的不同之處在于：對(duì)棧的使用方式不同。因?yàn)橐粋€(gè)是從文法的開(kāi)始符號(hào)出發(fā)，一個(gè)是從給定的輸入串出發(fā)開(kāi)始分析的。

自動(dòng)機(jī)理論可以用來(lái)描述系統(tǒng)行為。如：有窮自動(dòng)機(jī)FA可以描述如（abc）*的語(yǔ)言。（abc）*的FA表示如圖2所示。相應(yīng)地，F(xiàn)A可用于刻畫(huà)并發(fā)系統(tǒng)，在一個(gè)時(shí)間段內(nèi)執(zhí)行一系列操作，這些操作之間滿足一定的先后順序。

下推自動(dòng)機(jī)PDA可以描述如anbn（n∈N）語(yǔ)言。相應(yīng)地，PDA可刻畫(huà)這樣的系統(tǒng)：在一個(gè)時(shí)間段內(nèi)執(zhí)行一系列操作，這些操作之間不但滿足一定的先后順序，而且某兩個(gè)不同操作的數(shù)量之間有匹配關(guān)系。PDA可看成帶有下推棧的FA，但是不能用FA的狀態(tài)轉(zhuǎn)換圖表示。

語(yǔ)法分析后，要完成語(yǔ)義分析。語(yǔ)義分析主要完成程序設(shè)計(jì)語(yǔ)言中上下文相關(guān)（敏感）成分的分析。如類(lèi)型檢查，標(biāo)識(shí)符需要先定義再使用，函數(shù)的形參個(gè)數(shù)和實(shí)參個(gè)數(shù)應(yīng)該一致等。學(xué)生很容易理解這些要求，雖然這些要求本來(lái)都是語(yǔ)法規(guī)定，但由于無(wú)法用上下文無(wú)關(guān)文法CFG來(lái)描述，才將它們納入語(yǔ)義分析范疇。我們可借助符號(hào)表，采用語(yǔ)法制導(dǎo)翻譯，完成語(yǔ)義分析和中間代碼的生成。

只有清楚地認(rèn)識(shí)編譯程序各階段的任務(wù)，學(xué)生才能在學(xué)習(xí)中保持濃厚的興趣，積極思考解決問(wèn)題的方法。如在語(yǔ)法分析中，有了自己的深入思考、探究后，學(xué)生對(duì)自上而下的LL分析方法以及自下而上的LR分析方法的提出，就會(huì)有更深刻的體會(huì)。課堂上先給出一定時(shí)間思考，怎么來(lái)分析？如果是自己來(lái)構(gòu)造會(huì)怎么做？還差哪些條件？這樣，有了主動(dòng)的思考，工具的提出也順理成章，而不是生硬地拋出一個(gè)個(gè)抽象的原理和概念。

4.結(jié)語(yǔ)

啟發(fā)式教學(xué)是充分調(diào)動(dòng)學(xué)生學(xué)習(xí)興趣、學(xué)習(xí)潛能和學(xué)習(xí)積極性的一種重要教學(xué)方式。文章根據(jù)筆者十余年的“編譯原理”教學(xué)實(shí)踐及體會(huì)，提出實(shí)施啟發(fā)式教學(xué)的一種有益嘗試，即抓住主要脈絡(luò)（一條主線），順藤摸瓜，將編譯的所有概念、原理、技術(shù)和方法都串在這條線上。學(xué)到哪兒，首先抓住當(dāng)前要解決的問(wèn)題，然后找方法，最后在實(shí)踐中（課程設(shè)計(jì)）加以應(yīng)用。所有學(xué)習(xí)的內(nèi)容，都是圍繞著編譯程序的翻譯工作這樣一個(gè)中心任務(wù)，來(lái)分析應(yīng)該使用哪些工具才能完成相應(yīng)的詞法分析（有窮自動(dòng)機(jī)）、語(yǔ)法分析（下推自動(dòng)機(jī)）、語(yǔ)義分析和目標(biāo)代碼生成。這樣，學(xué)生在學(xué)習(xí)過(guò)程中思維清楚、目的性強(qiáng)，容易產(chǎn)生興奮點(diǎn)，自主學(xué)習(xí)的效果非常好。

“教”與“學(xué)”需要雙方密切配合。教師應(yīng)該關(guān)注“教什么”和“怎么教”，即關(guān)注課程的基本內(nèi)容、重點(diǎn)、難點(diǎn)是什么，將培養(yǎng)學(xué)生什么樣的能力，用哪種教學(xué)手段教學(xué)比較恰當(dāng)。在課堂教學(xué)中，以學(xué)生為主體、教師為主導(dǎo)，教師和學(xué)生建立良好的教學(xué)關(guān)系，師生互動(dòng)，教學(xué)相長(zhǎng)，不但給學(xué)生提供更多有益的指導(dǎo)，也促進(jìn)了教師自身素質(zhì)的提高。教師還應(yīng)及時(shí)把握本學(xué)科的最新發(fā)展動(dòng)向，更好地服務(wù)于教學(xué)。

（見(jiàn)習(xí)編輯：劉麗麗）