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

前言

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

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

二是，教學(xué)偏重理論。教學(xué)內(nèi)容過多放在詞法分析、語法分析及代碼優(yōu)化上，對實際編程語言及目標(biāo)機器翻譯較少。學(xué)習(xí)難度大，導(dǎo)致學(xué)生興趣不高。編譯原理課程內(nèi)容仍然是基于過程式語言展開的，沒有及時跟進程序設(shè)計從傳統(tǒng)的過程式轉(zhuǎn)向函數(shù)式、對象式、組件型的變化，導(dǎo)致學(xué)生感到學(xué)習(xí)這門課程沒有實際意義且太難。

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

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

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

實驗教學(xué)內(nèi)容設(shè)計

1.設(shè)計目標(biāo)

設(shè)計一個完整的實驗教學(xué)方案，學(xué)生可以在32個實驗課時內(nèi)，系統(tǒng)地學(xué)習(xí)編譯器的構(gòu)建過程，并完成一個完整的編譯器實現(xiàn)。通過這一過程，培養(yǎng)學(xué)生的理論知識和實踐技能，提高他們的問題解決能力和創(chuàng)新思維。

2.設(shè)計思路

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

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

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

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

⑤ 采用Python編程實現(xiàn)。

3.主要內(nèi)容

① 先將編譯器的實現(xiàn)過程分解為若干個模塊，如詞法分析、語法分析、語義分析、中間代碼生成、代碼優(yōu)化和目標(biāo)代碼生成等，再通過具體的編程語言案例，引導(dǎo)學(xué)生逐步構(gòu)建編譯器，并圍繞一個簡單的語言，完成相應(yīng)各環(huán)節(jié)的設(shè)計和實現(xiàn)。

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

③ 設(shè)計相應(yīng)的實驗指導(dǎo)書，內(nèi)容包括理論基礎(chǔ)、實驗步驟、代碼示例和常見問題解答。

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

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

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

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

Cilly語言描述

考慮到現(xiàn)有的高級語言太復(fù)雜，不適合一學(xué)期的實驗教學(xué)，筆者設(shè)計了一個動態(tài)類型、支持閉包的函數(shù)式編程語言Cilly。

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

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

主要實驗內(nèi)容

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

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

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

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

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

Cilly_lexer中反復(fù)調(diào)用函數(shù)token，直到讀到文件結(jié)束符，該函數(shù)每次返回當(dāng)前位置下的詞法單元。函數(shù)token實現(xiàn)如圖4所示。

函數(shù)token首先跳過所有的空白字符和注釋，然后調(diào)用peek查看當(dāng)前字符，再根據(jù)不同類型來分別識別數(shù)字、標(biāo)識符、字符串、運算符和其他符號。

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

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

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

Cilly_parser的主函數(shù)為program，該函數(shù)反復(fù)調(diào)用statement函數(shù)，將識別到的語句添加到數(shù)組stats中，直到讀到EOF詞法單元，然后構(gòu)建ast的父節(jié)點“program”返回（如圖6）。

函數(shù)statement則是根據(jù)當(dāng)前的詞法單元來分別處理不同的語句，如圖7所示。

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

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

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

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

3.Cilly解釋器及REPL執(zhí)行環(huán)境

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

筆者使用訪問器模式來實現(xiàn)解釋器，每個節(jié)點都有一個求值函數(shù)，存放在visitors的字典中，在主程序中定義visit函數(shù)，根據(jù)節(jié)點類型來調(diào)用相應(yīng)的求值函數(shù)（如圖11）。

如節(jié)點program和打印的求值函數(shù)為ev_program.ev_print，其實現(xiàn)如圖12所示。

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

在Cilly_eval函數(shù)基礎(chǔ)上，可以實現(xiàn)一個類似于Python的交互式命令行repl（如圖13）。

4.虛擬機及編譯

模塊二實現(xiàn)了一個目標(biāo)機器為虛擬機的編譯器。

（1）虛擬機的實現(xiàn)

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

設(shè)計的虛擬機的指令包括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等。

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

大部分指令的實現(xiàn)比較簡單，"此處不詳細(xì)介紹。

（2）編譯器實現(xiàn)

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

這兩個函數(shù)和解釋器中的對應(yīng)函數(shù)結(jié)構(gòu)基本類似，主要區(qū)別是這兒調(diào)用emit生成機器指令，而不是執(zhí)行語句。其余語句的翻譯也類似。

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

注意，遍歷一次ast樹生成目標(biāo)代碼，因此一些轉(zhuǎn)移指令的目標(biāo)地址需要用回填技術(shù)來實現(xiàn)。

（3）反匯編器

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

5.Cilly語言的risc-v編譯器實現(xiàn)

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

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

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

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

6.優(yōu)化

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

教學(xué)實踐效果總結(jié)

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

通過一個學(xué)期的教學(xué)實踐，整體下來，學(xué)生對“編譯原理”課程的興趣有較大提升，基本掌握了遞歸下降分析、表達式分析以及解釋器、編譯器等各環(huán)節(jié)原理和實現(xiàn)方法，能夠完成如json、sql、mermaid等的語法分析，以及l(fā)ogo、lisp這類動態(tài)語言的解釋器實現(xiàn)，為進一步深入學(xué)習(xí)編譯技術(shù)打下了基礎(chǔ)。

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

參考文獻：

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

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

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

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

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

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