尤 楓 史晟輝

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

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

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

1引言

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

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

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

2在線評(píng)測(cè)系統(tǒng)的功能

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

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

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

2.2需解決的問(wèn)題

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.2評(píng)測(cè)方法的改進(jìn)

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

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

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

5結(jié)束語(yǔ)

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

參考文獻(xiàn):

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

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

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