ACM在線評測在編譯原理實踐教學中的應用探討

尤 楓 史晟輝

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

關鍵詞:ACM;編譯原理;在線評測;實踐教學

中圖分類號:G642 文獻標識碼:B

1引言

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

中國大陸地區1997年開始舉辦區域賽和參加世界總決賽。十幾年來,全國近百所知名高校積極響應,熱心參與,已成為我國高校科技活動的一個熱點和展示計算機教育成果及優秀人才綜合素質的一項重要活動,目前更是出現迅速普及的趨勢。

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

2在線評測系統的功能

“編譯原理”是一門理論和實踐緊密結合的課程,但其內容抽象、邏輯性強、不易理解,是計算機專業課中公認的難學課程。學習理論知識難,編程訓練更是讓學生望而生畏。如何使學生掌握編譯技術、循序漸進地參與復雜軟件系統的設計開發,是需要深入研究的問題。

2.1ACM在線評測系統的主要功能

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

2.2需解決的問題

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

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

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

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

3實踐教學內容設計

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

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

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

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

4編譯程序在線評測系統的實現

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

4.1組合模塊功能實現

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

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

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

4.2評測方法的改進

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

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

當然這種方式對用戶而言是透明的,用戶體會到的是對其實現的模塊進行了單元測試。

5結束語

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

參考文獻:

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

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

[3] 教育部高等學校計算機科學與技術教學指導委員會. 高等學校計算機科學與技術專業實踐教學體系與規范[M]. 北京:清華大學出版社,2008.