尤 楓 史晟輝

摘要:本文對ACM在線評測在計算機(jī)算法類課程實踐教學(xué)中的應(yīng)用現(xiàn)狀進(jìn)行了介紹,分析了在“編譯原理”課程實踐教學(xué)中引入在線評測的可行性,闡述了如何組織適于在線評測模式的“編譯原理”實踐教學(xué)內(nèi)容,并給出了“編譯原理”在線評測系統(tǒng)的設(shè)計方案,對“編譯原理”實踐教學(xué)模式進(jìn)行了有益探索。

關(guān)鍵詞:ACM;編譯原理;在線評測;實踐教學(xué)

中圖分類號:G642 文獻(xiàn)標(biāo)識碼:B

1引言

多年來,ACM在線評測一直被成功應(yīng)用于ACM國際大學(xué)生程序設(shè)計競賽(ACM/ICPC:ACM International Collegiate Programming Contest),這是美國計算機(jī)協(xié)會(ACM:Association for Computer Machinery)組織的、世界上公認(rèn)的規(guī)模最大、水平最高的國際大學(xué)生程序設(shè)計競賽,旨在使大學(xué)生運用計算機(jī)程序設(shè)計理論充分展示自己分析問題和解決問題的能力。

中國大陸地區(qū)1997年開始舉辦區(qū)域賽和參加世界總決賽。十幾年來,全國近百所知名高校積極響應(yīng),熱心參與,已成為我國高?？萍蓟顒拥囊粋€熱點和展示計算機(jī)教育成果及優(yōu)秀人才綜合素質(zhì)的一項重要活動,目前更是出現(xiàn)迅速普及的趨勢。

鑒于ACM在線評測提供了完整的計算機(jī)實踐教學(xué)模式,在培養(yǎng)學(xué)生創(chuàng)新能力、綜合能力、鍛煉學(xué)生心理素質(zhì)和團(tuán)隊合作精神方面起到了積極的促進(jìn)作用,目前我國的許多高校,如北京大學(xué)、清華大學(xué)、浙江大學(xué)和中山大學(xué)等均開發(fā)了自己的ACM在線評測系統(tǒng),并將其引入到了計算機(jī)算法設(shè)計類課程的實踐教學(xué)和學(xué)生能力評測中,如程序設(shè)計基礎(chǔ)、數(shù)據(jù)結(jié)構(gòu)與算法、人工智能、算法分析與設(shè)計等,并取得了非常好的效果,在很大程度上彌補(bǔ)了計算機(jī)實踐教學(xué)中的不足。我校在2008年初開發(fā)了編譯程序在線評測系統(tǒng),開始探討將這一模式引入“編譯原理”課程的實踐教學(xué)中,取得了很好的效果,現(xiàn)正在進(jìn)一步完善。

2在線評測系統(tǒng)的功能

“編譯原理”是一門理論和實踐緊密結(jié)合的課程,但其內(nèi)容抽象、邏輯性強(qiáng)、不易理解,是計算機(jī)專業(yè)課中公認(rèn)的難學(xué)課程。學(xué)習(xí)理論知識難,編程訓(xùn)練更是讓學(xué)生望而生畏。如何使學(xué)生掌握編譯技術(shù)、循序漸進(jìn)地參與復(fù)雜軟件系統(tǒng)的設(shè)計開發(fā),是需要深入研究的問題。

2.1ACM在線評測系統(tǒng)的主要功能

ACM在線評測系統(tǒng)是一個基于B/S結(jié)構(gòu)的在線程序與算法設(shè)計練習(xí)、競賽平臺,主要功能可分為用戶管理、題庫管理、在線提交、在線比賽及在線排名、在線討論等。該系統(tǒng)提供了大量供學(xué)生練習(xí)和競賽的競賽題目,學(xué)生在線提交解決相關(guān)練習(xí)和競賽題的程序代碼,系統(tǒng)可以自動編譯程序代碼,生成可執(zhí)行文件,并根據(jù)已存儲的測試用例,從程序的正確性、程序運行總時間、耗費內(nèi)存、單用例執(zhí)行時間、程序返回結(jié)果等各方面評測程序代碼,并精確返回各方面的評測結(jié)果。這不僅要求學(xué)生能夠分析問題,綜合利用知識點,而且還要在算法上進(jìn)行合理的優(yōu)化,并在更短的時間內(nèi)給出準(zhǔn)確解答,大大提高了教學(xué)質(zhì)量和教學(xué)效果。

2.2需解決的問題

不同于算法設(shè)計類課程,編譯程序復(fù)雜、規(guī)模龐大,程序模塊之間關(guān)系緊密,編譯結(jié)果可能不具唯一性等,都造成編譯程序在線評測的困難。除了評測外,課程各個知識點和算法關(guān)聯(lián)程度高,后續(xù)內(nèi)容往往需要前面的內(nèi)容作支撐,一環(huán)緊扣一環(huán),學(xué)生只想練習(xí)后面部分知識點和算法幾乎不可能,他們對編寫復(fù)雜程序很恐懼,造成很大心理負(fù)擔(dān)。

“編譯原理”的實踐教學(xué)主要由兩部分組成,課程實驗和課程設(shè)計。

課程實驗是實踐教學(xué)的重要環(huán)節(jié),也是課堂理論教學(xué)的重要補(bǔ)充,通過實驗,學(xué)生能夠更好地理解課程中的基本概念和原理,通過自己動手體驗提高實踐能力。通常這一類的實驗多為驗證性的,規(guī)模相對較小,主要是對一、二個知識點和算法的實踐訓(xùn)練,如詞法分析中的正則表達(dá)式到NFA的轉(zhuǎn)換、NFA到DFA的轉(zhuǎn)換、DFA的最小化等程序的實現(xiàn)等。因此,如何更合理地將“編譯原理”中的各知識點和算法進(jìn)行劃分和歸類,使其更適合于練習(xí)和在線評測,是要解決的一個問題。

課程設(shè)計與課程實驗不同,主要是培養(yǎng)學(xué)生的綜合設(shè)計能力,無論是從綜合性、設(shè)計性要求,還是從規(guī)模上要求,課程設(shè)計的復(fù)雜度都高于課程實驗。因此,如何更合理地組合“編譯原理”中的各知識點和算法,形成完整的編譯程序前端、后端乃致整個編譯程序,以滿足課程設(shè)計的要求,并適合于在線評測,是要解決的另一個問題。

3實踐教學(xué)內(nèi)容設(shè)計

一般地,編譯程序主要由詞法分析、語法分析、語義分析和目標(biāo)代碼生成程序等幾個部分組成,每一部分又包含若干個知識點和算法。因此,首先要將這些知識點和算法合理地拆分成若干個模塊,使之簡單化、小型化、獨立化,使學(xué)生可以以任意順序?qū)崿F(xiàn)各模塊的功能。

以編譯程序前端的詞法分析和語法分析兩部分為例,共拆分設(shè)置了18個核心模塊,并進(jìn)一步擴(kuò)展為21個模塊,如圖1所示,其中灰色顯示的3個模塊為外部輸入模塊,圖中的箭頭表示各模塊之間的依賴關(guān)系。由于語法分析部分的各模塊均依賴于產(chǎn)生式表和符號表,為使關(guān)系圖更清晰,在圖中隱去了這兩個模塊的依賴。

由于模塊之間具有獨立性,用戶可以單獨實現(xiàn)其中的某一模塊而無須實現(xiàn)其所依賴的各模塊,其依賴的模塊將由評測系統(tǒng)提供接口予以使用。這樣,完整的詞法分析程序需要實現(xiàn)4個模塊,而語法分析具體分為5種:①對于LL(1)分析法,需要實現(xiàn)LL產(chǎn)生式表、符號表、First集、Follow集、LL(1)分析表、分析樹共6個模塊;②對于LR(0)分析法,需要實現(xiàn)LR分析表、符號表、LR(0)自動機(jī)、LR(0)分析表、分析樹共5個模塊;③對于SLR分析法,需要實現(xiàn)LR分析表、符號表、First集、Follow集、LR(0)自動機(jī)、SLR分析表、分析樹共7個模塊;④對于LR(1)分析法,需要實現(xiàn)LR分析表、符號表、First集、Follow集、LR(1)自動機(jī)、LR(1)分析表、分析樹共7個模塊;⑤對于LALR分析法,需要實現(xiàn)LR分析表、符號表、First集、Follow集、LR(1)自動機(jī)或LR(0)自動機(jī)、LALR自動機(jī)、LALR分析表、分析樹共8個模塊。

以上5種只需要實現(xiàn)其中一種,即可實現(xiàn)語法分析程序。對于語義分析和目標(biāo)代碼生成程序的模塊拆分及依賴關(guān)系,也采用類似的方法進(jìn)行。

4編譯程序在線評測系統(tǒng)的實現(xiàn)

為了與現(xiàn)有的ACM在線評測系統(tǒng)接軌,編譯程序在線評測系統(tǒng)是通過在北京化工大學(xué)ACM在線評測系統(tǒng)上進(jìn)行改進(jìn)和增加功能來實現(xiàn)的,主要包括如下幾個部分。

4.1組合模塊功能實現(xiàn)

要實現(xiàn)編譯程序,除了要實現(xiàn)上述拆分后的各相關(guān)模塊功能外,還要進(jìn)行組合。例如對于詞法分析程序,除要分別實現(xiàn)“正則表達(dá)式轉(zhuǎn)NFA”、“NFA轉(zhuǎn)DFA”、“DFA轉(zhuǎn)最小化DFA”和“最小化DFA轉(zhuǎn)符號序列”四個算法,在評測系統(tǒng)中體現(xiàn)為實現(xiàn)NFA模塊(輸入為正則表達(dá)式,輸出為NFA)、DFA模塊、最小化DFA模塊和符號序列模塊外,還要將其組合,形成最終的詞法分析程序,這就提出了組合模塊的思想。

一般來說,簡單的組合模塊思路是針對每一種可能的組合方式設(shè)計一個組合模塊,但由于編譯原理知識點和算法拆分后模塊數(shù)量較多,其組合方式更是呈指數(shù)級增長,這無疑增加了實現(xiàn)的難度,同時也會產(chǎn)生冗余。因此,評測系統(tǒng)采用了一種自動組合的思路,在遵循編譯原理的情況下,可進(jìn)行任意模塊的組合,用戶在需要組合時可以自行選擇需要組合的模塊,系統(tǒng)針對用戶的選擇自動生成組合模塊。評測系統(tǒng)對組合過程進(jìn)行了如下約束:①組合模塊的最后只能是一個輸出。如“LR(0)自動機(jī)”、“SLR分析表”、“LR(0)分析表”這三個模塊就不能組合,因為組合之后就存在SLR分析表、LR(0)分析表兩個輸出。②組合模塊不能有跳躍性。如“LALR分析表”和“First集”這兩個模塊就不能組合,當(dāng)然,這樣的組合也沒有實際意義。③組合模塊中不能出現(xiàn)依賴沖突的模塊。如“符號表”和“Follow集”模塊不能組合,因為Follow集的依賴項First集需要符號表,但是符號表是用戶實現(xiàn)的。這種組合形成了依賴沖突。

圖2所示為組合模塊頁面,這里顯示了一種組合的情況,當(dāng)選擇了“LR(0)自動機(jī)”、“SLR分析表”、“分析樹”三個模塊時,系統(tǒng)會將其組合成一個新的模塊,輸入為LR(0)自動機(jī)需要的數(shù)據(jù),輸出為分析樹。

4.2評測方法的改進(jìn)

一般的ACM在線評測系統(tǒng)只能評測輸出結(jié)果唯一的程序,對不唯一的情況要使用額外手段進(jìn)行正確性評價,如編寫一段輔助測試程序進(jìn)行評測。然而,“編譯原理”中絕大部分模塊產(chǎn)生的結(jié)果都是不確定或不唯一的,因此,簡單地套用現(xiàn)有評測技術(shù)是無法實現(xiàn)編譯程序的在線評測的。

在這里提出改進(jìn)的評測方法,也是“編譯原理”在線評測系統(tǒng)采用的評測方法。針對模塊輸出結(jié)果不唯一的問題,例如正則表達(dá)式轉(zhuǎn)NFA,系統(tǒng)設(shè)計了兩種有效的方法:一種是采用模塊替換方法,將用戶編寫好的模塊放入評測系統(tǒng)提供的整個框架中去編譯執(zhí)行,評價整個框架執(zhí)行的最終結(jié)果;另一種方法是評測時從用戶提交的模塊開始執(zhí)行,結(jié)合系統(tǒng)提供的后續(xù)模塊繼續(xù)執(zhí)行至能夠產(chǎn)生唯一結(jié)果的模塊為止,這時的結(jié)果也就可以利用現(xiàn)有的評測技術(shù)進(jìn)行評測。如NFA的等價性判斷較為困難,當(dāng)用戶提交了NFA模塊后,系統(tǒng)會使用其提供的已實現(xiàn)的框架,將其轉(zhuǎn)化為DFA乃至最小化DFA,再進(jìn)行評測。

當(dāng)然這種方式對用戶而言是透明的,用戶體會到的是對其實現(xiàn)的模塊進(jìn)行了單元測試。

5結(jié)束語

實踐表明,“編譯原理”的實踐教學(xué)中引入ACM在線評測為實踐教學(xué)提供了新的方法和手段,是一個有益的探索。在線評測系統(tǒng)是一個很好的實踐教學(xué)平臺,通過這個平臺,學(xué)生能夠更好地將理論與實踐緊密結(jié)合,動手能力、創(chuàng)造能力和協(xié)調(diào)能力會得到進(jìn)一步提高。

參考文獻(xiàn):

[1] 郭嵩山,王磊,張子臻. ACM/ICPC與創(chuàng)新IT人才的培養(yǎng)[J]. 實驗室研究與探索,2007,26(12):181-185.

[2] 武建華. 基于ACM模式的數(shù)據(jù)結(jié)構(gòu)實踐教學(xué)改革與探討[J]. 計算機(jī)教育,2007(12):114-116.

[3] 教育部高等學(xué)校計算機(jī)科學(xué)與技術(shù)教學(xué)指導(dǎo)委員會. 高等學(xué)校計算機(jī)科學(xué)與技術(shù)專業(yè)實踐教學(xué)體系與規(guī)范[M]. 北京:清華大學(xué)出版社,2008.