一种面向数组C程序的静态评分方法

2021-11-10舒新峰何孝敏郭芳瑶

西安邮电大学学报 2021年4期

舒新峰，何孝敏，郭芳瑶

(西安邮电大学计算机学院，陕西西安 710121)

C语言具备表达能力强、语法简洁紧凑以及执行效率高等特点，已广泛应用于操作系统和控制系统等各类底层软件开发中，是高校信息类专业普遍开设的必修课程。为了提升学生C语言编程能力，许多高校在C语言程序设计课程教学中打破传统的纸质作业和试卷的考核方式，引入“程序自动判定系统”对学生的作业和试卷进行计算机自动判定，通过考核手段改革引导学生强化C语言编写程序能力训练，并取得了良好的教学效果。数组是C语言广泛使用的一种数据类型，操作数组的方法和程序表达方式的多样性，给程序自动评分带来了困难。

栈返回地址保护[1-2]、数据追踪和插入检测代码[3]等动态评分方法可以应用于含有数组的C程序评分，但评测结果单一，只有0分或满分，不能很好地满足教学需要。静态评分方法主要是将源程序转化为系统依赖图[4]、控制流[5]和抽象语法树[6](Abstract Syntax Tree,AST)等中间表示形式，然后通过树或图的匹配算法[7]计算语句相似度进行评分。该方法虽然考虑了程序结构，但现有的中间表示形式不能准确表达程序语义及语句依赖关系，若数组空间大小不同或计算数组下标方式不同，则会导致误判，降低了评分的准确性。文献[8]将数组越界问题转化为下标变量取值的范围分析问题，利用抽象解释技术[9]进行数组越界的判定，但该方法对循环语句中数组的检测结果精度较低。

针对上述问题，拟提出一种面向数组C程序的静态评分方法。首先，对待判定程序进行预处理，构造抽象语法树，通过标准化算法消除程序的多样性，获取数组和变量的信息。其次，引入程序语句依赖图[10](Program Statement Dependency Graph，PSDG)描述语句之间的依赖关系。然后，对学生编写程序和答案程序的PSDG进行相似度匹配，通过数组下标访问检测和表达式等价识别方法修正误判结点。最后，根据相似结点所占比例计算程序分值。

1 程序预处理

AST是程序的一种中间表示形式，可以准确表达程序的语法结构，存储效率高，能方便地对其进行遍历和操作[11]。对待判定程序进行预处理，首先将待判定程序转化为AST，然后从AST中提取变量信息，便于后续使用，最后对程序进行标准化处理，消除因C程序表达多样性对评分结果带来的不利影响。

1.1 变量信息提取

通过GNU编译套件(GNU Compiler Collection，GCC)将待判定程序转化为AST。提取变量信息时，先定义好存储变量信息的数据结构，其形式化定义如图1所示。分别保存数组类型的变量Arr和其他类型的变量Var，vRange表示变量的取值范围，size表示数组的空间大小，pSet表示引用数组的指针变量，其中包括指针变量p_id和表示数组下标的变量var_id。

图1 变量存储结构的形式化定义

提取变量及数组信息的算法步骤如下。

步骤1新建arrList和varList两个表，分别用来存储数组变量和其他变量的信息。

步骤2遍历抽象语法树，寻找函数的变量结点Attr，通过type对变量类型进行判断：若为数组类型，则需记录数组名arrName和空间大小size；若为其他类型的变量，则记录变量的名称name和初始值value。

步骤3将数组变量信息添加到arrList中，将其他变量信息添加到varList中，其中vRange的值为value。

1.2 数组标准化

C程序中可以通过下标或指针引用一个数组元素，当指针变量引用数组时，该指针就获得了数组中某个元素的地址。虽然指针在程序中运行速度快，占用内存小，但在静态分析程序时无法直接确定指针指向数组中的具体位置，因此需要将指针对数组的操作标准化为数组下标的形式。

令arr表示任意n(n≥1)维数组，p表示指向n维数组的指针变量，ei(1≤i≤n)为任意整数表达式，数组标准化算法具体步骤如下，其他语句的标准化方法可参照文献[12]。

步骤1遍历待判定程序的AST，对于形如p=& arr[e1]...[en]的语句，将指针变量p的id添加到数组arr的指针变量表pSet的p_id中，并定义n个新下标变量index_1，...，index_n，初始值分别为e1，...，en，将这些下标变量的信息存储到变量表中，并将对应的id存入数组arr中pSet的var_id中。形如p=arr的语句做类似处理，区别在于所有下标变量初始值为0。

步骤2形如

p=*{...*[*(p+e1)+e2]+...}+en

的指针运算表达式，将其转化为数组下标的运算形式

index_1=index_1+e1，...，index_n= index_n+en

步骤3形如

*{*[...(*(p+e1)+e2)+...]+en}

的表达式，将其替换为数组元素访问的表达式

arr[index_1+e1] ...[index_n+en]

步骤4对于数组元素访问表达式arr[e1]...[en]，将其每个不是整型变量的下标表达式ei替换为新的临时变量ti，将ti加入变量表中，令ti=ei，并将原表达式替换为arr[t1]...[tn]。

以“冒泡排序”算法为例，源程序代码如图2所示。

图2 “冒泡排序”算法源程序代码

部分源程序转换为标准化后的抽象语法树结构如图3所示。图3中，arr表示数组类型，数组名为a，空间的大小为4。“p=a”表示指针变量p引用数组a，根据标准化规则定义了表示数组下标的变量index并赋初值为0。main函数循环结构中的单次表达式“i=0”被前提到循环之前，“*(p+i)”中首先定义临时变量t，然后将指针变量运算p+i转换为t= index+i，最后通过数组下标a[t]的方式访问数组中的元素。

图3 标准化后的部分程序语句的抽象语法树

2 程序评分方法

AST能准确表示程序的结构，但无法精确表达程序语句间执行的依赖关系，为了解决该问题，引入PSDG描述待判定程序的结构。含有数组的C程序评分方法，首先，构建程序的PSDG[11]，将学生编写程序和答案程序的PSDG进行匹配，划分相似结点集合和不相似结点集合。其次，通过表达式等价识别的方法对PSDG匹配过程中产生的误判结点进行消除，提高评分的准确性。最后，通过计算相似结点个数所占比例得到程序分值。

2.1 程序语句依赖图匹配

图匹配[13-14]的过程主要是图相似度计算的问题，PSDG为有向图，以待判定程序stuPSDG和答案程序teaPSDG的函数名结点main为起始点，通过图同构算法[15]和树的编辑距离算法进行结点间的匹配。PSDG匹配算法步骤如下。

步骤1消除变量名多样性。首先，对程序中的变量按照类型进行划分。其次，在程序语句依赖图中，对学生编写程序和答案程序按照变量类型进行结点间的匹配，若结点中所存储语句的结构相同，则将两个变量以二元组的形式加入集合varSet中，构成映射关系，表示这两个变量可以相互替换。最后，将没有映射关系的变量统一命名为unRecVar。

步骤2新建stuSet和teaSet两个集合，分别以学生编写程序和答案程序的函数名结点main作为起始点，找到对应的所有邻点并分别添加到集合stuSet和teaSet中。

步骤3将stuSet中的每个结点与teaSet中的所有结点相匹配，执行步骤4。stuSet中的所有结点都匹配完成后，执行步骤5。

步骤4匹配结点类型nodeType，若不同，则结束步骤4，否则，将结点中的变量按照varSet中变量之间的映射关系替换为teaSet中的变量。通过树的编辑距离算法对结点中的expTree进行匹配。若相似，则将两个结点以二元组的形式添加到集合sameSet中，否则，结束步骤4。

步骤5分别以stuSet中的结点stuNode和与之匹配的teaSet中的结点teaNode为起始点，深度优先搜索获取待匹配结点newstuNode和newteaNode，执行步骤4。若两个结点不匹配，则回溯。

步骤6将stuPSDG 中与teaPSDG不匹配的结点添加到unsameSet中。

2.2 误判修正

在PSDG的匹配过程中，若待判定程序和答案程序中部分语句语义相同，表示方式不同，则会造成结点误判，导致评分结果有较大的误差。例如，在“冒泡排序”算法中，若main函数调用sort函数时传递的第二个参数的值为3，则在sort函数中两个循环语句的条件控制表达式就分别变为“i

为解决该问题，首先分别以待判定程序stuPSDG和答案程序teaPSDG中含有数组的表达式结点为起始点，通过回溯进行变量替换，最终替换后的语句为关于数组下标变量的表达式。然后引入区间计算[16]的方法对变量取值范围进行运算，判断数组下标的取值范围是否超出数组空间大小，若未超出，则对含有数组下标变量的表达式进行等价识别，修正误判结点。定义var为任意变量，Expr为任意表达式，误判修正步骤如下。

步骤1遍历sameSet，找到含有数组表达式的结点，分别在stuPSDG和teaPSDG中确定其位置，以该结点为起始点回溯，对于形如var=Exp的语句，将数组下标表达式中的非下标变量var替换为Exp的形式，并对常量表达式进行计算，将替换的结点添加到repSet中，直到函数名结点为止，替换后的表达式表示为stuExpr和teaExpr。若含有复合语句，则从最内层开始进行表达式的替换，直到最外层的名称结点YES/NO为止。

步骤2确定取值范围。首先从变量表varList中获取结点中变量当前的取值范围valueRange，然后通过区间运算的方法对stuExpr中下标变量的取值范围进行计算并更新，最后通过步骤3判断取值范围是否合法。

步骤3在arrList中获取当前数组的长度size，与下标的取值范围vRange进行比较，若vRange未超过size，则执行步骤4，否则结束步骤3。

步骤4通过树的编辑距离算法比较stuExpr和teaExpr两者的相似度，若相同，表示stuExpr和teaExpr等价，执行步骤5，否则结束步骤4。

步骤5在unsameSet中查找是否存在repSet中的结点，若存在，则将其从unsameSet中删除，再添加到sameSet中。

2.3 评分

学生编写程序和答案程序通过程序语句依赖图匹配算法进行匹配后，将学生编写程序的PSDG中的结点划分为相似结点集合sameSet和不相似结点集合unsameSet，通过表达式等价识别的方法对unsameSet中的误判结点进行修正，最终，学生编写程序得分由相似结点集合中的结点个数sameNodeNum除以答案程序的PSDG中的结点个数teaPSDGNum，再乘以总分值Score得出。

3 实验

选取某高校2019届300位本科生的3道C程序作业题目作为实验对象，第一题为数组元素排序，第二题为环形打印二维数组，第三题为打印出所有的水仙花数，每道题目总分为10分，分别使用所提方法、北京大学程序在线评测系统(Peking University Online Judge，POJ)和基于AST的自动评分方法[13]计算学生编写程序得分，并与人工评分结果进行对比，验证所提方法的有效性。每道题目的平均分值如表1所示。

表1 不同方法对每道题目评分的平均分值

由表1可知，POJ需要编译运行程序，学生编写程序得分只有0分和10分两种形式，平均分值与人工评分的结果相差较大。基于AST的自动评分方法能够表达程序的语法结构，通过计算学生编写程序和答案程序的抽象语法树相似度进行评分，该方法在对不含有数组的程序评分时，评分结果与人工评分结果接近，但在对含有数组的程序进行评分时，评分结果与人工评分结果误差较大。所提方法首先通过PSDG精确表达了程序语句之间的依赖关系，然后通过区间运算和表达式等价识别的方法误判结点进行了修正，提高了评分的准确度，更接近人工评分结果。

以第二题为例，随机抽取50位学生的试题评测结果，计算所提方法和基于AST的程序自动评分方法与人工评分结果的误差率，计算表达式为

其中：E表示误差率；S表示使用不同方法评测学生编写程序的评分结果；T表示人工评分结果。评分误差率分布如表2所示。

表2 评分误差率分布对比

由表2可知，基于AST的评分方法的误差率主要集中在5%～15%之间，该区间的人数占总人数72%，且存在评分结果误差率为25%以上的试题，误差较高。这是因为，首先，该评分方法主要是根据学生编写程序和答案程序AST的相似度进行评分，没有考虑到学生编写程序中所定义的数组空间大小的不同及表达式的多样性表示给程序评分带来的问题。其次，没有考虑到因程序语句顺序不同给评分结果带来的影响。所提方法的误差率分布在0～25%之间，其中，误差率在10%以上的试题数量占总试题数量的18%，通过查看该部分试题，发现主要是因为学生只编写了部分关键程序，人工评分时会给与一定的分值，而所提方法依赖于程序语句依赖图的匹配和数组下标访问检测的结果，没有考虑程序语句分值的权重，导致评分结果与人工之间存在较大差异，82%的试题的误差率在0～10%之间，接近人工评分结果。因此，所提方法与POJ和基于AST的程序评分方法相比，评分结果的准确度更高。