基于动态检测与静态分析的自动评分方法研究

Research on automatic scoring system of programming questions based on dynamic detection and static analysis

为了给C语言编程题进行合理评分,本文提出了一种新型的自动评分方法,在动态检测阶段先利用KMP算法执行关键字匹配,若匹配相似度落入预期值区间,则将学生源程序转换为可执行文件,通过预先设置的测试用例来驱动评分;若关键字匹配未通过、程序无法运行或者运行期间出现异常,则执行静态分析。静态分析阶段选取控制结构作为静态评分的关键因素,采用抽象语法树作为源代码的中间转换形式,并对其标准化以消除代码语义的多样性;根据抽象语法树中的结点类型提取出控制结构子树;最后,利用基于结点权值的树编辑距离算法来匹配标准化后的学生源程序与模板程序的控制结构子树,计算相似度并给出综合评分结果。实验结果表明,该方法能够对程序进行合理有效地评分,并且具有较高的准确率。

This article proposes a new type of automatic grading method to reasonably grade students’C language programming questions.In the dynamic detection stage,the KMP algorithm is used to perform keyword matching first.If the matching similarity falls within the preset value range,the student source program is converted into an executable file,and then the score is driven by the preset test cases.Perform static analysis when the keyword match fails,the program cannot run,or an exception occurs during operation.In the static analysis stage,the control structure is selected as the key factor of the static scoring.The abstract syntax tree is used as the intermediate conversion form of the source code,and it is standardized to eliminate the diversity of code semantics.Then,the control structure subtree is extracted from the node type in the abstract syntax tree Finally,use the tree edit distance algorithm based on node weights to match the standardized control structure subtrees of the student source program and the template program,calculate the similarity,and give a comprehensive scoring result.The final experimental results show that this method can reasonably score student programs and has a high accuracy rate.