面向“新質生產力”的編譯原理”課程實驗教學改革實踐

中圖分類號：G434文獻標識碼：A論文編號：1674—2117（2025）12-0090—07

前言

“編譯原理”課程是計算機專業的核心課程之一，主要介紹編譯程序構造的一般原理和基本方法，內容涵蓋了語言和文法、詞法分析、語法分析、語法制導翻譯、中間代碼生成、存儲管理、代碼優化和目標代碼生成等。通過該課程的學習，使學生在了解編程語言的設計理念和實現機制的同時，能更好地理解計算機如何處理和執行代碼。同時，通過理解編譯過程，學生能夠更好地編寫高效、可維護的代碼，避免常見的編程錯誤，提高代碼的可讀性和可重用性。這對于學生未來從事編程開發、語言/編譯器設計或相關領域的工作具有重要意義。上述目標的實現除了要學習編譯理論外，還需要大量的實踐。然而在教學實施過程中，由于理論教學內容多、課時少且師資缺乏，實驗教學課時往往不足，實驗內容的深度和廣度也不夠，使得學生雖然學習了編譯原理課程，卻難以自己動手去實現一個編譯器或解釋器。筆者研究發現，現有的編譯原理教學體系，特別是實驗教學，存在以下幾個問題，無法滿足新質生產力對人才培養的需求。

一是，實驗內容的碎片化。大多數編譯原理實驗內容是理論課程配套的小實驗，如DFA、NFA自動機、LL/LR分析器、語法制導翻譯等，這些實驗雖然與理論授課進度同步，有助于學生理解課堂學習的知識，但人為分裂了編譯程序的完整性，導致學生不能學習到一個完整的編譯器的開發運行過程。

二是，教學偏重理論。教學內容過多放在詞法分析、語法分析及代碼優化上，對實際編程語言及目標機器翻譯較少。學習難度大，導致學生興趣不高。編譯原理課程內容仍然是基于過程式語言展開的，沒有及時跟進程序設計從傳統的過程式轉向函數式、對象式、組件型的變化，導致學生感到學習這門課程沒有實際意義且太難。

三是，實驗設計不合理。實驗設計往往要求學生完成小型模型語言的完整編譯程序，但這樣的任務對于部分學生來說難以完成，不能激發他們的興趣。同時，實驗周期短、模塊間銜接復雜，不易立即看到整體效果，缺乏可用的實驗教學資料。

四是，缺乏實驗教材和工具。教材偏重理論，缺乏對具體實現的介紹，對一些新的編譯技術如組合子解析器、Pratt解析器沒有涉及，實驗工具使用LEX/YACC等，基本沒有引入如ANTLR、LLVM、CLANG、WASM等新型的前后端編譯工具，內容陳舊。學生對開發工具和環境不熟悉，語言描述不夠詳細，導致實驗項目難以順利進行。

針對上述問題，筆者重新設計了編譯原理課程的實驗內容，目的是使學生能夠掌握一個完整的函數式編程語言的編譯器/解釋器的實現。

實驗教學內容設計

1.設計目標

設計一個完整的實驗教學方案，學生可以在32個實驗課時內，系統地學習編譯器的構建過程，并完成一個完整的編譯器實現。通過這一過程，培養學生的理論知識和實踐技能，提高他們的問題解決能力和創新思維。

2.設計思路

① 使用一個簡單但足夠復雜的函數式編程語言。

② 簡化詞法分析和語法分析，聚焦語義分析和代碼生成。

③ 采用多趟（PASS）、多段（STAGE）設計，編譯器各段之間相互獨立。

④ 覆蓋解釋器、虛擬機、編譯器。

⑤ 采用Python編程實現。

3.主要內容

① 先將編譯器的實現過程分解為若干個模塊，如詞法分析、語法分析、語義分析、中間代碼生成、代碼優化和目標代碼生成等，再通過具體的編程語言案例，引導學生逐步構建編譯器，并圍繞一個簡單的語言，完成相應各環節的設計和實現。

② 鼓勵學生以小組形式合作，共同討論和解決問題，同時要求每個學生獨立完成部分模塊的實現，以確保每個人都能掌握關鍵技能。在每個階段結束時，進行代碼審查和測試，確保學生的工作進度和質量，并提供及時的反饋和指導。在課程結束時，要求學生展示他們的編譯器實現，并進行性能測試和比較。設計合理的評估體系，其中包括實驗報告、代碼質量、項目展示和個人貢獻等多個維度。

③ 設計相應的實驗指導書，內容包括理論基礎、實驗步驟、代碼示例和常見問題解答。

實驗包含三個模塊，包括一個解釋器、兩個編譯器，其中一個編譯器的目標機器為堆棧式虛擬機，另一個編譯器的目標機器為RV32I指令集的RISC-V處理器（如圖1）。

模塊一實現一個解釋器，通過該模塊使學生掌握詞法分析、語法分析、語義分析（可選，用于介紹類型自動推導）的基本技術，以及編程語言的解釋實現。

在模塊一基礎上，模塊二實現一個目標為堆棧式虛擬機的編譯器。在模塊二中，直接使用模塊一里面的詞法分析器、語法分析器、語義分析等。使用堆棧式虛擬機作為目標機器的好處在于，機器指令數少，不用考慮寄存器分配，同時利用宿主語言的特性可以簡化內存的使用和管理。此外，學生可以通過虛擬機的實現了解底層機器工作機制，為模塊三的以RISC-V為目標的編譯器提供基礎。

模塊三設計實現一個面向RISC-V機器（RV32I指令集）的編譯器。RISC-V的設計簡單而精簡，RV32I指令集只有47條指令，尋址模式簡單，指令功能正交化，大的寄存器文件，使得編譯器開發相對容易。此外，使用RISC-V模擬器RARS，RARS自帶了一個圖形化的集成開發和仿真環境，包括編輯器、匯編器和模擬器，編譯器生成的RISC-V匯編代碼可以直接在RARS中編譯、調試、執行，不需要專門的RISC-V開發板或像QEMU的仿真環境。

Cilly語言描述

考慮到現有的高級語言太復雜，不適合一學期的實驗教學，筆者設計了一個動態類型、支持閉包的函數式編程語言Cilly。

使用動態類型可以大大簡化語法，同時只支持數值（整數和浮點數）、字符串、布爾值、數組、結構體（類似于JSON對象）等基本和復合數據類型，實現if/for/while等基本控制流語法。這使得詞法、語法分析及語義分析代碼行數只需要700＼～800行Python語句就可以實現。

筆者還在語言中引入嵌套函數、閉包。目前，大多數編譯原理教材沒有介紹閉包，主流的編程語言如C、Java等也很少支持嵌套函數。但筆者認為利用嵌套函數和閉包可以實現很多語法特性（如對象、流等），雖然增加了實現的復雜性，但有助于學生更好地理解編程語言。

主要實驗內容

1.基于遞歸下降分析的詞法分析器

Cilly語言的詞法屬于正則文法。正則文法可以使用確定性有限自動機（DFA）來實現，lex/bison等工具可以根據詞法自動生成詞法分析器，供后續的語法分析器如yacc調用。手工去實現這樣的分析器比較復雜。在組合子解析器實現中，通常在語法分析過程中直接使用正則表達式來進行token的識別，不需要單獨的詞法分析器。

遞歸下降分析傳統上用來處理上下文無關文法，而正則文法也屬于上下文無關文法，因此完全可以用來實現詞法分析。而有些語言如Python，其詞法屬于上下文無關文法，不能用lex來解析。遞歸下降分析很適合于手工編寫，因此本實驗采用遞歸下降分析來實現Cilly的詞法分析。

token的表示——筆者定義了三個函數mk_tk、tk_tag、tk_val來封裝token，具體實現使用Python的數組list來表示，這里忽略了token所在的行號等位置信息（如圖2）。

詞法分析器Cilly_Lexer輸入為字符串，輸出為token的list，其實現如圖3所示。

Cilly_lexer中反復調用函數token，直到讀到文件結束符，該函數每次返回當前位置下的詞法單元。函數token實現如圖4所示。

函數token首先跳過所有的空白字符和注釋，然后調用peek查看當前字符，再根據不同類型來分別識別數字、標識符、字符串、運算符和其他符號。

2.基于遞歸下降分析和Pratt解析器的語法分析器

Cilly的語法分析器cilly_parser的輸人為cilly_lexer產生的token數組，輸出為抽象語法樹（也可以根據實際后續任務，輸出其他形式的語法樹，如用于集成開發環境中語法高亮、代碼輸人自動完def cilly_parser（tokens）：def program：stats σ=σ []while peek！='eof'：stats.append（ statement）return['program'，stats]return program成等）。

抽象語法樹ast的節點采用Python的數組實現，通過兩個輔助函數node_tag和node_val得到節點的類型和值，如上頁圖5所示。

Cilly_parser的主函數為program，該函數反復調用statement函數，將識別到的語句添加到數組stats中，直到讀到EOF詞法單元，然后構建ast的父節點“program”返回（如圖6）。

函數statement則是根據當前的詞法單元來分別處理不同的語句，如圖7所示。

表達式expr的解析使用了Pratt解析器。在傳統的遞歸下降分析中，處理表達式中的左遞歸、運算符的優先級和結合性，必須進行語法改造，消除左遞歸，把表達式語法變成如圖8所示的分層表示。

這使得程序里多了很多個結構類似、重復的非終結符的實現。本實驗引入了Pratt解析器，可以非常優雅地同時處理左遞歸、運算符優先級和結合性問題。Pratt解析器也稱為自頂向下的運算符優先級解析器，由VaughanPratt在1973年提出，實際上它是一種更通用的解析技術。

Pratt算法為每個一元運算符或二元運算符（也適用于像C語言這樣的多元運算符）定義了左、右的結合力（BindPower），如假定 ?₊， 的左、右結合力分別為10、20， ‘*’的左、右結合力分別為30、40，如圖9所示。則在表達式 1+2+3*4 中，由于2左邊的 ‘*’的右結合力大于2右邊的'+' 的左結合力，因此，上式應該解析為 （1+2）+3*40 同樣，3的兩邊結合力分別為20和30，因此3要先和‘*’結合： （1+2）+（3*4）。

一元前綴運算符只有右結合力，后綴運算符可以視為二元運算符的特殊情況。上述思想可以用如圖10所示的算法實現，其中parse_uniop和parse_binop分別用于解析一元表達式和二元表達式。這樣只要定義了不同運算符的結合力，不同優先級的一元、二元表達式都可以用上述函數來解析。

3.Cilly解釋器及REPL執行環境

解釋cilly_eval_使用cilly_parse生成的抽象語法樹作為輸入。解釋器還有一個輸入變量為求值環境env，環境用于查找變量。

筆者使用訪問器模式來實現解釋器，每個節點都有一個求值函數，存放在visitors的字典中，在主程序中定義visit函數，根據節點類型來調用相應的求值函數（如圖11）。

如節點program和打印的求值函數為ev_program.ev_print，其實現如圖12所示。

解釋器主要難點包括變量（全局變量、嵌套函數里的變量）的定義、引用和賦值，函數的定義（閉包）、調用等，此處不詳細介紹。

在Cilly_eval函數基礎上，可以實現一個類似于Python的交互式命令行repl（如圖13）。

4.虛擬機及編譯

模塊二實現了一個目標機器為虛擬機的編譯器。

（1）虛擬機的實現

筆者定義了一個類似于Python虛擬機的堆棧式虛擬機cilly_vm。該虛擬機有一個常量池、運算堆、作用域棧（用于嵌套函數、閉包）、調用棧、代碼和程序指針pc，其實現如圖14所示。

設計的虛擬機的指令包括LOAD_CONST，LOAD_TRUE、LOAD_FALSE、LOAD_NULL、POP、LOAD_GLOBAL、STOREGLOBAL、BINOP_ADD、BINOPSUB、BINOP_MUL、BINOP_DIV、BINOP_GT、BINOP_GE、BINOP_LT、BINOP_LE、BINOP_EQ、BINOP_NE、UNIOP_NOT、UNIOP_NEG，JMP，JMP_TRUE、JMP_FALSE、PRINT_ITEM、PRINT_NEWLINE、LOAD_VAR、STORE_VAR、MAKEPROC、CALL、RETENTER_SCOPE，LEAVE_SCOPE等。

所有的指令使用一個整數表示，可以有0、1、2個參數，如LOAD_CONSTi，表示把常數池中編號為i的常數壓人運算棧，而BINOPADD指令沒有參數，其作用是將棧頂兩個數彈出，然后把它們的和壓人運算棧。

大部分指令的實現比較簡單，"此處不詳細介紹。

（2）編譯器實現

編譯器cilly_vm_compiler將源程序的抽象語法樹翻譯成目標代碼為上述虛擬機的機器碼。編譯器的輸出為生成的代碼和常量池：[code，consts]。編譯器采用與解釋器類似的訪問者模式實現（如圖15）。例如，頂層節點program及打印語句print的實現如圖16所示。

這兩個函數和解釋器中的對應函數結構基本類似，主要區別是這兒調用emit生成機器指令，而不是執行語句。其余語句的翻譯也類似。

在解釋器中的變量都是通過環境來實現存儲、查找，在編譯器中變量的查找和引用分別是在編譯器和虛擬機中，因此必須將解釋器中環境的有關信息分別放在編譯器和虛擬機中。

注意，遍歷一次ast樹生成目標代碼，因此一些轉移指令的目標地址需要用回填技術來實現。

（3）反匯編器

為了檢查生成的機器碼是否正確，還要實現一個反匯編器，將數字形式的機器碼轉換為容易閱讀的匯編指令格式。反匯編器的結構和虛擬機的實現類似，這里不做具體介紹，圖17是反匯編器的輸出示例。

5.Cilly語言的risc-v編譯器實現

這部分內容是模塊三的主要內容。此處，筆者采用RARS這樣的RISC-V模擬器，該模擬器只實現了用戶模式，但對編譯器應用來說足夠了，學生可以利用RARS來編譯和運行所生成的匯編程序。此外，該模擬器自帶的匯編器語法基本與risc-v的gcc匯編器類似，學生很容易將生成的代碼轉換為gcc所支持的匯編代碼。

與虛擬機編譯器不同的是，cilly_risc_compiler需要處理內存管理，包括在內存中分配、查找常量、變量，維護記錄棧以及堆的變化。此處筆者沒有處理內存的釋放，也沒有實現垃圾回收機制，這么做也是為了簡化實現。常量放在data區，為了支持閉包和嵌套函數，將參數和局部變量放在堆上，而不是堆棧上，堆棧上存放調用時的返回地址以及作用域指針。

cilly_riscv_compiler的輸出為RARS格式的匯編代碼，實現方式和前面的解釋器和堆棧虛擬機的編譯器結構類似，也采用了訪問者模式（如圖18）。

其中，函數rars_output是將生成的代碼和數據合起來，輸出為RARS的匯編格式。

6.優化

筆者提供了一些如常量合并、強度削弱等的優化模塊，這些優化通常作為一個獨立的階段在抽象語法樹上進行。這么做的好處是可以將不同的優化技術組合起來，盡管效率不高，但每個階段處理非常簡單。

教學實踐效果總結

筆者在承擔的“編譯原理”課程教學中對上述實驗教學內容實施過一次，共有三個班（兩個計科專業班、一個信息安全班，二年級下），學生90人左右。由于實驗教學內容調整較大，內容較多，而總課時不能調整，因此壓縮或去除了部分理論教學內容（詞法分析中的子集法及自動機理論，語法分析中的LR文法，中間代碼生成、數據流分析等），多出來的時間用于實驗課時。同時，采用翻轉課堂（學生提前自學相關理論部分）、課后自主實驗（不占課內時間）等形式，這樣基本保證了32課時的實驗課時。實驗教學形式采用教師課堂上編寫程序框架，介紹實驗原理，學生課后填充細節。要求所有學生完成模塊一所有內容，并對完整的解釋器運行結果進行展示，模塊二和模塊三選做。期末考核包括兩部分： ① 模塊一的任務 （40%） ‘ ② 大作業 （60%） ，實現logo語言解釋器或SQL語言解釋器。

通過一個學期的教學實踐，整體下來，學生對“編譯原理”課程的興趣有較大提升，基本掌握了遞歸下降分析、表達式分析以及解釋器、編譯器等各環節原理和實現方法，能夠完成如json、sql、mermaid等的語法分析，以及logo、lisp這類動態語言的解釋器實現，為進一步深入學習編譯技術打下了基礎。

受教學課時等因素的限制，本實驗沒有采用像llvm、gcc等之類的前后端，也沒有使用真實的編程語言，這使得學生對生產環境下的編譯工具和編譯技術缺乏了解。筆者希望在后面的教學實踐中逐漸改進，使實驗教學內容更貼合實際應用。

參考文獻：

[1]RARS—RlSC—VAssemblerandRuntime Simulator[EB/OL].https：//github.com/TheThirdOne/rars.

[2]KeithCooperamp;LindaTorczon.編譯器設計[M].北京：人民郵電出版社，2012.

[4]海納.自已動手寫Python虛擬機M.北京：北京航空航天大學出版社，2019.

[5]RobertNystrom，CraftinghterpretersM].GeneverBenning，2021.

[6]索斯藤·鮑爾.用Go語言自制解釋器M.北京：人民郵電出版社，2022.

[7]Harold Abelson，GeraldJay Sussmanamp;JuieSusman.計算機程序的構造和解釋（第二版）[M].北京：機械工業出版社，2004.e