智能評卷系統(tǒng)中程序題語法出錯處理的研究

摘要：該文分析了編程題智能評卷系統(tǒng)中語法出錯處理的研究現(xiàn)狀，指出了目前研究中存在的不足，并將應(yīng)用于評卷系統(tǒng)和編譯器的語法出錯處理的特定進(jìn)行了分析，指出了兩者之間的根本差異，提出了一種適用于評卷系統(tǒng)的語法出錯處理的解決方案。經(jīng)實驗證明，基于動態(tài)可擴(kuò)充的同步符號集的應(yīng)急模式能夠較好的滿足智能閱卷的需要。

關(guān)鍵詞：出錯處理；同步符號；應(yīng)急模式

中圖分類號：TP311 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044(2009)05-1188-03

The Research about Managing Syntax Error in Auto-Checking System

DENG Chen-xi

(Department of Information Technology， Hunan Environment-Biological Polytechnic， Hengyang 421005， China)

Abstract: This paper analyzed the current status of managing syntax errors in auto-checking programs， and figured out the shortages in current researches. The key difference between compiler and auto-checking system has been listed after analyzing， and a particular solution was supposed for the system. With the results of the experiments， we can see the solution may have a good application in auto-checking system.

Key words: syntax error management; synchronized tokens; panic mode

1 引言

近年來，隨著計算機(jī)輔助處理、多媒體技術(shù)以及計算機(jī)網(wǎng)絡(luò)等技術(shù)的飛速發(fā)展和推廣應(yīng)用，在計算機(jī)基礎(chǔ)教育中采用計算機(jī)實現(xiàn)考試無紙化已成為目前發(fā)展的必然趨勢。其涉及到多個重要組成部分，如題庫的建立與維護(hù)，試卷的智能組卷以及智能批閱等。其中試卷的智能批閱對于大規(guī)模的考試來說意義非常重大。特別是當(dāng)前各類計算機(jī)相關(guān)考試頻繁，給教師帶來了巨大的工作量，因此，實現(xiàn)智能化披閱是目前迫切的需要。

在計算機(jī)相關(guān)考試中，編程題的自動閱卷技術(shù)是一項非常具有實用價值的應(yīng)用，也是實現(xiàn)計算機(jī)在線考試以及全自動閱卷的一個關(guān)鍵技術(shù)。由于程序?qū)崿F(xiàn)同一功能的代碼具有多樣化的特性，因此，制定標(biāo)準(zhǔn)答案變得很復(fù)雜。專家學(xué)者們致力于去尋找一個程序的中間表示形式，并希望通過這樣的一種形式來表示程序的標(biāo)準(zhǔn)答案，然后把考生的代碼也通過同樣的方法進(jìn)行轉(zhuǎn)換，最后來對它們進(jìn)行匹配，根據(jù)匹配的程度來給分。

雖然研究取得了一定的成果，但尚處于研究階段，還未能投入到真正的應(yīng)用之中。并且在這個領(lǐng)域中，目前研究的熱點是如何進(jìn)行語義分析，即分析考生代碼在語義上的正確性，而對考生代碼中錯誤的處理相關(guān)的研究較少。

2 語法出錯處理的分析與研究

2.1 出錯處理研究的必要性分析

一個智能評卷系統(tǒng)的優(yōu)劣取決于其評分結(jié)果與正確的人工閱卷評分結(jié)果的接近程度。在人工閱卷過程中，語法錯誤顯然是要計入最后得分的，因此，智能評卷需要計算語法錯誤數(shù)量勢在必行。由此，智能評卷系統(tǒng)中需要加入一個語法分析器來統(tǒng)計代碼中的語法錯誤數(shù)量。就目前的情況而言，一些主流的編程語言如java，c的編譯器中的語法分析都不能滿足這一特定的需求。這并不是說當(dāng)前的編譯器不夠好，而是其側(cè)重點不同，它們更加重視的是找到錯誤并盡量給出相關(guān)的錯誤報告，而閱卷看重的卻是錯誤的真實數(shù)目?？梢詮囊粋€簡單的示例中來說明這個問題。

void main()

{ a++;

a--;

a = a++;

a = a--;}

上述的c語義代碼經(jīng)過編譯后得到的錯誤數(shù)量是6，也就是說，對于未經(jīng)聲明的變量a，在程序中每使用一次，錯誤的數(shù)量就會相應(yīng)增加。對于程序員調(diào)試程序來說，這樣的提示當(dāng)然是合理的，但若應(yīng)用于智能閱卷，這樣的結(jié)果卻是不能接受的。因為只要添加一句聲明性的語句就可以解決所有的錯誤，筆者認(rèn)為在這種情況下，錯誤的數(shù)量應(yīng)為1。

究其原因，普通的編譯器對錯誤的數(shù)量并不重視，而這恰恰是評卷系統(tǒng)中至關(guān)重要的，這樣就導(dǎo)致它無法滿足評卷系統(tǒng)的需要。因此，智能評卷系統(tǒng)需要一個獨立的有針對性的語法分析器來對考生的程序進(jìn)行語法錯誤的統(tǒng)計。

2.2 出錯處理的解決方案

語法分析的難點主要不在于找到錯誤，而在于如何準(zhǔn)確定位錯誤位置，避免虛假錯誤和錯誤級聯(lián)，以及找到錯誤之后從何處開始恢復(fù)分析的問題。而對于評卷這一應(yīng)用來說，其主要的目的是統(tǒng)計錯誤的數(shù)量，因此，避免虛假錯誤和出錯恢復(fù)尤為重要。下面給出一個語法分析的大致流程。

就現(xiàn)階段的研究來說，在編譯器中語法分析和錯誤校正中需要遵循的一些重要事項如下[1]：

1) 分析程序應(yīng)該試著盡可能快地判斷出錯誤的發(fā)生。

2) 在錯誤發(fā)生之后，分析程序必須挑選出一個可能的位置來恢復(fù)分析。分析程序應(yīng)總是嘗試盡可能多地分析代碼，這是為了在翻譯中盡可能多地找到真實的錯誤。

3) 分析程序應(yīng)避免出現(xiàn)錯誤級聯(lián)問題，在這里錯誤會產(chǎn)生一個冗長的虛假的出錯信息。

4) 分析程序必須避免錯誤的無限循環(huán)，此時不用任何輸入都會產(chǎn)生一個出錯信息的無限級聯(lián)。

可以看出，其中的一些目標(biāo)存在著矛盾，所以構(gòu)建語法分析器必須在進(jìn)行錯誤處理的時候作一些折衷。例如，避免錯誤級聯(lián)和無窮循環(huán)問題會引起分析程序跳過一些輸入，它與處理盡可能多的輸入找出盡可能多的錯誤相矛盾?？紤]到本文的具體需要，在問題的嚴(yán)重性上，漏掉一部分錯誤和引起虛假錯誤，前者遠(yuǎn)輕于后者，因此，對語法和詞法的檢查宜松不宜緊。

2.2.1 應(yīng)急模式

一般而言，術(shù)語“語法錯誤恢復(fù)”涵蓋了編譯器遇到程序里的錯誤之后繼續(xù)去查找錯誤的一切技術(shù)[2]。一種較為簡單的方式稱為應(yīng)急模式，其中定義了一集“安全符號”，用于區(qū)分輸入里的一些非常清晰的位置。當(dāng)出現(xiàn)了一個錯誤時，應(yīng)急模式恢復(fù)算法不斷刪除輸入單詞，直至它遇到一個安全符號，然后就讓語法分析器回到這一符號可能出現(xiàn)的上下文里。

由于應(yīng)急模式把自己限制到一個“安全”符號的靜態(tài)集合里，并總是從那里重新開始語法分析，這種分析程序很可能在尋找這種符號的過程中刪除掉大量輸入。更糟糕的是，如果某些被刪除的單詞是語言里某個大規(guī)模結(jié)構(gòu)的“起始”符號（例如for、while等關(guān)鍵字），那么在到達(dá)這種結(jié)構(gòu)的結(jié)束位置之前，肯定會出現(xiàn)級聯(lián)式的虛假錯誤。因此，簡單的應(yīng)急模式不能滿足評卷的需求。

2.2.2 短語層恢復(fù)

后來人們發(fā)現(xiàn)通過對不同的上下文使用不同的“安全”符號集合，有可能改善恢復(fù)的質(zhì)量。結(jié)合了這種改良的語法分析器被稱為實現(xiàn)了短語層恢復(fù)的分析器。當(dāng)分析器在一個表達(dá)式里發(fā)現(xiàn)了錯誤時，短語層恢復(fù)算法會刪除一些單詞，直至遇到某個可能出現(xiàn)在表達(dá)式之后的單詞。這種更局部的恢復(fù)方式比總是回到當(dāng)前語句的結(jié)束更好一些，因為它給了一個機(jī)會，使得有可能去檢查語句里位于出錯表達(dá)式之后的那一部分。

1976年Niklaus Wirth發(fā)表了遞歸下降分析器的短語層恢復(fù)的一個很優(yōu)雅的實現(xiàn)。他的算法依賴于FIRST和FOLLOW集合。如果針對非終結(jié)符foo的分析例程在其代碼開始處發(fā)現(xiàn)一個錯誤，它就刪除得到的單詞，直至遇到一個FIRST(foo) 的成員或者一個FOLLOW(foo) 的成員。在前一種情況下它繼續(xù)下去，在后一種情況下就返回。

這種恢復(fù)算法雖然簡單，但卻有一種很不幸的傾向：如果存在foo →e 的情況，在確實應(yīng)該發(fā)布一個錯誤信息時，它卻會去預(yù)測一個或者幾個 e 產(chǎn)生式。這一弱點被稱為直接錯誤檢查問題。出現(xiàn)這一問題是因為FOLLOW(foo) 是與上下文有關(guān)的，其中包含了在合法程序里可能在某個地方出現(xiàn)在foo之后的所有單詞，但它們未必能出現(xiàn)在當(dāng)前程序里的當(dāng)前這個位置。

3 改進(jìn)的動態(tài)同步符號集恢復(fù)解決方案

3.1 動態(tài)符號集的基本思想

由前面的分析可知，語法出錯處理的一個關(guān)鍵點是找到錯誤之后如何繼續(xù)進(jìn)行語法分析的問題[2]。前面所介紹的方法里面有一個共同點，即如何尋找到一個同步符號集，使得語法分析能夠根據(jù)這個符號集來恢復(fù)分析。

現(xiàn)在的同步符號集合不管是FIRST集還是FOLLOW集，對于一種特定的語言來說，它都是一個固定的符號集。本文提出一種動態(tài)的可擴(kuò)展的同步符號集的方案來解決智能評卷系統(tǒng)中的語法出錯處理問題，整個分析采用遞歸下降的分析方法。同步符號集的定義如下：

1) FIRST集合。FIRST集能讓遞歸下降分析程序能夠在分析的時候盡早的檢測出語法錯誤。

2) FOLLOW集合。FOLLOW集合可用來使錯誤處理器避免跳過開始新的主要結(jié)構(gòu)的重要記號（如語句或表達(dá)式）。

3) 針對特定語言的關(guān)鍵字集合。加入關(guān)鍵字集合可以使分析器更快的恢復(fù)分析。

4) 運行時添加的符號集。此符號集是分析器在分析的過程中在考生的代碼中所抓取的一些符號，并且此符號集不與前三個集合放在同一地方存儲，而是分離開來。這個符號集用于減少虛假錯誤。

通過在分析考生代碼的時候動態(tài)的添加同步符號集，能夠幫助分析程序更加智能的找到恢復(fù)點，也使得分析更加類似于人工閱卷，有利于減少虛假錯誤的發(fā)生。舉例來說，對于一個未經(jīng)定義的變量，考生進(jìn)行了多次使用，則通過動態(tài)的同步符號集機(jī)制，在第一次分析到錯誤的時候，會把此變量名加入到同步符號集中，而在下一次碰到此符號時，將不會再次當(dāng)成錯誤。

3.2 解決方案的過程分析及具體實現(xiàn)

3.2.1 詞法分析階段

由于語法分析要使用到詞法分析所得到的符號集，因此有必要對采用的詞法分析做一個介紹。詞法掃描程序從考生源程序中識別出各種單詞，然后將其表示成一種特殊的形式，交給語法分析程序。這種特殊的形式稱之為Token字，用一個二元組來表示，其形式為：

（單詞種別碼，單詞符號的屬性值）

其中：單詞種別碼表示單詞的種類。對于種別碼如何進(jìn)行編碼，取決于處理上的方便，在本文中按以下方式處理：關(guān)鍵字為一字一碼，標(biāo)識符統(tǒng)歸為一種，常數(shù)則按類型（整型，實型，字符型等）分種，運算符一符一種，界符亦采用一符一種的方法。單詞符號屬性值作為一個指示器，標(biāo)示標(biāo)識符在符號表中的位置。

考生代碼經(jīng)過與處理之后，剔除掉了一些注釋和多余的空白符號，進(jìn)入到了符號識別階段。符號識別將考生的代碼分為上述的幾種類型，分別存入到一個容器之中。假如設(shè)定標(biāo)識符的單詞種別碼為30，在符號識別時，遇到第一個標(biāo)識符，可存為Token字（30，0），第二個可存為（30，1），依次類推。

3.2.2 普通語法錯誤的處理

普通語法錯誤是指詞法上的錯誤或者漏泄、多寫單詞，下面給出偽代碼來說明這類錯誤處理是如何進(jìn)行的：其中的match()方法用于進(jìn)行匹配，error()方法用于紀(jì)錄錯誤，但并不退出分析程序。本文關(guān)心錯誤數(shù)量，因此可設(shè)一變量來存儲語法錯誤的數(shù)量，在error()方法中來改變它的值。syncset表示當(dāng)前非終結(jié)符的同步符號集，在前面的討論中可知對于文法的開始符號要給synchset賦以初值，然后在遞歸的過程中傳遞此集合，傳遞的過程中不斷地修改此集合。scanto函數(shù)用于出錯后對同步符號集進(jìn)行掃描，并一直丟棄不在同步符號集中的輸入單詞。函數(shù)checkinput()用于早期的錯誤檢查，以便盡快發(fā)現(xiàn)錯誤。此函數(shù)有兩個形式參數(shù)，分別為firstset和followset。若面臨的非終結(jié)符為A，若輸入的token不在FIRST(A)中，顯然出現(xiàn)了語法錯誤，于是調(diào)用scanto函數(shù)來跳過一些輸入。

void match(expectedToken)

{ If(token == expectedToken)

{ getToken();}

else

{ error();}}

void scanto(sychset)

{ while(!token∈(syncset∪{#}))

{getToken();}}

void checkinput(firstset，followset)

{ if(!token∈firstset)

{ error();

scanto(firstset∪followset);}}

假如考生輸入了這樣的代碼：i = )i*+i;這是一個賦值語句，在賦值語句右邊的候選的FIRST集中不包含“)”，由checkinput函數(shù)可判斷出錯，調(diào)用scanto函數(shù)，跳過此輸入，讀取下一個輸入i，i顯然在此候選的FIRST集中，也即在同步符號集中，因此從此處開始恢復(fù)分析。當(dāng)匹配完“*”號之后，后出現(xiàn)了“+”號，而當(dāng)前用來匹配的非終結(jié)符應(yīng)該為一個factor，即乘法的一個因子，它的FIRST集中不包含“+”，因此又可判斷出現(xiàn)了語法錯誤；又由于“+”屬于factor的FOLLOW集，因此也在factor的同步符號集中，在這種情況下，采取放棄當(dāng)前的非終結(jié)符，使用下一個非終結(jié)符來進(jìn)行匹配的措施來恢復(fù)分析。經(jīng)過這樣的分析，得到了兩處語法錯誤，可見，這種錯誤處理方式可以得到較為合理的錯誤診斷信息。

3.2.3 變量未定義錯誤的處理

變量未定義錯誤包括了多種情況，不僅僅是使用了未定義變量，如變量名或函數(shù)名的拼寫錯誤也會算入變量未定義錯誤[3]。對于這類錯誤，如果僅僅使用普通錯誤的處理方案，將會出現(xiàn)較多的虛假錯誤信息。因此，可以使用前文所提到的一個動態(tài)的可擴(kuò)充的符號集來處理此類問題。定義一個標(biāo)識符信息的類如下：

class Var

{ String type;

char kind;

String name;

int value;}

其中：type用來存放變量的類型，包括int，float，char，double等；kind用于存放變量的種類，包括簡單變量，數(shù)組變量以及指針變量等；name用來存放變量的名字；value用于存放變量是否賦值的標(biāo)志，若已賦值則為1，否則為0。

在分析的時候，建立Var類的一個數(shù)組V，充當(dāng)一個動態(tài)的同步符號集?？啥ㄩL為20個，對于考生程序來講已經(jīng)夠用了。分析到變量定義語句的時候進(jìn)行類似填表的工作，把程序中定義了的變量的信息添加到Var數(shù)組中的元素中去。分析到執(zhí)行語句時，則查看變量表，所有的變量都應(yīng)該在變量表中有定義的。若無，則報錯。然后，將此變量也添加到V數(shù)組中去，這樣，在下次掃描到它的時候就不會再報錯。

另外，考慮到每遇到一個變量就要掃描V數(shù)組會造成很大的性能消耗，而在前面的詞法分析中可知，它提供給語法分析的數(shù)據(jù)是一種Token字的結(jié)構(gòu)。變量在程序中的出現(xiàn)順序與其Token字中的屬性值的大小相對應(yīng)，屬性值越小的變量表明越在前面。另外變量表中的順序與變量在程序中的出現(xiàn)順序也是一致的。即若某個變量的Token字為(30，0)，若其已經(jīng)定義，則其信息肯定已經(jīng)存放于V[0]中，反過來，V[1]、V[2]中存放的必然是Token字為(30，1)和(30，2)的變量。因此，若某個標(biāo)識符的Token字為(30，n)，而V數(shù)組中目前有m個變量的信息，若n>m，則可知該變量沒有定義，把它加到V數(shù)組中去；若n

4 實驗及結(jié)果

實驗題目主要采用C語言教材的課后習(xí)題，因其知識點較具代表性。為了全面的驗證閱卷模型的功能和評分準(zhǔn)確程度，對清華大學(xué)出版社的《C語言程序設(shè)計》教材的第四章到第十一章的一些章節(jié)中每章選取兩個題目作為代表，共14道題[4]。

為了檢驗評分的準(zhǔn)確性，對每道題都選取了30份考生答案作為樣本，并嚴(yán)格按照評分標(biāo)準(zhǔn)為每個程序進(jìn)行了人工評分，分別紀(jì)錄了評分結(jié)果。對給出的實驗數(shù)據(jù)任意抽取三道題做為測試樣本，結(jié)果見表1。

5 結(jié)束語

從表1中可以看出，語法錯誤的程序檢查的準(zhǔn)確性達(dá)到了90%以上，并且其總數(shù)并未多于真正的錯誤數(shù)量，可見其出現(xiàn)錯誤級聯(lián)和虛假錯誤的可能性還是較少的，應(yīng)用于評卷系統(tǒng)，具有較好的可信度。

參考文獻(xiàn)：

[1] 馮博琴.編譯原理及實踐[M].北京：機(jī)械工業(yè)出版社，2000:123-165.

[2] 斯科特.程序設(shè)計語言：實踐之路[M].2版.北京:電子工業(yè)出版社，2007.

[3] 孫坤.C語言上機(jī)考試及自動評分系統(tǒng)的研究與實現(xiàn)[D].沈陽工業(yè)大學(xué)，2005.

[4] 譚浩強(qiáng).C語言程序設(shè)計[M].3版.北京：清華大學(xué)出版社，2005.