编译原理理论在C程序题自动评分系统中的应用

赵 晓， 刘学锋， 王晓霞

(1.陕西科技大学电气与信息工程学院， 陕西 西安 710021； 2.西安飞机工业有限责任公司， 陕西 西安 710089)

0 前言

众所周知，C语言的学习，不但要加强理论知识的学习，更要注重学生实践应用能力的培养，而在采用已有上机考试环境对C语言考核时，大多数仅涉及选择题、填空题和程序改错题，对程序设计题自动评分主要采用的是结果评分法.这种评分机制显然是不科学、不公平的，程序由于一个很小的错误就将导致一个几近正确的程序无法运行，从而考生将丢失全部分数.这一评分结果自然不能反映出考生的真实水平，而且与传统人工阅卷中的评分原则是不相一致的.作者结合所在学校陕西科技大学的教学实际情况提出了一种基于编译原理理论的C程序题自动评分算法，在比较结果的评分方法基础上设计了动态评阅与静态评阅相结合的方法，使得评分结果更加公正、准确.

1 编译原理的理论基础

1.1 词法分析与语法分析

依据编译原理的理论知识，编译原理的第一个阶段词法分析是将源程序进行扫描和分解，识别为一个个的单词，并生成TOKEN文件；在语法分析阶段将词法分析程序生成的TOKEN文件用作语法分析的输入数据，以确定整个输入程序是否构成语法上正确的“程序”[2].这一阶段是编译原理的核心部分，基于这一理论基础本文提出了实现C程序题的自动评分系统.

在语法分析阶段应尽量发现更多的语法错误，并指出各错误的位置，还要对错误进行相关处理.语法分析中的错误处理遵循以下原则：

(l)发现错误并校正错误，校正的目的是为了使语法分析能进行下去；

(2)使错误局部化，使语法分析程序跳过的语法成分最小；

(3)准确报错，减少重复信息与株连信息.

1.2 正规表达式

正规表达式(Regular Expression)是指一个用来描述或者匹配一系列符合某个句法规则的字符串的单个字符串.在很多文本编辑器或其他工具里，正规表达式通常被用来检索或替换那些符合某个模式的文本内容，许多程序设计语言都支持利用正规表达式进行字符串操作.基于正规表达式在处理动态文本时具有的灵活性，本系统借助其实现程序的静态评阅.

例如，要检查一个程序中的for语句，常用形式为：for(express1；express2；express3)，用正规表达式可以有效地表示，其形式如下：

for(([∧;]*)?;([∧;]*)?;([∧;]*)?;)

在表达式中，用问号标记的分组是可选的，刚好能够准确的表达原意.

输入和输出语句所对应的正规表达式表示如下：

scanf(”(%d(,%d)?”,&w+,(?(1)(,&w+)))

printf(”(%d(,%d)?”,w+,(?(1)(,w+)))

因为篇幅所限其他知识要点的正规表达式的表示形式不再一一描述.

利用正规表达式描述程序的得分知识要点，在自动评分系统中进行匹配的方法具有灵活性、动态且准确度高的特点.

图1 阅卷流程图

2 系统的实现

2.1 程序评阅的流程图

程序评阅的基本思路为：在比较结果的评分方法基础上，将动态评阅与静态评阅相结合实现自动评分系统.具体过程是：如果学生有上交的程序，则首先编译、运行程序，如果运行成功则得满分，否则借助算法进行动态评阅并对错误进行修改和记录，如果可以编译、运行程序则根据存在的错误情况适当扣分；如果动态分析后程序仍不能编译、运行则采用静态分析法直接对程序代码进行分析，即知识要点的分析，依据答对的知识要点给出相应的分数.程序题的阅卷流程图如图1所示.

2.2 评阅实现的核心步骤

2.2.1 结果比对

利用数组定义一组测试数据，分别执行程序，并将执行结果和答案进行比对，如果都正确则给出满分的成绩，否则转到下一级的评判.

2.2.2 动态评阅

当考生的程序不能成功运行时说明程序存在语法错误，自动评阅转到动态评阅处理.动态评阅的实现依据编译原理的词法分析和语法分析，对考生程序进行以下的处理：

(1)对考生源程序进行词法分析.扫描源程序，生成TOKEN文件.

(2)根据TOKEN文件进行语法分析.在保证不对考生程序正确部分产生破坏的前提下，尽最大可能将考生程序修改正确，生成修改后的TOKEN文件，并保存错误文件.

(3)调用转换程序将修改后的TOKEN文件生成新的与原程序不同的考生程序.

(4)调用TCC程序以命令行方式对新程序进行编译连接.

(5)编译连接成功，运行新程序的执行文件，并调用API函数控制程序运行，以防由于死锁的发生导致系统崩溃；编译失败则退出动态评阅过程，转为静态评阅.

(6)对新程序的运行结果进行检测，若有结果，则转去进行结果比较，若无结果则转去进行静态评阅.

2.2.3 静态评阅

对于不能编译运行的考生程序，本系统依据正规表达式描述的知识要点进行匹配.知识要点分析的主要思想是：在录入考试题目要求的同时将考题答案所对应的知识要点一并录入，在考生所提交的答案不能正常运行时，用知识要点数据表中的知识要点信息和考生答案 进行匹配，以评判考生程序答案中是否包含了考试所要求的知识要点信息.

知识要点分析的匹配算法如下：

第一步：调入并打开考生程序文件；

第二步：读出文件中的题号；

第三步：根据题号打开知识要点信息表，获取知识要点信息数据；

第四步：对考生程序进行预处理；

第五步：逐条对考生程序和相关知识要点信息进行匹配，直到该题对应的要点信息数据表结束.

3 结束语

本文在结果对比的评分基础上，设计并提出了动态评阅与静态评阅相结合的程序题评阅方法，其中静态评阅的实现借助正规表达式，使得评分结果更加准确、公平.动态评阅方法的引入避免了多数考生因编程中的很小失误而导致大量丢分的问题；而通过静态检查，可根据程序中的知识点数给出相应分数，即使错误严重或结果不正确的程序也能得到应得的分数，使评分结果更加接近于人工阅卷.整个算法的实现原理是编译原理知识，因为编译原理的知识比较成熟，所以本系统通过实际的测试表明评分的准确性非常高，而且避免了人工评阅因主观因素而出现的偏差.

[1]谭浩强. C程序设计(第三版)[M]．北京：清华大学出版社，2005．

[2]陈火旺. 程序设计语言编译原理(第三版) [M]．北京：国防工业出版社，2004.

[3]孙 坤. C语言上机考试及自动评分系统的研究与实现[D]．沈阳：沈阳工业大学硕士学位论文，2005.

[4]贾电如，李阳明.基于语句结构及语义相似度计算主观题评分算法的研究[J].信息化纵横， 2009，(5)：5-7.

[5]朱征宇，苑昆峰.一种基于最大权匹配计算的信息检索方法[J].计算机工程与应用，2007，43(33)：176-179.