ACM在线评测在编译原理实践教学中的应用探讨

尤 枫 史晟辉

摘要:本文对ACM在线评测在计算机算法类课程实践教学中的应用现状进行了介绍,分析了在“编译原理”课程实践教学中引入在线评测的可行性,阐述了如何组织适于在线评测模式的“编译原理”实践教学内容,并给出了“编译原理”在线评测系统的设计方案,对“编译原理”实践教学模式进行了有益探索。

关键词:ACM;编译原理;在线评测;实践教学

中图分类号:G642 文献标识码:B

1引言

多年来,ACM在线评测一直被成功应用于ACM国际大学生程序设计竞赛(ACM/ICPC:ACM International Collegiate Programming Contest),这是美国计算机协会(ACM:Association for Computer Machinery)组织的、世界上公认的规模最大、水平最高的国际大学生程序设计竞赛,旨在使大学生运用计算机程序设计理论充分展示自己分析问题和解决问题的能力。

中国大陆地区1997年开始举办区域赛和参加世界总决赛。十几年来,全国近百所知名高校积极响应,热心参与,已成为我国高校科技活动的一个热点和展示计算机教育成果及优秀人才综合素质的一项重要活动,目前更是出现迅速普及的趋势。

鉴于ACM在线评测提供了完整的计算机实践教学模式,在培养学生创新能力、综合能力、锻炼学生心理素质和团队合作精神方面起到了积极的促进作用,目前我国的许多高校,如北京大学、清华大学、浙江大学和中山大学等均开发了自己的ACM在线评测系统,并将其引入到了计算机算法设计类课程的实践教学和学生能力评测中,如程序设计基础、数据结构与算法、人工智能、算法分析与设计等,并取得了非常好的效果,在很大程度上弥补了计算机实践教学中的不足。我校在2008年初开发了编译程序在线评测系统,开始探讨将这一模式引入“编译原理”课程的实践教学中,取得了很好的效果,现正在进一步完善。

2在线评测系统的功能

“编译原理”是一门理论和实践紧密结合的课程,但其内容抽象、逻辑性强、不易理解,是计算机专业课中公认的难学课程。学习理论知识难,编程训练更是让学生望而生畏。如何使学生掌握编译技术、循序渐进地参与复杂软件系统的设计开发,是需要深入研究的问题。

2.1ACM在线评测系统的主要功能

ACM在线评测系统是一个基于B/S结构的在线程序与算法设计练习、竞赛平台,主要功能可分为用户管理、题库管理、在线提交、在线比赛及在线排名、在线讨论等。该系统提供了大量供学生练习和竞赛的竞赛题目,学生在线提交解决相关练习和竞赛题的程序代码,系统可以自动编译程序代码,生成可执行文件,并根据已存储的测试用例,从程序的正确性、程序运行总时间、耗费内存、单用例执行时间、程序返回结果等各方面评测程序代码,并精确返回各方面的评测结果。这不仅要求学生能够分析问题,综合利用知识点,而且还要在算法上进行合理的优化,并在更短的时间内给出准确解答,大大提高了教学质量和教学效果。

2.2需解决的问题

不同于算法设计类课程,编译程序复杂、规模庞大,程序模块之间关系紧密,编译结果可能不具唯一性等,都造成编译程序在线评测的困难。除了评测外,课程各个知识点和算法关联程度高,后续内容往往需要前面的内容作支撑,一环紧扣一环,学生只想练习后面部分知识点和算法几乎不可能,他们对编写复杂程序很恐惧,造成很大心理负担。

“编译原理”的实践教学主要由两部分组成,课程实验和课程设计。

课程实验是实践教学的重要环节,也是课堂理论教学的重要补充,通过实验,学生能够更好地理解课程中的基本概念和原理,通过自己动手体验提高实践能力。通常这一类的实验多为验证性的,规模相对较小,主要是对一、二个知识点和算法的实践训练,如词法分析中的正则表达式到NFA的转换、NFA到DFA的转换、DFA的最小化等程序的实现等。因此,如何更合理地将“编译原理”中的各知识点和算法进行划分和归类,使其更适合于练习和在线评测,是要解决的一个问题。

课程设计与课程实验不同,主要是培养学生的综合设计能力,无论是从综合性、设计性要求,还是从规模上要求,课程设计的复杂度都高于课程实验。因此,如何更合理地组合“编译原理”中的各知识点和算法,形成完整的编译程序前端、后端乃致整个编译程序,以满足课程设计的要求,并适合于在线评测,是要解决的另一个问题。

3实践教学内容设计

一般地,编译程序主要由词法分析、语法分析、语义分析和目标代码生成程序等几个部分组成,每一部分又包含若干个知识点和算法。因此,首先要将这些知识点和算法合理地拆分成若干个模块,使之简单化、小型化、独立化,使学生可以以任意顺序实现各模块的功能。

以编译程序前端的词法分析和语法分析两部分为例,共拆分设置了18个核心模块,并进一步扩展为21个模块,如图1所示,其中灰色显示的3个模块为外部输入模块,图中的箭头表示各模块之间的依赖关系。由于语法分析部分的各模块均依赖于产生式表和符号表,为使关系图更清晰,在图中隐去了这两个模块的依赖。

由于模块之间具有独立性,用户可以单独实现其中的某一模块而无须实现其所依赖的各模块,其依赖的模块将由评测系统提供接口予以使用。这样,完整的词法分析程序需要实现4个模块,而语法分析具体分为5种:①对于LL(1)分析法,需要实现LL产生式表、符号表、First集、Follow集、LL(1)分析表、分析树共6个模块;②对于LR(0)分析法,需要实现LR分析表、符号表、LR(0)自动机、LR(0)分析表、分析树共5个模块;③对于SLR分析法,需要实现LR分析表、符号表、First集、Follow集、LR(0)自动机、SLR分析表、分析树共7个模块;④对于LR(1)分析法,需要实现LR分析表、符号表、First集、Follow集、LR(1)自动机、LR(1)分析表、分析树共7个模块;⑤对于LALR分析法,需要实现LR分析表、符号表、First集、Follow集、LR(1)自动机或LR(0)自动机、LALR自动机、LALR分析表、分析树共8个模块。

以上5种只需要实现其中一种,即可实现语法分析程序。对于语义分析和目标代码生成程序的模块拆分及依赖关系,也采用类似的方法进行。

4编译程序在线评测系统的实现

为了与现有的ACM在线评测系统接轨,编译程序在线评测系统是通过在北京化工大学ACM在线评测系统上进行改进和增加功能来实现的,主要包括如下几个部分。

4.1组合模块功能实现

要实现编译程序,除了要实现上述拆分后的各相关模块功能外,还要进行组合。例如对于词法分析程序,除要分别实现“正则表达式转NFA”、“NFA转DFA”、“DFA转最小化DFA”和“最小化DFA转符号序列”四个算法,在评测系统中体现为实现NFA模块(输入为正则表达式,输出为NFA)、DFA模块、最小化DFA模块和符号序列模块外,还要将其组合,形成最终的词法分析程序,这就提出了组合模块的思想。

一般来说,简单的组合模块思路是针对每一种可能的组合方式设计一个组合模块,但由于编译原理知识点和算法拆分后模块数量较多,其组合方式更是呈指数级增长,这无疑增加了实现的难度,同时也会产生冗余。因此,评测系统采用了一种自动组合的思路,在遵循编译原理的情况下,可进行任意模块的组合,用户在需要组合时可以自行选择需要组合的模块,系统针对用户的选择自动生成组合模块。评测系统对组合过程进行了如下约束:①组合模块的最后只能是一个输出。如“LR(0)自动机”、“SLR分析表”、“LR(0)分析表”这三个模块就不能组合,因为组合之后就存在SLR分析表、LR(0)分析表两个输出。②组合模块不能有跳跃性。如“LALR分析表”和“First集”这两个模块就不能组合,当然,这样的组合也没有实际意义。③组合模块中不能出现依赖冲突的模块。如“符号表”和“Follow集”模块不能组合,因为Follow集的依赖项First集需要符号表,但是符号表是用户实现的。这种组合形成了依赖冲突。

图2所示为组合模块页面,这里显示了一种组合的情况,当选择了“LR(0)自动机”、“SLR分析表”、“分析树”三个模块时,系统会将其组合成一个新的模块,输入为LR(0)自动机需要的数据,输出为分析树。

4.2评测方法的改进

一般的ACM在线评测系统只能评测输出结果唯一的程序,对不唯一的情况要使用额外手段进行正确性评价,如编写一段辅助测试程序进行评测。然而,“编译原理”中绝大部分模块产生的结果都是不确定或不唯一的,因此,简单地套用现有评测技术是无法实现编译程序的在线评测的。

在这里提出改进的评测方法,也是“编译原理”在线评测系统采用的评测方法。针对模块输出结果不唯一的问题,例如正则表达式转NFA,系统设计了两种有效的方法:一种是采用模块替换方法,将用户编写好的模块放入评测系统提供的整个框架中去编译执行,评价整个框架执行的最终结果;另一种方法是评测时从用户提交的模块开始执行,结合系统提供的后续模块继续执行至能够产生唯一结果的模块为止,这时的结果也就可以利用现有的评测技术进行评测。如NFA的等价性判断较为困难,当用户提交了NFA模块后,系统会使用其提供的已实现的框架,将其转化为DFA乃至最小化DFA,再进行评测。

当然这种方式对用户而言是透明的,用户体会到的是对其实现的模块进行了单元测试。

5结束语

实践表明,“编译原理”的实践教学中引入ACM在线评测为实践教学提供了新的方法和手段,是一个有益的探索。在线评测系统是一个很好的实践教学平台,通过这个平台,学生能够更好地将理论与实践紧密结合,动手能力、创造能力和协调能力会得到进一步提高。

参考文献:

[1] 郭嵩山,王磊,张子臻. ACM/ICPC与创新IT人才的培养[J]. 实验室研究与探索,2007,26(12):181-185.

[2] 武建华. 基于ACM模式的数据结构实践教学改革与探讨[J]. 计算机教育,2007(12):114-116.

[3] 教育部高等学校计算机科学与技术教学指导委员会. 高等学校计算机科学与技术专业实践教学体系与规范[M]. 北京:清华大学出版社,2008.