“編譯原理”課程的教學改革實踐

邢建國

摘要：作者針對計算機專業“編譯原理”課程教學實踐中存在的一些問題，提出了在編譯原理課程中要引入兩個基于λ-演算的小語言，通過對這兩個小語言的文法和解釋器實現的介紹，使學生了解課程體系結構和課程目標，掌握編程語言重要的基本概念和實現方法，為后續的進一步學習打下基礎。

關鍵詞：編譯原理；λ-演算；解釋器；ANTLR

中圖分類號：G434? 文獻標識碼：A? 論文編號：1674-2117（2023）10-0096-04

前言

編譯原理是計算機專業的一門高年級選修課，主要介紹編譯器構造的一般原理、基本實現方法，內容包括詞法分析、語法分析、語義分析、中間代碼生成、代碼優化和目標代碼生成等。該課程涉及很多先修課程，如數據結構和算法、編程語言理論（PLT）、計算理論、計算機組成和體系結構、操作系統等，是計算機專業理論知識的重要組成部分。

近年來，編譯原理面臨著因課程體系調整導致的課時不足、先修和銜接課程斷檔等問題，教師對課程定位和教學目標不明確，而學生普遍反映課程難學、不實用。這一方面是由于編譯器是一個復雜的軟件系統，前后端各子系統耦合密切，很難在一個學期內用線性的教學組織方式來完成。另一方面是因為現有的教學內容過于龐雜，國內外主流的教材包含了編譯相關的很多算法和概念，如DFA子集構造及化簡、LL（1）分析算法、LR（1）分析算法、各種數據流分析、寄存器分配等，學生淹沒在一堆算法和術語中，不知道教學重點和學習目標。同時，很多在教學中強調的內容實際上并不重要，而生產實踐中有用的知識在教學中卻語焉不詳。

針對上述問題，筆者根據所在學院專業課程體系設置特點（編譯一般安排在第6或7學期，學生已系統學習過兩門以上編程語言、數據結構、操作系統和計算機組成等課程，但沒有學習過編程語言理論、計算理論等），對教學內容進行適當的調整，主要思路是在學生學習文法之后，在學習詞法分析、語法分析以及語義制導翻譯之前，首先引入兩個類似于λ-演算[1][2][3]的小語言，使學生通過這兩個語言的使用和解釋器的實現，了解課程總體框架和目標，了解編程語言重要的基本概念和實現方法，為后續的進一步學習打下基礎。其次，在教學中盡早引入現代的編譯工具，如前端工具ANTLR[4][5]、后端LLVM以及一些主流的中間語言，使學生能夠接觸到應用編譯原理解決的實際問題（如IDE的語法高亮實現、領域語言的解釋和實現）。在本文中，筆者主要討論了前者。

為使學生了解編程語言和計算，筆者設計了基于λ-演算的兩個小語言，每個語言只有4條語法規則，通過3～6課時的教師介紹，學生很容易學會并使用該語言的編程及實現一個解釋器。另外，筆者還安排了3課時的λ-演算的Python示例，通過構造布爾邏輯、自然數的算術體系，使學生了解λ-演算語言及計算的本質。λ-演算由Church[6]在20世紀30年代提出，主要是為解決可決判定性問題的一個研究函數抽象、函數應用以及遞歸的形式系統，它與同時期的圖靈的圖靈機、哥德爾的部分遞歸函數、

Sch nfinkel的SKI組合子以及波斯特的標簽系統等在計算能力上是等價的。

本文重點介紹這兩個小語言的設計和實現，第二部分介紹以json格式定義的jLambda語言的文法和解釋器實現；第三部分介紹使用ANTLR文法定義的aLambda語言的文法和解釋器實現。

jLambda：λ-演算語言解釋器I

和編譯器類似，實現一個解釋器，首先要根據文法對程序進行詞法分析和語法分析。這對于剛開始學習《編譯原理》的學生來說過于復雜，即使使用ANTLR這樣的編譯器生成工具，也需要了解很多的概念，學生很容易迷失在一堆不相關的知識中。

為解決這個問題，第一個小語言jLambda使用json來定義。使用json的好處在于，大部分語言如Python、Javascript等都提供了json解析庫，可以將其轉換為內部的樹狀數據結構，省去了詞法分析與語法分析。缺點也很明顯，就是語法比較笨拙，但對于教學目標來說是值得的。

1.jLambda語法

基于json的λ-演算語言，有四條語法規則——變量、變量賦值、函數定義、函數調用，用EBNF描述如圖1所示。

例如，函數add（x，y）定義如圖2所示。這里定義了一個變量“add”，其值為一個有兩個參數的函數，參數為“x”“y”，而函數體為[“+”， “x”，“b”]。這里假定有一個名為“+”函數能執行實際的加法。

可以使用該語言來定義在附錄中定義的布爾量、布爾運算、自然數以及自然數上的算術及邏輯運算。例如，K和KI定義如圖3所示。在這些基本函數基礎上，可以定義階乘fact（如圖4）。注意，這里假定實現的解釋器和Python一樣，在參數調用時使用Eager Evaluation策略。

2.解釋器實現

和原始的純函數式語言λ-演算不一樣，小語言中可對變量賦值，因此筆者首先引入環境env，變量及其對應的值以鍵值對的形式存儲在環境中。因為環境是嵌套的，所以查找一個變量時要先從最外面的環境開始，依次從外向內，如果找到了則返回對應的值，如果遍歷所有的環境都沒找到，則報錯。這里筆者使用了Python Collection庫中的ChainMap來實現環境。與環境相關的三個函數lookup_var、set_var以及extend_env分別如圖5所示。其中，extend_env是在env的外面添加一個新的環境，這個新的環境中包括變量vars和它們對應的值。

解釋器所做的工作是從用戶輸入得到一個表達式exp，然后調用求值器eval在環境env中對該表達式exp求值，求值器eval函數結構如圖6所示。

其中，各謂詞函數以及選擇函數is_var、is_assigment、assignment_var、assignment_val、is_fun、fun_params、fun_body、is_apply、operator、operands根據json定義的語法來實現，如賦值語句的三個函數實現如圖7所示。這與前面的賦值語句（如圖8）的定義是一致的。

這里要注意的是make_proc函數，該函數用于創建一個稱為函數閉包的數據結構。函數閉包包括函數參數、函數體以及定義該函數時的環境，這個環境用于查找自由變量（自由變量是指那些不在函數參數中定義的變量）。除了函數式編程語言，一般使用全局環境這個環境，如C語言，因此不需要把環境放在函數的定義中。而在函數式編程語言中，通常允許嵌套函數定義，這些嵌套函數往往會引用外部環境中的變量，如K函數的定義（如圖9）。

它返回一個函數，這個返回的函數里面引用了外部的x，那么在后續使用這個函數時必須提供訪問x的環境。筆者把函數以及定義該函數時的環境稱為閉包。

make_proc根據輸入的函數參數、函數體以及當前環境創建該函數的閉包（如圖10）。

當調用該函數時，就會從該函數對應的閉包中取出函數體body、參數params、定義該函數時的環境saved_env，在saved_env之外添加調用時形參和實參組成了一個新環境，然后在這個環境中對函數體進行求值，圖11所示的代碼是求值器最重要的一環，對于理解函數的調用實現有十分重要的意義。

有了eval定義后，完整的解釋器程序如圖12所示。

aLambda：λ-演算語言解釋器II

使用第二部分中的jLambda語言編寫程序很麻煩。筆者通過一個編譯器生成工具ANTLR來定義一個更接近于學生熟悉的編程語言文法的λ-演算語言aLambda，然后介紹該語言的解釋器實現。

ANTLR[4][5]是一個開源的編譯器生成器，與傳統的lex/yacc等編譯器工具相比，最新的ANTLR v4生成的語法分析器使用Adaptive LL（*）或ALL（*）的語法分析技術，允許左遞歸的遞歸下降分析，這使傳統上只能用LR（K）分析的很多文法也可以使用ANTLR來定義。同時，ANTLAR提供了兩種更現代的vistor和listener訪問模式，可以方便地遍歷語法樹。ANTLR還支持Java、C、C#、Python等多種目標語言。目前，ANTLR v4被廣泛應用于學術界和工業界構建各種語言、工具和框架。

1.aLambda語法

圖13所示是使用ANTLR描述的aLambda語言。

ANTLR中詞法和語法定義都使用相同的文法描述。使用這個文法定義的附錄中的K、KI、pair、first和second分別如圖14所示。

通過ANTLR提供了相應的Python編譯工具和Python的運行時庫，將上述文法aLambda進行編譯，生成相應的Python幾個類，如aLamdaLexer（詞法分析類）、aLamdaParser（語法分析類）、aLamdaVisitor（語法樹遍歷類）等。我們只要在visitor對象的基礎上訪問生成的語法樹，完成解釋器的工作。

2.解釋器實現

解釋器首先從用戶讀入一個表達式，然后調用Lexer生成詞法串流tokens，Larser將tokens流翻譯成語法樹，然后通過Visitor來遍歷語法樹個節點。解釋器的實現如圖15所示。

求值的工作放在繼承MyVistor的aLambdaVisitor的類中（如圖16），實現類似于前一節。

只要在aLambdaVisitor的繼承類MyVisitor中，把4條語法處理代碼放在相應的visit方法中就可以了，無需像在jLambda的實現中要手工分派。在使用ANTLR時，aLambda的文法比jLambda要簡潔，詞法分析和語法分析由ANTLR運行時處理，解釋器實現也更簡單。

總結

筆者所在學校已在編譯原理課程中引入上述教學內容。在教學實踐中，筆者發現課程安排的教學課時原本不足，在引入λ-演算和兩個小語言的介紹后時間更是緊張，因此把部分內容安排在開放實驗中，開放實驗9～12課時，時間安排較靈活，可以與課堂教學交替進行。λ-演算介紹放在第三周，jLambda放在第四周，此時學生已了解BNF描述的文法、文法和語言的形式化定義。aLambda的介紹安排在自頂向下的遞歸下降分析（LL（K）文法）之后、語法制導翻譯之前。在介紹完中間語言翻譯后，在aLambda的解釋器框架上將aLamba程序翻譯成目標代碼，為WebAssembly的一個子集。

通過三個學期的教學實踐，學生對相關教學內容的興趣有較大提升，對教學目標有了進一步的認識，同時對編譯原理的知識與生產實踐的關系也有所了解，對一些使用了編譯技術的生產力工具有了更新的認識。

參考文獻：

[1]Daniel P. Friedman & Mitchell Wand.Essentials of Programming Languages， third edition[M].Cambridge，MA：MIT Press，2008.

[2]Robert Nystrom.Crafting Interpreters[M].Genever Benning，2021.

[3]Harold Abelson， Gerald Jay Sussman & Julie Sussman.計算機程序的構造和解釋：第二版[M].北京：機械工業出版社，2004.

[4]ANTLR[EB/OL].https：//www.antlr.org/.

[5]Terence Parr.ANTLR4權威指南[M].北京：機械工業出版社，2017.

[6]Alonzo Church.An Unsolvable Problem of Elementary Number Theory[J].American Journal of Mathematics，1936，58（02）：345-363.