邢建國

摘要：作者針對計(jì)算機(jī)專業(yè)“編譯原理”課程教學(xué)實(shí)踐中存在的一些問題，提出了在編譯原理課程中要引入兩個(gè)基于λ-演算的小語言，通過對這兩個(gè)小語言的文法和解釋器實(shí)現(xiàn)的介紹，使學(xué)生了解課程體系結(jié)構(gòu)和課程目標(biāo)，掌握編程語言重要的基本概念和實(shí)現(xiàn)方法，為后續(xù)的進(jìn)一步學(xué)習(xí)打下基礎(chǔ)。

關(guān)鍵詞：編譯原理；λ-演算；解釋器；ANTLR

中圖分類號：G434? 文獻(xiàn)標(biāo)識碼：A? 論文編號：1674-2117（2023）10-0096-04

前言

編譯原理是計(jì)算機(jī)專業(yè)的一門高年級選修課，主要介紹編譯器構(gòu)造的一般原理、基本實(shí)現(xiàn)方法，內(nèi)容包括詞法分析、語法分析、語義分析、中間代碼生成、代碼優(yōu)化和目標(biāo)代碼生成等。該課程涉及很多先修課程，如數(shù)據(jù)結(jié)構(gòu)和算法、編程語言理論（PLT）、計(jì)算理論、計(jì)算機(jī)組成和體系結(jié)構(gòu)、操作系統(tǒng)等，是計(jì)算機(jī)專業(yè)理論知識的重要組成部分。

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

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

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

Sch nfinkel的SKI組合子以及波斯特的標(biāo)簽系統(tǒng)等在計(jì)算能力上是等價(jià)的。

本文重點(diǎn)介紹這兩個(gè)小語言的設(shè)計(jì)和實(shí)現(xiàn)，第二部分介紹以json格式定義的jLambda語言的文法和解釋器實(shí)現(xiàn)；第三部分介紹使用ANTLR文法定義的aLambda語言的文法和解釋器實(shí)現(xiàn)。

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

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

為解決這個(gè)問題，第一個(gè)小語言jLambda使用json來定義。使用json的好處在于，大部分語言如Python、Javascript等都提供了json解析庫，可以將其轉(zhuǎn)換為內(nèi)部的樹狀數(shù)據(jù)結(jié)構(gòu)，省去了詞法分析與語法分析。缺點(diǎn)也很明顯，就是語法比較笨拙，但對于教學(xué)目標(biāo)來說是值得的。

1.jLambda語法

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

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

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

2.解釋器實(shí)現(xiàn)

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

解釋器所做的工作是從用戶輸入得到一個(gè)表達(dá)式exp，然后調(diào)用求值器eval在環(huán)境env中對該表達(dá)式exp求值，求值器eval函數(shù)結(jié)構(gòu)如圖6所示。

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

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

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

make_proc根據(jù)輸入的函數(shù)參數(shù)、函數(shù)體以及當(dāng)前環(huán)境創(chuàng)建該函數(shù)的閉包（如圖10）。

當(dāng)調(diào)用該函數(shù)時(shí)，就會從該函數(shù)對應(yīng)的閉包中取出函數(shù)體body、參數(shù)params、定義該函數(shù)時(shí)的環(huán)境saved_env，在saved_env之外添加調(diào)用時(shí)形參和實(shí)參組成了一個(gè)新環(huán)境，然后在這個(gè)環(huán)境中對函數(shù)體進(jìn)行求值，圖11所示的代碼是求值器最重要的一環(huán)，對于理解函數(shù)的調(diào)用實(shí)現(xiàn)有十分重要的意義。

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

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

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

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

1.aLambda語法

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

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

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

2.解釋器實(shí)現(xiàn)

解釋器首先從用戶讀入一個(gè)表達(dá)式，然后調(diào)用Lexer生成詞法串流tokens，Larser將tokens流翻譯成語法樹，然后通過Visitor來遍歷語法樹個(gè)節(jié)點(diǎn)。解釋器的實(shí)現(xiàn)如圖15所示。

求值的工作放在繼承MyVistor的aLambdaVisitor的類中（如圖16），實(shí)現(xiàn)類似于前一節(jié)。

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

總結(jié)

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

通過三個(gè)學(xué)期的教學(xué)實(shí)踐，學(xué)生對相關(guān)教學(xué)內(nèi)容的興趣有較大提升，對教學(xué)目標(biāo)有了進(jìn)一步的認(rèn)識，同時(shí)對編譯原理的知識與生產(chǎn)實(shí)踐的關(guān)系也有所了解，對一些使用了編譯技術(shù)的生產(chǎn)力工具有了更新的認(rèn)識。

參考文獻(xiàn)：

[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.計(jì)算機(jī)程序的構(gòu)造和解釋：第二版[M].北京：機(jī)械工業(yè)出版社，2004.

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

[5]Terence Parr.ANTLR4權(quán)威指南[M].北京：機(jī)械工業(yè)出版社，2017.

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