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

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

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

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

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

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

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

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