王大衛(wèi)，王俊峰

（四川大學(xué) 計(jì)算機(jī)學(xué)院，四川 成都610065）

0 引 言

使用TTCN－3編寫的測(cè)試程序，僅根據(jù)被測(cè)協(xié)議的規(guī)格進(jìn)行編寫，因此不可直接執(zhí)行，需要轉(zhuǎn)化為高級(jí)語(yǔ)言形式的可執(zhí)行測(cè)試集 （executable test suite，ETS）才能完成測(cè)試操作語(yǔ)義，傳遞給被測(cè)系統(tǒng)并完成交互［1－3］。因此，實(shí)現(xiàn)一個(gè)由TTCN－3到高級(jí)語(yǔ)言的轉(zhuǎn)換方案，解決轉(zhuǎn)換過程中出現(xiàn)的問題并最終生成高級(jí)語(yǔ)言，對(duì)基于TTCN－3的測(cè)試系統(tǒng)實(shí)現(xiàn)是十分重要的。

1 以C＋＋為目標(biāo)代碼的編譯測(cè)試

目前國(guó)內(nèi)外對(duì)TTCN－3測(cè)試平臺(tái)的構(gòu)建方案，基本都是根據(jù)TTCN－3核心語(yǔ)言的標(biāo)準(zhǔn)，編寫適配層，然后通過編譯、翻譯或解釋的方式，將TTCN－3測(cè)試腳本轉(zhuǎn)換為能夠被測(cè)試平臺(tái)執(zhí)行的對(duì)象，再由測(cè)試平臺(tái)執(zhí)行，與被測(cè)系統(tǒng)進(jìn)行交互、分析輸出、完成測(cè)試。常見的TTCN－3測(cè)試系統(tǒng)如中國(guó)科學(xué)技術(shù)大學(xué)的TTPlatForm［4］、Testingtech公司的TTWorkbench［5］、清華大學(xué)的PITSv3［6］均采用這種方式，只是其ATS→ETS的轉(zhuǎn)換方案各有不同，各方案特點(diǎn)見表1。

協(xié)議測(cè)試領(lǐng)域的發(fā)展現(xiàn)狀使得翻譯方案的工作量及維護(hù)難度變得難以大范圍應(yīng)用，將TTCN－3語(yǔ)言編譯為C＋＋并與C＋＋測(cè)試平臺(tái)聯(lián)合編譯的方案目前在業(yè)內(nèi)尚且屬于空白，C＋＋作為C語(yǔ)言的延伸，具備面向?qū)ο筇匦?，針?duì)協(xié)議測(cè)試的系統(tǒng)化自動(dòng)化的發(fā)展趨勢(shì)，其優(yōu)秀的執(zhí)行效率相對(duì)于Java，在通信設(shè)備測(cè)試領(lǐng)域具有十分明顯的優(yōu)勢(shì)。因此，本文通過詞法分析、語(yǔ)法分析、語(yǔ)義分析、代碼生成這4個(gè)步驟，將TTCN－3測(cè)試集編譯得到C＋＋代碼，再利用與測(cè)試平臺(tái)聯(lián)合編譯獲得可執(zhí)行系統(tǒng)［2］，并應(yīng)用于IPv6協(xié)議的一致性測(cè)試，其設(shè)計(jì)遵循TTCN－3標(biāo)準(zhǔn)，具有較好的應(yīng)用前景。其系統(tǒng)架構(gòu)如圖1所示。

表1 現(xiàn)有TTCN－3測(cè)試系統(tǒng)執(zhí)行方案特點(diǎn)

圖1 基于TTCN－3的IPv6一致性測(cè)試系統(tǒng)架構(gòu)

2 TTCN－3／C＋＋編譯器設(shè)計(jì)

由于測(cè)試平臺(tái)所能執(zhí)行的是C＋＋代碼，因此編譯器的目標(biāo)代碼即是C＋＋，需要詞法分析、語(yǔ)法分析、語(yǔ)義分析、代碼生成4個(gè)階段［7］，其中以TTCN－3v4.4.1核心語(yǔ)言標(biāo)準(zhǔn)的詞法／語(yǔ)法分析的前端部分為本文研究的重點(diǎn)。

通常詞法／語(yǔ)法分析可以使用一些自動(dòng)構(gòu)造解析工具來(lái)生成。目前常見的工具有Parser Generator，F(xiàn)lex／Bison，Antlr等。其中Parser Generator和Flex＆Bison 都是基于LEX 和YACC的工具，生成的是LALR（1）分析器。Antlr前身是PCCTS，生成LL（K）分析器［8］。

經(jīng)過分析研究，目前TTCN－3Core Language中對(duì)詞法語(yǔ)法表達(dá)的使用EBNF，更接近LEX／YACC 所能接受的LALR（1）文法；且LALR（1）分析器執(zhí)行效率要高于LL（k）分析器［3，9］，故本文采用基于LALR（1）文法分析工具Flex／Bison作為詞法／語(yǔ)法分析器的輔助工具。

本次設(shè)計(jì)的編譯器目標(biāo)語(yǔ)言為C＋＋，在測(cè)試平臺(tái)上通過extern “C”的方式聲明并調(diào)用函數(shù)，實(shí)現(xiàn)聯(lián)合編譯。編譯系統(tǒng)與測(cè)試平臺(tái)模塊設(shè)計(jì)如圖2所示。

圖2 編譯系統(tǒng)與測(cè)試平臺(tái)模塊設(shè)計(jì)

2.1 詞法分析器的實(shí)現(xiàn)

詞法分析是編譯過程的第一個(gè)階段。這個(gè)階段逐個(gè)字符地讀入TTCN－3源程序，產(chǎn)生單詞符號(hào)序列，以提交給語(yǔ)法分析使用。通過輸入表示詞法結(jié)構(gòu)的正則表達(dá)式及相應(yīng)的動(dòng)作，把解析動(dòng)作翻譯成一種高效的確定性有窮自動(dòng)機(jī)DFA［10］，從而以十分快的速度去處理所需要匹配的模式，最終輸出一個(gè)C 語(yǔ)言的程序，來(lái)對(duì)源程序進(jìn)行詞法分析處理。

在編譯器中，根據(jù)TTCN－3核心語(yǔ)言編寫的規(guī)則文件命名為TTCN3＿C.l。在第一部分中定義了6 個(gè)正則表達(dá)式對(duì)數(shù)字、字母、十六進(jìn)制、指數(shù)數(shù)值、浮點(diǎn)數(shù)和整形數(shù)進(jìn)行初步定義，并區(qū)分了換行符和其它空白格；第二部分中的轉(zhuǎn)換規(guī)則，包含了注釋代碼提取、TTCN－3 的139 個(gè)保留字、36 個(gè)終結(jié)符、TTCN－3 變量識(shí)別的正則表達(dá)式，以及各個(gè)規(guī)則相應(yīng)的return 語(yǔ)句；第三部分：輔助過程，定義了讀輸入串和寫輸出單詞符號(hào)串的C 程序段，包含了處理部分的函數(shù)定義。

對(duì)生成的C程序源文件使用GCC編譯，獲得的可執(zhí)行文件以參數(shù)形式處理TTCN－3源文件，能夠正確進(jìn)行詞法解析，輸出單詞符號(hào)序列。

2.2 語(yǔ)法分析器的實(shí)現(xiàn)

語(yǔ)法分析是第二個(gè)階段，本階段通過編寫操作語(yǔ)義對(duì)應(yīng)的語(yǔ)法規(guī)則，規(guī)則文件命名為 “TTCN3＿Bison.y”，使用LALR（1）分析方法生成識(shí)別語(yǔ)法中有效 “語(yǔ)句”的語(yǔ)法分析器［10］。

第一部分包含與詞法分析器交互所需要的一些外部函數(shù)聲明和頭文件、變量定義，以及終結(jié)符和非終結(jié)符聲明、語(yǔ)法起始符號(hào) （start symbol）聲明等；

第二部分則包括BNF格式書寫的文法規(guī)則，以分號(hào)結(jié)束每一條規(guī)則，對(duì)應(yīng)的執(zhí)行動(dòng)作由C 代碼編寫，用花括號(hào)括起。Bison根據(jù)被匹配的規(guī)則、動(dòng)作代碼維護(hù)每個(gè)語(yǔ)法符號(hào)關(guān)聯(lián)的語(yǔ)義值。每個(gè)規(guī)則中的語(yǔ)法符號(hào)都有一個(gè)語(yǔ)義值，目標(biāo)符號(hào)LHS （冒號(hào)左邊的語(yǔ)法符號(hào)）的值在動(dòng)作中代碼用MYMMYM 代替，右邊語(yǔ)法符號(hào)的語(yǔ)義值依次為MYM1、MYM2，直到規(guī)則的結(jié)束。當(dāng)詞法分析器返回記號(hào)時(shí)，記號(hào)值儲(chǔ)存在yylval里，其它語(yǔ)法符號(hào)的語(yǔ)義值則在語(yǔ)法分析器的規(guī)則里進(jìn)行設(shè)置。

測(cè)試集入口規(guī)則如下：

在針對(duì)TTCN－3 提供的EBNF 文法編寫語(yǔ)法規(guī)則時(shí)，僅僅使用Bison默認(rèn)的上下文無(wú)關(guān)消歧規(guī)則會(huì)導(dǎo)致錯(cuò)誤的語(yǔ)法現(xiàn)象，經(jīng)過研究，基于默認(rèn)的沖突處理機(jī)制，對(duì)于錯(cuò)誤的語(yǔ)法語(yǔ)義結(jié)果，采用改寫文法的手段進(jìn)行徹底的語(yǔ)法分析沖突消除，此部分于第四節(jié)詳述。

第三部分則包括了過程、函數(shù)聲明的C程序段等。

對(duì)該語(yǔ)法規(guī)則文件進(jìn)行處理后，將獲得的源文件與詞法分析代碼進(jìn)行處理后使用GCC 編譯，獲得的可執(zhí)行文件能夠?qū)TCN－3源文件進(jìn)行語(yǔ)法分析，對(duì)不符合給定語(yǔ)法規(guī)則的錯(cuò)誤進(jìn)行定位和輸出提示。

3 語(yǔ)法分析的沖突處理

由于TTCN－3 語(yǔ)言本身存在二義性、LALR（1）分析方法僅能向前查看1個(gè)字符，導(dǎo)致創(chuàng)建語(yǔ)法分析器時(shí)遇到大量的沖突。正確的消除語(yǔ)法分析沖突一直是使用LALR（1）分析器時(shí)最難解決的問題。常見的語(yǔ)法沖突處理方法［8，11］見表2。

其中非確定性分析法由于時(shí)間復(fù)雜度過高，一般不用于計(jì)算機(jī)語(yǔ)言的語(yǔ)法分析，消歧規(guī)則和默認(rèn)機(jī)制單獨(dú)使用均無(wú)法完全處理沖突［12］。因此，本文經(jīng)過對(duì)LALR（1）處理機(jī)制及TTCN－3核心語(yǔ)言的研究和實(shí)踐，在編譯器中綜合采用了后3種方案。

表2 常用的語(yǔ)法沖突處理方案

3.1 消歧規(guī)則及默認(rèn)機(jī)制

由于TTCN－3在核心語(yǔ)言里規(guī)定了各個(gè)語(yǔ)法現(xiàn)象的優(yōu)先級(jí)及結(jié)合性，因此對(duì)文法的處理本身已融入TTCN－3本身的消歧規(guī)則。

本次選用默認(rèn)的處理機(jī)制為：移進(jìn)／規(guī)約沖突一律以移進(jìn)操作優(yōu)先、規(guī)約／規(guī)約沖突根據(jù)規(guī)則文件中排序先后處理沖突。因此，出現(xiàn)文法沖突時(shí)會(huì)進(jìn)行提示，同時(shí)按照默認(rèn)機(jī)制進(jìn)行處理。

利用這兩種方法可能導(dǎo)致錯(cuò)誤的語(yǔ)法。因?yàn)闆_突的識(shí)別意味著存在著二義性文法，而該處理方式雖然可以使得程序正常運(yùn)行掃描，但獲得的結(jié)果可能導(dǎo)致錯(cuò)誤的語(yǔ)法規(guī)則和語(yǔ)義識(shí)別，因此必須在此機(jī)制的基礎(chǔ)上，采取改寫文法規(guī)則的機(jī)制消除二義性，從根本上解決語(yǔ)法沖突。

3.2 改寫文法：提因子

默認(rèn)機(jī)制無(wú)法正確處理的語(yǔ)法現(xiàn)象中，大部分規(guī)約／規(guī)約沖突源于產(chǎn)生式右部的相同規(guī)則。針對(duì)此問題，通過 “提因子模式”［12，13］，合并可移進(jìn)字符的可選項(xiàng)、提取相同右部并替換上層產(chǎn)生式。根據(jù)該思路對(duì)TTCN－3文法進(jìn)行改寫后，有效的解決了TTCN－3語(yǔ)法的部分規(guī)約／規(guī)約沖突。

如針對(duì)TTCN－3的IF 語(yǔ)句，如果根據(jù)BNF 的格式書寫如下規(guī)則，將提示產(chǎn)生了規(guī)約／規(guī)約沖突，該沖突會(huì)導(dǎo)致無(wú)法正確處理IF－ELSE語(yǔ)句。

ELSE StatementBlock；

經(jīng)分析，該沖突產(chǎn)生的原因在于：當(dāng)掃描到字符流中的ELSE 關(guān)鍵字時(shí)，有兩條規(guī)則可支持移進(jìn)：OptElseIf－Clauses規(guī)則中的ELSE，以及OptElseClause中的ELSE，二者有相同的可移進(jìn)字符ELSE，于是產(chǎn)生了沖突，該沖突屬于規(guī)約／規(guī)約沖突。通過合并可選項(xiàng)，把OptElseIfClauses規(guī)則和OptElseClause規(guī)則合并為一條規(guī)則的方法來(lái)消除這一沖突。

對(duì)此規(guī)則進(jìn)行合并改寫后如下：

改寫后，對(duì)該規(guī)則文件處理不再報(bào)沖突且能夠正確識(shí)別If－Else條件語(yǔ)句。針對(duì)類似原因?qū)е碌囊?guī)約／規(guī)約沖突，該方法都能較好的處理。

3.3 改寫文法：減少嵌套

采用減少嵌套的方法處理部分移進(jìn)／規(guī)約沖突。如針對(duì)TTCN－3的SEND 語(yǔ)句，如果根據(jù)BNF的格式書寫如下規(guī)則，將會(huì)提示產(chǎn)生了移進(jìn)／規(guī)約沖突［2，12］，該沖突會(huì)導(dǎo)致無(wú)法識(shí)別SEND 語(yǔ)句。

針對(duì)TTCN－3語(yǔ)句IPPort.Send （OK），詞法分析后語(yǔ)法分析器首先讀入IPPort，此時(shí)既可根據(jù)Port：ID 來(lái)規(guī)約，也可以根據(jù)ValueReference：ID‘.’ID 來(lái)移進(jìn)下一個(gè)字符 ‘.’，于是就出現(xiàn)了移進(jìn)／規(guī)約沖突。根據(jù)默認(rèn)的處理機(jī)制選擇移進(jìn)的話，會(huì)按照ValueReference：ID ‘.’ID 來(lái)移進(jìn) ‘.’并繼續(xù)分析語(yǔ)句IPPort.Send （ok），這種錯(cuò)誤的選擇機(jī)制導(dǎo)致無(wú)法識(shí)別SEND 語(yǔ)句。

針對(duì)這一沖突，可采用減少嵌套的方法，使同優(yōu)先級(jí)的字符處于同一移進(jìn)或規(guī)約的層次。此處可在規(guī)則中去掉Port 規(guī) 則 的 嵌 套，使Sendstatement 中 的 字 符ID 和ValueReference中的字符ID 處于同一層次中，回避了對(duì)兩條產(chǎn)生式進(jìn)行默認(rèn)機(jī)制選擇時(shí)導(dǎo)致的語(yǔ)法錯(cuò)誤。

改寫該規(guī)則后如下：

如此改寫后，分析處理不再報(bào)沖突。同理，該方案也應(yīng)用于TTCN－3其它通信操作類的語(yǔ)句，均能正確處理沖突，獲得良好的效果。

3.4 沖突處理總結(jié)

相對(duì)于常見的語(yǔ)法沖突處理方案，本文針對(duì)TTCN－3語(yǔ)言的規(guī)則，采用了消歧規(guī)則、默認(rèn)機(jī)制、改寫文法綜合應(yīng)用的方案，對(duì)于產(chǎn)生沖突的大部分簡(jiǎn)單規(guī)則，采用消歧和默認(rèn)處理的方式能夠得到較好的效果，而針對(duì)具體的語(yǔ)法沖突現(xiàn)象，則采用提因子、減少嵌套的方案分別處理。實(shí)驗(yàn)結(jié)果表明，針對(duì)TTCN－3具體語(yǔ)法，按照分析器的工作機(jī)制，遵循相應(yīng)規(guī)律的上下文無(wú)關(guān)文法改寫可徹底解決沖突問題，保證分析程序的正確性，并對(duì)輸入的單詞符號(hào)串生成初步的分析樹。

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

本文介紹一種基于TTCN－3／C＋＋的測(cè)試平臺(tái)中，ATS向ETS編譯執(zhí)行的編譯器構(gòu)造方法，并對(duì)詞法分析和語(yǔ)法分析的前端模塊進(jìn)行實(shí)現(xiàn)。通過編寫詞法、語(yǔ)法分析規(guī)則，識(shí)別單詞符號(hào)并解決語(yǔ)法沖突，能夠?qū)TCN－3源程序進(jìn)行分析，正確輸出token序列并對(duì)token序列按照給定語(yǔ)法規(guī)則進(jìn)行語(yǔ)法分析，生成初步的分析樹。

借助本論文實(shí)現(xiàn)的兩部分模塊，用戶能夠?qū)TCN－3編寫的代碼進(jìn)行分析，對(duì)語(yǔ)法規(guī)則進(jìn)行檢查，并提示語(yǔ)法錯(cuò)誤。由于以C＋＋作為目標(biāo)代碼，采用LALR（1）分析法并通過文法改寫方式有效消除了語(yǔ)法沖突問題，本文相比國(guó)內(nèi)外現(xiàn)有方案具有以下優(yōu)點(diǎn)：①可批量處理，相比翻譯方案工作量少，容易維護(hù)；②以C＋＋作為目標(biāo)代碼，執(zhí)行效率高，無(wú)須虛擬機(jī)支持；③綜合采用多種方案處理沖突，通過改寫文法徹底解決語(yǔ)法沖突問題，有利于后期增加語(yǔ)法的擴(kuò)展支持［14］。

［1］ETSI ES 201 873－1v4.4.1（2012－04）methods for testing and specification（MTS）；the testing and test control notation version3；part 1：TTCN－3core language［S］.2012.

［2］ETSI ES 201 873－5v4.4.1（2012－04）methods for testing and specification（MTS）；the testing and test control notation version 3；part 5：TTCN－3tuntime interface（TRI）［S］.2012.

［3］ETSI ES 201 873－4v4.4.1（2012－04）methods for testing and specification（MTS）；the testing and test control notation version 3；Part 4：TTCN－3operational semantics［S］.2012.

［4］JIANG Fan，WANG Jianxue，ZHANG Lei，et al.Translation scheme from type system of TTCN－3to C＋＋ ［J］.Computer Engineering and Applications，2009，45 （30）：65－68（in Chinese）.［蔣凡，王建學(xué)，章磊，等.TTCN－3語(yǔ)言類型系統(tǒng)到C＋＋語(yǔ)言的翻譯方案 ［J］.計(jì)算機(jī)工程與應(yīng)用，2009，45 （30）：65－68.］

［5］Testingtech.com.TTWorkbench－the reliable test automation platform［EB／OL］.http：／／www.testingtech.com／products／ttworkbench.php，2013.

［6］YIN Xia， WANG Zhiliang，JING Chuanming，et al.A TTCN－3－based protocol testing system and its extension ［J］.Science in China Series F：Information Science，2008，51（11）：1703－1722.

［7］Alfred V Aho，Monica S Lam，Ravi Sethi，et al.Compilers：Principles，techniques，and tools ［M］.Beijing：China Machine Press，2011.

［8］John Levine.Flex＆Bison ［M］.LU Jun，transl.Nanjing：Southeast University Press，2011（in Chinese）. ［John Levine.Flex與Bison （中文版）［M］.陸軍，譯.南京：東南大學(xué)出版社，2011.］

［9］XU Ling，WEI Wei.The object oriented design of TTCN－3 compiler based on ANTLR ［J］.Control Engineering of China，2012，19 （S1）：122－125 （in Chinese）. ［徐玲，韋巍.基于ANTLR 的TTCN－3編譯器的面向?qū)ο笤O(shè)計(jì) ［J］.控制工程，2012，19 （S1）：122－125.］

［10］CHEN Wenyu，WANG Xiaobin，CHENG Xiaoou，et al.Issues regardingεin formal language and automata theory ［J］.Computer Science，2010，37 （1）：243－264 （in Chinese）.［陳文宇，王曉斌，程小鷗，等.形式語(yǔ)言與自動(dòng)機(jī)中關(guān)于ε的一些問題 ［J］.計(jì)算機(jī)科學(xué)，2010，37 （1）：243－264.］

［11］ZHENG Lixiao，XU Zhiwu，CHEN Haiming.Algorithm for generating short sentences from grammars based on branch coverage criterion ［J］.Journal of Software，2011，22 （11）：2564－2576 （in Chinese）.［鄭黎曉，徐智武，陳海明.基于文法分支覆蓋的短句子生成算法 ［J］.軟件學(xué)報(bào)，2011，22（11）：2564－2576.］

［12］ZENG Weiming，XUE Yunzhi，ZHAO Chen，et al.Design and implementation of an automatic test case generation method for compiler optimization［J］.Journal of Chinese Computer Systems，2009，30 （1）：13－18（in Chinese）.［曾偉明，薛云志，趙琛，等.一種編譯優(yōu)化測(cè)試用例自動(dòng)生成方法的設(shè)計(jì)與實(shí)現(xiàn) ［J］.小型微型計(jì)算機(jī)系統(tǒng)，2009，30 （1）：13－18.］

［13］Gnu.org.Bison－GNU Parser Generator［EB／OL］.http：／／www.gnu.org／software／bison／，2013.

［14］ZHU Hengwei，ZHANG Mingguo，QIAO Haiquan.Grammar and semantic extensions of Front compiler front－end generator for elegant ［J］.Computer Engineering and Applications，2010，46 （21）：66－68 （in Chinese）. ［朱恒偉，張明國(guó)，喬海泉.對(duì)編譯器前端生成器Front的語(yǔ)法和語(yǔ)義擴(kuò)展［J］.計(jì)算機(jī)工程與應(yīng)用，2010，46 （21）：66－68.］