趙銀亮，戴慧珺，李 昊，李 波

（西安交通大學 電子與信息工程學院，陜西 西安 710049）

1 背 景

編譯原理課程由來已久，至今仍然是計算機專業(yè)主干課程。筆者經過長期的教學實踐，觀察到與本課程有關的教學問題，概括為以下四個。

問題一：現有的編譯原理課程在內容上存在理論完整性不足，使學生產生“知其然不知其所以然”的困惑。編譯原理課程中介紹程序分析變換和優(yōu)化技術的部分，涉及程序語言理論和大量具體方法，從教學方法上有強調理論性和強調技術實現兩個極端[1]。為了降低課程難度，授課教師一般直接使用形式語言理論的相關結論來解決詞法和語法分析問題，課程并不覆蓋形式語言理論，結果造成課程所包含的理論內容不夠完整。

問題二：對于編譯原理課程在課程體系中的地位存在著不同觀點，讓課程體系設計者陷入決策困境。這里羅列一些觀點：編譯原理是最有價值的課程之一[2]，課程太抽象、難度太大[3]，對開設該課程的必要性存在質疑[4-5]，該課程是其他課程的綜合練習[2]，等。這些觀點導致編譯原理課程的開設與不開設都在兩可之間，且實際情況也是如此。

問題三：編譯原理課程雖然屬于計算機科學基礎理論范疇，但一般沒有在大學前兩個學年的課程中出現，影響了計算機專業(yè)學生對于基礎理論的掌握。通常認為，大學前兩年是基礎理論學習和綜合素質培養(yǎng)階段，如西安交通大學的“2+4+X”模式等。在課程體系設計中，前兩年的候選課程很多，但沒有編譯原理課程，導致計算機專業(yè)學生基礎理論的掌握減弱，不利于后續(xù)專業(yè)課程的學習和能力培養(yǎng)。

問題四：在學科快速發(fā)展和課程學時數被壓縮這一背景下，與其他課程內容重疊問題變得日益明顯。目前，計算機學科知識構成呈現多樣化趨勢，這就要求許多新的課程加入到課程體系中來，必然造成已有課程總學時數呈現下降趨勢。III型和II型語言理論作為編譯原理課程與形式語言與自動機課程的共同相關部分，自然面臨合并和優(yōu)化設計問題。

2 對存在問題的分析與求解

2.1 課程的理論完整性

現有編譯原理課程的理論完整性不足表現在幾個方面：①在詞法分析器設計中使用了有限狀態(tài)自動機，但沒有完整包括正則語言的判定性理論；②介紹的語法分析框架，沒有明確給出理論依據；③語義分析使用的是語法制導翻譯方法，僅在方法學上將屬性文法與分析框架進行了集成；④基于工具自動生成詞法與語法分析器，沒有生成原理的介紹；⑤選擇性介紹類型檢查、類型推理的具體實現，沒有類型理論的系統介紹；⑥介紹運行環(huán)境的實現，沒有介紹程序語義支持。

為了有助于學生融會貫通課程知識，在課程中闡明理論依據是必要的。解決的方法是完整引入相應理論，并將原有內容與這些理論結合起來。此外，由于課時的限制和降低課程難度的要求，謹慎選擇較復雜的理論（如類型理論和語義學等），轉而求助于課程體系層面的解決方法。

2.2 課程定位與作用

引起課程定位與作用模糊問題是有客觀原因的：一方面，經過計算機系統的早期發(fā)展，編譯器技術已經相對成熟穩(wěn)定，盡管隨著體系結構演變也在緩慢發(fā)展，但與計算機技術整體快速發(fā)展相比，可以認為處于相對停滯狀態(tài)，因而直接相關的工作崗位需求也少；另一方面，幾乎所有軟件和計算系統都由程序構成，程序決定計算機應用的幾乎所有方面，所以，編譯原理課程所介紹的程序分析變換和優(yōu)化是計算機科學與技術的基礎。此外，編譯技術還是軟硬件協同設計的組成部分，也是計算機系統發(fā)展的支撐技術，其重要意義不言而喻。另外，從人才培養(yǎng)模式的角度也能找到存在這種問題的原因。一般觀點認為大學“2+2”模式分別注重基礎培養(yǎng)和專業(yè)培養(yǎng)，但編譯原理課程一般在大三開設，因而不能歸為基礎理論環(huán)節(jié)，從而錯過對學生進行相關抽象思維能力培養(yǎng)的最佳時間節(jié)點。

綜上分析，可以使用如下判據解決問題：①課程的類型歸屬：強調理論性的課程還是技術基礎課程？②課程內容選擇范圍：作為系統軟件關注設計方法還是軟硬件實現細節(jié)？③本課程對于專業(yè)課程的作用：作為理論基礎課程還是專業(yè)技術課程？④課程的難易程度：偏重抽象的形式化描述還是實現細節(jié)？⑤與其他課程的關系：是獨立的有內涵的課程還是其它課程的綜合練習？

事實上，對這些判據的不同回答就構成了各自特色的編譯原理課程，本文的形式語言與編譯課程在構建過程中選擇每個判據中的第一個選項，由此明晰了課程定位和作用。

2.3 課程內容重疊

編譯原理課程與形式語言理論、語言范型和類型系統等先修課程發(fā)生重疊，前者涉及該課程核心，后者是編譯需求。編譯原理課程也與系統類課程發(fā)生重疊，如指令系統、程序映像、優(yōu)化技術等，屬于技術細節(jié)層面重疊。

為了消除與其他課程重疊，可采用多種方法：第一種是課程體系設計層面的解決方法，結合課程進度和側重點，分別落實客觀的重疊知識點，分配給相應課程，這種方法對解決課程群間的內容重疊有效，比如采用課程之間互相兼顧、優(yōu)化系統類課程群等方法。第二種方法是避免重復先修課程的內容，該方法適用于解決人為造成的與離散數學和數據結構課程的重疊，比如不要試圖將編譯原理課程設計為先修課程的綜合練習。最后一類方法是將其他課程內容合并到本課程中，該方法適用于消除和形式語言與自動機、程序設計等課程的重疊，該方法的副作用是容易導致課程名稱和內涵發(fā)生重構。

運用以上三種消除重疊的方法，編譯原理課程內容的合理性得到優(yōu)化，優(yōu)化后的內容涵蓋了完整的形式語言理論，所以其名稱也必將發(fā)生變更，形成了形式語言與編譯課程，就是本文標題所指?？紤]到程序設計語言也是形式語言，將原有的程序設計語言的編譯原理課程改名為形式語言與編譯課程并不會破壞一致性，反而更有普遍適用性。

3 課程內容與教學過程設計

課程內容與教學過程設計本著簡單的設計原則：控制課程難度，將原理與實現分開，由課時數限定理論內容的選擇。課程內容選擇如圖1所示。

在圖1中，形式語言與編譯課程的內容一部分取自形式語言與自動機課程，另一部分為重新設計的編譯原理課程的詞法分析、語法分析和語義分析部分，所形成的形式語言與編譯課程可以看作是對原有兩門課程的合并。

形式語言與自動機課程中余下的內容屬于計算導論中的高級內容，必要時可以作為高年級選修課程獨立設課；編譯原理課程中的代碼優(yōu)化和代碼生成也是專業(yè)重要內容，也可以作為選修課單獨設課或編譯原理高級專題講座內容。

圖1 課程設計方案

這個設計方案突出了課程的理論性，另外從專業(yè)技術內容角度考慮，編譯原理核心部分中的編譯器設計與實現仍然作為實驗教學單獨設課，即編譯器設計專題實驗課程，以此訓練學生閱讀編譯源代碼并進行詞法分析、語法分析、語義分析和代碼生成方面的動手能力，達到對編譯器技術層面的掌握。

3.1 形式語言與編譯課程的內容設計

1）完整引入III型和II型語言理論。

III型語言理論包括DFA、NFA、ε-NFA、GNFA、r、文法、正則語言、等價性；II型語言理論包括CFG、推導、歸約、語法樹、PDA、PDA與CFG等價性、CFL性質、范式等。這部分內容移自形式語言與自動機課程。

2）更新詞法分析。

利用正則語言判定性從輸入流中識別單詞符號，只需很少保留編譯原理的詞法分析內容。更新后的內容包括詞法分析器框架、單詞符號設計、多DFA集成設計、詞法分析器自動生成等。

從源程序中識別詞法單位的方法涉及一個通用的框架（見圖2），圖2中的判定框是框架的核心，用形式語言的方法決定輸入串所屬的詞法單位。圖中附加處理框表示對接受的輸入串進行額外處理，包括將識別出的符號串轉換為內部表示或者插入符號表，并對不接受的輸入串進行錯誤處理。框架中的前處理部分也叫預處理，是對源程序文本進行一定程度的清洗（如刪除注解、規(guī)范空白字符等），之后才提供給判定框處理?？蚣苤械暮筇幚硎菍⑴卸ńY果和附加處理結果構造成單詞符號并按照某種方式呈現出來，如保存在文件中或者返回給語法分析等。這個識別框架體現了詞法分析的原理與通用性。

多DFA集成設計解決了同時識別源程序中多個詞法單位的問題，具體方法是構造判定詞法單位的自動機，將識別每個詞法單位的DFA集成為一個DFA。算法[6]的輸入是需要識別的單詞符號，它們屬于那些由序列中的正則表達式r0, ...,rn-1定義的詞法單位（種屬），而輸出就是集成后的DFA。

3）更新語法分析。

這個算法正確工作的條件是∩iL(ri)=?；如果x∈L(ri)且xy∈L(rj)，那么x優(yōu)先被識別為單詞符號，當然這個條件還可以放松，將識別更靈活的語言如Lisp詞法單位。這部分最主要的改變是增加了項目下推自動機IPDA作為自上而下分析和自下而上分析統一的理論依據。

上下文無關文法G 的IPDA 為 (itemG,T,itemG,Δ, [S'→·S], [S'→·S], {[S'→S·]})，其中遷移函數分為 (E)Δ([A→α·Nη],ε)={[A→α·Nη][N→·γ]| (N,γ)∈Ρ}、(S)Δ([A→α·aη], c)={[A→αa·η]}和 (R)Δ([A→α·Nη][N→·γ],ε)={[A→αN·η]} 三 類（IPDA 中狀態(tài)與棧頂符號相同）[6]。

自上而下分析是E-遷移對應于推導。自下而上分析使用了IPDA的棧作為狀態(tài)棧，當前棧頂元素為當前狀態(tài)，對于IPDA的三種遷移，符號棧進行相應地操作：(E)符號棧沒有動作；(S)符號棧壓入a；(R)符號棧彈出|γ|個符號, 然后壓入N。

形式語言與編譯課程的理論完整性體現在III型和II型語言理論完整。詞法分析基于III型語言的判定性，自上而下和自下而上的語法分析被統一在項目下推自動機上，而語義分析仍采用語法制導的翻譯原理，并與IPDA結合起來，中間代碼生成和運行時環(huán)境歸屬到語義分析中，本身是完整的形式化代碼變換和優(yōu)化設計。

圖2 詞法單位的識別框架

4）更新語義分析。

沿用編譯原理中語法制導的語義分析，具體基于IPDA 來描述，假定當前項目為[A→α·Xη],當X=a時采用 S-遷移，Δ(-,a,ρ[A→α·aη])={(-,ρ[A→αa·η])}，相應的屬性求值工作是，將詞法分析器返回的結果作為a的綜合屬性的值。當X=B時采用 E-遷移，Δ([A→α·Bη],ε,ρ)={(-,ρ[B→·γ]) | (B,γ)∈Ρ}，對于新棧頂 [B→·γ]根據規(guī)則γ中所有符號的綜合屬性已經算出值，同時B的繼承屬性也已經求過值。

對于完全項目 [B→γ·]采用 R-遷移，Δ(-,ε,ρ[A→α·Bη][B→γ·])={(-,ρ[A→αB·η])}，這時γ中所有符號的綜合屬性已經算出，同時B的繼承屬性也已經求出。所以，B的綜合屬性的值應根據該產生式的語義規(guī)則進行計算作為該項目A→αBη中B的屬性值。

3.2 形式語言與編譯課程的教學過程設計

教學過程見表1。

表1 形式語言與編譯課程的教學過程

4 效果評價

采用兩種方法評價該課程效果，一種是分析的方法，另一種是實現并通過學生成績進行評價。

4.1 方案分析

1）涵蓋完整的理論和原理。

編譯原理課程使用形式語言的有關結論解決詞法語法分析的問題，但沒有完整描述為什么這么做以及這樣做為什么可以，使教學內容變成為一種技術要求學生掌握或記住，既會引起有用無用的疑問，也容易造成學生不知道所以然。本方案試圖改變這一狀況。以有窮自動機為例，編譯中介紹的NFA映射函數δ是一個從 S×Σ*至2S的映射，這種表示給引入NFA接受串、擴展遷移函數、DFA等價性的概念顯著增加了復雜度。往往最基本的形式是最有用的，也是最重要的，所以III型語言理論包含最基本的NFA（δ為從 S×Σ至2S的映射）和ε-NFA（δ為從S×Σ{ε}至2S的映射），并包括一般化的GNFA（弧上標記為正則表達式）。更重要的是，組成該理論的定理及其證明建立了計算的模型，這些理論不僅用于解決編譯中的問題，也用于解決計算機科學中的其他問題，具有廣泛意義，借此在教學過程中培養(yǎng)學生觀察現象、認識規(guī)律和發(fā)現規(guī)律的能力。

2）在正確的時間節(jié)點上培養(yǎng)學生抽象思維能力。

抽象是計算的基本屬性，抽象思維能力是計算機專業(yè)人才培養(yǎng)的重點之一。學習抽象知識是培養(yǎng)抽象思維能力的途徑。

形式語言與編譯課程的內容有很高的抽象性：首先，來自于編譯原理的部分，因為它是關于程序分析變換和優(yōu)化的，相比程序設計屬于元級處理，其抽象性在教學實踐中也已有共識；其次，就是形式化計算模型，包括III型和II型語言理論、類型系統、還包括形式語義學。形式語言與編譯課程的抽象性表現在上述兩個方面，單純的理論性課程和專業(yè)核心課程最多包括一個抽象性方面，因此，該課程是培養(yǎng)計算機專業(yè)學生抽象思維能力的主要課程之一。

能力培養(yǎng)的重點在大學4年各階段有所不同，從培養(yǎng)方案可以看出有多種模式：典型的“1+3”方案，即1年通識教育加上3年專業(yè)教育；另一種是“2+4”，即2年基礎教育加上4年專業(yè)教育。大一大二是理論基礎建立的黃金時段，過后由于專業(yè)課程加重且課程更關注方法論和技術層面的知識，導致理論基礎變得沒有彌補和擴展的空間，而且，后期也到了理論知識發(fā)揮潛在作用的時候。

培養(yǎng)方案的設計者面臨將部分課程作為前2年課程的選擇，他們往往站在學校的高度做決策，因此像電工實習、金工實習、工程制圖、生命科學基礎、數學建模等課程被選中，在這種情況下，也需要選擇計算機理論基礎課程。形式語言與編譯課程在大二下學期開始，就提供了這類選擇性。

表2是計算機專業(yè)2015級學生第4學期課表（2016—2017學年第2學期），從中可以看出通識課程占比情況。一般情況下，傳統編譯原理課程在大三作為專業(yè)課開設。本方案只是在時間上往前提前了一個學期，但課程性質發(fā)生了變化，即從專業(yè)課變成作為理論基礎課，實現了在正確的時間節(jié)點上培養(yǎng)學生抽象思維能力的教學目標。

4.2 形式語言與編譯課程的實現效果

該課程設計結果列入西安交通大學最新版培養(yǎng)計劃，面向2015級計算機班、少年班（選修）和錢學森班（選修），于2016—2017學年第2學期開課。

期末筆試試題共有9道題，全面覆蓋課程內容。各題描述及得分情況如表3所述。

在表3中，除了第8題外，各題平均得分和分數分布正常。第4題平均得分較高，說明形式語言部分掌握較好，與學生反饋也吻合。第8題失分原因歸結為方案多、教材不配套和時間緊3點，其中方案多是指要求掌握多個活動記錄方案（如fp-sp活動記錄格式[7]和sp-top格式[8]），并學會棧式存儲的設計原理，相比以往提高了要求。筆者計劃通過提供配套教材并放棄sp-top格式來解決。表4、表5、表6是各班級成績匯總，其中只包括計算機2個班。

從各班成績來看，分布基本合理，總體上達到成績良好。

與此課程配套的專題實驗課采用引進斯坦福大學COOL實驗平臺以及題目，結果得分情況正常，而少年班完成效果最好，平均分在90分以上。表明從編譯器設計角度來看，本課程設計合理，能夠為大二學生所接受。

表2 計算機專業(yè)第4學期課表

表3 試題描述及平均得分

表4 2015級少年班和錢學森班選修學生的分數分布

表5 計算機2015級4班分數分布

表6 計算機2015級5班分數分布

另外值得一提的是，少年班和錢學森班的離散數學課程和數據結構與本課程在同一學期同時開課。事實證明，這兩門先修課程與本課程同時進行也是可行的。

5 結 語

形式語言與編譯課程被設計為形式語言與自動機課程和編譯原理課程的替代，將III型和II型語言理論與編譯前端的原理結合起來，在大二下學期開設，實踐證明能夠取得良好的學習效果。該課程涵蓋完整的理論和原理，消除了課程間重疊，明晰了作為理論基礎的合理性，達到在正確的時間節(jié)點上培養(yǎng)學生抽象思維能力的目標。

設計本課程貫穿了三個原則：觀察現象，認識規(guī)律，學著揭示規(guī)律；知其所以然；會做與想通，以后者為重。本課程方案適合重點高校計算機專業(yè)普通班級及拔尖班級使用，不失普遍意義。

本文提出的形式語言與編譯課程設計為54學時內容，尚有一些必要的內容沒有包括進去，如LALR分析、上下文無關語言泵引理、類型系統與類型推理、面向對象語言等，可通過進一步優(yōu)化課程內容、調整課時得到解決。此外，在設計上沒有解決與程序設計語言的重疊問題，需要進一步研究。

參考文獻：

[1]趙銀亮. 關注編譯原理的等價性[J].計算機教育, 2011(11): 37-44.

[2]蔣宗禮. "編譯原理"課程與專業(yè)能力培養(yǎng)[J]. 計算機教育, 2009(21): 4-6.

[3]王挺, 李夢君, 周會平. 對編譯原理課程教學中計算思維培養(yǎng)的探討[J]. 計算機教育, 2009(21): 11-13.

[4]何炎祥, 伍春香. 計算機專業(yè)不需要開設編譯原理課程嗎?[J]. 計算機教育, 2009(4): 61-62.

[5]周會平, 王挺, 李夢君. 關于編譯原理課程定位的思考[J]. 計算機教育,2011(11): 45-47.

[6]Wilhelm R, Seidl H, Hack S. Compiler design: Syntactic and semantic analysis [M]. Berlin: Springer-Verlag Berlin Heidelberg,2013.

[7]Kenneth C, Louden. Compiler construction: Principles and practice [M].South Melbourn: Cengage Learning, 1997.

[8]陳火旺, 錢家驊, 孫永強. 程序設計語言: 編譯原理 [M]. 北京: 國防工業(yè)出版社, 2004.