一個(gè)編譯器實(shí)驗(yàn)的設(shè)計(jì)與實(shí)現(xiàn)

趙會(huì)群 孫 晶 譚效輝

摘要:本文介紹了一個(gè)適合描述球類比賽戰(zhàn)術(shù)特點(diǎn)的腳本描述語言,并把該語言作為實(shí)驗(yàn)題目進(jìn)行實(shí)驗(yàn)教學(xué),介紹了學(xué)生設(shè)計(jì)并實(shí)現(xiàn)的腳本描述語言編譯器,該腳本描述語言的詞法和文法描述定義,給出詞法分析器和語法分析器的結(jié)構(gòu)設(shè)計(jì),最后介紹實(shí)現(xiàn)中采用的關(guān)鍵技術(shù)。

關(guān)鍵詞:腳本描述語言;詞法分析器;語法分析器

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

傳統(tǒng)的編譯原理實(shí)驗(yàn)基本以高級(jí)程序設(shè)計(jì)語言為對(duì)象進(jìn)行組織,一般包括詞法分析、語法分析和語義分析等,教學(xué)內(nèi)容和實(shí)驗(yàn)設(shè)計(jì)幾乎幾十年不變。由于現(xiàn)在的本科生畢業(yè)后很少有機(jī)會(huì)從事高級(jí)語言翻譯工作,所以學(xué)生對(duì)該課程的興趣不大。隨著計(jì)算機(jī)技術(shù)的發(fā)展和基于互聯(lián)網(wǎng)的搜索技術(shù)和智能處理技術(shù)的廣泛應(yīng)用,編譯技術(shù)已經(jīng)不再局限于高級(jí)語言的翻譯和處理——利用編譯原理解決更廣泛的應(yīng)用問題是新的需求。因此筆者在這方面也做了有益嘗試。

腳本語言是隨著互聯(lián)網(wǎng)發(fā)展起來的信息描述技術(shù),它具有以下特點(diǎn):

(1) 腳本語言簡(jiǎn)單易學(xué),開發(fā)成本較低。

(2) 腳本語言很容易被解釋執(zhí)行,而且花費(fèi)時(shí)間比較短。

(3) 腳本描述語言設(shè)計(jì)的設(shè)備無關(guān)性。

但是,腳本描述語言沒有自然語言容易理解,所以最終還是要把腳本語言翻譯為自然語言(目標(biāo)語言)。一般編程語言編寫的程序要在計(jì)算機(jī)上運(yùn)行,必須轉(zhuǎn)化為計(jì)算機(jī)能夠識(shí)別的機(jī)器語言,轉(zhuǎn)化過程一般包括詞法分析、語法分析、語義分析、中間代碼生成、代碼優(yōu)化和目標(biāo)代碼生成等環(huán)節(jié)。我們?cè)O(shè)計(jì)的球類腳本描述語言主要用于對(duì)體育比賽視頻進(jìn)行標(biāo)準(zhǔn)化,所以在語言構(gòu)成上沒有高級(jí)語言復(fù)雜,翻譯時(shí)也不需要上面提到的編譯實(shí)現(xiàn)全過程,只需要進(jìn)行詞法分析、語法分析和語義分析3個(gè)環(huán)節(jié)。

1球類腳本描述語言

隨著社會(huì)文明的發(fā)展與進(jìn)步,體育比賽已經(jīng)成為人民文化生活中不可缺少的組成部分。2008年,北京成功舉辦了第29屆奧林匹克運(yùn)動(dòng)會(huì),運(yùn)動(dòng)員共打破38項(xiàng)世界紀(jì)錄,取得了驕人的成績。作為本次奧運(yùn)會(huì)科技攻關(guān)課題組的成員,我們參加了國家乒乓球隊(duì)攻關(guān)項(xiàng)目的研究工作,為中國乒乓球隊(duì)設(shè)計(jì)實(shí)現(xiàn)了一個(gè)基于視頻標(biāo)注的技、戰(zhàn)術(shù)分析系統(tǒng)。我們采用編譯技術(shù)翻譯乒乓球腳本描述語言,實(shí)時(shí)、準(zhǔn)確地記錄并分析比賽中發(fā)生的各種技、戰(zhàn)術(shù)細(xì)節(jié),為教練員提供客觀翔實(shí)的分析數(shù)據(jù)。

作為“編譯原理”的任課教師,我們認(rèn)為該課對(duì)學(xué)生系統(tǒng)掌握計(jì)算機(jī)基礎(chǔ)理論十分重要,但由于學(xué)生在今后工作中很難用到編譯技術(shù),就會(huì)產(chǎn)生厭學(xué)思想,因此為學(xué)生設(shè)計(jì)一個(gè)好的編譯原理實(shí)驗(yàn)成為當(dāng)務(wù)之急。為此,我們結(jié)合承擔(dān)的科研課題,設(shè)計(jì)了一個(gè)既讓學(xué)生感興趣,又能加深他們對(duì)編譯原理思想理解的實(shí)驗(yàn)。

根據(jù)球類比賽的特點(diǎn)和腳本描述語言的設(shè)計(jì)要求,球類比賽可分為兩種:一是比賽需主、客隊(duì)同臺(tái)(場(chǎng))競(jìng)技,如沙灘排球、乒乓球、籃球、足球和網(wǎng)球等;二是主、客隊(duì)輪流上場(chǎng),比賽對(duì)手不是同臺(tái)競(jìng)技,如臺(tái)球和保齡球等。第一種球類比賽具有以下特點(diǎn):(1)進(jìn)攻/防守形成博弈;(2)博弈雙方的技術(shù)動(dòng)作具有相似性。為此,我們把第一種比賽的相關(guān)技、戰(zhàn)術(shù)描述抽象成如下形式:

隊(duì)員+技術(shù)動(dòng)作+技術(shù)動(dòng)作發(fā)生區(qū)域+技術(shù)動(dòng)作結(jié)束區(qū)域

我們的設(shè)計(jì)目標(biāo)主要針對(duì)第一種比賽。腳本描述語言的語法結(jié)構(gòu)如圖1所示。

其中單詞由英文字母構(gòu)成,可以采用漢語拼音的字首進(jìn)行編碼;句子由單詞加分隔符“●”構(gòu)成。圖2是一個(gè)乒乓球比賽腳本描述語言的案例。

2解釋器的設(shè)計(jì)與實(shí)現(xiàn)

根據(jù)球類比賽技、戰(zhàn)術(shù)分析的需求,設(shè)計(jì)的解釋器由

詞法器、語法器和語義分析模塊三部分組成,如圖3所示。其中詞法分析器負(fù)責(zé)詞法分析的預(yù)處理和輸入單詞的解釋;語法分析器負(fù)責(zé)分析輸入碼的語法結(jié)構(gòu)檢查和解釋;在詞法和語法分析器的基礎(chǔ)上,語義分析模塊負(fù)責(zé)比賽技戰(zhàn)術(shù)的分類與統(tǒng)計(jì)工作。下面分別介紹上述邏輯部件的設(shè)計(jì)與實(shí)現(xiàn)。

2.1詞法分析器

根據(jù)第1節(jié)對(duì)球類比賽腳本描述語言語法結(jié)構(gòu)的設(shè)計(jì)以及球類比賽描述的特點(diǎn),我們對(duì)該描述語言的單詞符號(hào)進(jìn)行設(shè)計(jì)。單詞符號(hào)有以下4種:

(1) 技術(shù)動(dòng)作描述符:一般由四類字符組成,英文字母、數(shù)字、“+”和“-”。其中,英文字母是技術(shù)動(dòng)作的編碼,由一個(gè)編碼映射表支持詞法解釋;數(shù)字用于描述技術(shù)動(dòng)作發(fā)生的區(qū)域,該語言總是把比賽場(chǎng)地分割成若干個(gè)不同的區(qū)域;“+”和“-”是兩個(gè)特殊符號(hào),一般用于一些極其特殊的技、戰(zhàn)術(shù)描述,如乒乓球中的“擦邊球”或“擦網(wǎng)”等。

(2) 間隔符:用于區(qū)分不同的技術(shù)動(dòng)作,一般用“●”表示。

(3) 保留字:為了明確標(biāo)示比賽視頻的開始和結(jié)束、每一小節(jié)或單局比賽的開始和結(jié)束、比賽中的暫停和開始,設(shè)計(jì)了一些保留字,如Match: Start、Match: End、Set1:Start、Set1:End等。

(4) 控制符:用于比賽中的比分調(diào)整,如ap03:05、*p02:05。

上述單詞符號(hào)構(gòu)成單詞的詞法分析狀態(tài)轉(zhuǎn)換描述如圖4所示。

上述詞法分析的算法如下:

算法1一個(gè)乒乓球腳本描述語言的詞法分析算法

Input: 基于乒乓球比賽腳本簡(jiǎn)碼的技戰(zhàn)術(shù)輸入碼

Output: 描述語言完全碼

Step1: 詞法檢測(cè)、運(yùn)動(dòng)區(qū)域補(bǔ)償

Word=Read(code); // 輸入一個(gè)單詞符號(hào)//

Do while word<>‘

If field(word, Last_position )=‘● then break

else if field(word,start_position )and field(word,target_position )=

num then return //詞法檢測(cè)結(jié)束//

else if field(previous_word,target_position)=num

then field(word, start_position)=field(previous_word,target_position);

word=read(code);

enddo

Step2: 詞法檢測(cè)、動(dòng)作補(bǔ)償

Word=Read(code); //輸入一個(gè)單詞符號(hào)//

Do while word<>‘

If field(word, style_position )<>‘ then break;

else if word.artribute=offence and field(word,start_position )=right_domain //該動(dòng)作為進(jìn)攻動(dòng)作//

then field(word, style_position)=‘z;

else if word.artribute=offence and field(word,start_position )=left_domain //該動(dòng)作為進(jìn)攻動(dòng)作//

then field(word, style_position)=‘f;

else print(‘a(chǎn)n error be found);

word=read(code);

enddo

end

在上面的算法中,每一個(gè)單詞由四位碼構(gòu)成,field(word, style_position)是單詞的第一位,表示動(dòng)作的方式;field(word, act_position)是單詞的第二位,表示動(dòng)作的類型;field(word, start_position)是單詞的第三位,表示球的起點(diǎn);field(word, target_position)是單詞的第四位,表示球飛行的結(jié)束位置。該算法需要兩次遍歷輸入碼,因此算法的復(fù)雜性為O(L)。

2.2語法分析器

根據(jù)圖1所示的腳本描述語言結(jié)構(gòu),它的文法G如圖5所示:

其中:S為開始符號(hào),表示一個(gè)輸入碼,T為非終結(jié)符,它可以是ε 字;C1為動(dòng)作方式碼,它只能產(chǎn)生一個(gè)表示動(dòng)作方式終結(jié)符號(hào);C2為動(dòng)作分類碼,它只能產(chǎn)生一個(gè)表示動(dòng)作的終結(jié)符號(hào);N1為動(dòng)作起始區(qū)域,它只能產(chǎn)生一個(gè)表示區(qū)域的終結(jié)符號(hào),N2為動(dòng)作終止區(qū)域,它只能產(chǎn)生一個(gè)表示區(qū)域的終結(jié)符號(hào)。

例如:乒乓球比賽的輸入碼為:ZX16●FB66●T62● ZH23●ZH33●ZH33●ZH31。它表示:正手發(fā)下旋球從1區(qū)到6區(qū)●對(duì)方反手?jǐn)[短從6區(qū)到6區(qū)●反手挑到2區(qū)●對(duì)手正手弧圈球從2區(qū)到3區(qū)●正手弧圈球從3區(qū)到3區(qū)●對(duì)手正手弧圈球從3區(qū)到3區(qū)●正手弧圈球至對(duì)方1區(qū)后得分。

定理:文法G是LL(1)文法。

證明:為每一個(gè)非終結(jié)符求FIRST()集和FOLLOW()集如下:

FIRST(S)={w, ε}; FIRST(T)={w,ε}; FIRST(S)

={●,ε};FIRST(W)={w};

FOLLOW(S)={#}, FOLLOW(T)={● , #}; FIRST(S)

={#}; FOLLOW(W)={●, #}

由LL(1)文法的條件可知,G文法滿足:

FIRST(αi) ?FIRST(αj)=?;

FOLLOW(A) ?FOLLOW(A) = ?

因此,G是LL(1)文法。

對(duì)文法G的語法分析可以采用遞歸下降法或預(yù)測(cè)分析表法。由于腳步描述語言中采用的文法符號(hào)可以自定義,符號(hào)的數(shù)量并不多,所以建議采用預(yù)測(cè)分析表來實(shí)現(xiàn)。下面是一個(gè)改進(jìn)的預(yù)測(cè)分析表算法。

算法2基于預(yù)測(cè)分析的語法分析算法

首先把“#”,然后把文法開始符號(hào)“S”推進(jìn)棧charstack;

把第一個(gè)輸入符號(hào)讀進(jìn)a(char類型);

Flag = TRUE;

Do while (Flag)

{取棧(charstack)頂?shù)脑胤湃隭(char類型)中

If( X是文法中終結(jié)符號(hào)中的一個(gè))

{If(X==a) Then

把下一個(gè)符號(hào)讀進(jìn)a

把棧頂?shù)脑貏h除

else

Flag = FALSE; //詞法錯(cuò)誤

}

else if (X==#)

{if (X==a) then Flag = TRUE; //詞法分析結(jié)束

else Flag = FALSE; //詞法分析錯(cuò)誤}

else

{

找出X在二維數(shù)組中的行數(shù)Row; //用二維數(shù)組表示預(yù)測(cè)分析表

找出a在二維數(shù)組中的列數(shù)Column; //CString m_strTemp[4[6]

If (m_strTemp[Row][Column]!=“ ” && m_strTemp[Row][Column]!=“E”) //E代表ε

把棧頂元素刪除;

把m_strTemp[Row][Column]中的元素從后往前推入棧中;

else if (m_strTemp[Row][Column]==“E”) then 刪除棧頂元素;

else Flag = FALSE;

}

}

算法2的執(zhí)行時(shí)間為O(M*N),M和N分別為預(yù)測(cè)分析表的行和列下標(biāo)。

3實(shí)驗(yàn)設(shè)計(jì)

根據(jù)第2節(jié)對(duì)球類腳本描述語言中詞法、語法分析器的討論,我們?cè)O(shè)計(jì)了兩個(gè)實(shí)驗(yàn):

實(shí)驗(yàn)一:基于球類腳本描述語言的詞法分析器的設(shè)計(jì)與實(shí)現(xiàn)。

實(shí)驗(yàn)?zāi)康?通過本實(shí)驗(yàn),學(xué)生掌握詞法分析器的體系結(jié)構(gòu)、各功能部件的設(shè)計(jì)與實(shí)現(xiàn)方法,為進(jìn)一步學(xué)習(xí)語法分析器奠定基礎(chǔ),能夠靈活掌握詞法分析的原理和技術(shù)。

實(shí)驗(yàn)條件:圖6給出了一個(gè)乒乓球臺(tái)的分割圖,用于表示擊球的區(qū)域;表1和表2分別用于描述擊球的方式和動(dòng)作,這些描述信息可以供學(xué)生設(shè)計(jì)乒乓球腳本描述語言時(shí)參考。

實(shí)驗(yàn)要求:

? 畫出腳本描述語言的體系結(jié)構(gòu)圖,并定義各個(gè)功能模塊的實(shí)現(xiàn)策略

? 定義一個(gè)小型球類腳本描述語言,可以參照乒乓球比賽的技戰(zhàn)術(shù)描述需求定義,具體形式如圖6所示

? 完成一個(gè)實(shí)驗(yàn)報(bào)告,分析具體輸出結(jié)果的 語義

實(shí)驗(yàn)二:基于文法G的語法分析器設(shè)計(jì)與實(shí)現(xiàn)

實(shí)驗(yàn)?zāi)康?通過本實(shí)驗(yàn),學(xué)生掌握語法分析器的體系結(jié)構(gòu)、各功能部件的設(shè)計(jì)與實(shí)現(xiàn)方法,為進(jìn)一步學(xué)習(xí)語義分析器奠定基礎(chǔ),能夠靈活掌握語法分析的原理和技術(shù)。

實(shí)驗(yàn)條件:表3給出了預(yù)測(cè)分析表結(jié)構(gòu),學(xué)生根據(jù)所設(shè)計(jì)的描述語言填寫具體預(yù)測(cè)動(dòng)作。

實(shí)驗(yàn)要求:

? 給出非簡(jiǎn)化G文法,對(duì)其進(jìn)行消除左遞歸操作

? 在實(shí)驗(yàn)一定義的球類腳本描述語言基礎(chǔ)上設(shè)計(jì)具體的符號(hào)表

? 手工完成預(yù)測(cè)分析表的構(gòu)造,如表3所示,并用數(shù)組結(jié)構(gòu)存儲(chǔ)

? 完成一個(gè)實(shí)驗(yàn)報(bào)告,分析具體輸出結(jié)果的 語義

4結(jié)論

筆者在本文中設(shè)計(jì)了一個(gè)球類比賽腳本描述語言編譯器實(shí)驗(yàn),給出球類腳本描述語言的語法結(jié)構(gòu),包括詞法和文法規(guī)則;給出了詞法分析器和語法分析器實(shí)現(xiàn)需要的關(guān)鍵算法,為學(xué)生進(jìn)一步實(shí)現(xiàn)奠定了基礎(chǔ);給出詞法分析器和語法分析器實(shí)驗(yàn)?zāi)０?為學(xué)生完成實(shí)驗(yàn)規(guī)范了必要的格式和實(shí)驗(yàn)要求。

與傳統(tǒng)的編譯器實(shí)驗(yàn)相比,本文設(shè)計(jì)的編譯器實(shí)驗(yàn)有較強(qiáng)的應(yīng)用背景,更接近大學(xué)生的實(shí)際經(jīng)歷,能夠激發(fā)絕大多數(shù)學(xué)生的學(xué)習(xí)熱情,收到了比較好的教學(xué)效果。本實(shí)驗(yàn)并沒有改變傳統(tǒng)實(shí)驗(yàn)的本質(zhì),還是在高級(jí)語言編譯器的實(shí)現(xiàn)技術(shù)基礎(chǔ)上完成,只是對(duì)具體的語言背景進(jìn)行了調(diào)整,同樣可以達(dá)到系統(tǒng)掌握編譯原理的教學(xué)要求,讀者可以根據(jù)自己的實(shí)際情況,選擇本實(shí)驗(yàn)作為教學(xué)補(bǔ)充內(nèi)容。

自行設(shè)計(jì)腳本描述語言并實(shí)現(xiàn)其編譯器是我們的一種嘗試,該項(xiàng)工作基于我國的奧運(yùn)攻關(guān)課題。在完成科研任務(wù)的同時(shí),我們將對(duì)教學(xué)環(huán)節(jié)進(jìn)行適當(dāng)?shù)难a(bǔ)充和擴(kuò)展,希望讀者提出寶貴意見。

參考文獻(xiàn):

[1] 陳火旺,劉春林. 程序設(shè)計(jì)語言編譯原理[M]. 3版. 北京:國防工業(yè)出版社,2000.

[2] 官尚元,張芝萍,徐立鋒,等. C/C++代碼自動(dòng)生成腳本語言接口的實(shí)現(xiàn)[J]. 計(jì)算機(jī)工程,2005,31(8):102-104.

[3] 李愛萍,王家禮,段利國. ATLAS語言中大量關(guān)鍵詞的處理方法研究[J]. 計(jì)算機(jī)工程與設(shè)計(jì),2006,27(9):1581-1582,1600.

[4] 趙會(huì)群,孫晶. 體育計(jì)算:一個(gè)新的計(jì)算機(jī)應(yīng)用研究領(lǐng)域[J]. 計(jì)算機(jī)科學(xué),2004,31(8):89-92.

[5] Zhao HQ,Chen L. The Application of PipeFilter Architecture to Semantic Analysis and the Realization Skills and Tactics of Table Tennis Analysis System[C]. Nanjing,2008.