TTCN－3編譯器前端模塊的設(shè)計與實現(xiàn)

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

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

0 引 言

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

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

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

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

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

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

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

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

通常詞法／語法分析可以使用一些自動構(gòu)造解析工具來生成。目前常見的工具有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中對詞法語法表達(dá)的使用EBNF，更接近LEX／YACC 所能接受的LALR（1）文法；且LALR（1）分析器執(zhí)行效率要高于LL（k）分析器［3，9］，故本文采用基于LALR（1）文法分析工具Flex／Bison作為詞法／語法分析器的輔助工具。

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

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

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

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

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

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

2.2 語法分析器的實現(xiàn)

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

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

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

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

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

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

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

3 語法分析的沖突處理

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

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

表2 常用的語法沖突處理方案

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

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

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

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

3.2 改寫文法：提因子

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

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

ELSE StatementBlock；

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

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

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

3.3 改寫文法：減少嵌套

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

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

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

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

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

3.4 沖突處理總結(jié)

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

4 結(jié)束語

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

借助本論文實現(xiàn)的兩部分模塊，用戶能夠?qū)TCN－3編寫的代碼進(jìn)行分析，對語法規(guī)則進(jìn)行檢查，并提示語法錯誤。由于以C＋＋作為目標(biāo)代碼，采用LALR（1）分析法并通過文法改寫方式有效消除了語法沖突問題，本文相比國內(nèi)外現(xiàn)有方案具有以下優(yōu)點：①可批量處理，相比翻譯方案工作量少，容易維護(hù)；②以C＋＋作為目標(biāo)代碼，執(zhí)行效率高，無須虛擬機支持；③綜合采用多種方案處理沖突，通過改寫文法徹底解決語法沖突問題，有利于后期增加語法的擴展支持［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語言類型系統(tǒng)到C＋＋語言的翻譯方案 ［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］.控制工程，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）.［陳文宇，王曉斌，程小鷗，等.形式語言與自動機中關(guān)于ε的一些問題 ［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é)報，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)化測試用例自動生成方法的設(shè)計與實現(xiàn) ［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）. ［朱恒偉，張明國，喬海泉.對編譯器前端生成器Front的語法和語義擴展［J］.計算機工程與應(yīng)用，2010，46 （21）：66－68.］