邢建国

摘要：作者针对计算机专业“编译原理”课程教学实践中存在的一些问题，提出了在编译原理课程中要引入两个基于λ-演算的小语言，通过对这两个小语言的文法和解释器实现的介绍，使学生了解课程体系结构和课程目标，掌握编程语言重要的基本概念和实现方法，为后续的进一步学习打下基础。

关键词：编译原理；λ-演算；解释器；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.