閻萍

摘要：針對(duì)C語(yǔ)言中函數(shù)間的結(jié)構(gòu)比較問(wèn)題，描述了通過(guò)分解函數(shù)的結(jié)構(gòu)得到函數(shù)的結(jié)構(gòu)字符串表示的方法，給出了兩個(gè)函數(shù)的結(jié)構(gòu)串間公共串的計(jì)算方法，定義了函數(shù)間的結(jié)構(gòu)相似度，有助于函數(shù)根據(jù)結(jié)構(gòu)進(jìn)行分類。

關(guān)鍵詞：C語(yǔ)言；函數(shù)；結(jié)構(gòu)字符串；結(jié)構(gòu)相似度

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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語(yǔ)言是一門很重要的基礎(chǔ)性的程序設(shè)計(jì)語(yǔ)言，在實(shí)際的實(shí)驗(yàn)教學(xué)考試中，經(jīng)常遇到給定其它函數(shù)，只要求學(xué)生寫出另外一個(gè)函數(shù)的實(shí)現(xiàn)代碼的情況。為了評(píng)價(jià)學(xué)生代碼的正確性，通常需要先將學(xué)生所寫的函數(shù)與作為參考答案的函數(shù)代碼的結(jié)構(gòu)進(jìn)行比較，只有在滿足函數(shù)結(jié)構(gòu)相似的情況下，才會(huì)對(duì)函數(shù)的字符內(nèi)容進(jìn)行進(jìn)一步的評(píng)價(jià)，從而方便對(duì)學(xué)生提供的函數(shù)的源代碼進(jìn)行分類處理，為此就需要對(duì)函數(shù)的代碼進(jìn)行相似性分析，正如文獻(xiàn)[1]所指出的，一個(gè)良好的源代碼相似程度分析系統(tǒng)有助于教師把多份學(xué)生作業(yè)按照相似程度進(jìn)行分類，從而發(fā)現(xiàn)對(duì)于一道題目學(xué)生有多少種不同的解法。該文考慮任意兩個(gè)函數(shù)的結(jié)構(gòu)比較和結(jié)構(gòu)相似性度量，對(duì)函數(shù)代碼做靜態(tài)分析。

1 函數(shù)的結(jié)構(gòu)表示

1.1描述函數(shù)結(jié)構(gòu)的字符和函數(shù)的結(jié)構(gòu)分解

假設(shè)C語(yǔ)言程序的結(jié)構(gòu)采用一個(gè)字符串表示，稱為程序結(jié)構(gòu)串，并且假設(shè)用于表示結(jié)構(gòu)的字符有：e表示表達(dá)式，s表示語(yǔ)句，b表示塊，f表示函數(shù)，k表示關(guān)鍵詞，n表示變量名和函數(shù)名，c表示常量，o表示語(yǔ)句的結(jié)束符，l1、r1分別表示左、右小括號(hào)，l2、r2分別表示左、右大括號(hào)，p表示算符，e是p的操作數(shù)，p0表示程序，空字符是一個(gè)常量c，程序結(jié)構(gòu)串是一個(gè)含e、s、b、f、p0的字符串。其后不跟左括號(hào)的結(jié)構(gòu)字符e、s、b、f、p0是待分解的結(jié)構(gòu)字符，通過(guò)對(duì)它們所代表的程序字符子串，按成分由大到小進(jìn)行結(jié)構(gòu)分解，可以得到一個(gè)程序結(jié)構(gòu)串，初始為p0，代表源程序字符串，每步分解記為：結(jié)構(gòu)字符（子結(jié)構(gòu)字符串）形式，并替換掉當(dāng)前程序結(jié)構(gòu)串中那個(gè)待分解的結(jié)構(gòu)字符，經(jīng)過(guò)多步分解后得到最終的程序結(jié)構(gòu)串，于是程序結(jié)構(gòu)串就是由結(jié)構(gòu)字符和左右括號(hào)形成的符號(hào)串。當(dāng)e、s、b、f、p0不再作結(jié)構(gòu)分解時(shí)，表示為e（）、s（）、b（）、f（）、p0（）。特別地，當(dāng)我們只考慮函數(shù)的結(jié)構(gòu)分解和結(jié)構(gòu)串的表示時(shí)，只須對(duì)代表函數(shù)的結(jié)構(gòu)字符f逐步做結(jié)構(gòu)上的分解。由于函數(shù)中可能含有表達(dá)式e、語(yǔ)句s、塊b等不同成分，因而，函數(shù)的結(jié)構(gòu)字符串是一個(gè)含結(jié)構(gòu)字符f、e、s、b的字符串。經(jīng)過(guò)對(duì)函數(shù)結(jié)構(gòu)的多步分解后得到最終的函數(shù)結(jié)構(gòu)串。函數(shù)中空語(yǔ)句S0是只有一個(gè)分號(hào)的語(yǔ)句，其結(jié)構(gòu)串記為g（S0），即為“s（o）” ；如果是單分支語(yǔ)句“if e s” 則需要補(bǔ)齊少掉的分支，假設(shè)該語(yǔ)句相應(yīng)的結(jié)構(gòu)串為s（g），其中g(shù)是一個(gè)結(jié)構(gòu)串，空的右分支相應(yīng)的結(jié)構(gòu)串認(rèn)為是s（），則語(yǔ)句結(jié)構(gòu)串理解為單分支時(shí)為s（g），而理解為兩分支時(shí)為：s（s（g）s（）），這樣做不會(huì)影響程序的執(zhí)行。這里假設(shè)用g（F）表示函數(shù)名為F的函數(shù)經(jīng)過(guò)結(jié)構(gòu)分解后得到的結(jié)構(gòu)字符串。

1.2分解函數(shù)的組成成分所遵循的文法規(guī)則

3 結(jié)束語(yǔ)

通過(guò)計(jì)算兩個(gè)函數(shù)的結(jié)構(gòu)相似度，可以有助于選擇出作為參考答案的教師函數(shù)，確定函數(shù)的歸類。如果有兩個(gè)函數(shù)F1，F(xiàn)2均可作為答案去評(píng)價(jià)學(xué)生提供的函數(shù)F，作為參照標(biāo)準(zhǔn)的教師函數(shù)F1，F(xiàn)2，如果Sim（F1，F(xiàn)）≥Sim（F2，F(xiàn)），則采用F1會(huì)比采用F2作為參照標(biāo)準(zhǔn)去評(píng)價(jià)學(xué)生函數(shù)F的結(jié)構(gòu)更好，因?yàn)镕1與被評(píng)價(jià)函數(shù)F的結(jié)構(gòu)更相似，從而函數(shù)F歸為F1這一類會(huì)更好一些。在此基礎(chǔ)上，為進(jìn)一步度量學(xué)生函數(shù)的字符內(nèi)容的正確性，提供了可供參考的依據(jù)。正如文獻(xiàn)[3]中指出的，學(xué)生代碼的結(jié)構(gòu)分析，也是設(shè)計(jì)程序作業(yè)評(píng)價(jià)系統(tǒng)時(shí)應(yīng)考慮的重要功能，當(dāng)自動(dòng)評(píng)估程序作業(yè)時(shí)，測(cè)試程序的結(jié)構(gòu)和檢測(cè)抄襲是重要的。分析C語(yǔ)言中函數(shù)的結(jié)構(gòu)，有助于對(duì)一些小的程序作業(yè)作一些自動(dòng)評(píng)價(jià)，這是因?yàn)樵趯?shí)際學(xué)習(xí)程序的過(guò)程中，學(xué)生通常寫簡(jiǎn)單的函數(shù)而不是整個(gè)程序。

參考文獻(xiàn)：

[1] 陳新.基于程序控制流圖源代碼相似程度分析系統(tǒng)[J].計(jì)算機(jī)系統(tǒng)應(yīng)用，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.