智能評卷系統中程序題語法出錯處理的研究

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

關鍵詞：出錯處理；同步符號；應急模式

中圖分類號：TP311 文獻標識碼：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 引言

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

在計算機相關考試中，編程題的自動閱卷技術是一項非常具有實用價值的應用，也是實現計算機在線考試以及全自動閱卷的一個關鍵技術。由于程序實現同一功能的代碼具有多樣化的特性，因此，制定標準答案變得很復雜。專家學者們致力于去尋找一個程序的中間表示形式，并希望通過這樣的一種形式來表示程序的標準答案，然后把考生的代碼也通過同樣的方法進行轉換，最后來對它們進行匹配，根據匹配的程度來給分。

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

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

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

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

void main()

{ a++;

a--;

a = a++;

a = a--;}

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

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

2.2 出錯處理的解決方案

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

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

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

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

3) 分析程序應避免出現錯誤級聯問題，在這里錯誤會產生一個冗長的虛假的出錯信息。

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

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

2.2.1 應急模式

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

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

2.2.2 短語層恢復

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

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

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

3 改進的動態同步符號集恢復解決方案

3.1 動態符號集的基本思想

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

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

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

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

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

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

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

3.2 解決方案的過程分析及具體實現

3.2.1 詞法分析階段

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

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

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

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

3.2.2 普通語法錯誤的處理

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

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函數可判斷出錯，調用scanto函數，跳過此輸入，讀取下一個輸入i，i顯然在此候選的FIRST集中，也即在同步符號集中，因此從此處開始恢復分析。當匹配完“*”號之后，后出現了“+”號，而當前用來匹配的非終結符應該為一個factor，即乘法的一個因子，它的FIRST集中不包含“+”，因此又可判斷出現了語法錯誤；又由于“+”屬于factor的FOLLOW集，因此也在factor的同步符號集中，在這種情況下，采取放棄當前的非終結符，使用下一個非終結符來進行匹配的措施來恢復分析。經過這樣的分析，得到了兩處語法錯誤，可見，這種錯誤處理方式可以得到較為合理的錯誤診斷信息。

3.2.3 變量未定義錯誤的處理

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

class Var

{ String type;

char kind;

String name;

int value;}

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

在分析的時候，建立Var類的一個數組V，充當一個動態的同步符號集。可定長為20個，對于考生程序來講已經夠用了。分析到變量定義語句的時候進行類似填表的工作，把程序中定義了的變量的信息添加到Var數組中的元素中去。分析到執行語句時，則查看變量表，所有的變量都應該在變量表中有定義的。若無，則報錯。然后，將此變量也添加到V數組中去，這樣，在下次掃描到它的時候就不會再報錯。

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

4 實驗及結果

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

為了檢驗評分的準確性，對每道題都選取了30份考生答案作為樣本，并嚴格按照評分標準為每個程序進行了人工評分，分別紀錄了評分結果。對給出的實驗數據任意抽取三道題做為測試樣本，結果見表1。

5 結束語

從表1中可以看出，語法錯誤的程序檢查的準確性達到了90%以上，并且其總數并未多于真正的錯誤數量，可見其出現錯誤級聯和虛假錯誤的可能性還是較少的，應用于評卷系統，具有較好的可信度。

參考文獻：

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

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

[3] 孫坤.C語言上機考試及自動評分系統的研究與實現[D].沈陽工業大學，2005.

[4] 譚浩強.C語言程序設計[M].3版.北京：清華大學出版社，2005.