TTCN－3編譯器前端模塊的設計與實現

王大衛，王俊峰

（四川大學 計算機學院，四川 成都610065）

0 引 言

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

1 以C＋＋為目標代碼的編譯測試

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

協議測試領域的發展現狀使得翻譯方案的工作量及維護難度變得難以大范圍應用，將TTCN－3語言編譯為C＋＋并與C＋＋測試平臺聯合編譯的方案目前在業內尚且屬于空白，C＋＋作為C語言的延伸，具備面向對象特性，針對協議測試的系統化自動化的發展趨勢，其優秀的執行效率相對于Java，在通信設備測試領域具有十分明顯的優勢。因此，本文通過詞法分析、語法分析、語義分析、代碼生成這4個步驟，將TTCN－3測試集編譯得到C＋＋代碼，再利用與測試平臺聯合編譯獲得可執行系統［2］，并應用于IPv6協議的一致性測試，其設計遵循TTCN－3標準，具有較好的應用前景。其系統架構如圖1所示。

表1 現有TTCN－3測試系統執行方案特點

圖1 基于TTCN－3的IPv6一致性測試系統架構

2 TTCN－3／C＋＋編譯器設計

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

通常詞法／語法分析可以使用一些自動構造解析工具來生成。目前常見的工具有Parser Generator，Flex／Bison，Antlr等。其中Parser Generator和Flex＆Bison 都是基于LEX 和YACC的工具，生成的是LALR（1）分析器。Antlr前身是PCCTS，生成LL（K）分析器［8］。

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

本次設計的編譯器目標語言為C＋＋，在測試平臺上通過extern “C”的方式聲明并調用函數，實現聯合編譯。編譯系統與測試平臺模塊設計如圖2所示。

圖2 編譯系統與測試平臺模塊設計

2.1 詞法分析器的實現

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

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

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

2.2 語法分析器的實現

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

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

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

測試集入口規則如下：

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

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

對該語法規則文件進行處理后，將獲得的源文件與詞法分析代碼進行處理后使用GCC 編譯，獲得的可執行文件能夠對TTCN－3源文件進行語法分析，對不符合給定語法規則的錯誤進行定位和輸出提示。

3 語法分析的沖突處理

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

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

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

3.1 消歧規則及默認機制

由于TTCN－3在核心語言里規定了各個語法現象的優先級及結合性，因此對文法的處理本身已融入TTCN－3本身的消歧規則。

本次選用默認的處理機制為：移進／規約沖突一律以移進操作優先、規約／規約沖突根據規則文件中排序先后處理沖突。因此，出現文法沖突時會進行提示，同時按照默認機制進行處理。

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

3.2 改寫文法：提因子

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

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

ELSE StatementBlock；

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

對此規則進行合并改寫后如下：

改寫后，對該規則文件處理不再報沖突且能夠正確識別If－Else條件語句。針對類似原因導致的規約／規約沖突，該方法都能較好的處理。

3.3 改寫文法：減少嵌套

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

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

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

改寫該規則后如下：

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

3.4 沖突處理總結

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

4 結束語

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

借助本論文實現的兩部分模塊，用戶能夠對TTCN－3編寫的代碼進行分析，對語法規則進行檢查，并提示語法錯誤。由于以C＋＋作為目標代碼，采用LALR（1）分析法并通過文法改寫方式有效消除了語法沖突問題，本文相比國內外現有方案具有以下優點：①可批量處理，相比翻譯方案工作量少，容易維護；②以C＋＋作為目標代碼，執行效率高，無須虛擬機支持；③綜合采用多種方案處理沖突，通過改寫文法徹底解決語法沖突問題，有利于后期增加語法的擴展支持［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）.［蔣凡，王建學，章磊，等.TTCN－3語言類型系統到C＋＋語言的翻譯方案 ［J］.計算機工程與應用，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］.陸軍，譯.南京：東南大學出版社，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編譯器的面向對象設計 ［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）.［陳文宇，王曉斌，程小鷗，等.形式語言與自動機中關于ε的一些問題 ［J］.計算機科學，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］.軟件學報，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）.［曾偉明，薛云志，趙琛，等.一種編譯優化測試用例自動生成方法的設計與實現 ［J］.小型微型計算機系統，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］.計算機工程與應用，2010，46 （21）：66－68.］