宋麗華，張興元，王海濤

（1.陸軍工程大學 指揮控制工程學院，江蘇 南京 210007；2.南京審計大學金審學院 信息科學與工程學院，江蘇 南京 210023）

0 引 言

編譯原理主要介紹構造編譯器涉及的基本概念、理論和方法，是計算機專業(yè)核心課程。學習編譯的意義不僅在于學習編譯技術本身，使學生通過編譯過程深入了解計算機程序的行為，其更深遠的意義則在于培養(yǎng)“問題→形式化描述→計算機化”的問題求解習慣，培養(yǎng)將基礎理論和基本方法用于解決難度較大的問題、處理復雜軟件系統(tǒng)的設計與實現(xiàn)的能力[1-2]。

由于編譯原理課程固有的難度和實驗復雜度，部分高校要么不開設，要么實驗課時不足甚至不開實驗。從提高學生理論和實踐綜合能力的角度看這確是一個遺憾。國內(nèi)外一流高校通常將編譯原理作為必修課，配套大量實驗學時，考核上也更注重實踐，要求學生實現(xiàn)一個小型完整編譯器或關鍵組件，給學生提供充分訓練[3-6]。目前的編譯實驗基本上使用C、Java、Python 等命令式語言實現(xiàn)，導致一方面學生編程時需要采用復雜的內(nèi)部數(shù)據(jù)結構處理大量細節(jié)問題，另一方面最終呈現(xiàn)的代碼與算法理論描述在形式上有比較大的差別，學生很可能只見樹木（程序）不見森林（思想），最后結果往往是理論和實驗的彼此脫節(jié)。

1 函數(shù)式語言及其上面的單體編程技術

與廣為熟知的命令式語言（Imperative Language）相比，函數(shù)式語言（Functional Language）（如 ML、Ocaml、Haskell、Lisp）代表一種不同的程序設計“范型（paradigm）”。后者是人們對前者進行研究的過程中，為了準確而簡潔地表達程序的語義而提出的。函數(shù)式語言實質上是數(shù)學語言的子語言，其中的數(shù)據(jù)表示為數(shù)學表達式，程序表示為數(shù)學中的等式，計算則體現(xiàn)為用程序中的等式對數(shù)據(jù)進行化簡。對編程者來說，使用函數(shù)式語言編寫程序就像在做數(shù)學題，并且只需要列公式，結果將自動得出。

以ML 為例，函數(shù)式程序相比C 和Python更為簡潔，它屏蔽了指針、內(nèi)存分配等硬件相關的低層細節(jié)，程序代碼更接近于算法的抽象描述。此外，作為解釋型語言，ML 不需安排專門的打印語句即可自動顯示結果。

單體（Monad）是函數(shù)式程序設計中的一種“構件”技術，被稱為“可編程的分號”[7]。通過單體上的組合算子，小的計算步驟可以組合起來構成大的計算步驟，不斷積累構成最終的大程序[8]。

單體概念體現(xiàn)了函數(shù)式語言對“計算步驟”的刻畫，對“計算步驟”觀察角度不同產(chǎn)生了不同的單體定義，常見的有狀態(tài)單體、環(huán)境單體、異常處理單體、continuation 單體等。狀態(tài)單體將對狀態(tài)的修改看作“計算步驟”的副作用，通過Bind 算子把副作用按照計算步驟執(zhí)行順序從前往后傳遞。Bind 算子在隱式傳遞狀態(tài)的同時，還向后一個步驟傳遞前一個步驟的計算結果，這一巧妙設計帶來極大的靈活性，促使程序員在更高抽象層次思考問題，把注意力集中在各個計算步驟內(nèi)部，避免為中間結果、局部變量、接口之類的細節(jié)分神。

2 將函數(shù)式語言與單體用于編譯實驗的優(yōu)勢

與命令式語言相比，使用函數(shù)式語言和單體技術進行編譯實驗，不僅可以屏蔽繁雜的低層實現(xiàn)細節(jié)，在接近算法原理級別的抽象層次上編程，還可以在相當程度上減少實驗工作量、壓縮學時需求。實踐表明，大約可以在60～80 學時內(nèi)配合課程進度實現(xiàn)編譯全過程實驗，每個學生最終完成3 000 行左右ML 代碼，實現(xiàn)一個具備基本功能的完整編譯器。這對很多希望加強實驗環(huán)節(jié)但學時配置偏低的學校而言是一個可參考的解決方案。

1）提升編程效率，壓縮學時需求。

函數(shù)式語言將數(shù)據(jù)表示為數(shù)學表達式，其抽象級別的提高隱蔽了內(nèi)存分配和回收、指針運算等低層細節(jié)，顯著降低了出錯概率，節(jié)省程序調(diào)試時間。即使程序有錯，由于所有的數(shù)據(jù)都是具有直觀含義的數(shù)學表達式，且無需額外編程就可以顯示，查錯的工作量也大為減少。

2）算法和代碼之間有更明確的關聯(lián)映射關系，有助于學生緊密聯(lián)系理論和實踐。

命令式語言抽象級別低，程序中充斥大量與主體編程思想無關的低層操作細節(jié)，很容易將主體邏輯淹沒，難以看出原理和算法的脈絡，而函數(shù)式語言的抽象級別與各種形式化的定義和算法相同，用函數(shù)式語言和單體書寫的程序簡潔、可讀性很強，是這些定義和算法的嚴格形式化描述，但同時又是可以執(zhí)行的。這就使得學生可以方便地對算法進行實驗，通過反復的實驗深刻理解背后思想原理。不僅如此，免于繁瑣編程細節(jié)還意味著，學生可以專注于思考更為重要的問題，即怎樣利用基本原理去解決編譯各個階段所出現(xiàn)的各種復雜工程問題。只要想法足夠具體，就能很快實現(xiàn)為程序，用程序的執(zhí)行檢驗想法的可行性，想法中存在的偏差和漏洞也能及時暴漏出來。

3）支持師生對程序正確性進行討論，方便教師對學生代碼的檢查和提問。

為貼切地表示各個具體計算問題中的數(shù)據(jù)，程序員可以使用函數(shù)式語言特有的“數(shù)據(jù)類型”功能歸納定義新的數(shù)據(jù)類型，遞歸實現(xiàn)這些類型上的計算。編譯器構造過程中的抽象語法樹、中間代碼、機器指令等都可以表示為歸納定義數(shù)據(jù)類型，而語法分析、類型檢查、中間代碼生成、基本塊劃分、表達式化簡等模塊可實現(xiàn)這些數(shù)據(jù)類型上的遞歸程序。這就使得師生可以方便地使用歸納法對這些程序的正確性進行討論。由于程序足夠明晰簡潔，清晰地體現(xiàn)了算法脈絡，教師可以隨堂對學生代碼進行檢查和提問，確認學生對程序及其背后原理的掌握程度，及時發(fā)現(xiàn)其認知中的錯誤。這種檢查還能有效地抑制不良行為，不必單純依賴事后測試或是代碼克隆檢測[9-10]。

3 基于函數(shù)式語言和單體構建編譯實驗平臺對課程教學改革的要求

最重要的是教學模式的變化，可以改變傳統(tǒng)上理論和實驗分離的教學模式，采用以代碼為中心的授課模式：用函數(shù)式程序或者程序框架代替?zhèn)未a，課堂上圍繞代碼對算法進行討論，學生課后把代碼補全。相比偽代碼描述，代碼是嚴格的、實在的，教師可以當堂展示運行過程和結果，學生也可以反復觀察、修改、調(diào)試、運行，這就把理論教學和編程實踐無縫銜接起來。

采用以代碼為中心的教學模式，教學內(nèi)容設計與組織方面也要相應調(diào)整。內(nèi)容編排上應綜合考慮理論知識的前后銜接和代碼實現(xiàn)的完整性與獨立性。以每一周課時或每一小規(guī)模知識單元對應一個相對完整的程序模塊為宜，如線性化、基本塊劃分、算術指令化簡等，使學生及時消化知識并將之應用于實際問題求解。如果單元粒度過粗，或者理論授課與編程實踐脫節(jié)，都將影響教學實效。這種教學內(nèi)容編排無疑將使課程重心后移，因為中間代碼生成及后續(xù)各階段的編程工作量相對較大，而詞法和語法分析部分理論講解多?？紤]到詞法和語法分析技術已非常成熟，有自動生成工具，而自動機、文法等知識點與計算理論、形式語言和自動機等課程重疊，因此適當簡化這些內(nèi)容、突出后續(xù)各個階段也是合理之舉，畢竟后端仍然是編譯技術的研究熱點。

上述調(diào)整還會帶來考核方式的變化，不再“一卷定終身”，也不靠幾個大實驗拿分，而是將每一個小的知識單元和代碼模塊均納入評分依據(jù)，督促學生把功夫用在平時。對每一個小模塊，教師可以圍繞代碼檢查學生對知識的理解情況，結合代碼質量打分。由于程序足夠簡潔、貼近算法本身，這樣做并不會增加過多工作量。

4 基于新型實驗平臺的教學實踐

建設基于函數(shù)式語言和單體的全新實驗平臺，需要設計一組相互銜接、難度遞增的全過程實驗，并同步完成教學內(nèi)容、教學模式和考核方法的改革。

4.1 課程教學設計

課程共劃分20 個實驗內(nèi)容（見表 1），覆蓋編譯器構造全程，全部使用ML 和狀態(tài)單體實現(xiàn)。實驗1—16 為基本實驗，內(nèi)容相對簡單或提供代碼框架；實驗17—20 是高階實驗，難度和工作量均有明顯提升。全部代碼量（含提供的代碼）約為3 000 行。各模塊完成后將實現(xiàn)一個完整的命令式語言（不支持指針、數(shù)組等復雜數(shù)據(jù)結構）編譯器。

配合實驗，需要對教學內(nèi)容進行重新組織：從簡單的表達式語言開始，逐漸豐富語言功能，先介紹表達式語言的詞法、語法和語義分析，然后引入賦值、分支和循環(huán)結構，再介紹中間代碼生成、基本塊、寄存器分配等后端處理技術，最后引入函數(shù)和過程調(diào)用，介紹與其相關的語義分析和后端處理。與傳統(tǒng)教學內(nèi)容相比，對前端詞法和語法分析部分作了適當簡化，加強了后端，并引入了指稱語義、類型推導、錯誤定位、漂亮格式打印等內(nèi)容。

表1 教學內(nèi)容編排與實驗設計

課程采用以代碼為中心的授課模式，課堂在完成理論講解后即給出相關ML 類型定義和代碼框架，由學生在課后完成實驗內(nèi)容，不安排專門的實驗課時。課程成績以平時完成的實驗作為評定依據(jù)，通過平時隨機抽查、課終答辯等手段確保學生對原理和程序設計思想的掌握，同時抑制代碼克隆等不良行為。

4.2 實踐效果

在當前人才培養(yǎng)方案中，編譯原理課程為56 學時，開設時間是大三（上）學期。作為其預修課程，在大二（下）學期開設函數(shù)式程序設計（36 學時），教授ML 語言和單體編程技術。目前已經(jīng)完成的兩輪教學實踐取得了比較好的效果，學習積極性明顯提升，90%學生能完成基本實驗，約1/4 學生完成了高階實驗，獲得“頂峰體驗”。相對課內(nèi)時間，學生平均需要投入3 倍以上的課外時間用于消化學習內(nèi)容和編程，其編程能力比往屆學生有了明顯的、普遍的提高。優(yōu)秀學生感覺自己收獲很大、學得扎實，很多學生反映用ML 和單體編程比C 方便。

5 結 語

編譯原理介紹編譯器涉及的基本概念、理論和方法，使得學生深入了解計算機程序的行為，培養(yǎng)“問題、形式化描述、計算機化”的問題求解習慣和解決復雜工程問題的能力。課程難度大、實驗復雜耗時，而目前普遍采用的命令式語言實驗環(huán)境，更是加劇了這一傾向，將學生精力消耗在編程細節(jié)上，難以自覺建構理論和代碼之間的關聯(lián)，造成理論實踐脫節(jié)?；诤瘮?shù)式語言和單體編程技術的新型編譯實驗環(huán)境中，函數(shù)式語言抽象級別與數(shù)學語言接近，單體化函數(shù)式程序簡潔、清晰，與算法之間有清楚的對應關系，其屏蔽低層細節(jié)的特點還有助于提高編程效率，緩解學時壓力。采用新型實驗平臺在教學模式、教學內(nèi)容組織、考核方式等方面都將產(chǎn)生同步的改革需要。已在應用的以ML 語言和單體編程平臺為中心的改革方案，在過去兩年的教學實踐中取得了較好效果。