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.］