修曉杰，唐紅軍

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

0 引言

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

1 程序評(píng)測(cè)過(guò)程

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

圖1 程序評(píng)測(cè)過(guò)程

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

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

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

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

3 程序切片

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

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

圖4 程序劃分算法

4 程序比較與評(píng)測(cè)

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

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

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

圖5 程序的比較評(píng)測(cè)算法

5 實(shí)例分析

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

圖6 實(shí)驗(yàn)程序比較評(píng)測(cè)實(shí)例

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

表1 程序差異描述

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

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

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

［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(jià)轉(zhuǎn)換技術(shù)的研究與應(yīng)用［D］.廣州:廣東工業(yè)大學(xué)，2008.

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