（计算机软件与理论专业论文）z规格说明中序列和包的自动求精研究与实现.pdf

沈阳工业大学硕士学位论文 摘要 为了克服自然语言和程序设计语言描述规格说明产生的缺陷，人们提出了一种新的 软件开发范型，其基本思想是对系统建立一个数学模型，研究和提供一种基于数学的或 形式语义学的规格说明语言，用这种语言严格的描述所开发的软件功能，并由自动程序 设计的加工模型来得到可执行的代码。在软件开发系统开发过程中，系统需求分析和规 格说明非常重要该阶段形成的过程说明文档既是软件开发人员和用户之间的规约，又 是软件开发的起点。 本课题以z 规格说明的自动求精为目的，提出了用s t l 中的不同容器表示z 规格 说明数据类型的思想。结合c + + 语言的模板、重载技术和s t l 模板库对数据结构和通用 算法的强大支持功能，提供了相应的函数模板。以z 规格说明中的序列和包为研究对象， 利用c + + 及s t l 技术设计了序列和包各种操作的求精规则( 这里采用s t l 中的d e q 鹏 容器表示z 规格说明中的序列，m a p 容器表示z 规格说明中的包) ，并产生目标程序， 即把z 规格说明转换为c + + 代码。主要工作是设计了z 规格说明的自动扫描器、解释器， 定义了z 规格说明中的关键字和符号表，给出了对应规则，实现了序列和包的自动求精； 给出了z 规格说明的正确性验证方式，提供了错误处理的手段，并举例说明规格说明的 写法以及实现。最后提供了程序的实验结果。 z 规格说明可以贯穿软件开发的整个过程，而在软件开发过程中都会先应用于需求 分析阶段，本课题讨论的也就是这个阶段。由于求精过程不采用手工操作，避免了人工 的误操作或演算错误导致的求精前后不一致，保证了系统的一致性和完整性。加快了程 序软件开发的自动化和智能化的进程。 关键词：z 规格说明，序列，包，自动求精 z 规格说明中序列和包的自动求精研究与实现 i k s e a n ha n di k a l i 船t i o no fa u t o m a t i s mr e l i n e m e n to fl i s ta n d b a g i nt h ez s p e c m c a t i o n a b s 仃a c t ho 妇t o 州黜m en a t 咖il 醐a n dt h e 印g r a 瑚1 i i l gl 觚g u a g cd e s c i i p t i 耳i e c i f i 硎c x p l a i n c dp 重d d l l c e dd e f e c t ，t b ep e o p l et op _ o p o o n ck i n do fn e w 舳氐眦 d e v e l o p c d ，i 臼麟ct h o u g h tw 鹤岱忸b l i s h e san 岫b 盱s t i l d ym o d e l 幻t h c 掣蛳咖，s c ，i i d i e da n d 舯州d 嚣。辩啪b a s e d 伽北咄锄a 虹c s 盯t h c 南哪鳓加i i l i 印e c 狮c a t i o ne x p l a l l 觚 l 锄g u a g e ，d e l o p e dt h c r w a 砖f 哪t i o n 嘶t ht l l i sl a n 目l a g e 矧c td e f i p t i o n 柚d 矾l t a i 璀迥 衄c o d eb y 也e 锄l t l 咖a l i cp 乎铷m i n g 珥o 蚰gm o d c lw h i c hm i g h tc a 吖o i i t hs o f t w a 地 d e v e l o 舯嘛n ts y s i c mp e d i m n 锄l l i s t 0 1 s y s t e md e m 勰d 锄由s i s 柚d 印i 矗c a l i o n 唧i 锄a d o nc o l l n l 衙m l 砧h t t l i ss t a g ef o m sl b ep r o c e d l l 陀d c c l a 蒯d c 啊l m 伽【乜n o to i l l y 恤触撒抓l o ”a n d 姻呐t c r m so f 孤a g r e 咖吼a l i s t h c 嘲；i i l n i i l g w l l i c hs o f i 、j l ed e v e l 叩s 砸s t o p i c 蜘协k e t h c z s p o c 砸c 撕卸蛔埘如a l l ys v e s f o r 触雏a g o a l ，p p o s c d 既p r e s s 鼯l l 圮zs p e c i f i c a l i 麟p l 柚a t i d a 纽t y p el l l o u g h t 晰t l lt h es t li nd i 脑r 锄tv 璐s c l u n i 丘器t b ec + + l 锄g u a g el b et 锄p l 峨t h eh e a v y 枷t c d 呦l o g ya n d 也cs t l t c i i l p l a t c 咖r e h o u l o g a r i t h m c o r d i n gt ot h es m l c t l i a n dt h cg c n e r a la l 酬m mf 碱d a _ b l c 轴p p 积 矗m c 6 0 i l h 笛刚捌t h ec c 啪碟；p d i n gf i l n c 6 t e l n p l a 钯b yzs p e c i f i 谢o n 甑p l 锄d i n q u e ea n dm a pr e 撤ho 场t ，o l 埒r a t c d 璐i n gc + + 雒l dt h es t lt 。c h i l i c a ld e s i g n q u 肋c e 锄dm a p 勰k s 也e 痂艟n l l e 峨t ou 辨i ns t lt h ed e q u ev 豁lt oe x p r c s si nz s p e c i f i c a 6 0 ne x p l a n a t i s e q 啪c e ，t b en l a pv e 雠i 【p s s e di nzs p c c i f i c a t i e 】【p l 锄a l i p l 【a g e 辩q l l e n c c ) ，a n dh a st h et a r g e tp f o 孕锄，m 吩e l yt h ezs p 唁c m 洲姐“p l a n 砒i 岫s f b 咖觚i s 缸峙c + + c o d c 1 飞时耽i i l lw 讲k 啪sh 弱d e s i 罂托dn 砖z 印i f i c a l i c 】【p l 锄_ a l i o n 锄l t o m a t i c 缸m 盯，t h ei n t e r p 嘲l l a sd e f m e di nt h cz 叩i f i c a t i 锄e x p l a n a l i 鼯n 吐a lc h a r t e r 锄dl h es y m b o lt a b l e ，l l a s 删u c c dt h ec 咄鲫d i l l gm l c ，h 鹪r c a i i z e dt b c s e q u 蛐c ca n dt h ep l 【a g e 锄n o m a ：t i c a u y 雏k st h e 器s ；h 私p l 口血删t i 把zs p e c i f i c a l i c x p l 锄a t i o n c i 啪嚏cc 0 删f i m a l i w a y h a s 州d c dt h e 唧rp l n 踮i n gm e t l l o d ，觚d - 沈阳工业大学硕士学位论文 麟p l a i l 晦诵t he x 锄p l e st i l es p e c i f i c a t i o ne x p l 柚a t i o n m o d eo fw r i t i n g 鹞w e l l 够圮 化a i i z a t i o n f i l l a l l yh 勰p r o 讥d c dt l l ep i 口c e d u 肥e ) 【p e r i m e m a lr 髓l l l t n 圮zs p c c i f i 训o ns h o 删m a yp 猫sm m u g l lt l l ee n t i 心p f o c 鹤sw i l i c hs o f h v a 坞d c 、，e l o p s ， b u tc a nt i l 雠a p p l yi l l 血es o f h 张把p e f f b 加a n c et i i s t o r yt ot b e 出m a n da i l a l y s i ss b g e ，t h i st o p i c d i u 豁i o na l s oi sl 置l i ss t a i 昏e b e c a u a s i 【st l 蛇f i | ”弘o c e 鸽n o tt ol l t h em 锄t i a lo p 啪t i 呱 h 嬲a v o i d e dt h ea m f i c i a li i l i s o p e r a t i o nmt h ec a l c l l l a t i o nw m n g l yc a u s 嚣t o 髂ka m d 也c e s n c en o tt db ei n 删皓i g 嘲峨h 鹅毋m 阳n t e e dt h es y g t e mi i i l i f o r l i 哆锄d 也ei n t c 鲥t y s p e d 叩t h e 舯) c e d l 玳丘w i 睇卸劬僦龃d 血ei n t e l l o c t u a l i z e da d v 趾c e 删咀t k e yw o r d s ；zs p e c 塌c a t i o n ，l 酞，m a p ，a m t o m 叠l i s m 黜i f m e m 锯t i i i 独创性说明 本人郑重声明：所呈交的论文是我个人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得 沈阳工业大学或其他教育机构的学位或证书所使用过的材料。与我一同 工作的同志对本研究所做的任何贡献均已在论文中做了明确的说明并表 示了谢意。 关于论文使用授权的说明 加7 ，3 本人完全了解沈阳工业大学有关保留、使用学位论文的规定，即： 学校有权保留送交论文的复印件，允许论文被查阅和借阅；学校可以公 布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论 文。 ( 保密的论文在解密后应遵循此规定) 签名：名丽导师签名：里廖兰日期：翌2 ：! ：兰 沈阳工业大学硕士学位论文 1 绪论 1 1 课题研究背景 1 1 1 形式化方法 软件工程中的形式化方法是一种基于数学的软件开发方法，它可应用于软件工程的 各个阶段【1 1 用形式化方法开发软件可提高软件系统的正确性和可靠性，并可提高软件 开发效率，该方法日益受到计算机界和工业界的高度重视 形式化方法利用基于某些数学概念和符号的形式化语言来描述系统及其各组成部 分，产生系统形式化的规格说明，通过严格的数学推理揭示隐含的不一致性、不完整性， 从而尽早地发现设计中的错误和缺陷，并能够形式地验证能否满足规格说明，而非形式 化方法往往难以发现这些错误。 形式化方法在软件开发中能够起到的作用是多方面的【2 】。首先是对软件要求的描 述。软件要求的描述是软件开发的基础。比如说一般非形式化的描述很可能导致描述的 不明确和不一致。如果描述的不明确和不一致导致设计、编程的错误，将来的修改所要- 付出的代价就非常大了如果导致的错误没有被发现，则影响程序的可靠和使用。形式 化方法则要求描述的明确性，而描述的不一致性也就相对易于发现。其次是对软件设计 的描述。软件设计的描述和软件要求的描述一样重要。形式化方法的优点对于软件要求 的描述同样适用于软件设计的描述。另外由于有了软件要求的形式化描述，我们可以检 验软件的设计是否满足软件的要求。对于编程来讲，我们可以考虑自动代码生成。对于 些简单的系统，形式化的描述有可能直接转换成可执行程序，这就简化了软件开发过 程，节约了资源和减少了出错的可能性。另外，形式化方法可以用于程序的验证，以保 证程序的正确性。对于测试来讲，形式化方法可用于测试用例的自动生成，这可以节约 许多时间和在一定程度上保证测试用例的覆盖率。 软件形式规格说明的方法是形式方法最基本的部分，形式规格说明精确的描述了用 户的需求、软件系统的功能和各种性质，它描述的是“做什么”，而不考虑“怎么做”嘲。 z 规格说明中序列和包的自动求精研究与实现 1 1 2z 规格说明 形式化描述语言z 是以著名数学家z e 肋e l o 的名字命名的，它是目前使用最广泛的 一种形式化描述语言，在软件产业的一些大型项目中己经获得成功的应用【4 j 】。z 以一阶 谓词逻辑z f ( z e m e l o f r a e n k c l ，蔡梅罗一弗兰科尔) 公理集合论为主要数学基础。在 z 中有两种语言：数学语言和模式( s c h 锄) 语言。数学语言用来描述系统的各种特征： 对象及其之间的关系，并借助于构型来实现系统描述的结构化及复合化。它提供了一种 能推理的系统数学模型模型如图1 1 所示。 图1 1z 规格说明的模式 f i 晷1 1zs p c c i f i c a t i o ns c b c m a z 规格说明是通过实体s c h e r 眦和关系s c h c m a 共同来刻划状态空间的嘲。为了刻划 状态空间，在s c h 锄a 的描述部分列出了组成该空间的各个部件来描述空间的结构。谓 词部分以z 语言风格的谓词表达式给出状态的约束条件。 z 规格说明是一种半图形化的语言，它用来构造、组织形式化说明的描述、整理、 封装信息块并对其命名以便可以重用这些信息块闭。通常，形式化说明的可读性都不太 好，但由于z 采用半图形化的模式语言，能用一种比较直观、有条理的方式来表达形式 化说明，这就改善了可读性。 z 是一种形式规格说明。在规约说明中引入数学表示的优点是：它使规约说明精确、 严格和无歧义、便于进行推理。用z 语言书写的规约可以进行数学推理和证明，如果规 约中存在不正确性和不一致性，能及时发现、解决，并能确信它能满足系统功能需求【卅。 z 规格说明是一种以状态机为模型的形式规约语言，最早由法国人j r a m a l 提出， 由c a r h o a 嗄英国牛津大学) 领导的程序设计研究小组进一步发展而成。z 语言具有“状 态一操作”风格，利用集合、关系、函数、序列和包等数学概念，使用状态模式和操作 沈阳工业大学硕士学位论文 模式对目标系统的状态和行为进行说明，具有简明和精确的特点。它将规约与实现区别 开来。规约精确说明某软件片段应完成的功能，而不是刻画如何实现这些功能。写一个 形式规约与写一个计算机程序截然不同。形式规约是相应计算机程序所要完成任务的功 能描述。或者说是关于程序要做什么的陈述，而不是具体指明如何完成这些功能的规定。 z 规格说明在工业界和学术界得到了广泛的应用，被称为“软件工程语言” z 规格说明利用模式和模式演算对目标软件系统的结构和行为特征进行抽象描述。 其中状态模式对目标软件系统的结构特征进行抽象描述。操作模式对目标软件系统的行 为特征进行抽象描述一个操作模式可能涉及多个状态模式，并能够通过改变状态的方 法定义操作，因此可以使用z 规格说明来说明一个面向对象的系统。z 规格说明是基于 对象的一种方法，而不是面向对象的。它不支持类的继承、对象的封装。它排除了自然 语言或图形符号必须被读者解释时而经常产生的多义性。但是，z 语言主要关注于功能 和数据。而问题的时序、控制和行为等方而却更难于表示。 1 2 国内外研究现状 在国外，z 规格说明的研究已深入开展了许多年，它的研究队伍也不断地扩大，如 欧美，日本等国都有专门的相关研究人员。人们还把z 和结构化的分析方法、面向对象 的方法和程序变换等课题结合起来研究。关于z 的研究成果交流的“zu s 盯m e e t 啦” 每两年一届，并已成为一个重要的国际学术会议在每年的i e e e 有关软件工程的学术 会议上，也有不少关于z 研究成果的报道，如英国牛津大学设计的z 规格说明支持工具 c a d i z 能够对z 规格说明进行语法检查及类型检查，并支持排版，还能够与用户进行交 互地查看z 规格说明中的某些特性；美国芝加哥d c p a i l i 大学研制的类型检查工具z r c ， 它可以接受l 观z c d 格式和z s l 格式的规格说明；i n 哪研制的z e d b l 是能支 持包括模式修饰、模式复合、隐藏、求前置条件等z 规格说明模式运算的工具等等。 在国内，形式方法和规格说明语言一z 语言的关注也越来越多，如上海大学的缪淮扣 教授就著有很多关于z 语言的书籍和文献，国内很多其他学者也对形式方法和z 语言有很 多有意义的研究，并且将其运用于很多领域，如网络协议，系统建模等等方面，如缪淮扣 等人的t c p 协议的z 语言描述；上海交通大学韦银星等人的i n m ，类图的形式化及 分析。沈阳工业大学的王宏生老师及其学生对z 语言研究已完成的工作有： z 规格说明中序列和包的自动求精研究与实现 ( 1 ) 通过约束z 规格说明中计算机不能实现或不易实现部分，设计出z 规格说明的一 个子集s m a r t z ，并以标准c 抖和s t l 为工具，运用编译技术实现了s m a n z 规格说明中一 阶逻辑算子自动求精。使用编译技术实现s m a n z 的语法分析、语义分析及向目标代码的 转换，并且验证了z 语言经过适当的约束后，一阶逻辑算子的自动求精是可以实现的【9 】。 ( 2 ) 研究了z 规格说明的数据类型以及各类型之间的关系；以z 的自动求精为目的， 提出了用s t l 中的不同容器表示z 规格说明各数据类型的思想；利用c + + 及s t l 技术 设计了z 中集合、关系、包、序列等数据类型的求精规则；结合c + + 语言的模板、重载 技术和s t l 模板库对数据结构和通用算法的强大支持功能，为集合论中各操作算子到 c + + 代码自动求精提供了相应的函数模板，制定了集合论各算子的求精规则【设计了 自动求精处理过程的符号表；对于z 规格说明进行了词法分析；对于修改后的s m a r tz 设计语法规则并采用自顶向下方法进行了语法分析；语义分析阶段主要处理静态语义检 查及更新符号表的信息；集合论算子的求精规则可以产生目标程序，即c + + 程序代码。 ( 3 ) 实现了对z 规格说明编辑的可视化，对集合和谓词的操作设计窗口界面，采用 s i n i 图形式来对词法分析程序进行设计，对于录入的有关集合和谓词的z 规格说明，实 现了软件自动求精的过程。关于幂集的研究：对于单层的集合，可以用数组表示。面对 于多层的，考虑用数据结构和数组相结合来构造。在对其实现的过程中，针对其中集合 类型的不同要给予动态的分配，并且针对z 规格说明中的算子一一笛卡儿积的实现方法 进行深入研究。 经过3 0 多年的研究和应用，如今人们在形式化方法这一领域取得了大量、重要的成 果，从早期最简单的形式化方法一阶谓词演算方法到现在的应用于不同领域、不同 阶段的基于逻辑、状态机、网络、进程代数、代数等众多形式化方法【l “。形式化方法的 发展趋势是逐渐融入软件开发过程的各个阶段，从需求分析、功能描述( 规约) 、体系结 构、算法设计、编程、测试直至维护。 1 3 课题意义 1 3 1 采用z 规格说明的必要性 z 规格说明是为了克服自然语言和程序设计语言描述规格说明产生的缺陷而提出 的一种新的软件开发范型，其基本思想是对系统建立一个数学模型，研究和提供一种基 沈阳工业大学硕士学位论文 于数学的或形式语义学的规格说明语言，用这种语言严格地描述所开发的软件功能，并 由自动程序设计的加工模型来得到可执行的代码【协1 4 1 z 是目前最为流行的一种形式化规格说明语言，其不足之处是缺乏表达大型系统规 格说明的必要机制，另外由于z 并不直接支持系统实现，迄今为止，z 仍然是一种不可 运行的强类型的规格说明语言，尽管在z 的执行方面，人们已经做了不少研究工作，但 目前仍缺乏可用的z 规格说明编译工具，因而目前还不能直接从z 规格说明自动生成应 用程序，求精过程主要靠人工完成。 本文研究从序列和包的软件规格说明到可执行程序求精过程中的自动化技术，给出 了采用自动化技术进行操作求精的一般步骤。 1 3 2 自动求精的可行性分析 z 中的数据类型分为基本类型和复合类型两大类，复合类型又分为集合类型、笛卡。 尔乘积类型，模式类型三种。z 中的基本类型不再有内部结构，求精时有的可直接成为 程序设计语言中的数据类型( 如整型) ，其余的可与具体数据类型具有简单的对应关系 ( 如字符串类型等) 【坝。 z 规格说明与计算机的软硬件模型有相当好的匹配性，使它逐步求精成为可甜瑚 将z 规格说明转化成为c + + 语言的源程序，这样就可以间接地将规格说明转化为可执行 代码。本课题中研究的z 规格说明的自动求精的目标是c + + 源程序，c + + 源程序的逻辑层 次要比编译程序中的中间语言还要高很多1 ”叼。这样，z 规格说明的自动求精有些象自 动化程序设计 从不能直接执行的程序一即规格说明( 由抽象的描述语句构成) 转换到可以直接执 行的程序一即为程序代码( 由可执行的命令语句构成，如赋值语句、选择择语句、循环 语句等) ，它们之间的系列程序称之为混合程序，既含有抽象的描述语句，又含有可执 行的命令语句 从z 规格说明中推演出程序代码，需要做两方面的工作： ( 1 ) 用c + + s t l 语言中的数据结构来表现规格说明中的数学概念所描述的数学对象。 ( 2 ) 用c + + s t l 语言的算法来表示z 规格说明中所描述的操作行为。 z 规格说明中序列和包的自动求精研究与实现 2z 规格说明的预处理 2 1 扫描器 扫描器的设计可以基于一遍扫描完成也可以基于多遍扫描完成。对于一遍扫描的扫 描器，程序本身紧凑，编译速度快；对于多遍扫描的编译器，它的功能块清晰，占用内 存少( 因为各趟扫描可以重叠使用内存) 。这是它们各自的优点“9 】。 本文讨论的源程序需要经过两次扫描，就是进行词法分析、语法分析及静态语义检 查，并对相应的符号表进行添加或查询操作若遇见错误，提供相应出错信息并继续扫 描。先期的工作是按照编译器的结构来设计的，即要先分析词法、语法、语义刚。 扫描器的工作是： ( 1 ) 遇到单字符的专用符号，直接返回记号属性，存入t x t 文本文件中； ( 2 ) 遇到两个字符的专用符号的首字符，进入中间状态，根据第二个字符来确定它 的属性： ( 3 ) 遇到数字，继续读取，直到遇见的下一字符不是数字，把当前数字存入文本文 档中； ( 4 ) 遇到字母，继续读取，直到遇见的字符不是字母也不是数字，把当前字符串按 规则转换成自然数保存在中间文档中，并且调用函数检查该字符串是否为系统保留字， 如果是，则返回该保留字相应的代号，如果不是，则按顺序输出大于2 0 0 的数字保存在 中问文档中； ( 5 ) 遇到空格或者t a b 键直接跳过。 扫描工作的重点是： ( 1 ) z 中的操作符的识别。 ( 2 ) z 中的中文字符的识别。 2 1 1 字符表 字符表是指键盘的所有可输入字符，包括： 大小写字母：气，z ，a ，z ； 数字：0 ，9 ； 6 沈阳工业大学硕士学位论文 标点和其它符号：， ，? ，! ，；，：，( ，) ，【，】， ， ，+ ，一，+ ，、i ，& ，群， 。 2 1 2 单词表 单词表包括：关键字、标识符、整数、运算符、关系符、通用符、函数符、修饰符 和分隔符等 ( 1 ) 关键字 。 关键字yw i 谢s ) ，也称保留字 s 盯v c dw 玳坳。它们是由英文字母连接而成的用 于特殊用途的指定字串 关键字依据各自功能可分为以下几类： 用于标识语法结构的关键字，如：s p e c m c a t i o n ，戤i o m ，h 锄a ，w l 姗，e n d ； 前缀通用符，如：p ； 逻辑常量，如：t r i 峨蹦； 关系符，如：i n ，蛾s u hs l l b c q ； 连接词，如：锄d ； 所有z 中的保留字有：“s p i f i c a t i o n ”，”蕊o m ”，”h e 眦”，”w h e 埔。，”e 耐”，”z “，“r ，n ”， ”l c t ”，“仇圮”，”蜘”，“触1 1 ”，”麟i s t ”，”n o t ”，”s u b ”，”吼航q ”，”i n ”，”邶瞳i n ”，”t s u b “，“瑚t 蛐b e q ”， ”d o m ”，”瑚”，”p ”，”c 伽n t ”，”f ，”n ”，”i d ”，“s e q ”，”s c q l ”，”i s c q ”，b a g “，”h e a d “，“t a i l ”，”舶n t ! ”l a s t “，”d c l t a ”，”删”，一j u d g e ”，“p e r s o n ”，“p h o n e ”，”r c v ”，”嘲”，”s i f t ”，”s q 哪h ”，”p a r ”， ”c x t 扩，”i t e m s ”，”s c t ” ( 2 ) 标识符 除关键字外，符合下面正则表达式的字串称为标识符。 【a 办z 】【a z a z o 9 】 即z 的标识符必须以英文字母开头，剩余部分为字母或数字任意组合的序列。 对于关键字，处理方法是：建立一张关键字表。 所以此表设计成线性表不会浪费很多查找时间。先识别出一个标识符，然后查关键 字表，如果查找到，说明是关键字，则返回关键字内部符号，否则作为普通标识符处理。 为了区别不同的标识符，我们建立一个存放名字的标识符表。它的数据结构是一个数组， 不同的标识符在表中有不同的标号，我们就以相应的标号来代替相应的标识符。 z 规格说明中序列和包的自动求精研究与实现 图2 1 是处理关键字和标识符的流程图。 图2 1 关键字和标识符处理流程图 f i 晷2 1f l o wc h a nk e yw o r da i i di d 黼盯 ( 3 ) 整数 用正则表达式定义为：【o 9 】【o 9 】 ( 4 ) 运算符 z 的运算符分为算术运算符和集合运算符。 算术运算符有：+ ，- ，； 集合运算符有：m & ，、； z 中所有运算符：” ”，”v ”，”、”，”? ”，”，叩“，” ”，” ”，”) ”，”，”，”( ”，”( | ”) ”，”，“+ ”，”一， ，”，”| ，”p ”，”n 哆”，” = ”，”，” i ”， ”， ”+ ”，”+ + ”，”一”，”= ”，”； ”，” + ”，” ”，”，” ”，。 ”，” + + y ，。& ”， ”斗斗”，”& & ”，”：”，”；”，”【”，”】”，”- ”，”群”，” “，”( + ) ”，” ， - ， ，卅 ，抖 ； ( 7 ) 修饰符 修饰符有三种：! ，? ； “! ”表示变量输出，“? ”表示变量输入，“”表示变量的后状态。 ( 8 ) 其它符号 ，) ，( ，) ，l1 ，；，& ， ，v ， 2 1 3 公理描述 在z 规格说明中，用户的集合可用基本类型定义，系统中有了n 个连续的编了号的 存储块，而系统中所有自由存储块的结合以b 来表示，显然这两个变量将在整个规格说 明中起作用，并且希望是全局变量。对它们进行声明： 、 n ：n b ：p n 并且给一个限制：b = 1 n ，为了解决此类问题，公理描述引入一个或多个全程变量和关 于它们的谓词。一个公理描述的形式如图2 2 所示。 其中左图为公理描述的形式，右图为自由存储块b 的公理描述 z 规格说明中序列和包的自动求精研究与实现 图2 2 公理描述 f 培2 2a x i o mb e w r i t e 2 1 4 对表达式的处理 对于输入记号流，扫描器的词法工作主要有以下几步： ( 1 ) 先把词法模式从正则表达式形式转换成非确定有限自动机； ( 2 ) 然后把非确定有限自动机转换成确定有限自动机； ( 3 ) 再根据确定有限自动机生成转换表； ( 4 ) 在词法分析时，用确定有限自动机模拟器读取输入流中的字符，根据转换表进 行模式匹配，返回对应的模式标识并执行相应的动作。 此方法结合确定有限自动机状态化简算法和转换表压缩技术，具有较好的时间和空 间效率。 对表达式的处理过程为：对综合表达式进行自左向右扫描，每识别出一个数学表达 式时，将其提取出来，原字符串保持不变，扫描器继续识别下一个。对每一个识别出来 的数学表达式进行合法性检查，如检查有误，则出现出错信息，表明表达式句法错，需 重新输入；如检查无误，则利用数学解释器对其进行计算，计算结果作为逻辑表达式的 一个词法单元，进入为生成逻辑表达式的后缀式而设立的运算对象栈，与此同时，生成 一个形式上的逻辑字符串。 扫描输入的字符串函数如下： c h 盯g e t c h 哟 c h 盯c h - g e t c ( n ) ； i f 【c h 一、i l ) r o w = 1 ： 沈阳工业大学硕士学位论文 l j 玳+ + - e i s e i f 【c h f & & c h ! = d r 0 、妒卜卜： 把加m ( c 蛾 2 2 解释器 为了让一种语言投入使用，我们需要一个语言翻译器把这种语言的程序翻译成计算 机能够执行的表示形式或者直接执行这个程序【2 1 】。 对任何一种程序设计语言p l ，可以定义一种抽象机，p l 的运算、数据结构和控制 结构是这种机器的存储元素和指令在这样的机器上执行用p l 写的算法称为解释通 常，这种抽象机是用软件实现的，即程序设计语言和机器语言之间的差距用软件来填补， 这样的软件叫做解释器。 为了便于解释器的设计和实现，需建立若干用于词法分析、语法分析的数组、结构 等数据结构。同时，需构造识别数学表达式和识别逻辑表达式的有限状态自动机和相应 的状态图，作为词法分析的一种辅助手段，以便识别合法的数学和逻辑表达式。 2 2 1 解释器的设计思想 使用解释器的优点是：关于语言的问题可以通过实验来回答( 如同物理化学一样) 它的缺点是，关于程序行为的问题无法事先回答，我们必须执行程序才能发现它到底做 了什么另一个缺点是，解释器的缺陷和机器依赖性会在不经意间成为语言语义的一部 分并且解释器可能不具有针对所有机器的通用性 解释器设计的分三遍完成：第一遍用于词法分析和语法分析；第二遍用于语义分析 和中间代码生成；第三遍用于目标代码生成和结果执行。 这样程序整体设计结构清晰，便于实现优化措施，目标代码质量高。 一个解释器涉及三种语言： ( 1 ) 源语言一也就是所说的z 规格说明。 ( 2 ) 中间语言一中间过程产生的代码。 z 规格说明中序列和包的自动求精研究与实现 ：。( 3 ) 目标语言一在这里是指可执行的c + + 语言。 2 2 2 解释器的实现过程 首先利用识别表达式的有限状态自动机对输入串进行识别。如发现不合法的串，则 返回错误信息：如字符串符合词法，即进入自动机接受状态。当表明该串为合法数学表 达式，则进行下一步词法分析阶段，对字符串进行从左至右的扫描，识别出各种独立的 词法单位；如“+ ”、“一”，并且以代码形式返回，以便进行语法分析。 解释器的输入是z 规格说明，输出是c + + 程序。输出的c + + 程序应该是某个c * 编译器可正确编译的程序 解释器所要做的工作是： 第一阶段，解释器接受输入的源代码，经过词法、语法和语义分析等得到源程序的 某种中间表示方式，在这里我们采用的是一个自然数文档。 第二阶段，解释器的后端将前端处理生成的中间表示方式进行操作，并最终生成在 机器上可运行的c + + 代码。 为此我们需要不断收集、记录和使用源程序中一些语法符号的类型、特征和属性。 每遇到一个名字声明，就以此名字查符号表：若表中无此登记项，则将该名字填入表中； 若该表中已有此登记项，则说明该名字是重复声明，报告出错。 由于研究尚处于初级阶段，因此根据所要实现功能的需要，对符号表的设计也是从 简单入手。但是，要留出适当的扩充空阔，以便对日后功能的扩充提供方便。 定义形式如下的结构体： s t n l c ti n d c c h 盯蝴e 【2 1 】； c h 盯t y p e 【2 1 】； i ma d d r ： ) i n d e m 【1 0 0 0 】； 其中i n d c n t 【1 0 0 0 】代表可以存放l 0 0 0 个标识符的“表”；n a m e 【2 l 】代表标识符的名 字，标识符的长度限制为不超过2 1 个字符：t y p e 2 l 】存放的是该标识符的数据类型；而 沈阳工业大学硕士学位论文 a d d r 存放的是一个特定的整数，该整数表示的是标识符在自动转换阶段的信息，在转换 代码时将会应用同时，再定义一个整型变量l e n t h ，用来记录符号表的实际长度，初 值设置为o ，当有一个新的标识符插入的时候，i 棚t h 也相应的加1 一旦l 肋t l i 的值超 过已定义的长度即l o o o ，表明标识符的数量超过了已经分配值的上限，则需要另外再 申请，以满足标识符的需求；在不超过己分配的空间的时候，则对符号表所进行的操作 就可以以l 棚曲为基准，这样可以减少查询循环的次数，节省系统的工作量+ z 规格说明中序列和包的自动求精研究与实现 3 自动求精 3 1 求精的概念 所谓软件求精是指：整个软件开发过程可以看成从规格说明出发，经过一系列步骤 每一个步都增加一些可执行性，或提高执行效率，最终达到可以直接由计算机执行的程 序代码。这种开发过程可以形成以下程序序列： 规格说明混合程序l 混合程序2 混合程序n 程序代码 基于软件求精的软件开发过程的目标是从不可执行的形式规格说明开发逐步精化， 最终得到可以直接指导计算机执行的程序代码，这个过程实际上就是上述从左到右的过 程圈。 其框图如图3 1 所示： = ) 可扩展特征口不可扩展特征 图3 1 求精过程 f i g 3 1r e f i n 即d e mc o u r 3 2s t l 简介 3 2 1 概述 s t l ( s t a l l d a r dt 锄p l a c cl i b 删，即标准模板库，是一个具有工业强度的，高效的 c + + 程序库。从根本上说s t l 就是一些“容器”的集合，这些容器有l i s t 、v 衄、s c t 、 沈阳工业大学硕士学位论文 m a p 等网。它被容纳于c + + 标准程序库( c + + s t a l l d a i dl i b 捌叻中，是a n s 们s oc h 标准 中最新的也是极具革命性的一部分。该库包含了诸多在计算机科学领域里所常用的基本 数据结构和基本算法为广大c 卜 程序员们提供了一个可扩展的应用框架，高度体现了 软件的可复用性。这种现象有些类似于m i c r o f iv i s u a lc + + 中的m f c ( m i c r o s o f t f o m 枷o nc l 嘲l 嘞，或者是b o d 锄dc + + 酗i d 髓中的v c l ( v i 吼l a lc o m p o n 饥t l i b 埘叻 从逻辑层次来看，在s t l 中体现了泛型化程序设计的思想( g e r i cp 鲈u m l i l l g ) ， 引入了诸多新的名词，比如像需求u i 撒n e m s ) ，概念( o c 印1 ) ，模型( m o d c l ) ，容器 ( a ) n 1 删，算法( a l g o r i n l m n ) ，迭代器( i t 删等。与0 0 p ( o 巧e c t 捌e m c dp m 乒锄m i n g ) 中的多态o l y m o 叫s n l ) 一样，泛型也是一种软件的复用技术。 从实现层次看，整个s t l 是以一种类型参数化( 哆p ep a 删n 鼬e r i 抬d ) 的方式实现的， 这种方式基于一个在早先c 抖标准中没有出现的语言特性模板( 妇n p l a 妫。s t l 是最新 的c + + 标准函数库中的一个子集，这个庞大的子集占据了整个库的大约8 0 的分量。而 作为在实现s t l 过程中扮演关键角色的模板则充斥了几乎整个c h 标准函数库。在这 里，我们有必要看一看a 斗标准函数库里包含了哪些内容，其中又有哪些是属于标准模 板库( 即s t l ) 的 r” c h 标准函数库为c h 程序员们提供了一个可扩展的基础性框架。我们从中可以获 得极大的便利，同时也可以通过继承现有类，自己编制符合接口规范的容器、算法、迭 代器等方式对之进行扩展。 3 2 2 容器( c o n t a i 鹏r s ) 在实际的开发过程中，数据结构本身的重要性不会逊于操作于数据结构的算法的重 要性，当程序中存在着对时间要求很高的部分时，数据结构的选择就显得更加重要。 经典的数据结构数量有限，但是我们常常重复着一些为了实现向量、链表等结构而 编写的代码，这些代码都十分相似，只是为了适应不同数据的变化而在细节上有所出入 s 孔容器就为我们提供了这样的方便，它允许我们重复利用已有的实现构造自己的特定 类型下的数据结构，通过设置一些模版类，s t l 容器对最常用的数据结构提供了支持， 这些模板的参数允许指定容器中元素的数据类型，可以将许多重复而乏味的工作简化。 z 规格说明中序歹棚包的自动求精研究与实现 容器部分主要由头文件铡o f ， ， 组 成。对于常用的一些容器和容器适配器( 可以看作由其它容器实现的容器) ，可以通过 表3 1 总结了容器和相应头文件的对应关系。 表3 1s t l 中容器的主要构成 t a b 3 1c e n n _ a ls t c t u r eo f s t lc o m a i n 盯 3 2 3 算法( a i 和r i t h i i i s ) s t l 的一个重要组成部分，包含了大约7 0 个通用算法，用于操控各种容器，同时 也可以操控内建数组。所有这些操作都是在保证执行效率的前提下进行的。 算法部分主要由头文件 ，n l 蚴e r i c 和 组成。 是 所有s t l 头文件中最大的一个，它是由一大堆模版函数组成的，可以认为每个函数在很 大程度上都是独立的，其中常用到的功能范围涉及到比较、交换、查找、遍历操作、复 制、修改、移除、反转、排序、合并等等。 体积很小，只包括几个在序列上 面进行简单数学运算的模板函数，包括加法和乘法在序列上的一些操作。娟m c t i o 沈阳工业大学硕士学位论文 中则定义了一些模板类，用以声明函数对象。比如：矗n d 用于在容器中查找等于某个特 定值的元素，f o re h 用于将某个函数应用到容器中的各个元素上，r t 用于对容器中 的元素捧序。 3 2 4 迭代器( i t e r a t o r s ) 如果没有迭代器的撮合，容器和算法便无法结合的如此完美。事实上，每个容器都 有自己的迭代器，只有容器自己才知道如何访问自己的元素。它有点像指针，算法通过 迭代器来定位和操控容器中的元素。 例如：h p i i t i 衄劬d 体提供对数据的只读访问。 o i 印mn e 嘲d 格提供对数据的只写访问 f 凹悯r di t c r a l o 培提供读写操作，并能向前推进迭代器。 b i d 硫c t i o n a li t e r 呶瞄提供读写操作，并能向前和向后操作。 r 肌d o ma c c e 鹞i t c l 劬璐提供读写操作，并能在数据中随机移动。 3 2 5 其他组件 ( 1 ) c 标准函数库，在c + + 标准库中存在两套c 的函数库，一套是带有h 扩展名的 ( 比如 ) ，而另一套则没有( 比如q s t d i 0 ) ( 2 ) 语言支持( 1 如g g cs u p p o n ) 部分，包含了一些标准类型的定义以及其他特性的 定义，这些内容，被用于标准库的其他地方或是具体的应用程序中。 ( 3 ) 诊断( d i a g n o s t i c s ) 部分，提供了用于程序诊断和报错的功能，包含了异常处理 ( 瓴c e 硼h 锄d l i n g ) ，断言n i 伽回，错误代码( 盯州。n 啪b 盯c o d e s ) 三种方式 ( 4 ) 通用工具( g e n 啪lm i l i t i 哟部分，这部分内容为c + + 标准库的其他部分提供支 持，当然你也可以在自己的程序中调用相应功能比如：动态内存管理工具，日期时间 处理工具。记住，这里的内容也已经被泛化了( 即采用了模板机制) ( 5 ) 字符串( s 廿i l l g ) 部分，用来代表和处理文本。它提供了足够丰富的功能。事实上， 文本是一个s n i l l g 对象，它可以被看作是一个字符序列。s t r i n g 可以被转换成c h