修曉杰，唐紅軍

(杭州電子科技大學(xué)信息工程學(xué)院，浙江杭州310018)

0 引言

程序評測是指根據(jù)一定的標(biāo)準(zhǔn)對程序進行程序結(jié)構(gòu)和語義上的分析，并反饋分析結(jié)果。Marker［1］是一個C語言的測評軟件，它通過分析程序的結(jié)構(gòu)和輸出的結(jié)果來判定程序的準(zhǔn)確性。其不足之處是不能發(fā)現(xiàn)程序在語義級別上的錯誤和與模板程序的差異，沒能給出更多在程序理解上有利用價值的信息，此類工具還有 Generic Automated Marking Environment［2］，online assessment［3］，Online Judge［4］等等，但這些工具都不能滿足程序自動評測的要求。程序切片是一種用于分解程序的程序分析技術(shù)，是通過對源程序中每個興趣點分別進行技術(shù)切片來達到對程序的分析和理解［5］。本文在“C語言程序設(shè)計”課程基礎(chǔ)上，提出一種基于切片的C語言程序評測方法，并系統(tǒng)實現(xiàn)。系統(tǒng)能夠?qū)崟r評測學(xué)生的程序，并給出具體的錯誤信息和錯誤位置，同時給出相應(yīng)分數(shù)。

1 程序評測過程

對于學(xué)生提交的C語言程序，將從4部分進行評測:編譯是否通過、運行結(jié)果是否正確、是否抄襲和與模板程序的相似度。其中編譯是否通過在構(gòu)造程序抽象語法樹(AST，Abstract Syntax Tree)時完成;運行結(jié)果是否正確通過對測試數(shù)據(jù)運行結(jié)果自動測試實現(xiàn);是否抄襲，采用對評測結(jié)果相同或分數(shù)相近的學(xué)生程序進行匹配性對比完成，通過對兩棵生成AST樹進行結(jié)點匹配，根據(jù)相似度給出判斷;學(xué)生程序與模板程序相似度部分是C語言程序評測中的關(guān)鍵點，本文將著重闡述該部分。程序評測過程如圖1所示:

圖1 程序評測過程

2 程序標(biāo)準(zhǔn)化處理

學(xué)生程序作為一種主觀類型的作業(yè)，存在著主觀性的特點，同一作業(yè)程序有著不同的表達方式和語句順序，不同的學(xué)生程序有著不同的編程風(fēng)格和習(xí)慣，這就加深了對程序在語義級上進行自動評測的難度。因此，需要對學(xué)生程序進行標(biāo)準(zhǔn)化處理，使得學(xué)生程序與模板程序具有對等性比較的可能。學(xué)生程序的標(biāo)準(zhǔn)化處理過程主要包括3個主要部分:抽象語法樹的生成、結(jié)構(gòu)分析和等價轉(zhuǎn)換。學(xué)生程序標(biāo)準(zhǔn)化處理過程如圖2所示:

圖2 程序標(biāo)準(zhǔn)化處理過程

程序的標(biāo)準(zhǔn)化處理是依據(jù)于程序存在保留語義的變化，即SPV(Semantics Preserving Variation)。它是指盡管學(xué)生程序在表達上與模板程序有著不同的地方，但如果它的語義與模板程序的語義是一致的，那么該學(xué)生程序就存在著保留語義的變化。對于這類學(xué)生程序經(jīng)過標(biāo)準(zhǔn)化處理，消除學(xué)生程序與模板程序在表達上的差別，達到相匹配的目的。在程序解析時，應(yīng)用現(xiàn)有的程序解析器，生成程序抽象語法樹;在程序的結(jié)構(gòu)分析過程中，對程序進行保留語義轉(zhuǎn)換和規(guī)范處理;然后利用文獻［6］的標(biāo)準(zhǔn)化轉(zhuǎn)換規(guī)則進行等價轉(zhuǎn)換，消除SPV(文獻7中所列);最后，對轉(zhuǎn)換后的程序重新生成抽象語法樹。此部分，本文將不再詳細贅述。

3 程序切片

程序切片大致可分為靜態(tài)、有條件和動態(tài)切片，各種切片都有各自的優(yōu)勢與劣勢。計算程序切片的方法主要有兩種:根據(jù)數(shù)據(jù)流方程計算和根據(jù)依賴圖關(guān)系計算［5］。本文將實現(xiàn)靜態(tài)切片算法，通過構(gòu)造程序依賴圖，利用計算圖的可達性算法計算程序切片。程序的函數(shù)內(nèi)算法如圖3所示。其中二元組〈n，V〉表示感興趣的變量以及感興趣的變量定義位置和使用位置。其中n表示程序P中的興趣點(如某條語句);V代表程序P中在n點定義或使用的變量(或變量集合)。在上面的切片算法的基礎(chǔ)上，再結(jié)合編譯程序得到的抽象語法樹，就可以對程序進行劃分了，劃分的依據(jù)是按變量進行，包括全局和局部，并嚴格按照語法樹從上到下的順序進行劃分。程序劃分算法如圖4所示。

圖3 程序函數(shù)內(nèi)切片算法

圖4 程序劃分算法

4 程序比較與評測

對學(xué)生程序的評測，采用以下基本要求進行評測［7］:(1)程序是否編譯通過，有沒有警告;(2)程序的運行結(jié)果是否正確;(3)程序是否存在抄襲的可能;(4)程序與模板程序進行比較相似度，根據(jù)程序相似度進行評測。

其中，第4點是比較評測的關(guān)鍵。在相似度評測中，主要分兩個層次進行比較，一是程序結(jié)構(gòu)上的比較，另一個是語句層次上的比較。學(xué)生程序和模板程序在結(jié)構(gòu)上都要先經(jīng)過標(biāo)準(zhǔn)化處理，一般的語法結(jié)構(gòu)的不同都會通過標(biāo)準(zhǔn)化處理，如循環(huán)如果使用了for語句，標(biāo)準(zhǔn)化處理后都將使用while語句。但如果使用這些結(jié)構(gòu)的次數(shù)不同，標(biāo)準(zhǔn)化處理后還將有差異，對于這種情況，如果學(xué)生程序運行結(jié)果正確，則考慮將學(xué)生程序加入模板庫。

語句層次上的比較，在這一層次上將通過對程序劃分為等價成分后，在語義級上進行比較評測。在學(xué)生程序作業(yè)這類小模塊的程序比較中，經(jīng)過程序的規(guī)范化要求，以及各種標(biāo)準(zhǔn)化處理，學(xué)生程序與模板程序的近似度可以達到很高，甚至在語句上是完全一致的，很可能的不同之處是對變量的命名，但是只要在結(jié)構(gòu)上大致相同的，變量類型相同，以及在整個程序結(jié)構(gòu)上的位置大致相同(這可通過抽象語法樹進行識別)，在這些前提條件下，通過對變量切片代碼段進行命名替換后也就可以進行比較了。語句層次的比較算法如圖5所示:

圖5 程序的比較評測算法

5 實例分析

本文中的程序評測算法已經(jīng)程序?qū)崿F(xiàn)，并使用大量具體實例進行驗證，證明算法是有效的。實例程序:編程求一維數(shù)組中最大值(數(shù)組有10個元素)，數(shù)組元素的值由用戶輸入。通過程序自動評測功能進行分析和測評，并定位學(xué)生程序存在的錯誤和給出相應(yīng)提示信息。具體如圖6所示。

圖6 實驗程序比較評測實例

從圖6可見，模板程序與學(xué)生程序存在3個差異，其中區(qū)別2在標(biāo)準(zhǔn)化過程中得到處理。其它區(qū)別將在語句層次上的比較評測中檢測出來，并給出差異描述和評測結(jié)果，如表1所示。

表1 程序差異描述

對于實驗程序評測從三個方面綜合評價:(1)編譯情況:通過編譯;(2)程序測試用例測試結(jié)果:不通過;(3)模板程序與學(xué)生程序相似度:82%。根據(jù)這三方面，給出學(xué)生程序的相應(yīng)分數(shù)。給程序打分第一考慮測試用例測試是否通過，然后再看程序的相似度。這樣，采用人工設(shè)置分數(shù)比例的方法，如測試用例通過可得滿分60%的分數(shù)，若不通過則得40%的分數(shù)，而不管測試用例是否通過，程序結(jié)構(gòu)比較近似度占滿分的40%，由此，在上述的實驗中，設(shè)定滿分為100，則程序評測的結(jié)果為:總分 =100×40%+100×40% ×82% =73。對于目前使用的評測系統(tǒng)主要有兩種，一種針對ACM競賽的評測系統(tǒng)，該程序例子運行結(jié)果錯誤，得分0;另一種針對運行結(jié)果和格式兩方面進行評測(如北京航空航天大學(xué)的自動評測系統(tǒng))，得分由上述兩種因素的百分比決定。

6 結(jié)束語

本文提出的基于程序切片技術(shù)的程序評測方法已經(jīng)應(yīng)用在“C語言程序設(shè)計”課程的學(xué)生程序評測中，實踐證明該方法能有效評測出學(xué)生程序與模板程序的相似度，并給出出錯的具體語句，為高校C語言教學(xué)的老師提供了有效幫助。本文提出的程序評測方法不僅適用于過C語言程序評測，同樣適用于其它面向過程語言程序。

［1］ Ghosh M，Verma B，Nguyen A.An Automatic Assessment Marking and Plagiarism Detection［C］.Australia:First International Conference on Information Technology and Applications，2002:489-494.

［2］ Blumenstein，Michael，Green，et al.GAME:A Generic Automated Marking Environment for Programming Assessment［C］.Austrlia:International Conference on Information Technology，2004:212-216.

［3］ Fischer，Gregor，Von Gudenberg，et al.Improving the quality of programming education by online assessment［C］.Germany:ACM International Conference Proceeding Series，2006:208-211.

［4］ Brenda Cheang，Anay Kurnia，Andrew Limb，et al.On Automated Grading of Programming Assignments in an Academic Institution［J］.Computers＆ Education，2003，41(2):121-131.

［5］ Chen Duanzhi.Program slicing［C］.Guangzhou:2010 International Forum on Information Technology and Applications，2010:15-18.

［6］ 王歡.面向?qū)ο蟪绦虻葍r轉(zhuǎn)換技術(shù)的研究與應(yīng)用［D］.廣州:廣東工業(yè)大學(xué)，2008.

［7］ 陳楚明.基于切片的程序評測研究［D］.廣州:廣東工業(yè)大學(xué)，2009.