摘 要：針對傳統(tǒng)在線考試系統(tǒng)試題錄入效率低下的問題，提出了一種基于詞法分析和語法分析的試題驗證解析方法。闡述了試題導入系統(tǒng)的架構(gòu)和基本原理，重點說明了詞法分析和語法分析的應用原理和方法，并根據(jù)試題導入應用的特殊性，對語法分析進行改良，提出了附加棧法和錯誤預測捕捉法，從而提高解析能力和錯誤處理能力。
關(guān)鍵詞： 詞法分析; 語法分析； 試題導入; 附加棧法; 錯誤預測捕捉法

     利用自動化的手段將已有試題文檔直接導入在線考試系統(tǒng)，可以很大程度地減輕系統(tǒng)管理員的工作負擔。但自動化導入對于保證錄入試題的準確、保密等各方面，都有著嚴格要求。
     本文將編譯原理中的相關(guān)概念引入到試題導入系統(tǒng)中，提出了一種結(jié)合詞法分析、語法分析等技術(shù)的試題導入系統(tǒng)。在該系統(tǒng)中，首先通過詞法分析將試題文本打斷為孤立的單詞（token），進而將各個單詞進行歸類和封裝；之后，利用封裝后的單詞對象，使用預定義的語法樹進行匹配和驗證；同時，單詞表對整個過程涉及到的臨時數(shù)據(jù)進行存儲和必要支持。結(jié)果表明，此試題導入系統(tǒng)錄入效率高、保密性強、可重復使用，用戶體驗極佳。
   
1 試題導入系統(tǒng)的基本設計
    系統(tǒng)實現(xiàn)目標為：輸入文件對象，用戶控制導入，系統(tǒng)對被輸入文件中的各個試題信息元素進行驗證。如果合法，則導入數(shù)據(jù)庫；否則，定位文件中不合法的信息元素，并通過GUI界面給用戶提示?；谝陨系男枨?，決定使用MVC架構(gòu)（模型—視圖—控制器）來部署整個系統(tǒng)[1]。 總體架構(gòu)如圖1所示。   

     圖1中模型模塊是整個系統(tǒng)的核心，其中的詞法、語法分析是實現(xiàn)模型模塊的關(guān)鍵。
2 詞法、語法分析在試卷導入系統(tǒng)中的應用
     由于整個導入系統(tǒng)采用C#語言編寫，本著減小開發(fā)規(guī)模和提高開發(fā)品質(zhì)的原則，決定使用C#Lex和CsCup作為詞法、語法分析器生成工具。是本文使用的語法分析程序生成工具是當今流行的自下而上的前后文無關(guān)文法LR(1)[2]。
2.1 詞法分析的應用
2.1.1 詞法分析
    從左到右逐個字符地讀入源程序，對構(gòu)成源程序的字符流進行掃描之后根據(jù)構(gòu)詞規(guī)則識別單詞。詞法分析的輸入是源程序，輸出是各個單詞內(nèi)部表示的記號流。完成一個詞法分析周期需要3個步驟：讀入一定個數(shù)的字符、對當前字符的模式識別和生成并輸出單詞。
2.1.2 試卷導入系統(tǒng)中詞法分析的關(guān)鍵技術(shù)
    (1) 對字符串的模式識別。根據(jù)正則文法相關(guān)理論，正則文法可以構(gòu)造相應的正則式，而正則式可以構(gòu)造對應的DFA（有限自動機），DFA則可以有效地完成字符串的模式識別。即通過書寫正則式來定義模式。
    (2) 單詞對象的生成。在完成一個元素的模式識別后，需要向語法分析程序輸出已經(jīng)識別的單詞信息。在傳統(tǒng)的Lex中，輸出是以一個全局整形變量的形式提供給語法分析程序的。而針對面向?qū)ο笳Z言的詞法生成工具，都是以單詞類的實例——單詞對象的形式來輸出。
    在試卷導入程序中，單詞的諸多信息，包括單詞種類、行號、起始位置、內(nèi)容都是有意義的，所以單詞類應該包括這些信息。
2.2 語法分析的應用
2.2.1語法分析
    根據(jù)語言的語法規(guī)則，分析源程序的語法結(jié)構(gòu)，即分析如何由這些單詞組成各種語法范疇，并在分析過程中，對源程序進行語法檢查[3]。
    一個語法結(jié)構(gòu)，可以用文法的形式定義：一個文法G[S]可表示成形如(Vn，Vt，P,S)的四元式。其中Vn，Vt，P均為非空的有限集，分別稱為非終結(jié)符集、終結(jié)符號集和產(chǎn)生式集。S∈Vn為文法的開始符號。
    為說明問題，這里形式化[4]描述一道基本形式的選擇題。規(guī)定基本形式的選擇題有以下特征：（1）阿拉伯數(shù)字形式的試題序號；（2）分值；（3）題干；（4）若干個選項；（5）答案 。如圖2所示的試題就符合該特征。

　　 根據(jù)以上的規(guī)定和正則表達式的使用方法，可以確定選擇題的集合即終結(jié)符號集如表1所示。

    之后，可以從基本形式的選擇題的特征和表2的標識符號，構(gòu)造文法的Vn和P集合：

    該文法G(S)可以完整表示所定義的選擇題，并兼容多個此類選擇題的集合、不定選項、分數(shù)、試題號、題干若干種不同出現(xiàn)順序，答案、選項亂序的情況。而不符合該文法的則不接受。
    在試卷導入系統(tǒng)中，語法分析主要完成3個功能：根據(jù)預定義的語法對詞法分析輸出的單詞流進行驗證；根據(jù)語法對輸入錯誤進行捕捉；對于驗證成功的輸入生成試題對象。
2.2.2 單詞流驗證
    對于一個確定的文法G(S)，單詞流驗證的核心步驟是根據(jù)詞法分析得來的終結(jié)符t∈Vt,自下而上地構(gòu)造一個語法樹。其中該語法樹有以下特征：葉子節(jié)點僅為單詞t∈Vt；根節(jié)點僅為S；對任意一個父節(jié)點和其子節(jié)點，存在推導式p∈P，且p的左部分為父節(jié)點，右部分為子節(jié)點。
    例如，對于上例中的試題和文法G(S)，可以確定詞法分析返回的單詞流為：
     tnumber–tpoint–tmain–toption–toption–tanswer           （1）
    此時可以構(gòu)建一個如圖3所示的符合上述特征的語法樹。

    對任意一個單詞流和文法G(S)，該單詞流為該文法的一個句子，當且僅當單詞流中的各個元素能通過上述規(guī)則構(gòu)建一個語法樹。如果單詞流經(jīng)驗證是文法的句子，對于試卷導入系統(tǒng)來說，此時驗證成功；反之，需要進行錯誤捕捉和錯誤處理。
2.2.3 試題對象的產(chǎn)生
    規(guī)約過程將會進行彈出棧頂若干元素，規(guī)約成某非終結(jié)符，然后將此非終結(jié)符壓入當前分析棧的一系列動作。伴隨這個動作的完成，被彈出棧的若干個符號的細節(jié)信息將會丟失。因此，必須使用輔助手段來記錄被規(guī)約的符號，才可以有效地解決這個問題。
　為了實現(xiàn)邊驗證邊生成試題的目的，這里提出一種“附加分析棧”的方法來實現(xiàn)。
　附加分析棧方法： 設立一個棧以存儲各種分析的中間結(jié)果，對當前分析棧進行有限度的跟蹤。附加棧的運作方式為：
   （1） 移進動作，附加分析棧不進行任何操作；
   （2） 規(guī)約動作，則將規(guī)約動作對應的表達式右邊的部分封裝成一個預定義的對象，并壓入附加棧。
　例如，一個上文中的G(S)如果有一個單詞流為
　tnumber–tpoint–tmain–toption–toption–tanswer        （2）
　則附加棧的作用如表2所示。

    在表2中，需要注意兩個分析棧從上到下依次為棧頂、棧中、棧底；Obj_Number,Obj_Point,Obj_Mian對象為詞法分析輸出類的實例；Obj_Infor對象為Obj_Number,Obj_Point,Obj_Mian三元組構(gòu)成的對象。
　 一個成功的解析會生成Questions對象，通過控制器調(diào)用存儲過程，可以存入數(shù)據(jù)庫。　　
2.2.4 錯誤捕捉機制
　 試卷中可能的錯誤一般有3種：元素重復、元素缺失、其他未知錯誤。對于前兩種錯誤，由于其可預知的特性，這里提出一種“預測捕捉法”進行錯誤處理。
　 預測捕捉法：根據(jù)試題文件中可能的典型錯誤單詞流W，擴充文法G(S)中的產(chǎn)生式集合P，使得該錯誤單詞流W也可以根據(jù)上述規(guī)則P ∨Pe構(gòu)建一個語法樹,其中Pe為預測捕捉產(chǎn)生式集合。完成構(gòu)建后，則可以記錄該錯誤，并繼續(xù)剩下的單詞流分析。預測捕捉產(chǎn)生式一般由以下的原則產(chǎn)生：對于包含非終極符A，終結(jié)符a，產(chǎn)生式A:a的文法，元素a重復的錯誤，可以用A:A a | a的形式進行擴展；元素a缺失的錯誤，可以用A:ε的形式進行擴展。
　 例如，如果上述例題中“1.(10分) Dos目錄是()”被錯寫成“1. 1.(10分) Dos目錄是()”或“ (10分) Dos目錄是()”，此時，原先文法G(S)將無法成功構(gòu)建一個語法樹。但是，如果給P加入一個“Number: Number tnumber”或“Number: ε”的產(chǎn)生式，就能夠捕捉到這樣的錯誤情況。
　 其他形式的錯誤，因為其不可預知，采用特殊的單詞error進行捕捉。error單詞是語法生成工具中普遍預定義的單詞，其基本原理是：遇到不可辨識的棧頂狀態(tài)和當前單詞，它從棧中丟棄狀態(tài)和對象直到回到一個可以接受error的狀態(tài)，error單詞被移進，之后語法分析程序不斷地讀進單詞，如果可以接受則在分析棧中壓進，否則丟棄。
　 在語法生成工具CsCup中，通過列舉表達式集P可以很方便地生成一個接受表達式集P所表示文法句子的C#源文件。CsCup源文件書寫格式和error單詞使用方法請參閱參考文獻[5-6]。
     本文著重介紹了詞法、語法分析在試卷導入中應用的步驟和關(guān)鍵技術(shù)。實踐證明，該方法具有強大的錯誤捕捉和錯誤處理能力。同時，可以通過添加新的表達式，擴展所支持的題目類型，因此具有良好的可擴展性。另外，對其他涉及到數(shù)據(jù)驗證的應用，本文所介紹的方法也具有適用性。
參考文獻
[1] ERIC F,ELISABETH F,KETHY S.Head First 設計模式（中文版）[M].北京:中國電力出版社,2007.
[2] LEVINE J R,MASON T,BROWN D.lex & yacc, Second Edition[M].美國, O'Reilly Media,1992.
[3] 蔣立源，康慕寧.編譯原理[M].西安.西北工業(yè)大學出版社, 2005.
[4] 古天龍.軟件開發(fā)的形式化方法[M].北京:高等教育出版社,2005.
[5] SANUEL I. C# LEX Manual.[2009-10-16].http://www.seclab.tuwien.ac.at/projects/cuplex//lex.htm,2003.
[6] SAMUEL IMRISKA. C# CUP Manual.[2009-10-16].http://www.seclab.tuwien.ac.at/projects/cuplex//cup.htm,2005.