“编译原理”课程的教学改革实践

2023-06-09 13:58邢建国
中国信息技术教育 2023年10期

邢建国

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

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