以計算思維能力培養為導向的“編譯原理”教學改革探索

諶志群，王榮波，黃孝喜

（杭州電子科技大學 計算機學院，浙江 杭州 310018）

0 引言

“能力導向”是本科教育的基本追求，有利于培養學生的可持續發展能力。 “能力導向”教學與“知識導向”教學并不矛盾，兩者是相輔相成的關系：以知識為載體，通過對知識的學習，掌握恰當的問題求解思想和方法，培養學生的（專業）能力；能力的增強，反過來會促進學生學習、掌握甚至發現更多的知識。所以，先進的教育倡導研究型“教”與“學”，尊崇的是“能力導向”[1]。

計算思維能力是計算機類專業人才4 大專業基本能力之一 （另外3 個是算法設計與分析能力、程序設計與實現能力、系統能力）[2]。 計算思維是美國卡內基·梅隆大學計算機科學系主任周以真（Jeannette M. Wing）教授提出的。 2006 年 3 月，周教授在美國計算機權威期刊 《Communications of the ACM》上給出了計算思維（Computational Thinking）的定義：計算思維是運用計算機科學的基礎概念進行問題求解、系統設計以及人類行為理解等涵蓋計算機科學之廣度的一系列思維活動。

過去幾十年來，盡管我國在計算機專業教育上取得了很大的成績，培養出了數量眾多勝任工作的畢業生，計算思維的諸要素也或多或少滲透在培養方案和課程大綱中，但執行的情況還不夠理想[3]。不僅不同的學校在計算思維能力培養效果上差別大，而且計算思維能力培養的水平整體看還不夠高，學生對于計算思維要素掌握的程度還不夠深。 對此，我們需要更主動地采取有效措施， 從思想觀念、教學內容、教學方法等方面入手，進一步強化對學生開展計算思維能力的培養。

“編譯原理”作為計算機專業的核心基礎課程，它所涉及的大量知識都是計算思維的恰當詮釋和生動案例[4]。 將計算思維培養與“編譯原理”教學相結合，不僅可以從計算思維的角度重新審視和組織“編譯原理”的課堂教學，而且可以加強對學生計算思維能力的培養，使學生能夠更好地應用計算思維來解決實際問題。

1 教學改革思路與目標

計算的根本是抽象和自動化。用計算機解決問題，首先要對問題進行抽象和形式化描述，然后將問題求解方法算法化， 最后用編程語言實現算法。要有效解決問題，算法的復雜度還必須在可承受的范圍內[5]。 這是用計算思維解決實際問題的基本思路。 如何有效地將計算思維融入、滲透到課程的實際教學中，提高學生運用計算思維進行問題的抽象和分解能力，一直以來都是計算機教育界極為關心的熱點問題，也是一個巨大的挑戰。

“編譯原理”由于基礎概念繁雜、理論性內容比重大、抽象程度高等特點，被師生們普遍反映是一門難教又難學的課程。學生在學習過程中經常感到內容抽象、算法復雜、難于理解。 另外，學生普遍認為“編譯原理”不實用，導致缺乏學習熱情，失去積極性和主動性。如果從計算思維的角度來重新審視“編譯原理”這門課程，我們發現“編譯原理”是訓練學生計算思維、培養學生計算機專業素質、提高學生系統能力的良好載體。教師在教學過程中利用計算思維來重新梳理和組織“編譯原理”的教學內容，可以在一定程度上克服當前“編譯原理”教學中存在的問題，提高實際的“教”“學”水平。

以計算思維能力培養為導向，對“編譯原理”課程教學進行改革探索，可達到如下教學目標：

（1）培養學生對問題進行抽象的能力。 在計算機科學中，抽象化就是在解決問題時隱藏實現細節以減少問題的復雜度，使人們專注重要的、本質的部分來把握事物本質、發現事物的內在規律。

（2）培養學生對問題進行形式化描述的能力。形式化方法就是發現邏輯規律、 定義邏輯規則、完善理論體系，進而對問題進行數學建模的過程。

（3）培養學生設計算法求解實際問題的能力。設計復雜度合理的算法是解決實際問題的可行途徑， 算法設計是將計算思維的成果實物化的過程，也是將理論成果應用于具體技術的實踐過程。

（4）培養學生采用遞歸與迭代解決實際問題的能力。遞歸與迭代是解決復雜工程問題的強有力的方法。 遞歸與迭代在程序編譯過程中應用非常廣泛，通過對實際案例的剖析，可培養學生解決復雜問題的能力。

以計算思維能力培養為導向的 “編譯原理”教學改革實踐的基本流程如圖1 所示。

圖1 “編譯原理”教學改革實踐基本流程Figure 1 Basic process of teaching reform practice for “Compilation Principle”

2 教學改革方案分析與內容設計

2.1 “編譯原理”中的計算思維分析

計算思維中包含的計算特點是采用計算機科學的基本概念來求解問題、設計系統和理解人類行為，涵蓋了計算機科學一系列的思維方法。例如，經過數據仿真、嵌入實驗、等價轉化、合理約簡等步驟，把一個抽象復雜的問題解釋成簡單易懂、易解決的問題；通過分解和抽象解決復雜的任務；選擇恰當的表示方式表述問題或者對問題進行建模，進而把問題簡化處理；通過糾錯、冗余、容錯等方法預防、檢測或者以最差的情況恢復系統；在空間與時間、存儲容量與處理能力等方面進行平衡；進行遞歸轉化等。以上計算思維方法都可以在“編譯原理”的很多理論和相關技術中得以體現，并且很多編譯成果也利用了計算思維的核心。 例如，抽象和自動化就是編譯理論和方法產生的基礎；編譯中介紹的詞法、語法分析，屬性文法和優化等內容，都體現了從實際問題中抽象出共性，并且運用科學思維方法求解問題的思想。 其中，詞法分析主要涉及形式化、轉化、約簡的方法；語法分析主要涉及形式化、遞歸、分解的方法； 語義分析與中間代碼生成主要涉及形式化、嵌入、分解的方法；代碼優化主要涉及約簡、分解、仿真的方法；目標代碼生成主要涉及仿真、容錯的方法。 求解的成果建立在經典理論的基礎上，并應用到具體的實際問題中，進一步推動了編譯相關技術的進步。 因此，“編譯原理”課程處處滲透計算的特征，在理論和技術上都體現了計算思維。

2.2 教學改革方案中的內容設計

通過對“編譯原理”課程知識框架的梳理，可提取計算思維與課程內容之間的結合點，這些結合點可歸納為4 類，如圖2 所示。

圖2 計算思維能力培養與課程內容結合點Figure 2 Combination of computational thinking ability training and course content

（1）提取問題抽象化與課程內容的結合點。 編譯中的詞法分析、語法分析以及優化等都是首先進行抽象化的過程， 是通過發現不同分析方法的規律，然后進行數學建模，直至最后自動分析的過程。以詞法分析和語法分析為切入點，給出一個實際的小型語言系統的文法，通過課堂講解，讓學生建立起抽象符號與實際語義之間的聯系，反復強調兩者之間的對應關系， 最終使其專注于各種語法成分，把握分析對象的本質，忽略具體語言中各種語法成分的實現細節。

（2） 提取問題形式化描述與課程內容的結合點。編譯中的形式語言理論部分，關于文法、語言以及各種范式的定義， 都是基于形式化的描述方法。通過這部分內容的學習和練習，可以大大提升學生的形式化描述能力。這部分內容密切結合各種語法分析中使用到的算法， 以 LL （1） 文法為例，求FIRST、FOLLOW 集的算法是以形式化的方式來描述的，未掌握形式化語言和形式化思維的學生理解起來非常吃力，更不用談去實際應用。 在課堂講解的過程中，先讓學生接觸大量的實例，觀察FIRST、FOLLOW 集的構成， 引導學生總結各種符號的來源，最終靠自己的領悟形成對算法的形式化描述。通過這一方法， 學生可以領悟形式化思維和實際問題的聯系， 使形式化的思維真正被學生所接受和理解。

（3）提取算法設計及算法復雜度與課程內容的結合點。 編譯中自動生成工具LEX 和 YACC 的設計，就是在形式語言與自動機理論的前提下產生的高效詞法和語法自動產生器。算法及算法復雜度不僅體現在編譯程序本身的工作機制上， 更體現在編譯程序的生成工具的研究和設計上。

（4） 提取遞歸與迭代思想與課程內容的結合點。編譯中的自上而下語法分析中的遞歸下降分析程序、語法制導翻譯中的遞歸下降翻譯器的設計都是有關遞歸問題的典型代表。

算法設計部分、復雜度分析部分及遞歸迭代部分穿插在各算法的剖析中， 包括有限自動機的轉換、DFA 化簡、 遞歸下降語法分析方法、LR 語法分析算法、寄存器分配算法、代碼生成算法等。

在教學過程中，除了系統講授編譯過程中涉及的主要理論、技術和算法，可留出一部分時間穿插介紹涉及計算思維能力培養的相關內容，即跳出課程知識框架，從更高層次上審視編譯器的設計與實現，引導學生從中歸納總結通用問題求解的基本范式，以及在面對復雜工程問題時解決問題的基本思路與可行途徑。

3 教學改革實施與效果評價

以杭州電子科技大學計算機學院計算機科學與技術專業“編譯原理”教學為例。 課程組在2021學年第一學期期末考核時設計了一套計算思維能力試卷，并在泛雅網絡教學平臺上發布，要求選課學生完成。 試卷含3 種題型：判斷題、單選題、簡答題，各題型題量與內容見表1。

表1 計算思維能力考試題型與內容Table 1 Computational Thinking Ability Test Question Type and Content

考試共472 人參加，平均得分為76.9 分，成績分布如圖3 所示。這次考試的成績作為期末成績中課程思政得分的主要依據（占總成績的5%），學生們比較重視，促使他們在學習過程中除了對編譯課程具體知識點的掌握之外，也會同時思考編譯器設計與實現中涉及到的理論、技術遷移到其他應用領域的可能，在提高專業素養和計算思維能力的同時也提高了他們通用問題的求解能力。

圖3 計算思維能力考試成績分布Figure 3 Distribution of Computational Thinking Ability Test Scores

在2021 學年第一學期的“編譯原理”教學中，課程組兩位主講教師（A 教師、B 教師）采用新的教改方案，教學過程中注重強化對學生的計算思維能力的培養。另一位主講教師（C 教師）采用原有的教學模式。為客觀反映教改效果，比較了A 教師（4 個教學班）、B 教師（4 個教學班）與 C 教師（4 個教學班）之間客觀題的測試得分數據。 具體數據見表2。 從表 2 可以看出，A 和 B 兩位教師班級的得分率相對于C 教師來說有較大的優勢。 課程組將在今后的教學過程中，根據反饋不斷優化教改方案，如引入具體的工程案例，并從計算思維角度來剖析這些案例，將計算思維能力的培養落到實處。

表2 計算思維能力考試得分率比較Table 2 Scoring rate comparison of Computational Thinking Ability Test

4 結語

本文提出以計算思維能力培養為導向的“編譯原理”課程教學模式，圍繞編譯程序邏輯結構的各個部分，將計算思維的主要培養目標融合貫穿其中，有利于提高學生解決復雜工程問題的能力。 該教學模式將計算思維能力分解為問題抽象能力、問題形式化描述能力、算法設計能力、遞歸與迭代能力，并落實到“編譯原理”課程教學中，有利于提高學生的計算機專業素養和達成計算機專業對學生的能力培養目標。 提出的計算思維能力培養可推動學生從具備“實例計算（解決單一具體問題）”能力跨越到具備“類計算（完成一類問題系統求解）”能力，有利于培養學生的可持續發展能力。 教改方案實施后的評價結果初步展示了該教學模式的優越性。