趙會群 孫 晶 譚效輝

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

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

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

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

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

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

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

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

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

1球類腳本描述語言

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

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

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

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

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

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

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

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

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

2.1詞法分析器

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

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

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

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

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

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

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

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

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

Output: 描述語言完全碼

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

Word=Read(code); // 輸入一個單詞符號//

Do while word<>‘

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

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

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

else if field(previous_word,target_position)=num

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

word=read(code);

enddo

Step2: 詞法檢測、動作補(bǔ)償

Word=Read(code); //輸入一個單詞符號//

Do while word<>‘

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

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

then field(word, style_position)=‘z;

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

then field(word, style_position)=‘f;

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

word=read(code);

enddo

end

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

2.2語法分析器

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

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

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

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

證明:為每一個非終結(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)文法。

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

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

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

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

Flag = TRUE;

Do while (Flag)

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

If( X是文法中終結(jié)符號中的一個)

{If(X==a) Then

把下一個符號讀進(jìn)a

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

else

Flag = FALSE; //詞法錯誤

}

else if (X==#)

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

else Flag = FALSE; //詞法分析錯誤}

else

{

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

找出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í)行時間為O(M*N),M和N分別為預(yù)測分析表的行和列下標(biāo)。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4結(jié)論

筆者在本文中設(shè)計了一個球類比賽腳本描述語言編譯器實(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è)計的編譯器實(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ì),還是在高級語言編譯器的實(shí)現(xiàn)技術(shù)基礎(chǔ)上完成,只是對具體的語言背景進(jìn)行了調(diào)整,同樣可以達(dá)到系統(tǒng)掌握編譯原理的教學(xué)要求,讀者可以根據(jù)自己的實(shí)際情況,選擇本實(shí)驗(yàn)作為教學(xué)補(bǔ)充內(nèi)容。

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

參考文獻(xiàn):

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

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

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

[4] 趙會群,孫晶. 體育計算:一個新的計算機(jī)應(yīng)用研究領(lǐng)域[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.