（计算机应用技术专业论文）ttcn3c编译器研究与设计.pdf

西南交通大学硕士研究生学位论文 第1 页 摘要 随着i p v 6 协议族及相关产品的出现，路由协议测试又成为热点。传统的 路由器测试法只能对路由器的单端口或一对端口进行测试，不能全面反映真 实网络环境下路由器的功能与性能指标。四川i 省网络通信重点实验室设计了 路由器多端口并发测试系统，该测试系统可以模拟出路由器在实际网络环境 f 的f ：作情况，从而可以使测试更准确、更完备。本论文反映的工作是陔项 研究的测试支撑工具的重要组成部分。 本论文研究的主题是如何将用t t c n 一3 描述的测试控制数据转变为能够 被测试系统执行的可执行测试控制数据的技术。出于多方面考虑，笔者没有 采用较为普遍的解释方式，而采用了编译的方式。为了便于与测试系统中其 他部件融为一体，首先t t c n 一3 语言转换成c 这种高级语言，相关c 代码再与 其他部分进行联合编译，最终生成机器代码。 笔者开发的编译器的处理过程分为4 个阶段：词法分析、语法分析、语 义分析及代码生成。由于不生成最终的机器码，因此，t t c n 一3 c 编译器生成 的代码可以视为中间代码( 如许多程序设计编译器的生成汇编语言代码) ，因 此也不需要考虑最终代码优化问题。本编译器采用两遍扫描。第一遍扫描读 入t t c n 一3 源程序，并对其进行词法分析、语法分析和语义分析。第二遍通过 遍历第一遍输出的语法树来完成代码生成。 由于时间关系，本论文中反映的工作仅涵盖词法分析、语法分析、语义 分析、构造语法树、符号表的建立以及相关的错误处理。代码生成部分的具 体工作由t t c n 一3 编译器小组的另一位同学完成。为了减少编译器的开发周 期，并考虑到其它的一些因素，词法分析部分是用自动构造词法分析的工具 l e x 的f l e x 版本生成的，语法分析部分是用语法分析器的生成器y a c c 的 b i s i o n 版本生成的。语义分析部分作为语法分析的子程序，嵌入了y a c c 的 语法规则部分。 其。h 语法分析是笔者研究的核心部分。语法分析的难点是如何解决 y a c c 语法规则部分的冲突问题。笔者针对这一问题总结了三种通过改变 r t c n 一3 语法规则部分的书写格式束减少冲突的办法。 西南交通大学硕士研究生学位论文第1 j 页 在语法分析和语义分析阶段设计了语法树和符号表这两个编译器中重要 的数据结构。并且笔者抽象出了t t c n 一3 中和语义相关的内容。 最后简要介绍了错误处理，以及代码生成的设计思路。 关键词：编译器：t t c n 一3 ；语法分析；语义分板 西南交通大学硕士研究生学位论文 第l | i 页 a b s t r a c t w 】t ht h ea d v e n to ti p v 6 t e s t i n go fi p v 6r o u t e r sh a sr e d r a w na t t e n t i o n so ft h e n e t w o r kc o m m u n i t y t r a d i t i o n a lt e s tm e t h o d sa r eo n l yc a p a b l eo fo b s e r v i n ga n d t e s t i n gas i n g l ep o r to rap a i ro fp o r t ss i m u l t a n e o u s l y t h e ya r en o ta d e q u a t ef o r t e s t i n go fm o d e mt o u t e r s i ni t sr e a l w o r k i n ge n v i r o n m e n t ，e s p e c i a l l y i n p e r f o r m a n c et e s t i n g t h i si st h ev e r yr e a s o nf o rs c - n e t c o ml a b ( s i c h u a n n e t w o r kc o m m u n i c a t i o nk e yl a b o r a t o r y ) t os e t u pt h ep r o j e c to fc m p t ( c o n c u r r e n tm u k i p o r tt e s t i n g ) f o ri pr o u t e r 8 ，w h i c hc a r le f f e c t i v e l ys i m u l a t ea l l p o s s i b l ew o r k i n gc o n d i t i o n sf o rm u l t i p o r tr o u t e r s t h ew o r kp r e s e n t e di nt h i s d i s s e r t a t i o ni sp a r to f t e s ts u p p o r t - t o o ld e v e l o p m e n t t h et e s tc o n t r o ld a t ad e s c r i b e di nt h ei s os t a n d a r d i z e d s p e c i f i c a t i o n l a n g u a g e t t c n 3h a st ob ec o n v e r t e di n t oe x e c u t a b l ec o d ef o rt e s ts y s t e m st h e a u t h o rt a k e sc o m p i l i n ga p p r o a c hi n s t e a di n t e r p r e t a t i o na sm o s tt e s ts y s t e m sd oi n t t c n - 3c o n v e r s i o nt h ea u t h o r sc o m i l e ri n v o l v e s c o n v e r t i n g t t c n 一3 s p e c i f i c a t i o n si n t ocl a n g u a g ei no r d e rt oe n a b l en e c e s s a r yc o m b i n e dc o m p i l i n g w i t ho t h e rp a r t so ft h et e s ts y s t e m i no t h e rw o r d ，i ti sat t c n - 3 cc o m p i l e r t h ec o m p i l i n gp r o c e s sc a nb ed i v i d e di n t of o u rp h a s e s ：l e x i c a la n a l y s i s ， s y n t a xa n a l y s i s s e m a n t i ca n a l y s i s ，a n dc o d eg e n e r a t i o n t h ecc o d e sc a nb e t h o u g h t - 。o fa s t h ei n t e r m e d i a t ec o d e sa si n a s s e m b l yc o d e si np r o g r a m m i n g l a n g u a g ec o m p i l i n gt h e r e f o r e ，n om a c h i n ec o d eo p t i m i z i n gp r o c e s sh a sb e e n i n v o l v e d t h ec o m p i l i n gp r o c e s si s c o m p o s e do ft w op a s s e si n t h ea u t h o r c o m p i l e r i nt h ef i r s tp a s s ，l e x i c a la n a l y z i n g ，s y n t a xa n a l y z i n ga n ds e m a n t i c a n a l y z i n ga r ep r o c e s s e d ，w h i l es y n t a xt r e e se x p o r t e df r o mt h ef i r s tp a s sa r eu s e d t og e n e r a t i n gcc o d e si nt h ec o m p i l e r t h i sd i s s e r t a t i o nh a sb e e nd e d i c a t e dt ot e c h n i q u e sr e l e v a n tt ol e x i c a la n a l y s i s ， s y n t a xa n a l y s i s ，s e m a n t i ca n a l y s i s ，s y n t a x t r e e g e n e r a t i o n ，s y m b o l t a b l e c o n s t r u c t i o n ，a n de r r o rh a n d l i n g t h ew o r ko f c o d eg e n e r a t i o ni sd o n eb ya n o t h e r s t u d e n ti nt t c n 一3c o m p i l e rw o r k i n gg r o u p f l e x ( an e wv e r s i o no fp o p u l a r l e x ) i su s e dt oa u t o m a t ea n ds p e e du pl e x i c a la n a l y s i sa n db i s o n ( av e r s i o no f y a c c ) i su s e di ns y n t a xa n a l y s i sb yt h es a m et o k e n o n eo fd i f f i c n l t i e s e n c o u n t e r e di ns y n t a xa n a l y s i si sh o wt os o l v er u l ec o n f l i c t si ny a c c t h ea u t h o r 西南交通大学硕士研究生学位论文第lv 页 h a sa v o i d e ds u c hc o n f l i c tb yr e f o r m a t t i n gt t c n - 3r u l e si ny a c ca n do t h e r t a c t i c s f i n a l l y e r r o rh a n d l i n gi s s u e sa r ed i s c u s s e d ，a n db a s i ci d e ao f c o d eg e n e r a t i o n i sb r i e f l yi n t r o d u c e da l t h o t i 曲n op r o g r a m m i n gw o r kh a sb e e n d o n ei nt h i s r e s p e c t k e yw o r d s ：c o m p i l e r ；t t c n 一3 ；s y n t a xa n a l y s i s ；s e m a n t i ca n a l y s i s 西南交通大学硕士研究生学位论文第1 页 第一章绪论 1 1 研究i p v 6 协议测试技术的必要性 由于i p v 6 在地址空间、报头处理的简化和安全性等方面的优点，受到全 球网络界的重视，因此在全球范围内诈形成以i p v 6 为基础的“下一代 【n t e r n e t ”的建设高潮”1 。在这建设高潮的推动下，涌现出大量的基于ip v 6 的i n t e r n e t 协议和相应的网络产品。相应地，对新一代网络产品的测试以及 在i p v 4 ”向i p v 6 的过渡期两代产品间的互通，直接关系到下一代i n t e r n e t 网络产品的互通互联和两代网络的平滑过渡。因此，研究以i p v 6 为基础的网 络产品的测试技术，特别是基于i p v 6 的路由器产品的测试技术就具有十分重 要的意义。 e t f 的r f c ( r e q u e s tf o rc o m m e n t ) 对协议的描述主要以自然语言描述加 上部分状态变迁图表的方式进行的。由于自然语言可能产生二义性，对于协 议的不同理解有可能导致错误的实现。目前我国正进行中国的f 代 n t e r n e t ( c n g i c h i n an e x tg e n e r a t i o ni n t e r n e t ) 的建设，在引进图外产品时， 或在臼t ”发新。代 n t e r n e t 产品时，都会鲫l 蠡确定相关产品是否符台相关 协议文本，以及不同( 国内外) 厂家的产品是否可以实现互联互通的问题。 这就是所谓的“一致性测试”( c o n f o r m a n c et e s t i n g ) 和“互通测试” ( i n t e r o p e r a b i l i t yt e s t i n g ) 。解决这些问题的办法就是要对各种i p v 6 网络协议 实现进行测试，即进行i p v 6 融议测试。所以目前研究 p v 6 协议测试技术。” 具有定的必要性。 在从i p v 4 网络向i p v 6 网络的过渡期问，由于支持两种版本i p 的协议设 备同时并存，需要在两代i n t e r n e t 网络或设备之间实现互联。路由器通信子 嗍内的中继设备，必须支持i p v 4 或i p v 6 。在实现两代网络互联的路由器或 l x 日关发备，还必须分别支持l f ) v 4 对i p v 6 的封装( e n e a p s u l a t i o n ) 或叻议转 换( p r o t o c o lc o n v e r s i o n ) 方式。因此，路由器测试技术的研究和测试系统的 丌发是研究i p v 6 协议的测试技术的重点和难点。 西南交通大学硕士研究生学位论文第2 页 1 2 本项目的研究背景 1 2 1 传统的路由器测试方法及其局限性 目前，根据测试目的不同，对路由器的测试可划分为“一致性测试” ( c o n f o r m a n c et e s t ) 、“互操作性测试”( i n t e r o p e r a b i l i t yt e s t ) 和“性能 测试”( p e r f o r m a n c et e s t ) 三大类。一致性测试通过发送测试数据并观察测 试对象的应答，来判断协议实现是否具有相关协议规定的行为。互操作测试 解决实现同一协议集的不同设备能否实现互通；实践证明，即使两个设各都 通过了一致性测试，也不能完全保证二者能够正确互联，因此，互通测试还 具有两个系统不能正确互联时的仲裁功能。性能测试针对设备的定性( 安全 性、可管理性等) 或定量指标( 吞吐率、传输时延、数据丢失率、平均无故 障时间等) 进行测试”1 。迄今为止，国内外对路由器的测试方法仍然以i s o 9 6 4 6 ”中定义的“回绕测试法”( l o o p b a c kt e s tm e t h o d ) 和“穿越测试法” ( t r a n s v e r s et e s tm e t h o d ) 为主( 见图卜1 、卜2 ) “1 。 。 被测路由器被测路由器 - 图卜i 回绕测试法示意图图l - 2 穿越测试法示意图 图1 一l 中为回绕测试法的特例内部回绕测试的示意图。采用回绕测 试法的测试器所发送的测试数据报文的目的i p 地址就是测试器自身的i p 地 址，路由器收到测试数据后，根据内部的路径表的设置再将该数据回送到测 试器。回绕测试法十分简单，但由于只能观测一个端口的运行情况，测试能 力受到限制。如图l 一2 ，穿越测试法同时观测路由器的两个端口，测试数据 进入一个端口后，根据事先设定的路径表可以将该数据转发到另一个受观察 西南交通大学硕士研究生学位论文第3 页 的端口，所涉及的路由器协议实体，与路由器正常工作状况下所涉及的相同， 因此可完全模拟一对端口的工作状态。由于能同时观测一对端口，其测试能 力较回绕测试法的能力强“1 。 传统的路由器测试法最多能对一对端口进行测试，而路由器是典型的多 端口设备。由于端口之间的协议行为相互影响，各端口间的输入数据量和到 达规律都可能影响测试的结果。因此，单端口或一对端口的测试还不能全面 反映路由器的功能( 端口间活动对并行多端口间的数据流间的相互影响) ，特 别难以对路由器的综合性能指标进行全面的测试。正因为如此，国内外有人 对路由器并行测试技术进行研究。1 。但是相关的工作中强调了通路测试间的 并行性，但对测试过程并发性、同步与协调并未给予足够的重视。1 。 1 2 2 路由器并发多端口测试系统 针对以上提出的问题，笔者所在的四川i 省网络通信重点实验室研究了 i p v 6 路由器的多端口并发测试技术“，并提出了路由器并发多端口测试系 统。该测试系统可以模拟出路由器在实际网络环境下的工作情况，从而可以 使测试更准确、更完备”“。 并发多端口测试系统( c o n c u r r e n tm u l t i - p o r tt e s ts y s t e m ，简称为 c m p t s ) 是面向测试中心用的可进行一致性与性能测试的系统。系统总体结构 图卜3c m p t s 系统结构与测试例支撑工具 西南交通大学硕士研究生学位论文 第4 页 系统的总体框架由两部分组成，一部分是并发多端口测试系统c m p q s ( 图 1 3 左边部分) ，另一部分是测试支撑工具( 图l 一3 右边部分) 。c m p t s 又由 两部分组成：一是起协调、管理、控制功能的测试管理器c m p t m ，另一部分 是执行具体测试指令的多个双端口测试器t p t 。c m p t s 主要的功能是执行由测 试描述语吉定义并预先编译好的可执行测试例( 集) ，通过一系列动作完成对 被测系统的测试并得出结果。测试支撑：具包括：t e s ta n dt e s tc o n t f 0 1 n o t a t i o nv e r s i o n3 一t t c n 一3 ，抽象测试集，f t c n 一3 编译器，并发多端口测 试描述语言c m p t d i 。( c o r c u f f ef 1 1m u l ti p o r tt e s td e f i n j t i o nl a n g u a g e c m p t d l ) 的编译器j 。 c m p t s 以一种可控的方式完成对被测系统的并发测试。c m p t m 是c m p t s 的核心部件。测试系统中被测路由器r u t 的多个端口都分别与一个t p t 相连， 而每个t p t 都接受与之相连的c m p t m 的管理、控制和协调，也就是说，c m p t m 对多个t p t 测试过程进行协稠和同步，这样通过t p t ，r u t 的多个端口就可以 在c m p t m 的统一管理、调度下并发地收发数据，即可以完成并发的多端口的 测试。有关c m p t m 和t p t 的详细内容情参阅文献 2 ，1 1 。 该测试系统能模拟出真实的网络环境，适应了路由器的测试需求，因此 很有应用前景。 1 3 本论文反映的主要研究工作 本实验室依据并发多端口测试系统，把实现该测试系统的工作任务划分 为四大部分：c m t d l 定义与c m t d lc o m p i l e r 丌发；测试系统开发；测试支撑 环境歼发：测试集、测试组、测试例定义与描述。相应的，本实验室划分为 纠个研究小组。笔者所在的组是测试支撑环境开发中的t t c n 一3 编译器丌发小 组。本小组的工作任务是设计出测试系统中所需的t t c n 一3 编译器。 树表相结合的标记语言t t c n ( t r e e sa n dt a b 】e sc o m b i n e dn o t a t j o n ) 是i s o 制订的m 议控制数据描述语出，经过改进目前已经升级为第三版 ( r t c n 一3 ) 。本沦文的反映的工作是t t c n 一3 c 编泽器，笔者的具体分：【为 t t c n 一3 编译器的前级处理程序的研究与开发，即词法分析、语法分析、语义 分析，并构造语法树和符号表，为生成c 代码做准备。本论文反映的研究工 作主要有以下几个方面： 西南交通大学硕士研究生学位论文 第5 页 1 1 2 ) 3 ) 4 1 研究t t c n 3 语言的语法规则和语义规则。 探讨编译器的设计思路和方法，制定t t c n 3 编译器设计与开发路线。 探讨词法分析器的工作原理与设计技术：研究利用y a c c 构造语法分析器 的方法和在y a c c 中解决冲突的方法；研究如何构造语法树及符号表、 如何在y a c c 中利用语法树节点信息和y a c c 的语义值以及符号表来完 成语义分析：研究编译器对错误的处理。 用c 语言编程实现上述功能并对课题组内其他同学用t t c n 一3 编写的测 试控制数据进行语法语义检查。 1 4 本论文反映的工作的特点 1 ) 对t t c n 3 定义的测试控制数据的处理采用编译方式以实现处理高速化 鉴于国内外对t t c n t t c n 一3 描述的测试控制数据的处理，大多采用解 释方式，即对t t c n 测试例一边进行解释，边执行。这种方式的优点是修 改t t c n 拙述不影响测试例的执行，区l 为解释方式每次都必须对测试例从头 进行解释。但是，解释方式不适应对高速网络测试的需要。根据课题组对高 速i p v 6 路由器多种测试功能的需要，特别是性能测试的需要，笔者所在测试 支撑工具研究与开发小组决定采用编译方式，尽管占用的磁盘空间较大，但 用以存储空间为代价换取测试过程的高效性更适合本项目的需要。 2 ) 采用两步编译方式 根据课题组测试系统功能划分，部分测试部件实质上是可执行测试例的 部分( 例如编解码器- - e n c o d e r d e c o d e r ) ，需要最后融入测试例之中。为此， 本编译程序采用首先将t t c n 3 编译为c 代码，然后再与相关部件的c 代码 道进行联合c 编译。 3 ) 在国内首次探索关于t t c n 3 语言的编译技术 国外参考文献 1 2 、1 3 介绍的工作反映出相关单位完成了t t c n 3 c 和 t t c n 3 j a v a 的编译程序：国内除中科院成都计算机应用研究所在2 0 世纪8 0 年代术期，进行过第版t t c n 的编译程序的丌发工作外，至今尚无人丌发 过t t c n 3 编译程序。由于t t c n 3 增加了许多新的功能，因此，t t c n 一3 1 c 编译器的设计与开发有探讨价值。 西南交通大学硕士研究生学位论文第6 页 1 5 论文结构与安排 本论文后续章节安排如下： 第二章介绍t t c n 即其支撑工具，并探讨了t t c n 3 c 编译器的基本设计方 法；第三章详细讨论了笔者的词法分析、语法分析部件的设计，以及如何构 造语法树的过程；第四章进一步介绍笔者开发的编译器中的语义分析、符号 表的生成与管理：第五章：简要介绍了t t c n 一3 描述的测试例出错时的处理并 初步探讨了编译器中生成c 代码基本思路，为后续的开发工作做准备。最后， 在第六章。p 埘本项工作进行了总结，并对未来需要进一步完成的后续工作进 行了分析和展望。 西南交通大学硕士研究生学位论文第7 页 第二章t t c n 及支撑工具 2 1t t o n 及分布式测试系统对t t c n - 3 的新要求 2 1 it t c n 概述 t t c n ( t h et r e ea n dt a b u l a rc o m b i n e dn o t a t i o n ，树表结合的标记语 言) 。”是一种通过树表结构来描述测试集和测试例的半形式化语言，是 s 0 9 6 4 6 定义的测试控制数据描述语当。经过多年的发展，目前已经改进为 笫j i 个版本，划t t c n 3 ( t e s t jn ga n dt e s tc o n t r o ln o t a t l o n ，测试及测 试控制标记语者) ”。t t c n 一3 具有以下特点| ：l 、与a s n1 兼容。2 、有多 种描述方式，包括文本方式，表格方式，图形格式。3 、具有描述动态并发测 试配置的能力( 请参见21 2 节) 。4 、有两种通信方式：基于进程的和基于消 息的通信方式。5 、数据和签名( s i g n a t u r e ) 模板具有功能强大的匹配机制。 6 、具有描述编码信息和其它属性的能力。7 、具有测试集参数化机制和测试 例选择机制。8 、能够指定并控制测试结果。9 、详细定义了语法，静态语义 和操作语义 第一版t t c n 是为描述o s i 协议的一致性测试而定义的描述语言“，随着 其应用范明的拓宽，用t t c n 一3 描述的测试协 义的范围越来越广，描述的测试 种类也来越多。其应用的领域已经超过2 0 种。：移动通讯，无限局域网，无 绳电话，宽带技术，基于c o r b a 的客户服务、f 台，以及网络协议等。笔者所 在测试技术研究组的协议测试集与测试例的描述就采用t t c n 一3 。 2 1 2 由多台计算机组成的分布式测试系统对t t c n 3 的新要求 t t c n - 3 最显著的特点是突出了描述的并行性，允许有多于一个的测试部 件同时运行。但是，t t c n 一3 还不能满足由多台计算机组成的分布式测试系统 的需求，i 三要体现在以下几个方面： 1 )对于多端口分布式测试系统，尽管可以把各子测试器通过一个测试组件 来描述，但是这些组件之间的同步描述却异常困难。t t c n 一3 虽然定义了 协调点，来为并行测试部件间协调使用，但是具体如何协调、如何实现 西南交通大学硕士研究生学位论文第8 页 同步和控制，t t c n 3 并没有定义。 2 )d 阿：t 1 c n 一3 集中在功能测试上，所以对实时性和性能测试没有严格丽详 细的定义。缺乏对实时性、性能、协同、同步测试的描述。而并发多端 口测试要求既能完成功能性测试，也要能完成性能测试。 3 ) c m p t s1 1 | i 己置非常灵活，既可以把一个子测试器作为独立的采用穿越法的 测试小系统，又可以是在c o o r d i n a t o r 统一控制下的大测试系统的一部 分；同时，一个子测试器的两个端口既可作为陔测试器的一对测试端口， 也可动态配置为c m p t s 中独立的测试端口( 尤其是性能测试时) ，这种灵 活性无法用目前的t t c n 3 准确描述。 1 )同 个踟议划分是在不同的平叫束看待的，而在不同的平面，其所处的 层次也是不一样的，这样一来，要求测试器能用不同端旧测试它处于的 不同平面和层次的情况，当然，这需要在上层管理器统一协调下进行。 t t c n 一3 本身不具有这种层次结构。 为了满足多台计算机组成的分布式测试系统对t t c n 一3 的这些新要求，完 成并发多端口测试，本实验室对t t c n 一3 进行了部分扩充，在现有t t c n 一3 的 馨础一卜进步定义了殳宏观的并发语言c m p l 、队。有关c m p t d l 的详细内容请 参阅 1 1 。 2 2t t o n 的支撑工具简介 川1 1 c n 拙述的测试例研；能幽搂存测试系统中运行，必须经过t t c n 的支撑 工具j 可以执行测试例。t t c n 支撑工具就是将用t t c n 描述的测试控制数据 ( 即i s 0 9 6 4 6 术语中的抽象测试集组子组测试例) 转换为计算机可理解的 可执行测试控制数据的所有软件的总称。 早在8 0 年代，在t t c n 标准刚制定后不久，国内外就有一些研究机构开 始了对f t c n 支撑工具的研究。当时，由于第、二代的测试系统大都使用各 自定义的专用测试控制数据描述语言，并配有将各自的将专用测试语言转换 为可执行测试控制数据的支撑工具。当i s o 制订3 钡f j 试控制数据描述语言国 际标准t t c n 时，为了使各自定义的测试控制数据有可比性，或借用别人用 7 r t c n 捕述的测试控制数掘，人们丌始丌发+ i t c n 描述的测试集与各自的测试 捕述语言问的转换t 具。例如：英国国家物理实验室丌发了t t c n 向其测试描 西南交通大学硕士研究生学位论文 第9 页 述语言t d l 的转换程序，而加拿大i d i c o m 公司则开发了t t c n 到其专用测试语 言i t l 的转换程序。转换的结果再和用t d l 或i t l 自身的解释编译程序进 行处理。 对于没有专用测试描述语言的单位，则可省去前一步骤，直接将t t c n 描述的测试集转换为可执行测试集。转换方式包括对t t c n 进行解释和编译这 两种。国内外采用解释方式的系统较多，如国外的o p e n t t c no y ”公司开发 的o r e n t t c n 测试仪工具中的t t c n 一3 ( t t c n ) 解释器和国内清华大学网络安 全和协议测试实验室。”研制开发的基于t t c n 的p i t s 测试系统中的t t c n 解释 器。2 0 世纪8 0 年代，国内采用t t c n c 编译方式的典型单位是中科院成都计 算机应用研究所，该系统以o s i 第4 类传送层协议为对象开发的测试系统中 开发的t t c n c 编译器称为“t t c n t o o lk i t ”。“，曾在国外几家单位试用过。 近些年，随着t t c n - 3 的普及和i p v 6 测试系统的出现，一些研究机构正 在研究开发t t c n 一3 支撑工具。例如t e s t i n g t e c h “公司开发出的t t t h r e e 系列工具，该系列工具实现了对t t c n 一3 到c 语言的编译以及t t c n 一3 到j a v a 语言的编译：d a n e t “”公司开发的t t c n 一3t o o l b o x 中的编译器；o p e n t t c no y 公司开发的o p e n t t c n 测试仪工具中的t t c n 一3 解释器。国内目前正在开发 的t t c n 一3 ，支撑工具大多采用解释的方式，具有代表性的研究机构如清华大学 的网络安全和协议测试实验室。1 ，该实验室采用的测试描述语言是t t c n 和 t t c n 一3 ，实现了对啊州和t t c n - 3 的勰释，并对t t c n 进行了一定的扩展。值 得一提的是，国内另一家具有代表性的研究协议测试的机构是中科院计算机 研究所网络测试实验室。”，他们设计的测试系统中采用了编译的方式，但其 编译的对象是该实验室参考t t c n 定义的一种用于描述i p v 6 测试集的类形式 化语言。 2 3 并发多端口路由器测试系统中的t t c n - 3 支撑工具 如2 1 ，2 节所述，c m p t d l 是为了实现并发多端口测试而设计的一种并发 测试描述语言。在图1 3 中，c m p t d l 编译器的输入为c m p t d l 并发测试集， 输出为t t c n 一3 描述的测试集和用于并发多端口控制的c 代码。其中它输出的 t t c n 3 溺试集要想在测试系统中运行，就需要t t c n - 3 支撑工具。 本系统中，我们采用了直接将t t c n - 3 测试集转换为可执行的测试集的方 西南交通大学硕士研究生学位论文 第10 页 式。在编译与解释的选择中，我们采用了编译的方式。也就是况，该t t c n 一3 支撑工具设计为t t c n 一3 编译器，如图卜3 中所示的t t c n 一3c o m p i l e t 。 之所以采用编译两不是解释的方式，是由于考虑到以下几点： 1 )解释方式的优点是解释中出错可以修改t t c n 一3 描述后立即重新执行， 特别适合于对t t c n 描述的调试；但由于它的边解释边执行的特征不太 适合高速路由器的测试，特别是性能测试。 2 ) 考虑到本系统的设计目标是针对未来高速路由器的多端口并发测试，对 测试系统的效率要求较高。 3 )本质上，采用编译还是解释方式是时间与空间之间的折中与平衡问题。 采用编译的好处是以空闻换时同，测试运行效率高。特剐适合于测试集 已经通过调试的场合，特别是高速路由器的性能测试。考虑到现代微机 系统的存储空间已经不再成为难题，选择编译方式就更适合开发中的路 由器多端口测试。 t t c n 一3 的编译一般分为两个步骤，第一个步骤是将t t c n 一3 描述的测试 集编译成某种中间的高级语言，第二步再用该中问语言的编译程序编译成最 终的可执行文件。这样做的好处一是可以利用现有的高级语言编译程序，把 研究的重点放在t t c n 一3 和高级语言的转换上；二是可以利用中间语言的可移 植性，将编译过来的程序拿到多种平台上进行编译，从而提高编译程序的可 移植性和测试集对多操作系统平台的适应能力。本编译器采用的中间语言为 “c ”语言。选用c 语言的一个优点是，因为c 使用最为普遍，因此容易将经 编译后的t t c n 一3 的c 程序文件，与其他测试部件的c 程序联合进行c 编译 或进行链接。事实上，我们的测试系统中的编解码器( e d e n c o d e r d e c o d e r ) 和单测试例执行程序( t r a v e r s e r ) 就采用了这一方式。 综上，产生了如图2 - i 所示的扶c d p t d l 描述的抽象测试控制数据生成以 机器代码形式存放的可执行测试控制数据的过程。 图2 - 1 测试编译过狂 西南交通大掌硕士研究生学位论文第1 1 页 2 4 并发多端口路由器测试系统中t t c n - 3 c 编译器总体设计 2 4 1 编译器的阶段 从概念上讲，编译器是分阶段执行的。每个阶段将源程序从一种表示转 换成另一种表示。各个阶段进行的操作在逻辑上是紧密连接在一起的。编译 源程序 目标程序 图2 - 2 典型编泽器的各阶段 器的一个典型的阶段划分如图2 2 所示。“1 。它共有六个阶段。事实上，编 译器的某些阶段可以合并在一起。图2 2 中的前三个阶段构成了编译器的分 析部分。符号表管理和错误处理是编译器的六个阶段都要涉及的两项活动。 在本t t c n 3 6 的编译器中，由于不生成最终的机器码，因此不包括一般 编译器所具有的中间代码生成、代码优化这两个阶段。 2 4 2 编译器的遍 个编译过程可由一遍、两遍或多遍完成。所谓“遍”，是指对源程序 西南交通大学硕士研究生学位论文 第1 2 页 或其等价的中i 刈语言程序从头到尾扫描并完成规定任务的过程。每一遍扫描 呵以完成编译器的一个阶段或多个阶段的i ：作。 一方面，我们希望编译的遍数越少越好，以减少读写中间文件的时间开 销。另一方面，如果我们将多个阶段组合为一遍，我们将不得不把这些阶段 的整个程序保存在内存中，这样，空间可能是一个很大的问题”“。同样的道 理，一个越多遍的编译程序占的内存会越少，但开销的时间会越多。 中科院成都计算机应用研究所在开发o s i 第4 类传送层协议测试系统时 开发出的t t c n 编译器采用的是一遍扫描( 这里指的是针对t t c n - - m p 文 件采用了一遍扫描) ：t e s t i n gt e c h 公司开发的t t t h r e e 系列t t c n 3 编译器 t t c n 一3 编译器采用的是多遍扫描( 大于或等于三遍) 。 本t t c n 3 c 编译器采用了两遍扫描。第一遍扫描读入t t c n 一3 源程序， 并对其进行词法分析、语法分析和语义分析。第一遍扫描输出的是语法树。 第二遍的输入是第一遍输出的语法树，该遍通过对语法树的遍历来生成c 代 码。如图2 3 所示。笔者的工作重点是第一遍扫描。 图2 3t t c n3 c 编译器的谝 本编译器的两遍扫描是对编译的时间和空间问题上的折中态度。而导致 本编译器采用两遍扫描的更重要的因素是由于考虑了到以下三点： 1 ) 一遍扫描对生成的代码质量的限制太大，生成的编译器较难维护。 2 ) 本编译器由两个小组成员来完成。一遍扫描要求每个成员对编译器的各 个阶段的设计都充分了解；采用两遍扫描，由于前后两遍的设计相对独 立，使小组的两个成员可以较明确地分工。 3 ) 本编洋器用在并发多端口路由器测试系统中，。对时问即速度有较高的要 求。多遍扫描的编译速度相对较慢，可能会影响到路由器的测试效率。 西南交通大学硕士研究生学位论文第13 页 第三章词法分析及语法分析 3 1 词法分析 3 1 1 词法分析简介 词法分析是编译过程的第一个阶段。这个阶段的主要任务是从左到右 个字符个字符地读入t t c n 一3 源程序，产生单词符号序列，以提交给语法 分析使用“。词法分析还可以完成一些相关的辅助任务。一个任务是滤掉源 程序中的注释、空格、制表符、换行符；另一个任务是使编译器能将发现的 错误信息与源程序的出错位置联系起来”，例如，在本编译器中词法分析就 要负责记录遇到的换行符的个数，以便将行号与出错信息联系起来。 3 1 2 利用l e x 工具构造词法分析器 本编译器的词法分析部分是用自动构造词法分析的工具l e x “71 州的 f i 。e x 版本( f a s tl e x ) o ”3 生成的。工具l e x 通常全称为l e x 编译系统。l e x 粕洋系统的输入为l e x 语音，输出为c 语苦。如图3 一l 所示，l e x 编译系 统自动地把表示输入串词法结构的正规式及相应的动作转换成一个宿主语言 ( c 语言) 的程序。它有一个固定的名字为y y l e x ，y y l e x 是一个c 程序。经 c 语言编泽程序编译后可运行，它的功能就是对输入串识别出单词符号，一并 可作相应的动作“。 r 。- 1 l e x 源程序雌e x 编译系统l 刚l e x ij 姒小e 卜币词符剀： 图3 - 1l e x 编译系统的作用 l e x 输入源程序的格式如下。： 说明部分 西南交通大学硕士研究生学位论文第14 页 转换规则 辅助过程 在本编译器中，使用l e x 来生成词法分析程序的原因有两点： 1 )本编译器是用c 语言开发的，而l e x 的宿主语言是c ，所阻编译器中可 以直接使，日l e x 生成的文件。 2 ) 减少工作量。 在本编译器中，l e x 的输入文件为t t c n l 。在t t c n l 的说明部分定 义了2 9 个正则表达式，并区分了新的一行和其它的空白格；转换规则部分由 t t c n 一3 的13 6 个保留字规则，2 4 个终结符，正则表达式，以及相应的r e t u m 语句组成；辅助过程部分定义了读输入串和写输出单词符号串的c 程序段。 3 1 3 词法分析器的输出结果 利用生成的词法分析程序，可以对t t c n 一3 程序进行词法分析。例如， 读入以下一小段t t c n 一3 程序： m o d u lea i c h jc e c t u r e i m p o itf r o md a t a t y p e s1 1 e “1 r sr y ea ll ： g z o u pp o r t ，d e f i n i t i o t i sg 】o u p t y p ep o x ti p p o xt t y p em i x e d n o u ! n d m e ss a g e t y p e n d p ( “：e d u i e t v p e g _ r o u pc o m p o n e n t d e f i n i t i o n sg r o u p t y p ec o m p o n e n tn e t w o i k n o d e p o jlt p p o t t y p en s a p j 对其进行词法分析后输出 l ：r e s e r v e ( 1w o l ( 1 ：m o d u l 色 1 ：i d i y a u l e = a ic h i t e c t u r e 西南交通大学硕士研究生学位论文第15 页 2 r e s e r v e dw o r df r o m 2 2 ：r e s e ir e dw o r d a 1 1 3 ：r e s e r v e dw o r d ：g r o u p 3 ：i d ，n a m e ：p o r t d e f i n i t i o n s g l o u p 3 ： 4 ：r e s e ir e dw o r d ：t y p e 4 ：r e s e lr e dw e l d ：p o it 4 ：i d ，n a m e = i p p o r t t y p e 4r e s e r v e dw o r d ：m i x e d