“編譯原理”教學實踐探究

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

關鍵詞：編譯原理；文法；有窮自動機；下推自動機；啟發(fā)教學；教學策略

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

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

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

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

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

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

從計算機應用的發(fā)展來看，編譯技術在其中發(fā)揮著極其重要且不可替代的作用。正是在編譯技術的支持下，程序設計才從以繁瑣的低級語言為工具，發(fā)展到以接近自然語言和數(shù)學語言的高級程序設計語言為工具，軟件開發(fā)也從模塊化的軟件開發(fā)方法發(fā)展到了面向對象的開發(fā)方法。編譯技術的發(fā)展極大地提高了軟件開發(fā)的效率，深刻地影響著軟件開發(fā)方法的變革，推動著計算機應用不斷地向社會的方方面面延伸。

編譯程序作為符號處理系統(tǒng)，廣泛應用到其他軟件的設計中。

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

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

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

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

3.啟發(fā)式教學的設計及實施

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

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

在計算機學科中，“編譯原理”是公認較難也是非常重要的一門專業(yè)課程。如形式語言、自動機理論、LR分析、語法制導翻譯等理論，內容相對抽象。但若方法應用得當，也會化難為易，使學生非常輕松地掌握看似艱澀的編譯原理和相關技術。

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

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

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

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

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

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

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

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

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

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

不論是用于“自上而下”分析的LL分析器，還是“自下而上”分析的LR分析器，都是下推自動機的特例，它們的不同之處在于：對棧的使用方式不同。因為一個是從文法的開始符號出發(fā)，一個是從給定的輸入串出發(fā)開始分析的。

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

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

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

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

4.結語

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

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

（見習編輯：劉麗麗）