（计算机软件与理论专业论文）基于antlr的ttcn3分析器的设计与实现.pdf

- t jjijirillfjifjliflllfljlllif1111iriifllllll fy 17 3 6 1 17 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作及取得的研究成果。除了 文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其他人己经发表或撰写过的研 究成果，也不包含为获得内蒙古大学或其他教育机构的学位或证书而使用过的材料。与我一 同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示了谢意。 学位论文作者签名：杰幽易： 日期：洫f2 上。f 乡 指导教师签名：羔圣盏 日期：釜：! = ：垒：矿 在学期间研究成果使用说明书 学位论文作者完全了解内蒙古大学有关保留和使用学位论文的规定，即：内蒙古大学研 究生在校攻读学位期间论文工作的知识产权单位属内蒙古大学。学校有权保留并向国家有关 部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借阅；学校可以公布学位论文 的全部或部分内容，可以允许采用影印、缩印或其它复制手段保存、汇编学位论文。作者今 后使用涉及在学期间主要研究内容或研究成果，须征得内蒙古大学就读期间导师的同意；若 用于发表论文，版权单位必须署名为内蒙古大学方可投稿或公开发表。 学位论文作者签名：幽霆： 日期：丝 芝：! ； 指导教师签名：j 蛆 日期：兰里2 里：罗 内蒙古人学硕士学位论文 基于a n t l r 的t t c n - 3 分析器的设计和实现 摘要 随着计算机与网络技术的不断发展，测试越来越受到人们的重视。t t c n - 3 作为一种灵活的、强有力的测试描述语言，也越来越受到人们的关注。但是昂 贵的t t c n 3 商业软件在一定程度上限制了t t c n 3 的广泛使用。本文的主要 目标是在欧盟g 0 4 i t 开源项目a 0 阶段的基础上，设计与实现t t c n 3 编译器。 t t c n - 3 编译器在t t c n 3 测试平台中具有非常重要的地位，它的主要作 用是将t t c n 3 抽象测试套翻译成用高级程序设计语言描述的可执行测试套。 测试用户通过在测试平台下执行可执行测试套进行测试。t t c n - 3 编译器分为前 端和后端，前端包括词法分析到中间代码生成的整个过程，而后端指中间代码 到目标代码生成的过程。本文所设计实现的t t c n - 3 分析器就是指t t c n 一3 编译 器的前端，包括t t c n 一3 的词法分析、语法分析、语义分析及中间表示形式语 法树的生成。 本文通过对t t c n - 3 核心语言、编译理论及t t c n 3 编译器实现途径的分 析，采用编译器生成工具a n t l r 自动生成t t c n 3 词法分析器、语法分析器 的实现方式，对t t c n - 3 分析器的整体框架和语法树、符号表等数据结构进行 了设计和实现。由于t t c n 3 存在超前引用等复杂特性，本t t c n 3 分析器采 用两遍扫描的方式实现，第一遍扫描时进行词法分析和语法分析并生成语法树 及符号表，第二遍扫描时基于语法树和符号表进行语义分析。 基于a n t l r 的t t c n - 3 分析器的设计与实现 一_ - l _ _ _ 一 关键词：t t c n 3 ，编译器，a n t l r ，分析器 【一 内蒙古人学硕+ 学位论文 t h ed e s i g na n di m p l e m e n t a t i o no f a n t l r b a s e dt t c n 3p a r s e r a b s t r a c t w i t ht h ec o m p u t e ra n dn e t w o r k t e c h n o l o g yd e v e l o p i n gc o n t i n u a l l y , p e o p l ep a y a t t e n t i o nt ot h et e s tm o r ea n dm o r e a saf l e x i b l ea n dp o w e r f u lt e s td e s c r i p t i o n l a n g u a g e ，t t c n 一3i si n c r e a s i n g l yr e c o g n i z e db yp e o p l e b u tt t c n 3c o m m e r c i a l s o f f w a r e sa r ee x p e n s i v e ，w h i c hl i m i t st h ew i d e s p r e a du s eo f t t c n 3t os o m ee x t e n t t h e t a r g e to ft h i st h e s i si st od e s i g na n di m p l e m e n tat t c n 3c o m p i l e ro nt h eb a s i s o ft h ea 0s t a g ei nt h ee u r o p e a nu n i o ng 0 4 i t p r o j e c t t t c n _ 3c o m p i l e rh a sav e r yi m p o r t a n tr o l ei nt h et t c n 3t e s tp l a t f o r m ，a n d i t sm a i nf u n c t i o ni st ot r a n s l a t et h et t c n 3a b s t r a c tt e s ts u i t ei n t ot h ee x e c u t a b l e t e s ts u i t ed e s c r i b e dw i t hh i g h l e v e lp r o g r a m m i n gl a n g u a g e t h e t e s t i n gi sd o n eb y r u n n i n gt h ee t si nt h et e s te x e c u t i o np l a t f o r m t h et t c n 3c o m p i l e ri sd i v i d e d i n t ot h ef r o n t ，e n da n dt h eb a c k e n d t h ef r o n t e n dr e f e r st ot h ep r o c e s sf r o ml e x i c a l a n a l y s i st om i d d l er e p r e s e n t a t i o ng e n e r a t i o na n dt h eb a c k e n dr e f e r st ot h ep r o c e s s f r o mt h em i d d l er e p r e s e n t a t i o nt ot h e o b j e c tc o d eg e n e r a t i o n t t c n 3p a r s e r d e s i g n e di nt h et h e s i si st h ef r o n t e n do ft h et t c n 3c o m p i l e r , a n di tc o n t a i n 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 sa n dt h eg e n e r a t i o no f s y n t a xt r e e ， w h i c hi st h em i d d l er e p r e s e n t a t i o no ft h et t c n 3t e s ts u i t e t h et h e s i sd e s i g n st h eo v e r a l lf r a m e w o r ko ft h et t c n 3 p a r s e r , a n ds o m ed a t a 基丁：a n t l r 的t t c n - 3 分析器的设计与实现 一二i 一 s t r u c t u r e s ，f o re x a m p l e ，s y n t a x t r e ea n ds y m b o lt a b l e ，b ya n a l y z i n gt h et t c n - 3c o r e l a n g u a g e ，c o m p i l e rt h e o r y , t h ei m p l e m e n t a t i o na p p r o a c ho ft t c n l 3c o m p i l e ra n d u s i n gt h ei m p l e m e n t a t i o n s c h e m et h a ti sg e n e r a t i n gt h et t c n 3l e x e ra n dt t c n - 3 p a r s e ra u t o m a t i c a l l yb y a n t l r ，w h i c h i sa c o m p i l e rg e n e r a t i o n t o o l c o n s i d e r i n gt h a ts o m ec o m p l e x c h a r a c t e r i s t i c se x i s ti nt t c n 3 ，s u c ha sa d v a n c e d r e f e r e n c e ，t h et t c n 3p a r s e ri si m p l e m e n t e db yt w i c es c a n n i n g l e x i c a la n a l y s i s a n ds y n t a xa n a l y s i sh a v eb e e nd o n e ， a n ds y n t a xt r e ea n ds y m b o lt a b l eh a v eb e e n g e n e r a t e db yf i r s t l ys c a n n i n g b a s i n go nt h es y n t a x t r e ea n ds y m b o lt a b l e ， s e m a n t i ca n a l y s i sh a sb e e nd o n eb ys e c o n d l ys c a n n i n g 【 k e y w o r d s ：t t c n 一3 ，c o m p i l e r ，a n t l r ，p a r s e r 内蒙古火学硕士学位论文 目录 摘要i a b s t r a c t i i i 目录v 图表目录v i i 第一章绪论l 第二章t t c n 3 及a n t l r 概述4 2 1 测试描述语言t t c n 3 与测试4 2 2t t c n 3 测试体系结构6 2 3a n t l r 概j 苤7 第三章t t c n 3 分析器的分析与设计1 1 3 1t t c n 3 编译器的实现途径及编译流程1 1 3 2 基于a n t l r 的t t c n 3 分析器的实现设计1 3 3 2 1t t c n 3 语言规则描述1 3 3 2 2 基于a n t l r 的t t c n 3 分析器的设计分析1 4 3 3t t c n 3 语法树设计1 5 3 3 1 语法树存储结构1 6 3 3 2 语法树节点设计1 6 3 4 静态语义分析的任务。18 3 5t t c n 3 类型的相容性分析18 3 6t t c n 3 符号表的内容、组织方式及操作接口分析2 0 第四章t t c n 3 分析器的实现2 7 v 1 1 2 3 吠 一 现 用容 一 一 应内 展和 发标 及目 景究 一构 背研 结 题文写文 课本缩论 1 2 3 4 ，1 1 1 j i 基于a n t l r 的t t c n - 3 分析器的设计与实现 4 1 词法分析实现2 7 4 1 1 词法分析简介2 7 4 1 2 词法分析实现2 7 4 2 语法分析实现2 9 4 2 1 语法分析器的功能2 9 4 2 2 语法分析器的构造3 0 4 2 3 语法分析器的实现3 2 4 3 符号表及其接口的实现3 5 4 4 作用域检查的实现3 8 4 5t t c n 一3 的静态语义分析的实现3 9 4 5 1 声明的语义处理3 9 4 5 2 执行语句的语义处理。4 2 4 6t t c n 3 分析器的总体实现4 5 第五章实例应用4 7 5 1d n s 测试套及其说明4 7 5 2 对d n s 测试套的分析4 9 第六章总结展望。5 4 6 1 本文工作总结。5 4 6 2 未来工作展望5 5 参考文献5 6 致谢5 8 v i 内蒙古大学硕士学位论文 图表目录 图2 1t t c n 3 模块结构4 图2 2t t c n 3 模块定义部分5 图2 3t t c n 3 模块控制部分6 图2 4t t c n 3 测试体系结构 2 1 7 图2 5 语法分析流程9 图3 1 编译器的作用1 l 图3 2 编译器的功能结构2 3 1 11 图3 3t t c n 3 编译器流程13 图3 4t t c n 3 分析器的分析过程j 1 5 图3 5t t c n 3 语法树节点结构1 6 图3 6a * b + c d 对应的语法树1 6 图3 7a s t 结构1 7 17 表3 1 语法树节点属性1 7 图3 8a = 5 + 3 对应的语法树18 图3 9 t t c n 3 作用域【l 】2 2 图3 1 0t t c n 3 符号表作用域结构2 3 图3 1 1t t c n 一3 作用域栈和作用域树示例2 5 图4 1t t c n 3 词法分析器实现2 8 图4 2t t c n 3 语法分析器功能3 0 表4 1e b n f 语法【1 1 和a n t l r 的语法【6 1 31 图4 3p u t 函数流程3 7 图4 4f i n d 函数流程3 7 图4 5 作用域检查过程3 9 图4 6 类型声明的语义分析4 0 表4 2 符号表项示例4 1 图4 7 标签语句处理过程4 3 图4 8 跳转语句处理过程。4 4 v i i 基于a n t l r 的t t c n - 3 分析器的设计与实现 一一一 图4 9 标签跳转语句最后处理”4 4 图5 1d n s 测试过程【5 】4 7 内蒙古大学硕士学位论文 1 1 课题背景及发展应用现状 第一章绪论 随着计算机技术和通信技术的飞速发展，用户对计算机产品质量的要求也在不断提高。 那么如何对软件以及网络协议、通讯设备的安全性、稳定性、可靠性进行衡量判定，如何改 进产品过程，进而提高产品的质量，已经成为许多研发机构、软件企业和设备生产商迫切关 心的问题。测试作为保证产品质量的重要手段，越末越受到人们的关注和重视。 t t c n 3 ( t e s t i n ga n dt e s t c o n t r o ln o t a t i o nv e r s i o n3 ，测试及测试控制表示法第 三版) 是专门为测试领域制定的通用测试语言，用于描述在多种通信端口上的各种响应系统 测试【lj 。它作为一项已经成熟的技术，己经被广泛地应用于协议测试( 包括移动和互联网协议) 、 服务测试、基于平台的c o r b a 测试、a p i 测试等领域。同时，t t c n 3 并不仅限于一致性测 试领域，可以用于其他类型的测试，如互操作性测试、健壮性测试、回归测试、系统和集成 测试，随着技术的日趋完善和普及，t r c n 3 语言从开始仅涉及电信业测试扩展到嵌入系统 测试和一般软件测试等全新领域【5 j 。 t t c n 一3 是新型测试描述语言，国际上现已经有几种商业软件：如t e l e l o g i c 1 1 】公司丌发 的t a ut t c ns u i t e 包括t t c n 编辑器，t t c n 编译器以及t t c ne x e r c i s e r 等套件；o p e n t t c n i l 3 】 公司丌发的o p e n t t c n 软件包可进行t t c n 测试例的编辑编译，对语法语义进行检查并生成可 执行测试例；t e s t i n g _ t e c h i n 司研发的支持t t c n 一3 语言的测试系统t t w o r k b e n c h ， t t w o r k b e n c h 是基于t t c n 一3 国际标准测试语言的图形化测试开发环境和执行环境，它包括测 试过程所需要的全部功能如分析，测试，执行等。国内西南交大【2 l 】、中科大等也在进行 t t c n - 3 测试平台的相关研究开发。 1 2 本文研究目标和内容 t t c n 3 测试系统的设计与实现是一项复杂的工程，目前，市场上存在一些商用的t t c n 3 测试系统，用户可以购买某些协议的可执行测试套产品，或在这些测试平台上开发一些简单 的测试例。但是，测试平台或可执行测试套产品价格昂贵、部分核心技术对用户封闭，在一 定程度上限制了t t c n 3 语言的广泛使用。 基于a n t l r 的t t c n - 3 分析器的设计与实现 g 0 4 i t 项目1 9 是由欧盟创立的、多方参与的国际合作项目，旨在提供一个免费的、开源的 和通用的i p v 6 测试环境，此环境是基于t t c n 3 的，包括测试工具、测试套和相关服务等方 面。本文在g 0 4 i t 项目组a 0 阶段的基础上，从不改变现有实现接口的原则上出发，对t t c n 3 编译器的整体框架、语法树和符号表等数据结构进行设计，主要工作是通过语言识别工具 a n t l r 完成t t c n 3 编译器前端的设计与实现，即完成t t c n 3 编译器的词法分析、语法分 析、语义分析，生成t t c n 3 测试套的语法树以及符号表。 1 3 缩写 g 0 4 i t 欧盟g 0 4 i t 项目 a 0 阶段：g 0 4 i t 项目的第一阶段 a t s ： a b s t r a c tt e s ts u i t e 抽象测试套 t t c n 一3 ：t e s t i n ga n dt e s tc o n t r o ln o t a t i o n 测试和测试控制第三版 a n t l r ：a n o t h e rt o o lf o rl a n g u a g er e c o g n i t i o n 另一个语言识别工具 a s t ：a b s t r a c ts y n t a xt r e e 抽象语法树 b n f ：b a c k u s n a u rf o r m 巴科斯范式 c h ：c o m p o n e n th a n d l e r 成分控制模块 e t s ：e x e c u t a b l et e s ts u i t e 可执行测试套 m t c ：m a i nt e s tc o m p o n e n t 主测试成分 p a ：p l a t f o r ma d a p t e r 平台适配器 s a ： s u t a d a p t e r 被测系统适配器 s u t ： s y s t e mu n d e rt e s t 被测系统 t 3 r t s ：t t c n 3r u n t i m es y s t e mt t c n 3 运行时系统 t c i ：t t c n 3c o n t r o li n t e r f a c et t c n 3 控制接口 t e ：t t c n 3e x e c u t a b l e 测试执行器模块 t l ：t e s tl o g g i n g 测试同志模块 t m ：t e s tm a n a g e m e n t 测试管理模块 t r i ：t t c n 3r u n t i m ei n t e r f a c et t c n 3 运行时接口 t s h t e s ts y s t e mi n t e r f a c e 被测系统接口 2 内蒙古大学硕士学位论文 1 4 论文结构 本文共分六章。第一章为绪论部分，对于本文所涉及到的领域、课题来源以及论文所要 达到的目标做了阐述和说明：第二章对t t c n 3 语言及编译理论相关部分进行了介绍；第三 章，通过对编译理论的研究和对一般t t c n 3 编译器实现途径地分析，基于a n t l r 设计了 本分析器的整体结构及语法树和符号表等数据结构；第四章阐述了t t c n 3 分析器的词法分 析、语法分析及语义分析的具体实现过程；第五章作为分析器的实例部分，通过分析器对d n s 测试套的分析，验证了t t c n 3 分析器的设计实现；第六章是对本论文所做工作的总结和对 未来工作的展望。 基于a n t l r 的t t c n - 3 分析器的设计与实现 第二章t t c n - 3 及a n t l r 概述 2 1 测试描述语言t t c n 3 与测试 2 1 1t t c n - 3 简介 t t c n - 3 ( t e s t i n ga n dt e s tc o n t r o ln o t a t i o n3 ) 是由欧洲远程通信技术标准协会制定的 一种测试描述和实现的标准语言i 。它是由t t c n 2 ( t r e ea n dt a b u l a r c o m b i n e dn o t a t i o n ) 发展 而来的。t t c n 2 最初用来进行o s i 协议的一致性测试，后来广泛用于远程通信协议测试， 例如g s m ，u m t s 和d e c t 。t t c n 3 比t t c n 2 更加灵活，而且在保留以前特性的同时能 够用于其它目的，如互联网协议测试( 例如i p v 6 或s i p ) 和a p i s 测试。虽然互联网系统测 试是t t c n 3 的主要应用领域，但t t c n 3 还可以处理如集成测试、单元测试的下层测试【5 j 。 t t c n 3 是一种基于文本的语言，在语法和语义上和其他高级编程语言类似。因此，对于程 序员来说t t c n - 3 易学易用。 t t c n 3 除核心语言外还有表格表示格式、消息序列图表示格式等多种表示形式【l j 。但 核心语言是其它形式的语义基础，在本文以后章节的讨论中，核心语言是唯一的表示形式。 2 1 2t t c n - 3 模块 t t c n 3 最基本的结构是模块，模块是t t c n 3 的顶层单元。测试套可以只包含一个模 块，也可以通过i m p o r t 语句导入其它模块的所有定义。模块由模块定义部分和模块控制部 分组成f 1 】。模块定义部分包括常量、类型、模板、可选步、测试例、过程特征和模块参数等。 模块的结构如图2 1 所示。 图2 1t t c n 3 模块结构 f i g u r e2 1t t c n - 3m o d u l es t r u c t u r e t t c n 3 支持大量预定义的基本类型。这些基本的类型包含整型、布尔型、串类型和一 4 内蒙古人学硕士学位论文 些t t c n 3 特有的类型。用户可以通过这些基本类型定义结构类型，如记录类型、集合类 型和枚举类型。 t t c n - 3 模块的定义部分 模块定义部分描述了模块的顶层定义以及从其它模块导入的定义【i 】。主要包括：类型定 义、常量定义、模板定义、模块参数定义、函数定义、过程定义、测试例定义、可选步定 义、导入定义、组定义等，如图2 2 所示。 图2 2t t c n 一3 模块定义部分 f i g u r e2 2t t c n - 3m o d u l ed e f i n i t i o np a r t 在上图中，模块定义部分的定义都是全局的，所有类型定义、常量定义、过程特征定义、 模板定义都是有关测试数据的定义；端口定义、成份定义用于测试配置；函数定义、可选 步定义、测试例定义是测试行为的定义。 t t c n - 3 模块的控制部分 模块控制部分是t t c n 3 测试套的动态部分，用于控制测试例的执行。模块控制部分可 能包含局部定义( 如常量、模板) 、局部实例( 如变量、定时器) 以及实际测试例的参数、 选择、执行顺序的描述等内容。应该在模块的定义部分定义测试例或从其他模块导入，在 模块的控制部分调用测试例。模块控制部分通过测试例参数调用测试例并且控制测试例的 基于a n t l r 的t t c n - 3 分析器的设计与实现 执行，基本程序语句可以用来选择和执行测试例。模块控制部分的定义仅局部可见，即只 能在控制部分使用卯，如图2 3 所示。 2 1 3t t c n - 3 测试 图2 3t t c n 3 模块控制部分 f i g u r e2 3 t t c n 3m o d u l ec o n t r o lp a r t t t c n 一3 可以用于多种通信端口上的各种响应系统测试，包括协议测试( 如移动协议和互连 网协议) 、服务测试( 包括增补服务) 、模块测试、基于平台、a p i s 等的c o r b a 测试。t t c n 一3 并不仅仅局限于一致性测试，它可用于多种类型的测试，如互操作性测试( i n t e r o p e r a b i l i t y t e s t i n g ) 、健壮性测试( r o b u s t n e s st e s t i n g ) 、回归测试( r e g r e s s i o nt e s t i n g ) 、系统 和集成测试( s y s t e ma n di n t e g r a t i o nt e s t i n g ) 【l 】。t t c n 一3 测试语言是当前通信厂商通 信协议测试的主流，支持任何的黑盒测试，可以进行多种通信界面的各种系统测试。典型的 应用领域是移动通信协议测试( 如g s m ，3 g ) ，网际网络协定测试( 如i p v 6 ，s i p ，o s p ，h 3 2 3 ) ， 宽带技术测试( a t m ，b - i s d n ) 。t t c n - 3 提供各领域最佳解决方案，包括通信制造业，服务供 应商，测试研究单位，以及标准联盟等，目前的用户包括n o k i a ，m o t o r o l a ，e r i c s s o n ，华 为，中兴，中国移动等。 2 2t t c n 3 测试体系结构 t t c n 一3 测试系统用于执行t t c n 一3 描述的测试，t t c n 一3 标准规范t c i t 2 l 和t r i t a l 描述t t t c n 一3 测试体系结构。t t c n - 3 测试体系结构主要是由测试管理和配置( t m ) 、测试日志( t l ) 、 成分处理( c h ) 、编解码( c d ) 、测试执行( t e ) 、被测系统适配器( s a ) 和平台适配器( p a ) 组成，其中测试管理和配置实体与测试执行实体的接口称为测试控制接口( t c i ) ，测试执 行实体与被测系统适配器及平台适配器之间交互的接口称为测试控制接口( t r i ) ，如图2 4 所示。 6 内蒙古大学硕士学位论文 图2 4t t c n 3 测试体系结构1 2 】 f i g u r e2 4t t c n - 3t e s ta r c h i t e c t u r e 其中t m 实体负责整体的管理，包括用户接口的实现和测试执行的管理。c h 实体负责 测试成分的分布和测试成分之间的通信。c d 实体负责测试系统和被测系统问相互传输信息 的不同格式之间的转化。t e 实体负责解释和执行t t c n - 3 可执行测试套( e t s ) ，它从概念上 由t 3 r t s 、e d s 和e t s 三部分组成，t 3 r t s 是t t c n - 3 运行时系统，e d s 负责内部编解码工作， e t s 是可执行测试套。s a 实体使t t c n 3 测试系统和被测系统之间基于消息和过程的通讯 适合测试系统特定的执行平台。p a 实体实现t t c n 3 外部函数并为t t c n 3 测试系统提供 统一的时问概念。 在t e 模块中需要解释或执行的可执行测试套是由t t c n 3 语言编写的抽象测试套 ( a s t ) 经t t c n 3 编译器编译后产生的可执行代码。t t c n 3 编译器主要完成t t c n 3 语 言描述的抽象测试套的词法分析、语法分析、语义分析和代码生成等工作。 2 3a n t l r 概述 a n t l r ，语言识别的另一个工具( a n o t h e rt o o lf o rl a n g u a g er e c o g n i t i o n ) ，是一种语 言工具，它提供了一个可以通过包含j a v a 、c + + 等动作的语法描述来构造语言识别器、编译 器和解析器的框梨6 】【7 1 。a n t l r 是一个非常强大的编译器生成工具，它是由t e r e n c ep a r r 等人研究开发的，是目前主流的编译器生成工具之一。 7 基于a n t l r 的t t c n - - 3 分析器的设计与实现 用户可以利用a n t l r 根据自定义的词法分析规则和语法分析规则来生成需要的词法分析 器和语法分析器。通过词法分析器可以把输入的字符流转化为记号流( t o k e ns t r e a m s ) ， 然后记号流作为语法分析器的输入，通过语法分析器生成语法树，最后基于语法树根据实 际需要再做相应的处理。 2 3 1a n t l r 的元语言 a n t l r 要生成词法分析器、语法分析器，需要用户输入各种关于源语言的信息，如正则 表达式、上下文无关文法描述、语义动作等，而且用户还需要对生成的编译器进行一些设 置，所有这些工作都是通过a n t l r 的元语言来完成的，用户必须严格按照元语言的规定来 编写语法文件作为a n t l r 的输入。 a n t l r 的元语言元素主要包括元语言词汇、头部定义、分析器类定义、选项段、记号 段、语法继承、规则定义、产生式元素、产生式元素操作符、谓词、元素标签、扩展的b n f 规则元素等。 2 3 2 用a n t l r 生成词法分析器 词法分析器将输入的字符流分解为词汇表中的一个个的符号，然后输出到语法分析器。 为了执行词法分析，需要指定一个词法分析类，它描述了如何将字符输入流分解成记号流。 词法分析类中的词法规则成为生成类中的成员方法。一个词法分析器语法描述的总体结构 如下： c l a s sm y l e x e re x t e n d sl e x e r ； o p t i o n s s o m eo p t i o n s l e x e rc l a s sm e m b e r s ) l e x i c a lr u l e s 2 3 3 用a n t l r 生成语法分析器 语法分析的任务是识别单词符号序列是否符合给定的语法规则。a n t l r 生成的语法分 析器采用自项向下的递归子程序法进行语法分析。简单地说，就是对应每个非终结符语法 8 内蒙古大学硕士学位论文 单元，都有一个独立的处理子程序。语法分析从源程序的最顶层开始向下分析，每遇到非 终结符时，就调用相应的处理子程序，当遇到终结符时，则判断当前读入的单词是否与语 法规则定义的终结符相匹配，若匹配，则执行相应的语义处理，再读取下一个单词继续分 析，若不匹配，则出错。如果读入的源程序单词序列在整个语法分析中都能逐个得到匹配， 则说明该源程序在语法上是正确的。具体过程如图2 5 所示。 图2 5 语法分析流程 f i g u r e2 5p a r s i n gp r o c e s s 在语法分析阶段，a n t l r 可以构造抽象语法树( a s t ) 。a n t l r 提供了一整套a s t 类库， 用户可以让a n t l r 自动生成语法树，也可以完全自己建立语法树或部分自建语法树。而且 a n t l r 不仅可以在语法描述文法中传递参数和返回值，还允许在语法规则的各个部位放置 语义动作，这极大地方便了语义处理的完成。 2 3 4 基于a n t l r 实现抽象语法树分析器 一个树分析器就像一个语法分析器，不同的是树分析器处理的是二维的由结点组成的抽 象语法树( a b s t r a c ts y n t a xt r e e ) ，而不是处理由记号组成的记号流。树分析器定义类似 于语法分析类，不同的是规则定义中可能包含特殊形式来指示其递归下降树。 9 基于a n t l r 的t t c n 一3 分析器的设计与实现 一- - - i - - l - - _ _ _ - _ - l _ - _ - _ - _ _ _ - 一 通过树分析器可以对语法分析阶段产生的语法树进行遍历，在遍历语法树的同时进行相 关的语义处理，完成对源程序的语义分析，也可以通过对语法树的遍历生成相应的目标代 码。 l o 内蒙古大学硕士学位论文 第三章t t c n - 3 分析器的分析与设计 编译程序通常分为前端和后端，其中前端是指词法分析到中间代码生成的整个阶段， 而后端指中间代码到目标代码生成的阶段【2 3 】。本文所设计的t t c n 一3 分析器就是指t t c n 一3 编译器的前端，包括t t c n - 3 的词法分析、语法分析、语义分析及中间表示形式语法树的生 成。 3 1t t c n 3 编译器的实现途径及编译流程 编译器是一种计算机语言翻译程序，它将源程序作为输入，而产生用目标语言描述的 等价程序【2 劫。编译器在源程序和目标程序之间的关系可以用图3 1 来表示。 图3 1 编译器的作用 f i g u r e3 1t h er o l eo f t h ec o m p i l e r 编译程序完成从源程序到目标程序的翻译工作，一般要经过多个阶段，每个阶段实现不同 的功能。不同的编译器可能有不同的阶段，但从功能角度来说基本都是一致的，图3 2 给 出了一般编译器的功能结构划分。 源 程 序 图3 2 编译器的功能结构【2 3 】 f i g u r e3 2f u n c t i o n a ls t r u c t u r eo f t h ec o m p i l e r 目 标 程 序 在上图中，各部分指明了编译器内部所做的工作。其中，词法分析的主要任务是检查词法 基于a n t l r 的t t c n - 3 分析器的设计与实现 错误并把输入的源程序字符流转化为有意义的单词流；语法分析的任务是检查源程序的语 法错误，从形式上判断源程序的正确性；语义分析是从源程序表示的实际语义的角度所进 行地正确性检查；中间代码是源程序的一种便于优化便于产生目标代码的内部表示结构； 中间代码优化的任务是对中间代码进行不依赖于目标机的优化，以产生高质量的目标代码； 目标代码生成的任务是根据中间代码生成与源程序等价的目标代码。 在上面六个阶段中，有两个重要的工作贯穿其中：符号表处理和错误处理。编译过程 中源程序的各种信息被保留在符号表中，编译各阶段的工作都涉及到符号表的构造、查找 或更新，因此需要有符号表处理工作；如果编译过程中发现源程序有错误，编译程序应报 告错误的性质和错误发生的地点，并且将错误所造成的影响限制在尽可能小的范围内。现 在的编译程序一般都能自动校正错误，使得源程序的其余部分能继续被编译下去，这些工 作称之为出错处理与错误恢复。 现有的t t c n 3 编译器实现方案主要有两种：一种是将t t c n 3 源程序转化为用普通高级 程序语言描述的程序，如j a v a 、c 、c 抖等，然后利用高级程序语言编译器编译执行转化后的 程序；另一种是先将t t c n 3 编译为内存对象，然后再执行【3 0 】。本文所论述的t t c n 3 编译 器是基于前一种方案实现的，先将t t c n 3 源程序转化为c + + 代码，然后利用c + +