C语言程序设计题自动评分算法的研究

摘要：目前主要的C语言上机考试系统程序设计题主要采用的是结果比对评分法，这种方法并不查看考生的程序内容，不能反映考生的真实水平并且有失公允。在比较结果的评分方法基础上，增加了修复编译评分与关键代码对比评分，使评分结果更加公正、准确，使评分结果更加接近于人工阅卷，具有很好的实用价值和应用前景。

关键词：C语言程序设计题；自动阅卷；编译原理；关键代码对比

中图分类号：TP312文献标识码：A文章编号：1009-3044(2011)07-1585-04

A Research on the Way of C Language Programming Automatic Judging

LI Qi

(School of Computer Science, Sichuan University of Science and Engineering, Zigong 643000, China)

Abstract: Most of C language automatically scoring systems are based on results compared for marking on programming problems, can't accurately and impartially mark students' real ability. In order to make the marking system more objective and justly, basing on the method of compare result, New system has been designed to combine the method of modification compiling and key codes comparing judging. A lot of testing and using in a limited scope have proved that the score approaches to the standard which artificially scoring，the system has a good practical value and application prospects.

Key words: C language programming; automatic judging examination paper; compile principle; key codes comparing

1 前言

1.1 国内外主观性试题测评技术研究现状和发展态势

C语言是国际上广泛流行的计算机高级程序设计语言，在各类高等院校的计算机及相关专业中，C语言均被列为一门必修的基础课程。当前对该课程的考评，通常采用人工命题笔试、人工改卷评分。这种方式需付出大量劳动，效率低下，且客观性受到任课教师水平、经验、个性甚至道德水准的影响。这种考试方式，显然已经不适应计算机教育发展的需要。利用计算机实现无纸化考试，已经程序计算机考试的一种重要方式。

目前对于主观题中的一些题型，如Windows操作题、Word文字录入题、Excel表格处理题的自动阅卷技术，已经取得一些重要进展，但对主观题中的重要一类，程序设计题的自动评阅，目前还处于探索阶段。

1.1.1 国内情况

1) VB程序设计考核自动评阅系统

该系统由段汉周等研制，实现了对Visual Basic程序设计上机考核进行实时自动评阅的功能，该系统判断程序主要依据是用户程序是否达到或具备预先要求的功能，而程序内部的逻辑程序复杂度以及用户编程的灵活性等等并不是考核的目的，没有通过编译或者不能运行的程序属于完全错误。如前所述，这种方法也存在较大不合理性。

2) VFP表单计算机阅卷系统

该系统所探讨的是计算机二级等级考试由面向过程的程序设计转向面向对象的程序设计后VFP表单题型的计算机自动阅卷技术，针对VFP表单题型，采用自动读取表单上各对象的属性、自动触发可能符合题意的事件、判断事件触发后界面控件的显示值是否正确的方法，来实现的计算机自动阅卷。该方法是专门针对VFP表单题型设计的，有一定的局限性。

3) 全国计算机等级考试二级、三级上机考试系统

该系统采用的是结果比较，系统将考生程序的运行结果保存在指定的文件中，通过将考生程序的结果文件与标准答案文件作对比判定考生程序的对错。程序结果正确为满分、反之为零份。评分时不管程序内容，只依赖与运行结果，0分或满分的极端现象较多，在这种评分机制下，程序中一个小小的错误就将导致一个几近正确的程序无法运行或结果全部错误，考生将丢失全部分数。这与传统阅卷中的评分原则是不相一致，评分结果不能反映考生真实水平，存在很大的不合理性。

1.1.2 国外情况

1) 基于计算机的可迁移技能测评

该项目由英国东英格兰大学信息系统学院Roy Dowsing，Siew-and Long & Roman Sleep等人承担，英国高等教育基金会资助，主要对计算机字处理和电子表格的应用的辅助评测进行研究，项目主要成果是研制出关于字处理和电子表格应用的CAA系统“WordTask”和“SpreadTask”。从实际应用来看WordTask和SpreadTask效果良好，但也存在一些问题：采用字符串匹配法，完全依据的是结果信息，不适用于大多数评测场合；测评模型过于简单，缺乏一般性，对于其他类型的测评来说，借鉴意义不大。

2) A Software System for Grading Student Computer Program

该系统是英国利物浦大学研制的一个利用计算机对学生编写的程序在正确性、效率、风格、复杂性及容错性等方面进行自动评价，且可对给定程序产生一份评价报表，对程序进行评分。

3) 美国测试系统有限公司（简称ATA）的相关研究

ATA公司是国际上较有影响的考试技术服务公司他们开发了一种基于动态仿真技术的、专门用于TT技能考核的自动测评系统。其优点是：系统运行稳定，而且很容易获取与被试操作过程相关的信息。但是，由于很难对Word，Excel等应用软件从功能实现到操作方式进行完全仿真，因而将在一定程度上影响该系统的测试信度和效度。这种仿真系统的另一个缺点是对测评内容的适应性较差，考试内容要事先提交给公司去制作，用户不能命题。

综合国内外的研究及应用情况看，虽然有一些成果，提出了一些解决方法，但就目前情况看仍没有一个在动态测试或正确性检验方面比较成熟的程序题自动测评系统[9-14]。

2 C语言程序设计题自动评阅流程设计与实现

目前的很多自动化评分系统仍采用的是按结果评分的策略，这种评分方法，对整个程序基本正确仅因为个别小错误（如遗漏一个符号使程序不能编译运行），造成整个程序不得分，是有失公平的和不合理的。经过大量的调查和深入的研究，我们提出了结果对比评分、修复编译评分和关键代码对比评分相结合的程序设计题评分策略。

2.1 程序设计题自动评阅流程设计

程序设计题的评阅的整个过程包括：生成考生源程序文件、使用TCC编译链接程序、程序运行及控制（包括死循环处理）、程序运行结果对比、修复编译评分、关键代码对比评分。

具体步骤如下：

1) 对考生源程序进行编译连接，如果能正常运行并能产生结果文件，则将其运行结果与标准答案文件进行对比。与标准答案文件内容完全相同，则说明结果正确，得满分。如果结果部分对比正确，则按比例给分。如果得分为极端分（0分）或分数太低，则转入静态评阅，进行代码对比评分。若程序不能编译通过，无法运行产生结果文件，则转入修复编译评分。

2) 考生程序不能通过编译产生结果，说明考生程序存在语法错误，则转入一下修复编译过程继续处理：

① 对考生源程序进行词法分析。扫描源程序，对代码中的单词进行分析，识别各个单词的类型（常量，变量，关键字等）并保存到一个Token链表

② 根据词法分析的结果，再对考生程序进行语法分析，找出其中的语法错误并进行修正。如果修改次数过多，得分已经太低，则转入静态评阅。如果修改后程序能正常运行并生成结果文件，则进行结果对比评分，并根据修改次数给予适当扣分。如果仍不能编译通过，则转入静态评阅。

3) 静态评阅。静态评阅就是读取考生源程序文件的关键字（词、表达式或语句），对考生程序进行检测。根据检测出的关键字的条数判断程序的逻辑合理性，给出相应的分值。

2.2 程序设计题自动评阅的实现

2.2.1 生成源文件

根据用户需要及对需求分析的深入分析研究，本系统的程序设计题考试方式采用与全国等级考试相同的方式，即由考生完成部分程序代码（通常是一个关键性函数）。对于这种形式，需要从数据库中读取程序的非考生填写部分的代码，将其和考生答案拼合成一个完整的程序文件才能正确执行。

对于这种方式的处理办法是：在数据库中预留两段程序存储空间，由录题老师将非考生填写代码的前段和后段存入其中。在生成文件时，由系统将这两部分代码和考生文件连接就成了一个完整的程序文件。

这里的代码前段和后段是指用于后台评分测试用的，通常要涉及到存放输入数据文件in.dat和输出数据文件out.dat的打开和关闭。这与在前台考试界面中显示在学生考试界面中的前段和后段程序代码并不一定一致。

2.2.2 编译连接程序

1) 编译环境的构建。

将一个程序源文件编译成一个可执行文件，除了正确组成源程序外，还需构建编译的环境。本系统的处理方法是通过MS SqlServer的扩展存储过程Xp_CmdShell调用Tcc命令实现。

2) 判断编译是否成功的方法

编译是否成功可通过判断是否生成了可执行文件名来确定，跟据C程序的编译原理，名为X.c的源文件编译成功后会生成X.obj文件和X.exe的目标文件，可通过判断编译之后是否有X.exe文件来确定编译是否成功，而判断文件是否存在可用Asp的Fso.FileExists方法。

2.2.3 程序的运行

运行程序必需要在考生源程序文件编译成功生成了可执行文件的前提下进行。程序的运行所涉及到的问题也很多，它包括程序的执行、死循环处理等。

1) 执行程序

执行待评程序也是通过Ms SQLServer的扩展存储过程Xm_CmdShell调用程序实现，同时，通过“>>”重定向符，将屏幕输出的内容重定向到输出文件中去。

2) 死循环的处理

对于考生程序出现死循环的问题，系统采用的双线程的方法来处理。一个线程执行考生程序，别一个线程执行计时程序，任何一个线程执行完毕就立刻退出程序。对于计时线程的编写使用的是API函数WaitForSingleObject。

2.2.4 程序运行结果对比

将学生程序运行的结果与标准答案进行对比的方法是将考生答案从输出文件中读取出来存放到一个字符串中，再从数据库从读出标准答案，通过对比它们的相似度来获得得分结果。

如果只是简单的将两个字符串逐个比较，那么得出来比较结果是不科学的，例如标准答案是1 2 3，而学生答案是21 2 3，其第一个关键字错误但后两个是正确的，但逐个比较的结果相似度却是0。对于这种情况，系统处理的方法是用ASP的Split函数，把学生答案拆开成多个关键词，同时也把标准答案用同样的方法拆开，这样再逐个进行比较就不会出现刚才的问题。

同时，考虑到学生程序自由度比较大，如果学生输出答案不规范，比如说标准答案仍是1 2 3，而学生答案输出出现友好提示等附加内容，例如The answer is 1 2 3，虽然学生答案原则上是对的但却因为友好提示而得0分。

经过对C语言考试的程序设计题的研究分析，得知C语言程序设计题答案一般只含有数据不含文本，含文本的不含数据。由此系统采用如下方法处理：

① 首先设定程序设计题的输出结果的标准答案都严格为只含有数据或只含文本。

② 对于学生输出结果关键字，如果和标准答案关键同时为数字或同时不为数字即为有效关键词，否则视为无效关键词，此判断通过ASP的数值判断函数IsNumberic函数来实现。

③ 在对比结果时将考生答案与标准答案都拆成一个关键词数组，将数组元素逐个比较，如果遇到无效关键词，则考生数组游标自增一位。

对于语法错误编译通不过或无运行结果的，可采用修复编译评分（词法和语法分析改错）和关键代码匹配法来进行进一步的处理。

2.2.5 修复编译评分

一个考生的程序不能通编译，并不一定表示该考生的程序存在很大的错误，其原因可能仅仅是漏掉了一个分号或者无意输错了一个字母。修复编译的目的，不是试图纠正考生程序中的所有语法错误，而是修复考生常出现的一些导致程序不能编译的小错误，使之能编译运行，然后给出一个合理分数。

经过大量的调查分析，得知考生常犯的导致程序不能编译的小错误主要是遗漏界符、变量名或函数名输入错误等。这些错误编译过程中会出现株连错误，如果去试图修复每一处报错的地方，往往会造成更严重的错误。因此，本系统的编译修复程序每次只修改一个输入错误，修改后再次进行编译。这种方法也利于改错计数并扣分。如果修复编译的次数达到一定次数，则放弃修复进行关键代码比较计分。这种设计，也有利于提高评阅效率。

修复编译程序是一个专门设计的C语言编译器，这个编译器编译的部分是标准C语言编译器的一个字集，但是它具有一定修复考生程序常见错误，并能生成新较为正确的程序代码的能力。

以下是该修复编译程序处理过程与关键技术的简述。

1) 词法分析

这一步骤主要对代码中的单词进行分析，识别各个单词的类型（常量，变量，关键字等）并保存到一个Token链表中，这个链表就是源程序的一个词性解释。在进行词法分析的过程上还会检查到程序的词法错误，出于容易实现的考虑，在这个阶段并不进行词法修复。

词法分析的任务主要是识别程序中各个单词的类型的值。经过对程序的扫描，将各个单词识别后保存到该结构体变量中，然后将各个结构体变量连成一个链表，则形成了代码的词性说明形式，供语法分析使用。另外还需将识别出的已定义标识符名和C语言保留字保存在链表中，这些链表可以用于在语法分析时检查一个标识符是否正确声明。如果未声明即表明该标识符可能存在输入失误。

2) 语法分析

语法分析旨在根据C语言的方法分析词法分析生成的Token链表中的单词组合是否符合C语言的语法，如果不合法则判断错误位置并尝试修正。在本方法中主要用语法分析检查和修正分号遗漏、标示符未定义等错误，因为这些错误的修正是比较可行的，而且是考生最常犯的小错误。本系统中采用的LR分析法。

下为遗漏“;”号错误的处理过程。当发现遗漏“;”时，定位出错的位置（在某个单词后），然后向该单词后插入一个“;”号，如图1所示。

如果发现程序中出现未定义的标识符，那这个标识符很可能是由于考生输入失误而把变量名、函数名或关键字弄错。这种情况的修正策略是查找关键字表和已定义的标示符表，如果发现相似度很高的（通常这种情况考生只会错、漏、多了一个字母）单词则将其替换，再进行编译。

2.2.6 关键代码对比评分

程序经过编译修复仍然未能编译没通过，或者是结果对比得分太低，如果此时就给考生程序很低的分数甚至是零分显然是不合理的。因此这样的程序也可能存在一定的逻辑准确性。处理的方法是对考生程序进行关键代码对比。首先，由编题的教师在题库数据库中实现存放好适量的正确关键代码（语句、单词等），评分时，系统通过查找考生程序中这些关键代码的数量，给出一个比较合理的分数。

C语言程序书写格式多种多样，同一段程序可以用不同有的风格书写，程序中定义的变量名也随考生个人喜好有所不同，而且书写时会出现有无空格之类的区别，同样功能的程序编写方法千变万化，直接使用字符匹配方法显然存在很大的不合理性。经过对C程序语法等特性的研究，在自动评阅方法中采用正则表达式来表示一程序中的关键算法，例如实现1-10的整数求和程序段的通用句式可表示为：

int @VAR@; for( int @VAR@ = 1; @VAR@

这种形式可以表示上述程序的核心算法，而且具有通用性。

3 结束语

基于上述C语言程序设计题自动评阅方法的C语言考试系统已应用于实际教学和教学辅助网站。经过大量测试和使用，程序设计题的自动评分可全部实现。对于正确的考生程序，能100%的准确评分，对于存在错误的考生程序，评分结果接近人工评分标准，准确率在90%左右，避免了不合理极端分数的出现，完全可以在实际考试中使用。

此C语言程序设计题自动评阅方法，也可应用各种将C语言列入考试科目的各类计算机考试，如全国计算机等级考试二级、三级C语言上机，省二级C语言考试和国家程序员考试等，具有很好的应用和推广价值。

参考文献：

[1] 黄思先.程序设计填空题的自动评分[J].福建电脑,2003(7):26～27

[2] 段汉周,凌捷,郑衍衡.Visual Basic程序设计考核自动评阅系统中若干问题的研究[J].计算机工程,2001,27(4)167-168.

[3] 吴晓辉.VFP表单计算机阅卷系统[J].福州大学学报:自然科学版,2001,29(增刊)91-94.

[4] 何克抗,许骏.计算机辅助测评（CAA）研究新进展一技能性非客观题的自动测评[J].开放教育研究2005(2):78-83.

[5] 王春霞.自动阅卷系统的开发[J].盐城工学院学报:自然科学版,2002(1):47-49

[6] Joy M,Luck M.The BOSS System for On-line Submission and Assessment[J].Journal of the CTI Centre for Computing,1998(10):27-29.

[7] 邵晨辉,陈玉泉,徐良贤.基于题目反应理论的机助自适应考试系统[J].计算机工程,2000(11):161-163.

[8] CHEN J,Subramaniam S.Specification-based Testing for GUI-based Applications[J].Software Quality Journal,2002(10):204-224.

[9] Ajiro Y,Kima K U.An Automated Error Correction System for Concurrent Logic Programs[J].Automated Software Engineering.2002(9):67-94.

[10] 马航飞.基于B/S模式的在线考试系统ASP实现方案[J].中国西部科技,2005(11):15-16.