（计算机软件与理论专业论文）正规表达式到最简dfa的并行相关算法研究.pdf

摘要 计算机技术日益发展的今天，尽管目前单个c p u 的性能已经达到相当高的水平，但 就一些超大规模计算或一些必须实时完成的多媒体运算而言，如果不利用并行计算技术 是很难满足用户需求的。如何获得更高的速度和峰值已成为我们所追求的方向，并行技 术能够将原本串行( 线性) 处理的工作改成并行( 多维) 处理，不仅节省了使用的时间，并 且减少了所用的存储空间。并行程序设计和并行编译技术是提高实际运行速度的关键。 因此，并行优化编译技术已成为当代计算机软件的重要研究课题之一。 为正规表达式建立最小的确定性有限自动机( d f a ) 是编译系统的关键技术，高性 能计算和并行处理是当前提高计算机性能的主要手段。因此，正规表达式到d f a 的并行 转换是并行编译研究领域的重要分支。本课题主要研究其并行转换技术和其相关算法， 对并行编译理论研究和算法设计有其理论和实践意义。 构造正规表达式的最简d f a 需要三个步骤：构造正规表达式的非确定性有限自动机 ( n f a ) ，非确定性有限自动机的确定化以及有限自动机的最小化。在构造正规表达式的 非确定性有限自动机的时候，给出三种非确定的有限自动机即：t h o m p s o n 自动机、 g l u s h k o v 自动机和f o ll o w 自动机，它们的规模逐渐减小。本文详细地介绍构造正规表达 式的f o l l o w 自动机的并行算法。在非确定性有限自动机确定化的时候，基于g l u s h k o v 自动机利于并行计算的特点，用状态关系表实现有限自动机的确定化。最后，本文利用 粗糙集的知识划分理论，从一个新的角度，实现有限自动机的最小化 关键词：有限自动机，正则表达式，等价关系，知识划分 a b s t r a c t e v e ni ft h ep e r f o r m a n c eo fas i n g l ec p u ( c e n t r a lp r o c e s s i n gu n i t ) h a sr e a c h e dah i 曲l e v e lw i t ht h e d e v e l o p m e n to fc o m p u t e rt e c h n o l o g yi nt h o s ed a y s ，i ti sh a r d l yt om e e tt h eu s e rr e q u i r e m e n tf o rv e r y l a r g e s c a l ea n dr e a l - t i m em u l t i m e d i ap r o c e s s i n gi fw eh a sn o tp a r a l l e lt e c h n o l o g y h o wt oa c h i e v et h e h i g h e rc o m p u t a t i o n s p e e dh a s b e e na l l i n c r e a s i n g r e s e a r c hd i r e c t i o n f o r p a r a l l e lt e c h n o l o g y , i t s i m u l t a n e o u s l yu s e sm o r et h a no n ec p u o rp r o c e s s o rc o r et oe x e c u t eap r o g r a mo rm u l t i p l ec o m p u t a t i o n a l t h r e a d s t h a ti st os a y , i tc a np r o c e s sm a n yp a r t so fas e r i a lt a s ks i m u l t a n e o u s l y , a n dt h i sc a ni m p r o v et h e p r o c e s s i n gs p e e da n ds a v et h em e m o r yo ft h ec o m p u t e r t h ed e s i g no fp a r a l l e lp r o c e d u r ea n dt h e t e c h n o l o g yo fp a r a l l e lc o m p i l ea r et h ek e yp r o b l e mo fi m p r o v i n gt h er u n n i n gs p e e df o ras y s t e m s o ，t h e t e c h n o l o g yo fp a r a l l e lc o m p i l eh a sb e e nar e s e a r c hf o c u si ns o f t w a r ef i e l d s c o n s t r u c t i n gt h es i m p l e s td f a ( d e t e r m i n i s t i cf i n i t ea u t o m a t o n ) f o rr e g u l a re x p r e s s i o ni s ak e y t e c h n o l o g yf o rc o m p i l i n gs y s t e m ，a n dt h ep e r f o r m a n c eo ft h ew h o l es y s t e mi sd e p e n d e n to ni t ss p e e d i n o r d e rt oi m p r o v ei t ss p e e d ，h i 曲一p e r f o r m a n c ec o m p u t a t i o na n dp a r a l l e lt e c h n o l o g ya r et h em a i nm e a n sa t p r e s e n t i nt h i st h e s i s ，i tm a i n l yr e s e a r c ho nt h ep a r a l l e li m p l e m e n t a t i o no ft r a n s l a t i n gr e g u l a re x p r e s s i o n i n t os i m p l e s td f aa n di t sr e l a t e da l g o r i t h m ，a n di th a st h e o r e t i c a la n dp r a c t i c a ls i g n i f i c a n c ef o rt h e r e s e a r c ho nc o m p i l i n gt h e o r ya n dt h ed e s i g no fc o m p l i e ra l g o r i t h m c o n s t r u c t i n gt h es i m p l e s td f a ( d e t e r m i n i s t i cf i n i t ea u t o m a t o n ) f o rr e g u l a re x p r e s s i o nn e e d st h r e e s t e p s ：c o n s t r u c t i n gn f a ( n o n d e t e r m i n i s t i cf i n i t ea u t o m a t o n ) f o rr e g u l a re x p r e s s i o n ；n o n d e t e r m i n i s t i cf i n i t e a u t o m a t o nd e t e r m i n e da n dm i n i m i z i n gf i n i t ea u t o m a t i o n w h e nc o n s t r u c t i n gt h en o n d e t e r m i n i s t i cf i n i t e a u t o m a t ao fr e g u l a re x p r e s s i o n s ，t h r e en o n d e t e r m i n i s t i ef i n i t ea u t o m a t aa r eg i v e n ：t h o m p s o na u t o m a t a , g l u s h k o va n df o l l o wa u t o m a t a , a n dt h e i rs t a t e sg e ts m a l l e ra n ds m a l l e r t h i st h e s i sp r o p o s e sap a r a l l e l a l g o r i t h m o f c o n s t r u c t i n g f o l l o wa u t o m a t i o no fr e g u l a r e x p r e s s i o n w h e nd e t e r m i n i n g t h e n o n d e t e r m i n i s t i cf i n i t ea u t o m a t o n ，t h es t a t er e l a t i o nt a b l ei su s e da sd e t e r m i n i n gf i n i t ea u t o m a t o nb a s e do n g l u s h k o va u t o m a t ai sg o o df o rp a r a l l e lc o m p u t a t i o n i nt h ee n d ，an o v e ls c h e m eo fm i n i m i z i n gf i n i t e a u t o m a t i o ni sr e a l i z e du s i n gt h ek n o w l e d g ed i v i s i o nt h e o r yi nr o u g hs e t sf r o man e wp o i n to fv i e w i i i k e yw o r d s ：f i n i t ea u t o m a t o n ，r e g u l a re x p r e s s i o n s ，e q u i v a l e n c er e l a t i o n ，k n o w l e d g ed i v i s i o n i v 独创性声明和关于论文使用授权的说明 独创性声明 本人郑重声明：所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的 研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表或撰写的研究成果，也不包含为获得河南师范大学或其他教育机构的学位或证书 所使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示了谢意。 签名社址日期业 关于论文使用授权的说明 本人完全了解河南师范大学有关保留、使用学位论文的规定，即：有权保留并向国 家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权河南师 范大学可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩 印或扫描等复制手段保存、汇编学位论文。( 保密的学位论文在解密后适用本授权书) 5 7 第一章绪论 1 1 研究背景与发展现状 1 1 1 编译技术及其发展 第一章绪论 使用过现代计算机的入都知道，多数用户是应用高级语言来实现他们所需要的计算 的。现代计算机系统一般都含有不止一个的高级语言编译程序，对有些高级语言甚至配 置了几个不同性能的编译程序，供用户按不同需要进行选择。高级语言编译程序是计算 机系统软件最重要的组成部分之一，也是用户最直接关心的工具之一1 。 程序设计语言可分为低级语言和高级语言两大类，目前普遍使用的程序设计语言是 高级语言。然而，计算机硬件只懂自己的指令系统，即它只能直接执行用相应机器语言 编写的代码程序，而不能直接执行用高级语言编写的程序。因此，要在计算机上执行除 机器语言之外的任一程序设计语言，就必须有这样一个程序，它把用高级语言编写的程 序转换成等价的机器语言程序，我们把这种程序称为编译程序( 也称作编译器) 1 。即编 译程序的输入对象为源程序，输出对象为目标程序。且在这个转换过程中，编译器将源 程序中出现的错误报告给用户。 在计算机上执行一个高级语言程序一般分为两步：第一步，用一个编译程序把高级 语言翻译成机器语言程序；第二步，运行所得的机器语言程序求得结果。通常所说的翻 译程序是指这样的一个程序，它能够把某一种语言程序( 称为源语言程序) 转换成另一 种语言程序( 称为目标语言程序) ，而后者和前者在逻辑上是等价的。如果源语言是诸 如f o r t r a n 、p a s c a lc ，a d a ，s m a l l t a l k 或j a v a 这样的“高级语言 ，而目标程序是诸如 汇编语言或机器语言之类的“低级语言”，这样的一个翻译程序就称为编译程序。 根据不同的用途和侧重，编译程序还可进一步分类。专门用于帮助程序开发和调试 的编译程序称为诊断编译程序，着重于提高目标代码效率的编译程序叫优化编译程序。 现代很多编译程序同时提供了调试，优化等多种功能，用户可以通过“开关”进行选择。 运行编译程序的计算机称宿主机，运行编译程序所产生的目标代码的计算机称为目标 机。如果一个编译程序产生不同于其宿主机的机器代码，则称它为交叉编译程序。世界 上第一个编译程序一f o r t r a n 编译程序是2 0 世纪5 0 年代中期研制成功的。经过5 0 年的 正规表达式到最简d f a 的并行相关算法研究 努力，编译理论与技术得到迅速发展，现在已形成了一套比较成熟的、系统化的理论与 方法，并且开发出了一些好的编译程序的实现语言、环境与工具。在此基础上设计并实 现一个编译程序不再是高不可攀的事情。 在计算机软件科学中，编译是较早在实践上和理论上同时取得巨大发展的一个分 支。世界上第一个编译程序，早在2 0 世纪5 0 年代中期就己问世，多数早期的编译工作是 将算术公式翻译成机器代码。用现在的标准来衡量，当时的编译程序能完成的工作十分 初步，然而它们为高级语言编译系统的研究和开发莫定了基础。2 0 世纪5 0 年代中期出现 了f o r t r a n 等一批高级语言，相应的一批编译系统开发成功。随着编译技术的发展和社 会对编译程序需求的不断增长，2 0 世纪5 0 年代末有人开始研究编译程序的自动生成工 具，提出并研制编译程序的编译程序。它的功能是以任一语言的词法规则、语法规则和 语义解释出发，自动产生该语言的编译程序。目前很多自动生成工具己广泛使用，如词 法分析程序的生成系统：l e x ，语法分析程序的生成系统y a c c 等。2 0 世纪6 0 年代起，不断 有人使用自展技术来构造编译程序。自展的主要特征是用被编译的语言来书写该语言自 身的编译程序1 9 7 1 年，p a s c a l 的编译程序用自展技术生成后，其影响就越来越大。经 过近半个世纪的努力，编译理论和技术伴随着计算机技术的发展而迅速完备化和系统 化，形成了一个完整的理论体系，并且开发出了丰富的编译程序的实现语言、实现环境 和开发工具。在此基础上，设计并实现一个编译程序不再是高不可攀的事情伴随并行 计算机的出现，并行c 、并行c + + 、并行f o r t r a n 或高性能f o r t r a n ( h p f ) 等语言也纷纷出 台，这些语言的编译系统一般都是在相应串行语言编译系统的基础上增加并行部分把并 行语言转换成串行语言，再用串行语言编译系统编译。另外随着并行技术和并行语言的 发展，处理并行语言的并行编译技术，将串行程序转换成并行程序的自动并行编译技术 也正在深入研究之中。而今计算机的发展趋向于并行化，多处理机并行处理是不可逆转 的时代潮流。多处理机的硬件集成在技术上已不存在困难拍侧，但相应的并行编译软件 系统成了计算并行性发展的瓶颈，因此，开发并行编译成了当前计算机研究的一大课题。 编译实现方式的发展经历了手工，机器语言，汇编，系统程序设计语言和自动构造工具 l e x ，y a r n ，g c c 的过程。推动编译技术发展的因素包括语言范型( 计算模式) 和计算机体 系结构。语言范型分为：命令式( i m p e r a t i v el a n g u a g e ) ，应用式( a p p i l c a t i v e ) ，基于 规则的( r u l e b a s e d ) ，面向对象的( o b j e c t o r i e n t e d ) ，并行计算( p a r a l l e lc o m p u t i n g ) 体系结构有：万诺曼机体系结构，并行体系结构，嵌入系统。编译程序执行环境有：批处 2 第一章绪论 理，交互环境，嵌入系统环境。并行编译技术如图1 - 1 所示： 图1 - 1 并i 丁编译技术 1 1 2 编译程序的结构 编译程序的工作，从输入源程序开始到输出目标程序为止的整个过程，是非常复杂 的。编译程序的工作过程一般可以划分为五个阶段：词法分析，语法分析，语义分析与 中间代码产生，优化、目标代码生成。这五个阶段是编译程序工作时的动态特征。编译 程序的结构可以按照这五阶段的任务分模块进行设计。图卜2 给出了编译程序总框。 表 格 管 理 上 源程序 词法分析器 单词符号 语法分析器 语法单位 语义分析与中间代码产生器 上 中间代码 图1 - 2 编译程序总框 词法分析器又称扫描器，输入源程序，进行词法分析，输出单词符号。 语法分析器，简称分析器，对单词符号串进行语法分析( 根据语法规则进行推导或 规约) ，识别出各类语法单位，最终判断输入串是否构成语法上正确的“程序 。 语义分析与中间代码产生器，按照语义规则对语法分析器规约出( 或推导出) 的语 正规表达式到最简d f a 的并行相关算法研究 法单位进行语义分析并把它们翻译成一定形式的中间代码。 有的编译程序在识别出各类语法单位后，构造并输出一棵表示语法结构的语法树。 然后，根据语法树进行语义分析和中间代码产生。还有许多编译程序在识别出语法单位 后并不真正构造语法树，而是调用相应的语义子程序。在这种编译程序中，扫描器，分 析器和中间代码产生器三者并非是截然分开的，而是相互穿插的。 优化器，对中间代码进行优化处理。 目标代码生成器，把中间代码翻译成目标程序。 初了上述五个功能模块外，一个完整的编译程序还应包括“表格管理”和“出错处 理 两部分。 1 1 - 3 并行计算，并行计算机，并行算法的发展和现状 普通的一台计算机一般只有一个处理器，即使是最快的处理器也不能满足实际运算 的需要为了进一步提高性能，就需要更多的处理器，这类有多个处理器的计算机就称 为并行计算机并行计算机是使用多台计算机协同工作的一种高性能计算机系统从上 个世纪9 0 年代以来，并行计算机一直是世界各国计算机领域的主要研究课题。利用高性 能并行计算机，可以解决许多领域中一般计算机和一些仅靠理论和实验方法无法解决的 问题，对干一些涉及计算公式复杂、计算量大、时效性强、人工根本无法完成的问题， 用一般计算机也许需要数月甚至几年、几十年的时间，必须采用高性能并行计算机才能 处理。高性能并行计算机是现代科学技术研究，工程技术开发和大规模数据处理的关键 技术，是促进社会进步、国防安全、经济与科技发展的重要工具它代表着一个国家计 算机研制水平的高低，也是解决大型计算问题的唯一有效途径，体现着一个国家的综合 实力。随着大规模集成电路技术的不断进步，高性能并行机得到了迅速地发展，如何使 高性能并行机系统充分深入地在国民经济，科技和社会应用发展中发挥作用实为当务之 急，已引起人们普通关注。 为使高性能计算机运算成本合理而有效，采用并行处理技术，进行并行计算，已经 成为世界各国科技竞争的战略制高点。高性能计算机的峰值性能与其实际应用水平差距 很大。并行计算是提升运算效率、缩小这一差距的重要理论基础经过多年的发展，我 国在并行算法的研究上也取得了显著成绩，并行计算的应用已在天气预报、石油勘探、 航空航天、生命科学、材料工程、环境科学、核能利用、生物工程等领域的理论研究与 应用普及中均取得了很大发展，是这些领域不可缺少的高端计算工具。 4 第一章绪论 并行计算是伴随并行机的出现，在近3 0 年来迅速发展的一门交叉学科，涵盖的内容 非常广泛。参考文献 2 较为全面的综述了并行计算在各个方面的最新进展，内容包括 并行机体系结构，编译系统，并行算法，并行编程，并行软件技术，并行性能优化与评 价，并行应用等。从交叉学科的角度，并行计算可以定位为连接并行机系统和实际应用 问题之间的桥梁。它辅助科学，工程及商业应用的领域专家，为在并行机上求解领域问 题提供具有共性的关键支撑。并行计算是指，在并行机上，将一个应用分解成多个子 任务，分配给不同的处理器，各个处理器之间相互协同，并行地执行子任务，从而达到 加速求解速度，或者求解应用问题规模的目的。 并行计算机从7 0 年代开始，n 8 0 年代蓬勃发展和百家争鸣，9 0 年代体系结构框架趋 于统一，近5 年来机群技术的快速发展，并行机技术日趋成熟。并行算法是适合在并行 机上实现的算法，一个好的并行算法应该具备充分发挥并行机潜在性能的能力。并行计 算机的出现来源于实际应用程序中存在并行度这一基本事实。因此，应用问题中是否存 在可挖掘的并行度是并行计算机应用的关键，而并行算法作为应用程序开发的基础，自 然在并行计算机应用中具有举足轻重的地位。 目前并行算法根据运算基本对象的不同可分为：数值并行算法和非数值并行算法。 根据并行进程间相互执行顺序关系的不同可分为：同步并行算法，异步并行算法， 独立并行算法，细粒度并行算法，中粒度并行算法和大粒度并行算法。 而并行算法的发展经历了基于向量运算的并行算法设计阶段，基于多向量处理机的 并行算法设计阶段，s i m d 类并行机上的并行算法设计阶段，m i m d 类并行机上的并行算法 设计阶段和现代并行算法设计阶段。 1 1 4 并行编译程序及其发展 并行编译程序( p a r a l l e l i z i n gc o m p i l e r s ) 是处理并行语言的编译程序或串行语言 的程序并行化的编译程序( 自动并行编译程序) 。自动并行编译的实现在常规编译程序的 基础上采取两种途径：预处理方式，在词法语法分析前进行：中间代码优化，在中间代码 的基础上进行。预处理的方法，对数据依赖及循环中的数组下标分析清晰、精确，但并 不适用于多种语言而导致重复劳动：中间代码的优化方法可通用化，但由于各语言实现 时的中间代码形式各异且不对外开放，因而仅适用于系统制造者内部实现。自动并行编 译的主要内容是并行性的识别。其过程是：数据依赖分析，即识别各种依赖如数据依赖、 控制依赖等。程序转换，主要是循环的转换：借助运行系统和操作系统的支撑将源程序 5 正规表达式到最简d f a 的并行相关算法研究 转化为并行代码或并行程序。自动并行编译一般进行源到源转换，即将串行源代码转换 为并行源代码。并行语言的编译程序通常由词法语法分析、优化和代码生成三个阶段组 成。其中优化是主体，它包括依赖关系分析、循环转换及进程分配、调度、同步和通信 等。并行编译程序的主要研究内容包括：( 1 ) 依赖关系分析依赖关系主要有四种：流依 赖、反依赖、输出依赖及控制依赖。其中只有流依赖是固有依赖，其它依赖如输出依赖 和反依赖在一定条件下可通过换名扩张及设置必要的附加语句消去，而控制依赖亦可转 化为数据依赖。循环的并行化主要是通过依赖关系分析，改变原串行程序的词法次序， 以缩短程序的执行时间而不改变其语义。因此，依赖关系分析提供了保证串行程序语义 正确性的条件。编译程序依赖关系的测试方法主要有两种：精确测试法和近似测试法。 精确测试法试图求出丢番图方程的通解。所以适合于方程数目较少且循环具有确定的上 下界的情况，如依赖凸边域d c h 方法。近似测试法仅给出一些存在解的必要条件，如f 冶 n 幼e e n 试法、g c d i 贝 试法及入测试法等。( 2 ) 循环转换循环并行化之前应进行预优化工 作，这包括循环的规范化( 尽可能线性化以便于依赖关系的分析，使循环的上界和步长 均为1 等) 。循环的并行化可分为三个阶段：依赖分析( 跨迭代和迭代内依赖) 、循环转换 和循环调度。循环的转换技术是对循环变量的集合进行划分或改变循环，主要技术有循 环交换、合并、分布、分片和环路收缩等。循环调度则是为了取得更好的负载均衡，可 分为静态和动态两类调度方法。这样的技术有：自调度s s 、块调度( 芝吕、引导调度g s s 和梯形调度l 至8 等。( 3 ) 过程分析主要涉及别名分析、常数分析和引用分析，其目的是 为了发掘被过程所隐蔽的信息以及依赖分析。对过程调用的处理，可在程序优化之前， 采用内联扩展的办法，即将被调用过程通过参数代换嵌入到调用处，最终使整个程序只 包含唯一的过程。这种方法简单有效，但极耗内存，是一种消极的方法。己提出的过程 分析技术有数组线性化、线性不等式、原子图及简单域的区域分析r s d 、r r s i 和d a d 等。 自动并行编译工作最早始于7 0 年代，当时只能识别某些适合于向量化的模式。7 0 年 代末，美国i l l i n o i s 大学研制了p 班a l r a s e ，在向量化和并行化领域进行了开拓性的研 究。此后这方面的工作相继展开，及至8 0 年代，串行程序的自动并行化技术( 围绕f o r t r a n ) 取得了长足的进步，其主要标志是数据依赖关系的分析技术的成熟、商品化工具( 如k a p 等) 的出现。运用这些产品的系统开始获益n 2 1 副。由于现有程序中某些算法的固有顺序性， 完全自动化的并行编译十分困难。事实上，一个性能良好的并行程序可能需要设计合适 的并行算法，而不仅仅是并行性识别或代码转换。所以，增加并行语言成分和自动并行 6 第一章绪论 化的结合可能是今后发展的趋势。 1 1 5 并行技术的应用 并行技术应用非常广泛，平衡树设计技术用于求取最大值、计算机前缀和等；倍增 技术用于表序问题的计算、求森林的根等；分治设计技术用于双调归并网络、凸壳问题 等；划分技术用于归并原理、划分算法与归并算法等；而流水线技术主要用于一维心动 阵列上的d f t 计算和一维心动阵列上的卷积计算。本文用到的并行设计技术主要是分 治设计技术，将有限自动机的建立这个大而复杂的问题分解成若干特性相同的予问题分 而治之，也就是把三种有限自动机之间的转换分解成两个状态之间的关系转换，降低了 问题的规模，很自然的导致了递归的过程【1 9 乏o 】。 并行分治法分为三步：( 1 ) 将输入划分成若干个规模近于相等的子问题；( 2 ) 同时 递归地求解各个子问题；( 3 ) 归并各子问题的解为原问题的解。用分治法和划分法求解 问题共同点在于两者均试图将原问题分解成可并行求解的子问题，但分治法的侧重点在 于子问题的归并上；而划分法的注意力则集中在原问题的划分上。 1 2 论文研究内容 1 2 1 本课题研究的目的和意义 计算机技术日益发展的今天，尽管目前单个c p u 的性能已经达到相当高的水平，但 就一些超大规模计算或一些必须实时完成的多媒体运算而言，如果不利用并行计算技术 是很难满足用户需求的。如何获得更高的速度和峰值已成为我们所追求的方向，并行技 术能够将原本串行( 线性) 处理的工作改成并行( 多维) 处理，不仅节省了使用的时间并且 减少了所用的存储空间，因而并行计算机在近2 0 年迅速发展。并行程序设计和并行编译 技术是提高实际运行速度的关键。因此，并行优化编译技术已成为当代计算机软件的重 要研究课题之一。 为正规表达式建立最小的确定性有限自动机( d f a ) 是编译系统的关键技术，高性 能计算和并行处理是当前提高计算机性能的主要手段。因此，正规表达式蛰j d f a 的并行 转换是并行编译研究领域的重要分支。本课题主要研究其并行转换技术和其相关算法。 对并行编译理论研究和算法设计有其理论和实践意义。 7 正规表达式到最简d f a 的并行相关算法研究 1 2 2 本文的主要工作 正规表达式( r e ) 在编译技术和模式匹配中占有重要地位。其中构造正规表达式的 最简d f a 成为其应用的关键环节瞻1 。 构造正规表达式的最简d f a 需要三个步骤：构造正规表达式的非确定性有限自动机 ( n f a ) ，非确定性有限自动机的确定化以及有限自动机的最小化。在构造正规表达式 的非确定性有限自动机的时候，给出三种非确定的有限自动机即：t h o m p s o n 自动机、 g l u s h k o v 自动机和f o l l o w 自动机。它们的规模逐渐减小。本章将详细地介绍构造正规 表达式的f o l l o w 自动机的并行算法。在非确定性有限自动机确定化的时候，基于 g l u s h k o v 自动机利于并行计算的特点，用状态关系表实现有限自动机的确定化。对于有 限自动机的最小化，本文利用粗糙集的知识划分理论，从一个新的角度，实现有限自动 机的最小化。 1 3 论文的组织结构 本文有七个章节组成： 第l 章，概要性的论述了有关编译的概念和结构以及并行算法设计的概念，研究背 景以及发展现状，提出了本文的主要研究内容从正规表达式到有限自动机的并行转换， 最后介绍了本文的组织结构。 第2 章，为了介绍后文的传统算法和在并行环境下的推广，本章给出了正规表达式， 有限状态系统、确定性有限自动机和非确定性有限自动机的概念以及形式语言的分类。 第3 章，为了对构造正规表达式的最简d f a 的过程有所了解，在前文的基础上，对 于如何构造正规表达式的最简d f a ，本章给出了在串行环境下的描述。 第4 章，本章详细地给出了构造正规表达式的f o l l o w 自动机的并行算法。在非确 定性有限自动机确定化的时候，基于g l u s h k o v 自动机利于并行计算的特点，用状态关 系表实现了有限自动机的确定化。对于有限自动机的最小化，本章利用粗糙集的知识划 分理论，从一个新的角度，实现了有限自动机的最小化。 第5 章，为了研究该算法的应用，本章给出了求一个正规表达式对应的正规文法的 问题。过程是首先构造正规表达式的确定性有限自动机，然后详细的介绍了确定性有限 自动机到正规文法的转换过程。最后举例模拟该转换过程。 第6 章，总结全文，并展望了并行编译的研究前景和方向。 8 第二章编译理论基础 第二章编译理论基础 为了介绍后文的传统算法和在并行环境下的推广，本章给出了正规表达式，有限状 态系统、确定性有限自动机和非确定性有限自动机的概念。 2 1 正规表达式 正规表达式是以一个字母表中的字符和字符串为对象( 或者说元素) ，通过加法运 算，乘法运算和闭包运算组合起来的一种式子，用于表示这个字母表上的字符串集合。 能够用正规表达式表示的字符串集合称为正规集f 2 l 】。 定义1 设为一字母表，在该字母表中正规表达式和正规集的递归定义如下： ( 1 ) 善和缈都是上的正规式，它们所表示的正规集分别是 亭) 和妒； ( 2 ) 任何口，a 是上的一个正规式，它所表示的正规集是 a ) ； ( 3 ) 假定u 和v 都是上的正规式，它们所表示的正规集分别是l ( u ) 和l ( v ) ， 那么，( u iy ) ，( u y ) 和( + 也都是正规式，它们所表示的正规集分别是从u ) u 从 ， l ( u ) l ( v ) ( 连接积) 和( l ( u ) ) ( 闭包) 仅由有限次使用上述三步骤而得到的表达式才是上的正规式。仅由这些正规式所 表示的字集才是上的正规集。 正规式的运算符“i 读为“或 ；“”读为“连接”；“宰”读为“闭包”( 即，任 意有限次的自重复连接) 。在不致混淆时，括号可以省去，但规定算符的优先顺序为先 “木 ，次“ ，最后“l 。连接符“ 一般可以省略不写。 例2 1 令= 口，b ) ，下面是上的正规式和相应的正规集： 正规式正规集 6 口。 上所有以b 为首后跟任意多个a 的字。 a ( a l b ) 上所有以a 为首的字。 ( a l b ) + ( a a l b b ) ( a b ) 上所有含有两个相继的a 和两个相继的b 的字。 例2 2 令= 4 ，b ，0 ，l ，则 正规式正规集 9 正规表达式到最简d f a 的并行相关算法研究 ( a i b ) ( a i b o i ) + 上的“标识符“的全体。 ( 0 1 1 ) ( 0 1 1 ) 上“数“的全体。 若两个正规式所表示的正规集相同，则认为二者等价。两个等价的正规式u 和v 记为u = v 。例如， 令u ，v 和w 均为正规式，显而易见，下列关系普遍成立： ( 1 ) v l v = v l u ( 交换律) ( 2 ) u lc u l w ) = ( u i v ) 1 w ) ( 结合律) ( 3 ) u ( v - w ) = ( u v ) w ( 结合律) ( 4 ) u i ( y i 形) = t n t i u w ( 分配律) ( 矿1w ) u = 阿i 删； ( 5 ) 孝u = u 孝= u 2 2 有限自动机 有限自动机是最简单的一类语言识别器，也是有限状态系统的一种模型。它的基本 功能就是描述系统运行过程中状态之间的转换。有限自动机可以分为确定型和不确定型 两种类型。确定的有限自动机在一种状态下输入字符( 表示状态转换条件) 时，只能转 换成一种状态( 另一种状态或原状态本身) 。不确定的有限自动机在一种状态下输入一 个字符，可能转换成的状态可能有多种 2 2 。2 4 】。 2 2 1 有限状态系统 在系统运行过程中，系统的状态往往不断变化。对于许多实际系统来说，尽管状态 在不断变化，但整个运行过程中出现的状态只有有限多种( 只不过某些状态在运行过程 中反复出现) 。这样的系统称为有限状态系统。 在日常生活和科学技术中，许多问题都可以归结为有限状态系统。譬如，一个开关 电路是一个有限状态系统，一台电子计算机也是一个有限状态系统。 对于一个有限状态系统，可以用一个带标注的有向图来描述系统中状态之间的转换 关系。有向图的节点集就是系统的状态集，如果状态a 在某条件下可以转换为状态b ， 就在图的节点a 向节点b 引一条有向边，并在边上标注上转换的条件。这种图形描述 既可以清晰，直观地反映系统的可能运行情况，也可以借助它来对复杂的问题寻找求解 1 0 第二章编译理论基础 方案。下面我们通过对一个民间流传的智力问题求解来说明。 问题：有一个人带着一只狼、一只羊和一捆菜过河，河边只有一条小船，且承载量 很小，每次只能承载一个人加上一样物品( 一种动物或一捆菜) 。人不在场的情况下， 狼会把羊吃掉，羊会把菜吃掉。人怎样借助这条小船，安全地分批把狼、羊、菜都从河 的左岸运过河的右岸? 可能不少人在童年时代都为这个问题的求解花费过不少心思。如果借助有限状态系 统的概念和图形表示，就可以为这个问题的求解带来很大的方便。 人、狼、羊、菜 人、羊 j 人、羊 过河，r过河 狼、菜人、养 人过 。八也 河 河 人、狼、菜羊 剐器沁 菜人、狼、羊狼人、羊、菜 。人、羊人、障 。 过河矿金过河山。 过河立河 人、羊、菜狼人、狼、羊菜 全矿金詹 “1 。o l 羊人、狼、菜 人过i 。 人过 河 上 河 人、羊狼、菜 人、斟 一l 人、羊 过河l 过河 ， l 一人、狼、羊、菜 目标 图2 1 “人、狼、羊、菜问题”的状态转换图 刚开始时，人和狼、羊、菜都在河的左岸( 右岸为空) ，我们把这种情况看作问题 的初始状态。问题的目标状态( 或者说是终止状态) 是人和狼、羊、菜都在河的右岸( 左 岸为空) 。由于渡船的承载量的限制，我们无法一步从初始状态变成目标状态，只能寻 正规表达式到最简d f a 的并行相关算法研究 找一些中间状态来过渡。这些中间状态必须满足安全条件，即人不能自己在河的一边， 而把狼和羊或者羊和菜留在河的另一边。安全状态之间的转换通过人带着某种物品过河 或人自己单独过河等条件来实现。譬如，在初始状态下，如果人带着羊过河，就转换成 人羊在河的右岸，狼和菜在河的左岸的状态。图2 - 1 就是这个问题的全部安全状态以及 它们之间的转换关系的状态转换图。在这个图中，找出一条从初始状态通向目标状态的 条有向路，就是这个智力问题的一个解答( 解决方案) 。如果找出的有向路是所有从 初始状态到目标状态的有向路中最短的条，就是问题的一个最优的解决方案。 2 2 2 确定性有限自动机( d f a ) 有限自动机的基本机构包括一条输入带、一个有限状态控制器和连接这两者的一个 只读输入头，如图2 - 2 所示输入带从左到右分为多个格，用于存放输入字符串，每格存 放一个字符。有限自动机工作过程是这样的：把一个输入字符串存放到输入带上，从初 始状态开始，输入头从左到右逐格扫描输入带，每读到一个字符就传送给有限状态控制 器，有限状态控制器根据当前状态和读到的字符决定转换成什么状态乜 咖。状态转换后 再读入下一个输入字符，这样继续下去。直到把整个输入串扫描完毕，如果最终能转换 成一个终止状态有限自动机就接受输入字符串。一个有限自动机所接受的全体字符串的 集合，就是该有限自动机接受的语言。 图2 - 2有限自动机的基本结构 下面首先讨论在一个状态下读到一个字符只转换成一个新状态的有限自动机，这种 有限自动机就是确定的有限自动机。 定义2 1 一个确定有限自动机( d f a ) m 是一个五元式 m = ( s ，5 ，s o ，f ) 其中 ( 1 ) s 是个有限集，它的每个元素称为一个状态。 ( 2 ) 是个有穷字母表，它的每个元素称为一个输入字符。 1 2 第二章编译理论基础 ( 3 ) 6 是一个从sx 至s 的单值部分映射。8 ( s ，n ) = s 意味着：当现行状态为s ， 输入字符为a 时，将转换到下一状态s 。我们称s 为s 的一个后继状态。 ( 4 ) s 0 s ，是唯一的初态。 ( 5 ) ，s ，是一个终态集( 可空) 。 d f a 就是一种有限状态系统的模型。我们可以像描述有限状态系统的状态转换那 样，用一个带标注的有向图来表示一个d f a 。有向图的节点集就是d f a 的状态集。每 个节点用一个小圆圈表示，圆圈内写上该节点所对应的状态。为了在图中清晰地表示出 初始状态和终止状态集，用一个箭头指向初始状态并在箭头末端写上“开始”，各个终 止状态用双圆圈表示状态转换函数则通过有向边及边上的标注字符来表示：若 8 ( q ，口) = q 。，则代表状态q 的节点向代表状态q 的节点引一条有向边，并在这条有向边 旁标上字符f l , 。 显然，一个d f a 可用一个矩阵称为状态转换矩阵。例如，有d f a m = ( o ，1 ，2 ，3 ) ， 口，6 ) ，万，0 ， 3 ) ) 其中万为 8 ( 0 ，窿) 8 ( 1 ，口) 8 ( 2 ，口) 8 ( 3 ，口) 8 ( o ，6 ) = 2 8 0 ，6 ) = 2 8 ( 2 ，6 ) = 3 a ( 3 ，6 ) = 3 它所对应的状态转换如表2 - 1 所列 表2 - 1 状态转换矩阵 状态 ab 012 132 213 333 一个d f a 也可以表示成一张( 确定的) 状态转换图。假定d f a m 含有m 个状态和 1 1 个输入字符，那么，这个图含有m 个状态结点，每个结点顶多有1 1 条箭弧射出和别的 结点相连接，每条箭弧用中的个不同输入字符做标记，整张图含有唯一的一个初态 结点，若干个( 可以是0 个) 终态结点。 对于宰中的任何字a ，若存在一条从初态结点到终态结点的通路，且这条通路上所 正规表达式到最简d f a 的并行相关算法研究 有弧的标记符连接成的字等于a ，则称a 可为d f a m 所识别( 读出或接受) 。若m 的初 态结点又是终态结点，则空字f 可为m 所识别( 或接受) 。d f a m 所能识别的字的全体 记为l ( m ) 。 例如，上一例子所定义的d f am 相应的状态转换图如图2 3 所示。它能识别上 所有含有相继两个a 或者相继两个b 的字( 图中用“f l ，b ”标志的弧实际上是指分别由 a 和b 标志的两条弧) 。 图2 - 3 状态转换图 如果一个d f a m 的输入字母表为，则我们也称m 是上的一个d f a 。可以证明： 上的一个字集矿是正规的，当且仅当存在上的d f a m ，使得v = l ( m ) 。 d f a 的确定性表现在映射万：s e 专s 是一个单值函数。也就是说，对于任何s s 和输入符号口，8 ( s ，口) 唯一的确定下个状态。从转换图的角度来看，假定字母表含 有n 个字符，那么，任何一个状态最多只有n 条弧射出，而且每条弧以一个不同的输入 字符标记。如果也允许万是一个多值函数，我们就得到非确定自动机的概念。 2 2 3 非确定有限自动机( f a ) 不确定的有限自动机( m a ) 的基本结构同确定的有限自动机是一样的。它们之间 的区别只是在状态转换函数。不确定的有限自动机的状态转换函数是从状态集和字母表 的笛卡尔积到状态集的幂集的一个映射。也就是说，在一种状态下读到一个输入字符时， 不确定的有限自动机的转换函数万可以产生多个新的状态( 准确地说) ，可以产生o 个、 1 个或多个新状态【3 1 1 。 一个非确定有限自动机( n f a ) m 是一个五元式 m = ( s ，艿，s o ，f ) 其中 ( 1 ) s 是个有限集，它的每个元素称为一个状态。 ( 2 )