“編譯原理”綜合應(yīng)用型教學(xué)案例的設(shè)計

張妮 嚴(yán)迪新 陸衛(wèi)忠

摘 要：針對“編譯原理”課程教學(xué)中缺乏實踐的問題，設(shè)計了一個實踐強化的綜合應(yīng)用型教學(xué)案例。該案例以編譯原理課程為中心，綜合運用了多門計算機專業(yè)課程的相關(guān)知識，并具有相似性檢測的功能，能對學(xué)生提交的程序設(shè)計類作業(yè)進(jìn)行相似性檢測，以發(fā)現(xiàn)學(xué)生作業(yè)的原創(chuàng)性。學(xué)生通過對給出知識點的組合和擴展，完成案例的設(shè)計和程序?qū)崿F(xiàn)。彌補了課程教學(xué)中存在的不足，并具有一定的實用性。

關(guān)鍵詞：編譯原理；教學(xué)案例；相似性檢測

中圖分類號：G64文獻(xiàn)標(biāo)識碼：A 文章編號：1673-9795（2014）04（A）-0000-00

Design of an Integrated Application-oriented Teaching Instance

in “Compiler Principle”

ZHANG Ni，YAN Di-xin，LU Wei-zhong

（School of Electronic and Information Engineering， USTS， Suzhou 215011）

Abstract： Facing to the practice problems of the lack of the "compiler principle" teaching，the paper designed an integrated application-oriented teaching instance . The instance make compiler principle course as center， and integrate using of the relations knowledge of other professional courses，and has a similar detection function which can detect similarity of the students project， and verify the originality of students project. The design and implementation of the instance are completed by different combinations and expansion of knowledge. The instance make up for the deficiencies in teaching process， and also has a certain practicality.

Key words： Compiling Principles； teaching instance； similarity detection

“卓越工程師教育培養(yǎng)計劃”是教育部于2010年6月啟動的為期10年（2010—2020年）的重大改革項目。該計劃旨在培養(yǎng)一大批創(chuàng)新能力強、適應(yīng)社會經(jīng)濟發(fā)展需要的高質(zhì)量工程技術(shù)人才[1-3]。編譯原理課程作為計算機專業(yè)卓越工程師培養(yǎng)計劃中一門核心專業(yè)基礎(chǔ)課程，在新形勢下要求其教學(xué)過程必須以學(xué)生為中心，鞏固理論知識，加強實踐教學(xué)，注重學(xué)生創(chuàng)新意識的培養(yǎng)。

然而，由于編譯原理課程教學(xué)內(nèi)容不僅包含形式語言、有限自動機、正規(guī)文法、正規(guī)表達(dá)式和LL（1）分析法等理論知識，而且編譯的每個階段都包含大量的復(fù)雜算法，學(xué)生在學(xué)習(xí)過程中感到抽象和難以理解[4]。通過對國內(nèi)各高等院校教學(xué)現(xiàn)狀的調(diào)查，目前編譯原理課程教學(xué)過程中存在編譯教學(xué)難點較多[5]，實踐環(huán)節(jié)缺少實際應(yīng)用背景和以及未與其他課程進(jìn)行有效的融合[6]等幾個方面問題。為了達(dá)到“卓越計劃”培養(yǎng)目標(biāo)，必須對現(xiàn)有的教學(xué)方法和手段進(jìn)行改革，探討如何將編譯原理課程的理論知識應(yīng)用于實踐或?qū)嶋H項目和如何加強編譯原理課程與其他計算機課程之間的聯(lián)系的問題，更好地將理論知識點貫穿融合到實踐教學(xué)或?qū)嶋H項目中。

本文在“卓越計劃項目”的資助下，將案例教學(xué)法[7，12，13]引入編譯原理課程的教學(xué)過程中。通過選取恰當(dāng)?shù)睦碚撝R點，結(jié)合數(shù)據(jù)結(jié)構(gòu)、面向?qū)ο蟪绦蛟O(shè)計等計算機專業(yè)的相關(guān)課程，設(shè)計了一個能吸引學(xué)生興趣，實踐強化的綜合應(yīng)用型教學(xué)案例。

1 案例設(shè)計思想及意義

在計算機專業(yè)程序設(shè)計類課程的教學(xué)過程中，學(xué)生提交作業(yè)的形式是源程序的電子文檔，這為有些同學(xué)拷貝和抄襲提供了便利，不僅影響學(xué)生對課程的掌握度，還影響了老師判分的公正性。程序相似性檢測技術(shù)能夠?qū)W(xué)生提交的程序設(shè)計作業(yè)進(jìn)行檢測，驗證學(xué)生作業(yè)的原創(chuàng)性，幫助教師在大量的學(xué)生作業(yè)中找出相似性較高，即存在抄襲嫌疑的作業(yè)對象[11]，也有利于發(fā)現(xiàn)學(xué)生的創(chuàng)新性成果。通常程序相似性檢測過程由程序源代碼預(yù)處理，源代碼轉(zhuǎn)化，相似性比較，結(jié)果檢測四個階段構(gòu)成。

在設(shè)計案例時，我們用編譯原理課程中詞法分析和語法分析算法思想來完成代碼相似性檢測過程中的源代碼預(yù)處理和源代碼轉(zhuǎn)化兩個階段，使用數(shù)據(jù)結(jié)構(gòu)課程中學(xué)過的字符串比較算法（如最長公共子序列算法等）作為相似性檢測算法，可以選擇案例開發(fā)環(huán)境有Eclipse，VC6.0和VS2010等。

此案例以編譯原理課程為中心，結(jié)合了數(shù)據(jù)結(jié)構(gòu)、面向?qū)ο蟪绦蛟O(shè)計等計算機專業(yè)的相關(guān)課程，實現(xiàn)了具有程序相似性檢測功能的系統(tǒng)。大多數(shù)學(xué)生在理解和掌握案例中給出知識點的基礎(chǔ)上，通過對其進(jìn)行不同組合來完成案例的設(shè)計和程序?qū)崿F(xiàn)，達(dá)到教學(xué)的基本要求，基礎(chǔ)好的學(xué)生在掌握已給出案例的基礎(chǔ)上選擇更難的知識點來設(shè)計和實現(xiàn)案例，學(xué)到更多知識。使學(xué)生通過一個綜合案例的設(shè)計和實現(xiàn)，鞏固了多門課程的相關(guān)知識點，彌補了課程教學(xué)中缺乏實踐的問題，加強計算機相關(guān)課程之間的橫向聯(lián)系，培養(yǎng)學(xué)生的學(xué)以致用的實踐能力和創(chuàng)新能力。

2 案例相關(guān)的知識點

案例教學(xué)法的核心是案例的設(shè)計，案例設(shè)計應(yīng)該與教學(xué)內(nèi)容、教學(xué)進(jìn)度相適宜，能恰當(dāng)?shù)厝谌胂嚓P(guān)的知識點。本案例的相關(guān)知識點有：與編譯原理課程相關(guān)的基于程序設(shè)計語言的詞法分析程序?qū)崿F(xiàn)方法（手工方式）和基于LEX的詞法分析程序?qū)崿F(xiàn)方法（自動方式）；與數(shù)據(jù)結(jié)構(gòu)課程相關(guān)的一些字符串比較算法，如最長公共子序列（LCS）算法，Halstead算法和RKR-GST算法等；以及有一定的面向?qū)ο缶幊袒A(chǔ)，能使用JAVA，C++，C#等其中一種語言編寫程序。學(xué)生在熟悉和掌握這些知識點的基礎(chǔ)上進(jìn)行案例的設(shè)計和實現(xiàn)。

2.1 詞法分析程序的實現(xiàn)方法

詞法分析程序的工作原理是，從左至右掃描源程序的字符串，按照詞法規(guī)則（正則文法規(guī)則）識別出一個個正確的單詞，并轉(zhuǎn)換成該單詞相應(yīng)的二元式（種別碼、屬性值），以數(shù)組、鏈表或文本文件等形式保存，交給后續(xù)模塊使用。通常構(gòu)造詞法分析程序有兩種方法。第一種是手工方式，即根據(jù)識別語言單詞的狀態(tài)轉(zhuǎn)換圖，使用某種高級程序設(shè)計語言，如C、C++、JAVA等，直接編寫詞法分析程序。第二種是自動方式，即利用LEX工具自動生成詞法分析程序。

2.1.1 基于程序設(shè)計語言的詞法分析程序

設(shè)計的主要思想就是構(gòu)造出目標(biāo)語言單詞符號的有窮自動機（DFA）。手工方式實現(xiàn)詞法分析的程序的步驟分為四個階段，第一，定義目標(biāo)語言的可用符號表和構(gòu)詞規(guī)則，即目標(biāo)語言單詞的狀態(tài)轉(zhuǎn)換圖；第二，依次讀入源程序符號，對源程序進(jìn)行單詞切分和識別，直到源程序結(jié)束；第三，對正確的單詞，按照它的種別以〈記號類別，屬性值〉的形式保存在符號表（ 數(shù)組或鏈表）中；最后對不正確的單詞，做出錯誤處理。

2.1.2 基于 LEX的詞法分析程序

LEX是一個詞法分析器[8]的自動生成系統(tǒng)，它的輸入是一個文本文件，文件的擴展名習(xí)慣用.l表示，稱之為LEX源文件，該文件包含了用戶定義的正規(guī)表達(dá)式以及每個正規(guī)表達(dá)式相對應(yīng)的處理動作。LEX的工作原理是將源程序中的正規(guī)式轉(zhuǎn)換成相應(yīng)的DFA，而相應(yīng)的動作則插入到輸出的詞法分析器中適當(dāng)?shù)牡胤剑刂屏饔稍揇FA的解釋器掌握。對不同的源程序，這個解釋器是相同的。LEX最常見的版本是Flex，可以免費得到。基于 LEX的詞法分析程序設(shè)計思路：編寫LEX源文件，按要求抽象出正規(guī)表達(dá)式，同時濾掉輸入串中所有的空格、Tab、回車及注釋，最終形成.l文件。最后使用Flex編譯器生成詞法分析程序。

2.2 字符串匹配算法

除了數(shù)據(jù)結(jié)構(gòu)課程已經(jīng)介紹的字符串匹配算法（KMP算法），本案例還可以使用其他的字符串匹配算法，如最長公共子序列（LCS）算法，Halstead算法和RKR-GST算法等。依據(jù)詞法分析程序的輸出結(jié)果（單詞符號串），利用字符串匹配算法來度量兩個標(biāo)記串的相似度。本案例提供這些算法的實現(xiàn)思想和源代碼，供學(xué)生參考和進(jìn)一步改進(jìn)。

2.2.1 最長公共子序列（LCS）算法

LCS（Longest Common Subsequence）算法[9]即求兩個字符串的最長公共子序列算法。算法的主要思想是用一個矩陣來記錄兩個字符串中所有位置的兩個字符之間的匹配情況，若是匹配則為1，否則為0。然后求出對角線最長的1序列，其對應(yīng)的位置就是最長公共子序列的位置。其算法由求最長公共子序列的長度Length（l，j）和最長公共子序列LCS（A，B）兩步構(gòu)成。

2.2.2 Halstead算法

Halstead算法[10]以源代碼中出現(xiàn)的操作符和操作數(shù)為計數(shù)對象，以它們的出現(xiàn)次數(shù)作為計數(shù)目標(biāo)來測算程序容量和工作量。其基本原理是：統(tǒng)計每個程序段中用到的操作符和操作數(shù)，最終生成一個特征向量。操作符包括所使用編程語言的關(guān)鍵字、運算符和標(biāo)準(zhǔn)庫名稱。操作數(shù)是指程序段中所有由用戶自己定義的符號串。系統(tǒng)為每個待檢測相似性的源代碼生成一個特征向量之后，再計算每兩個向量之間的歐幾里德距離，若兩個程序段的特征向量之間的距離很小，就可以認(rèn)為這兩段程序很相似。

2.2.3 RKR-GST算法

RKR-GST （Running Karp Rabin Greedy String Tiling）是一種貪婪式字符串匹配算法[14]，循環(huán)求取兩個標(biāo)記串中未被匹配部分的最大公共子串，并根據(jù)相應(yīng)公式求出兩個字符串的相似度。對源程序代碼進(jìn)行相似性檢測的過程通常可分為兩個階段：第一階段，對源程序進(jìn)行詞法分析或語法分析，剔除與程序結(jié)構(gòu)無關(guān)的表面元素，產(chǎn)生標(biāo)準(zhǔn)化輸出。第二階段，采用字符串匹配技術(shù)兩兩比較各程序的標(biāo)準(zhǔn)化輸出，進(jìn)行相似度度量，求出其相似度。

3 案例設(shè)計與實現(xiàn)

本案例要求學(xué)生選擇一種熟悉的開發(fā)平臺（VC 6.0，Eclipse，VS 2010等），依照第二節(jié)中給出的基本知識點（學(xué)生需提前查閱相關(guān)資料，做好預(yù)習(xí)），通過對知識點的不同組合和擴展，如基于程序設(shè)計語言的詞法分析程序+ LCS算法，基于 LEX的詞法分析程序+RKR-GST算法和基于程序設(shè)計語言的詞法分析程序+RKR-GST算法等，設(shè)計具有程序相似性檢測功能的系統(tǒng)，然后編程實現(xiàn)綜合教學(xué)案例系統(tǒng)。

在此，將以采用基于 LEX的詞法分析程序（自動方式）來完成代碼預(yù)處理及轉(zhuǎn)換，使用RKR-GST算法進(jìn)行代碼相似性檢測為例，給出設(shè)計和實現(xiàn)程序相似性檢測系統(tǒng)的過程。在學(xué)生設(shè)計和實現(xiàn)本案例前，教師先演示這個已事先設(shè)計好的案例供學(xué)生參考，讓學(xué)生對案例實現(xiàn)過程有一個直觀的認(rèn)識。本次設(shè)計具體分為代碼預(yù)處理及轉(zhuǎn)換、將源代碼轉(zhuǎn)化為標(biāo)記串、RKR-GST算法實現(xiàn)及結(jié)果分析四個階段。

3.1代碼預(yù)處理及轉(zhuǎn)換階段

在理解有窮自動機知識點的基礎(chǔ)上，結(jié)合第二節(jié)中給出的設(shè)計思想，設(shè)計了LEX源文件——LexScanning.l，其中自定義了一些詞法規(guī)則、getToken（）以及printToken（）等函數(shù)，實現(xiàn)了詞法分析功能，同時濾掉了用戶源程序中所有的空格、Tab、回車及注釋。如圖1所示。之后使用Flex編譯器將LexScanning.l文件編譯生成名為CiFa.exe詞法分析程序。

圖1 LexScanning.l文件

3.2將源代碼轉(zhuǎn)化為標(biāo)記串

在主程序中運行時，通過創(chuàng)建一個線程來調(diào)用CiFa.exe文件，進(jìn)行詞法分析，將用戶源代碼轉(zhuǎn)化為標(biāo)記串。

3.2.1參數(shù)設(shè)置

STARTUPINFO si；

memset（&si，0，sizeof（STARTUPINFO））；

si.cb=sizeof（STARTUPINFO）；

si.dwFlags=STARTF_USESHOWWINDOW；

si.wShowWindow = SW_HIDE；

PROCESS_INFORMATION pi；

3.2.2 創(chuàng)建線程

CString cmd = _T（"CiFa.exe "）+m_file_path_1；

if（CreateProcess（_T（"CiFa.exe"），（LPTSTR）（LPCTSTR）cmd，NULL，NULL，F(xiàn)ALSE，0，NULL，NULL，&si，π））

{ WaitForSingleObject（pi.hProcess，INFINITE）；

CFile file（_T（"C：＼＼temp.txt"），CFile：：modeRead）；

……

dwFileLen=file.GetLength（）；

pBuf=new CHAR[dwFileLen+1]；

pBuf[dwFileLen]=0；

…… }

3.3 RKR-GST算法

兩個程序段之間的相似性即為它們對應(yīng)的標(biāo)記串之間的相似性。可將每個標(biāo)記串看成由若干個子串組成，那么兩個標(biāo)記串中相同的子串就是它們的公共子串，其相似性可用所有公共子串在整個串中所占的百分比表示。公式如下[14]：

其中： | A |、|B |為token串A、B的長度。match（i，j，length ） ： 在 A 中起始位置為i，在B中起始位置為j， 長度為n 的子串。Matches為公共子串集合。

案例中設(shè)計了函數(shù)void Greedy_String_Tiling （tile_type *tiles， char *A， char *B， unsigned MML） 循環(huán)求取兩個標(biāo)記串中未被匹配部分的最大公共子串，并根據(jù)公式求出兩個token串A、B的相似度。其中參數(shù) *tiles存放求出的所有最長公共子串，*A和*B分別來存放字符串A和字符串B，MML給出公共子串應(yīng)達(dá)到的最小長度。

4 系統(tǒng)的測試及結(jié)果分析

準(zhǔn)備了三個C語言源程序作為測試用例，其中測試用例一（test1.c）和測試用例二（test2.c）有少數(shù)變量名不一樣和源程序的組織結(jié)構(gòu)稍有差別之外，其他的內(nèi)容幾乎一樣。測試用例三（test3.c）與測試用例一和測試用例二在內(nèi)容和結(jié)構(gòu)上則完全不一樣。

4.1 test1.c與test2.c的比較

運行程序，點擊“瀏覽”按鈕選擇要比較的兩個源程序文件test1.c和test2.c，點擊“詞法分析”按鈕輸出test1.c和test2.c經(jīng)詞法分析后的結(jié)果，如圖2所示。

圖2 詞法分析結(jié)果

接下來，設(shè)置相似閾值為5之后，點擊“比較”按鈕，則進(jìn)行兩個源程序的相似性比較，比較的結(jié)果如圖3所示。兩個文件的相似度為91.089112%，結(jié)果符合我們的預(yù)想。

圖3 相似性檢測結(jié)果

4.2 test1.c與test3.c的比較圖4給出了test1.c和test3.c的相似性檢測結(jié)果，過程與上面相類似。相似度為13.265306%，符合我們的預(yù)期。

圖4 相似性檢測結(jié)果

5 結(jié)語

本文給出了筆者在編譯原理教學(xué)過程中使用的一個案例。該案例以編譯原理課程為中心，結(jié)合數(shù)據(jù)結(jié)構(gòu)、面向?qū)ο蟪绦蛟O(shè)計等計算機核心專業(yè)課程，將幾門課程的知識點聯(lián)系在一起，突出“編譯原理”課程的實用性。學(xué)生在實現(xiàn)綜合案例之前，教師通過對已實現(xiàn)案例的演示，讓學(xué)生有對實驗過程及要求有了直觀的了解，促使學(xué)生設(shè)計實現(xiàn)出更好的具有程序的相似性檢測功能系統(tǒng)，鞏固編譯原理和數(shù)據(jù)結(jié)構(gòu)等課程相關(guān)的知識點，激發(fā)學(xué)習(xí)興趣，提高學(xué)生的學(xué)習(xí)質(zhì)量和效率。今后的教學(xué)研究中，我們將對該案例進(jìn)行擴展，使之能分析如.net等高級語言編寫的源程序代碼，增加一些新的知識點，進(jìn)而可供高年級學(xué)生在課程設(shè)計中使用。

參考文獻(xiàn)

[1] 林健.面向卓越工程師培養(yǎng)的研究性學(xué)習(xí)[J]. 高等工程教育研究，2011，（6）：5-15.

[2] 徐世軍，范偉，黃賢英.面向卓越工程師培養(yǎng)的專業(yè)課程教學(xué)實踐. 計算機教育.2013（13） 22-25.

[3] 李鋒，夏小玲.計算機軟件工程專業(yè)卓越計劃實踐教學(xué). 計算機教育.2013（13） 18-21.

[4] 李冬梅，施海虎."編譯原理"課程的教學(xué)研究與探索. 計算機教育.2008（08）：10-12.

[5] 張昱，陳意云，鄭啟龍. 編譯原理課程的教學(xué)方法和教材建設(shè)[J]. 中國大學(xué)教學(xué)，2005，（7）：61-62.

[6] 計衛(wèi)星，陳英等.簡析計算機專業(yè)知識在編譯課程教學(xué)中的滲透與融合.計算機教育. 2010（03）：23-25.

[7] 秦艷琳，吳曉平.“信息安全數(shù)學(xué)基礎(chǔ)” 案例教學(xué)[J].計算機教育，2010（01）：141-144.

[8] 陳火旺，劉春林，譚慶平等. 程序設(shè)計語言編譯原理[M].北京：國防工業(yè)出版社，2000.

[9] 于海英.字符串相似度度量中LCS和GST算法比較[J].電子科技，2011（3）：101-103.

[10] Halstead， Howard M. Elements of Software Science[Z].Elsevier，1977.

[11] 張莉，周祖林.代碼相似性檢測在程序設(shè)計教學(xué)中的應(yīng)用.計算機教育.2009（13）：116-118.

[12] 張月琴，孫冰.案例教學(xué)法在“大學(xué)信息技術(shù)”課程中的應(yīng)用研究[J].中國電力教育，2012，（25）：63-64.

[13] 范巖.案例教學(xué)法在計算機教學(xué)中的應(yīng)用[J].科技信息，2008，（8）：35.

[14] Lutz Prechelt ， Guido Malpohl， and Michael Phlippsen. JPlag：Finding plagiarisms among a set of programs. Technical Report 2000-1， Fakult?t für Informatik， Universit?t Karlsruhe ， Germany， March 2000.