C语言中函数的结构比较

阎萍

摘要：针对C语言中函数间的结构比较问题，描述了通过分解函数的结构得到函数的结构字符串表示的方法，给出了两个函数的结构串间公共串的计算方法，定义了函数间的结构相似度，有助于函数根据结构进行分类。

关键词：C语言；函数；结构字符串；结构相似度

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2014）26-6093-03

Abstract： In view of the structure comparison problem between functions in C language， the structure string representation method is described by decomposition structure of function， the calculating method of the public string between two function structure strings is given， and the structure similarity between two functions is defined. It is helpful for function to be classified according to the structure.

Key words： C-language；function；structure string；structure similarity

C语言是一门很重要的基础性的程序设计语言，在实际的实验教学考试中，经常遇到给定其它函数，只要求学生写出另外一个函数的实现代码的情况。为了评价学生代码的正确性，通常需要先将学生所写的函数与作为参考答案的函数代码的结构进行比较，只有在满足函数结构相似的情况下，才会对函数的字符内容进行进一步的评价，从而方便对学生提供的函数的源代码进行分类处理，为此就需要对函数的代码进行相似性分析，正如文献[1]所指出的，一个良好的源代码相似程度分析系统有助于教师把多份学生作业按照相似程度进行分类，从而发现对于一道题目学生有多少种不同的解法。该文考虑任意两个函数的结构比较和结构相似性度量，对函数代码做静态分析。

1 函数的结构表示

1.1描述函数结构的字符和函数的结构分解

假设C语言程序的结构采用一个字符串表示，称为程序结构串，并且假设用于表示结构的字符有：e表示表达式，s表示语句，b表示块，f表示函数，k表示关键词，n表示变量名和函数名，c表示常量，o表示语句的结束符，l1、r1分别表示左、右小括号，l2、r2分别表示左、右大括号，p表示算符，e是p的操作数，p0表示程序，空字符是一个常量c，程序结构串是一个含e、s、b、f、p0的字符串。其后不跟左括号的结构字符e、s、b、f、p0是待分解的结构字符，通过对它们所代表的程序字符子串，按成分由大到小进行结构分解，可以得到一个程序结构串，初始为p0，代表源程序字符串，每步分解记为：结构字符（子结构字符串）形式，并替换掉当前程序结构串中那个待分解的结构字符，经过多步分解后得到最终的程序结构串，于是程序结构串就是由结构字符和左右括号形成的符号串。当e、s、b、f、p0不再作结构分解时，表示为e（）、s（）、b（）、f（）、p0（）。特别地，当我们只考虑函数的结构分解和结构串的表示时，只须对代表函数的结构字符f逐步做结构上的分解。由于函数中可能含有表达式e、语句s、块b等不同成分，因而，函数的结构字符串是一个含结构字符f、e、s、b的字符串。经过对函数结构的多步分解后得到最终的函数结构串。函数中空语句S0是只有一个分号的语句，其结构串记为g（S0），即为“s（o）” ；如果是单分支语句“if e s” 则需要补齐少掉的分支，假设该语句相应的结构串为s（g），其中g是一个结构串，空的右分支相应的结构串认为是s（），则语句结构串理解为单分支时为s（g），而理解为两分支时为：s（s（g）s（）），这样做不会影响程序的执行。这里假设用g（F）表示函数名为F的函数经过结构分解后得到的结构字符串。

1.2分解函数的组成成分所遵循的文法规则

3 结束语

通过计算两个函数的结构相似度，可以有助于选择出作为参考答案的教师函数，确定函数的归类。如果有两个函数F1，F2均可作为答案去评价学生提供的函数F，作为参照标准的教师函数F1，F2，如果Sim（F1，F）≥Sim（F2，F），则采用F1会比采用F2作为参照标准去评价学生函数F的结构更好，因为F1与被评价函数F的结构更相似，从而函数F归为F1这一类会更好一些。在此基础上，为进一步度量学生函数的字符内容的正确性，提供了可供参考的依据。正如文献[3]中指出的，学生代码的结构分析，也是设计程序作业评价系统时应考虑的重要功能，当自动评估程序作业时，测试程序的结构和检测抄袭是重要的。分析C语言中函数的结构，有助于对一些小的程序作业作一些自动评价，这是因为在实际学习程序的过程中，学生通常写简单的函数而不是整个程序。

参考文献：

[1] 陈新.基于程序控制流图源代码相似程度分析系统[J].计算机系统应用，2013，22（3）：144-147.

[2] Andrew Walenstein，Mohammad El-Ramly，James R Cordy，et al.Similarity in Programs[C]//Rainer Koschke and Ettore Merlo and Andrew Walenstein. Duplication， Redundancy， and Similarity in Software. Dagstuhl， Germany：Internationales Begegnungs- und Forschungszentrum fuer Informatik （IBFI）， Schloss Dagstuhl， Germany，2007.

[3] Riku Sikkonen，Lauri Malmi，Ari Korhonen.Fully Automatic Assessment of Programming Exercises[C].Proceedings of the 6th annual conference on Innovation and technology in computer science education.New York，USA： ACM，2001：133-136.