（计算机应用技术专业论文）表格公式引擎的研究与实现.pdf

韭塞銮遵太堂亟堂焦监塞生塞箍垩 中文摘要 摘要：表格公式引擎在应用系统中有很多应用，它主要涉及公式语法定义、公式 语法解析和公式计算等内容。 论文介绍了常用的语法分析生成器，包括j a v ac o m p i l e rc o m p i l e r 、 a n t l r ( a n o t h e r t o o l f o r l a n g u a g e r e c o g n i t i o n ) 、c h a p e r o n 、j f l e x 、s a b l e c c 、j t o p a s 、 r 1 1 n c c ，b e a v e r ，c u p 、s j p t ，l e x ( l e x i e a la n a l y z a r ) ，y a e e ( y e ta n o t h e rc o m p i l e r c o m p i l e r ) 、b i s o n 、l e m o n 、g r a m m a t i c a 等。 本文剖析了表格公式语法，设计和实现了适于该语法的公式引擎。该公式引 擎包括公式语法定义、公式语法解析以及公式计算三个部分。 公式语法定义包括终结符号处理和产生式集处理。终结符号处理过程中，深 入地研究了字符串匹配算法和j 下则表达式匹配算法，并实现了二叉排序树字符串 匹配算法。 公式语法解析实现了l l ( 1 ) 类型文法检查和一个递归下降分析法的语法分析 生成器主要功能。 公式计算是通过在公式语法解析返回的语法树的结点中添加辅助计算信息， 将用户输入的公式串转换成中间代码，最后得到公式计算结果。 关键词：表格公式引擎，语法分析生成器，自动机，j 下则表达式，二叉排序树 分类号：t p 3 9 1 j 立交道太堂亟堂位i 金奎 旦羔b 工 a b s t r a c t t a b l ef o r m u l ae n g i n ei sw i d e l yu s e di nm a n y a p p l i c a t i o ns y s t e m s i nt a b l ef o r m u l a e n g i n e ，f o r m u l ag r a m m e rd e f e n i t i o n ，f o r m u l ag r a m m e rp a r s i n ga n df o r m u l ac a l c u l a t i n g a r em o s ti m p o r tp a r t s c o m m o np a r s e rg e n e r a t o r sh a v eb e e ni n t r o d u c e d f o re x a m p l ej a v ac o m p i l e r c o m p i l e r , a n t l r , c h a p e r o n ，j f l e x ，s a b l e c c ，j t o p a s ，m n c c ，b e a v e r , c u p ，s j p t , l e x ( l e x i c a l a n a l y z a r ) ，y a c c ( y e ta n o t h e rc o m p i l e rc o m p i l e r ) ，b i s o n ，i , e l n o n ，g r a m m a t i c a t a b l ef o r m u l ag r a m m e rh a sb e e na n a l y z e da n da na p p r o p r i a t ef o r m u l ae n g i n ei s d e s i n g e da n dr e a l i z e di nt h ep a p e r t h ef o r m u l ae n g i n ei sc o m p o s e db yf o r m u l a g r a m m e rd e f i n i t i o n ，f o r m u l ag r a m m e rp a r s i n ga n df o r m u l ac a l c u l a t i n g c o n s t r u c t i n gt o k e na n dp r o d u c t i o ni sf o r m u l ag r a m m e rd e f i n i t i o n f i r s t ，c l a s s i c s t r i n gm a t c h i n ga l g o r i t h m sa n dr e g u l a re x p r e s s i o nm a t c h i n ga l g o r i t h m sa r es t u d i e d ； s e c o n da b i n a r ys o r tt r e es t r i n gm a t c h i n ga l g o r i t h mi sp r o p o s e da n dr e a l i z e d l l ( 1 ) g r a m m e rc h e c k i n ga n dar e c u r s i v ed e s c e n tp a r s e ra r er e a l i z e di nf o r m u l a g r a m m e rp a r s i n gp a r t b ya d d i n ga u x i l i a r yc a l c u l a t i n gi n f o r m a t i o ni n t op a r s et r e en o d e s ，f o r m u l as t r i n g i n p u tb yu s e r si sc o n v e r t e di n t ot e m p o r a r yc o d e s ；f i n a l l yw eg e tt h ec o r r e c tr e s u l t k e y w o r d s ：t a b l ef o r m u l ae n g i n e ，p a r s e rg e n e r a t o r ，a u t o m a t o n ，r e g u l a r e x p r e s s i o n ，b i n a r ys o r tt r e e c i a s s n 0 ：t p 3 9 1 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国 家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：锄 签字同期：z 唧年侄月2 午日 导师签名： 签字同期：似研年肛月2 多日 j e 哀銮亟盍堂亟蝗堂焦论室独创性岜明 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 学位论文作者签名：益9签字日期：2 吣7年，1 月2 霉日 致谢 本论文的工作是在尊敬的导师瞿有利的精心指导和悉心关怀下完成的。导师 渊博的学识、严谨的治学态度、孜孜不倦的进取精神、对问题实质的洞察入微和 高屋建瓴、以及宽广豁达的长者风范，都给我留下了深刻的印象。攻读硕士期间， 导师对我的学习、生活上给予了许多关心和帮助，不仅让我学到了很多的科研知 识，而且还给了我很好的实践机会，这些都将融入到我未来的奋斗当中，使我受 益终身。 感谢黄厚宽、田盛丰、于剑、王志海、林友芳、田风占、魏名元、尹传坏、 韩升老师的谆谆教导和帮助，他们一丝不苟的治学精神永远是我学习的榜样。 感谢我的同学孙慧婷，她给我的论文提供了很大的帮助，感谢李辉、赵伟和 实验室的各位博士、各位师兄、师姐、师弟、师妹，他们使我感受到集体的温暖， 让我的生活充满了快乐和自信。 最后我要感谢我的父母，是他们将我养育成人，给了我无私的爱。在交大的 日子里，他们始终都在给我默默地支持和鼓励，总在我最困难的时候给我最坚决 的支持，父母将永远是我人生最大的精神动力。 e 塞变通太堂亟堂短论塞i i 盍 1 引言 1 1 相关技术发展动态 1 1 1 语法分析生成器技术 表格公式引擎就是一套实现表格公式语法定义、公式语法解析和公式计算的 程序集。其中公式语法的处理实现了一个递归下降分析法语法分析生成器的主要 功能。 目前流行的语法分析生成器： j a v a c c j a v ac o m p i l e rc o m p i l e r 是一个用j a 、，a 开发的最受欢迎的语法分析生成器。 这个分析生成器工具可以读取上下文无关且有着特殊意义的语法并把它转换成可 以识别且匹配该语法的j a v a 程序。它还提供j j t r e e 等工具来帮助我们建立语法树。 a 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 ) 它可以接受词文法语言描述，并 能产生识别这些语言的语句的程序。作为翻译程序的一部分，可以使用简单的操作 符和动作束参数化文法，使之告诉a n t l r 怎样去创建抽象语法树( a s t ) 雨1 怎样产 生输出。 c h a p e r o n c h a p e r o n 是一个可以把有结构的文本转换成x m l 。它包括一个强大的l a l r ( 1 ) 解析器来解析文本和一个可以用来创建x m l 文档的t r e eb u i l d e r 。 j f l e x j f l e x 是一个j a v a 的词法语法分析生成器。 s a b l e c c 。s a b l e c c 是一个用来生成编译器和分析器的面向对象的框架。这个框架是基于 两个基本的设计决策：第一，利用面向对象技术自动构建精确的典型的抽象语法 树。第二，这个框架使用经过扩展的v i s i t o r 访问者模式来生成t r e e - w a l k e r 类。 b e a v e r b e a v e r 是一个l a l r ( 1 ) 语法分析生成器。它读取一些上下文无关的语法并把 它转换成一个利用该语法描述的语言分析器。 j t o p a s 韭塞交通太堂亟土堂僮j 金童 l 直 j t o p a s 这个开源项目提供了一个容易使用的用来分析特殊t e x t 数据的j a v a 类 包。这些数据可以是来自包含一些注释的简单配置文件，h t m l ，x m l ，r t fs t r e a m ， 和来自其程序语言的源代码等。有时需要解释所有的t e x t 数据，而有时只需解释 其中重要的部分。 r i l l n c e r u n c c 是一种在运行时生成p a r s e r s 和l e x e r s 的语法分析生成器。它自带一个 j a v a 和x m l 分析器的例子。 c u p 一个l a l r ( l o o k a h e a dl e f tt or i g h tp a r s i n g ) 语法词法分析生成器。 s j p t s j p t 是一个分析工具包支持包括自顶向下( l l ( 1 ) ) 和自底向上( l r ( o ) ，s l r ( 1 ) ， l r ( 1 ) a n dl a l r ( 1 ) ) 。该工具包同时支持为所有自底向上的分析法生成j a v a 剖析 器。 l e x l e x ( l e x i c a la n a l y z a r ) 是一种词法分析程序生成器，它可以根据词法规则说明 书的要求来生成单词识别程序，由该程序识别出输入文本中的各个单词。【1 】 y a c e y a c c 是y e t a n o t h e r c o m p i l e r c o m p i l e r 的缩写。是一种语法分析程序生成器， 它可以将有关某种语言的语法说明书转换成相应的语法分析程序，由该程序完成 对相应语言中语句的语法分析工作。 在使用y a c e 工具前，必须首先编写y a c c 程序，因为有关语法分析程序是根据 y a c c 程序生成的。y a c c 程序实际上是有关语法规则的说明书，它也是由定义部分、 规则部分和子程序部分组成的。y a c e 程序的定义部分类似于l e x 程序的定义部分， 只是在其后可带有y a c e 声明，其中包括词法单词、语法变量、优先级和结合性信 息。y a c c 程序的规则部分由语法规则和相应的动作组成，子程序部分可以包括在 前面规则部分用到的子程序定义。接下来是m a i n 主程序，它调用y y p a r s e 子程序 来对输入进行语法分析，而y y p a r s e 反复地调用y y l e x 子程序来获得输入单词，在 语法出错时可通过y y e r r o r 子程序来处理。【l 】 b i s o n y a c c 的g n u 版。b i s o n 基本兼容y a e e ，并做了一些改进。它一般与f l e x 一起 使用。 l e m o n l e m o n 是一个c 或者c + + 语言的l a l r ( 1 ) 语法分析器生成器。它和“b i s o n ” 与“y a e e ”的功能是一样的，但它不是“b i s o n ”或者“y a e e ”的简单复制。为了减 2 少编写代码的错误，它使用了一种不同的语法。l e m o n 使用了一种更为高级的分 析引擎，运行速度比“b i s o n ”与“y a e c ”要更快，并且该引擎是可重入的和线程 安全的。更进一步的，l e m o n 实现了能够消除资源泄漏的特性，适合于长时间运 行的程序例如g u i 或者嵌入式控制器中【2 j 。 g r a m m a t i e a g r a m m a t i e a 是一个咧和j a v a 的语法剖析器生成器( p a r s e rg e n e r a t o r 或叫作编 译器的编译器：c o m p i l e rc o m p l i e r ) 。 1 1 2 开发语言和开发平台 本文研究选择使用m i c r o s o f t n e t 技术来实现表格公式引擎，选用钟语言为 开发语言。 由文献1 4 5 1 可知，n e t 的核心是n e tf r a m e w o r k ，它是一种新的计算平台， 它简化了在高度分布式i n t e m e t 环境中的应用程序开发。n e t f r a m e w o r k 具有两个 主要组件：公共语言运行库和n e tf r a m e w o r k 类库。公共语言运行库是n e t f r a m e w o r k 的基础。可以将运行库看作一个在执行时管理代码的代理，它提供核心 服务( 如内存管理、线程管理和远程处理) ，而且还强制实施严格的类型安全以及 可确保安全性和可靠性的其他形式的代码准确性。事实上，代码管理是运行库的 基本原则。n e tf r a m e w o r k 的另一个主要组件是类库，它是一个综合性的面向对 象的可重用类型集合，可以使用它开发多种应用程序，这些应用程序包括传统的 命令行或图形用户界面( g u i ) 应用程序，也包括基于a s p n e t 所提供的最新创 新的应用程序( 如w 曲窗体和x m l w 曲s e r v i c e s ) 。 n e tf r a m e w o r k 类库是一个与公共语言运行库紧密集成的可重用的类型集 合。该类库是面向对象的，并提供托管代码可从中导出功能的类型。这不但使n e t f r a m e w o r k 类型易于使用，而且还减少了学习n e t f r a m e w o r k 的新功能所需要的时 问。此外，第三方组件可与n e t f r a m e w o r k 中的类无缝集成。n e tf r a m e w o r k 类 型能够完成一系列常见编程任务( 包括诸如字符串管理、数据收集、数据库连接 以及文件访问等任务) 1 6 j 。 c 群是一种从c + + 和j a v a 继承而来的、简单的、现代的、面向对象的语言，它 综合了v i s u a lb a s i c 高产和c + + 底层高效的特性，是m i c r o s o f tv i s u a ls t u d i o n e t 的一部分。v i s u a ls t u d i o 支持v b 、v c 抖、c 群、c + + 、v b s c r i p t 、j s c r i p t ，所有这 些语言提供对m i c r o s o f t n e t 平台的访问。础能够用于开发控制台应用程序、 w i n d o w s 应用程序、w e b 应用程序等。在c 拱中，微软解决了c h 所不能解决的一 些问题，比如内存管理、指针等，它支持垃圾回收( 无用内存回收) 、内存自动管 3 j b 裒变通太堂硒兰僮论室曼i 壹 理和其他许多特性 7 1 。具体来说，铹具有如下几个特点： ( 1 ) 简单 在c 撑中指针已经消失，一些不安全的操作，比如说直接内存操作，不再被允 许，并且甜中“：”和“? ”操作符是无效的。c 萍基于n e t 平台，它继承了该 平台的自动内存管理和垃圾回收特性。整形数值0 和l 不再作为布尔值出现，c 撑 中的布尔值是纯粹的t r u e 和f a l s e 值。而且不会有更多的“= ”运算符和“一”运 算符混用错误，在c # 中，“一”被用于比较运算，而“= ”被用做赋值运算。 ( 2 ) 现代 c # 是一种现代编程语言，它所拥有的特性对于创建相互兼容的、可缩放的、 健壮的应用程序来说非常强大和简单。c 撑拥有的内置支持可以将任何组件转换成 一个w e bs e r v i c e ，这样，运行在任何平台上的任何应用程序都可以通过互联网来 使用这个服务。 ( 3 ) 面向对象 c # 支持数据封装、继承、多态和接口。i n t 、f l o a t 、d o u b l e 在j a v a 中都不是对 象，但是c 拌引入了结构体来使原始数据类型变成对象。 ( 4 ) 类型安全 在c f ； 中，我们不能进行不安全的类型转换，例如将d o u b l e 转换成b o o l e a n 。 值类型( 常量类型) 在c 萍中被仞始化为零值，而引用类型对象和类被编译器自动 仞始化为空值。数组类型下杯从零开始而且进行越界检查，类型溢出将被检测。 ( 5 ) k h 互兼容性 c 撑提供对c o m 和基于w i n d o w s 的应用程序的原始支持，允许对原始指针的 有限使用，用户不再需要显式实现u n k o w n 和其他c o m 接口，这些功能已经内置 在系统中。例允许用户将指针作为不安全的代码段来操作1 日代码，v b n e t 和其 他中间代码语言中的组件可以在雠中直接使用。 ( 6 ) 可缩放性和可升级性 n e t 引入了零部件的概念，它们通过其“手册”提供自描述的功能，手册 确立了零部件的身份、版本、语言和数字签名等，零部件不需要在任何地方 注册。如果要扩展我们的程序，我们只需要删除老的文件并用新的文件来升级它 们，而不需要注册动态链接库。升级软件组件的过程只是一个纠错过程，对组件 代码的修改不会影响现存的程序，c 群支持版本修改，对接口和方法重载的支持使 得复杂的程序框架能逐渐完善和发展。 1 2 本文研究内容 4 本文作者就以下方面进行了研究： 1 、表格公式语法系统； 2 、语法生成器的开发与实现； 3 、字符串匹配算法： 4 、正则表达式处理； 5 、正则表达式算法； 6 、公式计算。 1 3 本文的组织结构 论文共包含五章： 第一章为引言。主要介绍了论文的相关技术背景、研究内容、文章组织结构 第二章为公式语法； 第三章为公式解析； 第四章为公式计算； 最后是结论。 s 韭立銮通盔堂亟堂使业塞公式蚤洼 2 公式语法 2 1 基本概念 公式语法是一套上下文无关文法。 一个上下文无关文法可定义为一个四元组：g = 眇，v ，p , s ) p ：产生式集，是一组产生式的集合。产生式，又叫产生规则或语法规则， 是定义语法范畴的一种书写规则，一个产生式的形式是一一口，我们说产生式 4 寸口是关于彳的一条产生规则，箭号”一”读为”是”或”定义为”。 v 。：非终极符集，是一个非空有限集，它的每个元素称为非终极符( 非终结 符号) 。非终极符，也可称做”非终结符号”，用来代表语法范畴，是可出现于产生 式左部的符号。 v ，：终极符集，是一个非空有限集，它的每个元素称为终极符( 终结符号) 。 终极符：也可称做”终结符号”，用来组成语言的基本符号，是只能出现于产生式右 部的符号。 z ：开始符号，是一个非终极符号，称为文法的开始符号( 初始符号) 。( 公式 语法中的开始符号是f o r m u l a ) 【8 】o 2 2 终结符号类的设计 我们为终结符号设计了t o k c n p a t t e m 类，详细设计如下： 属性： i d ：i n t 类型属性，终结符号i d 。 n a m e ：s t r i n g 类型属性，终结符号名称。 p a t t e r n t y p e ：枚举类型属性，终结符号类型( 枚举类型有两个分量：s t r i n g 、 r e g e x p 分别表示字符串类型终结符号和正则表达式类型终结符号) 。 p a t t e r n ：s t r i n g 类型属性，终结符号串。 方法： t o s t r i n g o ：s t r i n g 类型返回值，返回一个字符串表示t o k e n p a t t e m 对象。 例1 ：字符串类型 6 韭京交通左堂亟堂位j 金塞公式蚤选 a d d ( 1 0 0 1 ) ：”1 例中的字符串就是t o k e n p a t t e r n 类t o s t r i n 9 0 方法返回的字符串。其中a d d 是 终结符号的名称l l a l n e ；我们定义了一个枚举类把所有的终结符号一一对应于不同 的整数，这些整数是终结符号的i d ，终结符号a d d 的i d 是1 0 0 1 ；”+ ”是终结符号 a d d 在实际公式中对应的字符p a r e m 。 例2 ：正则表达式类型 s t r i n g _ l i t e r a l ( 1 0 1 8 ) ： 其中s t r i n gl i t e r a l 是终结符号的名称n a m e ；终结符号的i d 是1 0 0 1 ； 是终结符号在实际公式中对应的字符p a t t e r n 。 2 2 1 字符串类型( s t r i n g ) 终结符号t o s t r i n g ( ) 方法 以下是公式语法中所有的字符串类型的终结符号被实例化为t o k e n p a t t e m 对 象后调用t o s t r i n 9 0 方法返回的字符串： a d df 1 0 0 1 ) ：”+ ” s u br 1 0 0 2 ) ：”一” m u l ，1 0 0 3 ) ：。+ ” d i v ( 1 0 0 4 ) ：” e x p ( 1 0 0 5 ) ：”“” c o n c a t ( 1 0 0 6 ) ：” l e f t p a r e n ( 1 0 0 7 ) ：”( ” r i g h t _ p a r e n ( 1 0 0 8 ) ：”) ” p e r c e n t ( 1 0 0 9 ) ：” a r g _ s e p a r a t o r ( 1 0 11 ) ：”，” e q ( 1 0 1 2 ) ：2 ” l t ( 1 0 1 3 ) ：” “ l t e ( 1 0 1 5 、：”= ” g t e ( 1 0 1 6 ) ：” = ” n e ( 1 0 1 7 ) ：” t r u e ( 1 0 2 0 ) ：”t r u e ” f a l s e ( 1 0 2 1 ) ：”f a l s e ” d w e r r o r ( 1 0 2 3 ) ：”# d w 0 1 “ n a _ e r r o r ( 1 0 2 4 ) ： # n a ” 7 北立窑煎盘堂殛堂焦i 金塞公式蚤洼 n a m e _ e r r o r ( 1 0 2 5 ) ：”# n a m e ? ” n u l l e r r o r ( 1 0 2 6 ) ：”# n u l l ! ” r e f _ e r r o r ( 1 0 2 n ：”# r e f ! ” v a l u e _ e r r o r ( 1 0 2 8 ) ：”# v a l u e ! ” n u m _ e r r o r ( 1 0 2 9 ) ：”# n u m ! 【9 】 2 2 2 i e 贝0 j 表达式类型( r e g e x p ) 终结符号t o s t r i n 9 0 方法 以下是公式语法中所有的正则表达式类型的终结符号被实例化为 t o k e n p a t t e ：m 对象后调用t o s t r i n i g o 方法返回的字符串及其实际意义： w h i t e s p a c e ( 1 0 1 0 ) ： i g n o r e 空白字符类型 s t r i n g l i t e r a l ( 1 0 1 8 ) ： 字符串类型 n u m b e r ( 1 0 1 9 ) ： 数值类型 f u n c t i o n n a m e ( 1 0 2 2 ) ：“【a z 】 、w 】+ p 数名称类型 c e l l ( 1 0 3 0 ) ： 单元格名称类型 c e l l r a n g e ( 1 0 3 1 ) ： 单 元格区域名称类型 r o w _ r a n g e ( 1 0 3 2 ) ： 行区域名称类型 c o l u m n j n g e ( 1 0 3 3 ) ： 列区域名称类型 s h e e t n a m e ( 1 0 3 4 ) ： 变量名称类型。【9 】 2 3 终结符号的匹配算法 终结符号的匹配就是判断用户输入的字符串是否属于终结符号集。字符串的 匹配算法已经有很多研究，著名的算法有t h ek n u t h - m o m s p r a t ta l g o r i t h m ，t h e s i m o na l g o r i t h m ，s t r i n gm a t c h i n gb yd u e l s ，s 砸n g m a t c h i n gb ys a m o l i n g b o l 等，但是 这些算法的匹配效率不是很高。在公式语法的解析计算中，字符集相对稳定，为 了加快匹配速度，本文采用二叉排序树作为终结符号的存储结构，以此为基础进 行终结符号匹配。该方法采用了较大的存储空问，但是匹配的速度和输入的终结 符号的长度相同。 2 3 1 字符串类型终结符号的匹配算法 我们建立了一组二叉排序树来匹配字符串类型的终结符号。 二叉排序树的建立 二叉树或为空，或是由一个根结点加上两棵分别称为左子树和右子树的、互 不相交的二叉树组成【“l 。 二叉排序树( b i n a r ys o r tt r e e ) 或者是一棵空树；或者是具有下列性质的二叉树： ( 1 ) 若它的左子树不空，则左子树上所有的结点的值均小于它的根结点的值：( 2 ) 若 它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；( 3 ) 它的左、 右子树也分别为二叉排序树【”】。 我们把所有字符串类型终结符号的首字符取出，建立一棵二叉排序树，把第 一个终结符号的首字符作为二叉排序树的根结点，以后的每个终结符号的首字符 按照其a s i i c 码的大小顺序插入这棵二叉排序树。 所有的相同首字符的终结符号的第二位字符取出建立另一棵二叉排序树，如 a b c 、a c d 、a f e 三个字符串的首字符相同，它们的第二位字符b 、c 、f 就要建立一 棵二叉排序树。 所有前n 位字符( c h a r n ) 相同的字符串，将它们第n + i 位字符取出建立出一 棵二叉排序树。 若字符串类型终结符号中最长为m 位，我们将建立m 组二又排序树，我们称 由第n 位字符构成的二叉排序树为第n 代二叉排序树。 我们把所有的合法终结符号的所有前缀称为状态，如a b c 有四个状态：，a ， ”a b ”，”a b e ”。其中”被称为初始状态，”a b e ”被称为终结状态或最终状态，其余的 状态被称为中间状态。 一棵第n 代二叉排序树是由i j n 1 位字符相同的字符串类型终结符号的第n 位字符建立的，显然这些终结符号有共同的n 1 位前缀。我们称这个n 1 位前缀 是这棵第n 代二叉排序树所属于的状态。第一代二叉排序树所属于的状态为。 我们称上述n 代二叉排序树为匹配树。 例：所有字符串类型的终结符号定义如下： ”+ ”，”，叫，”， ”，”& ”，”( ”，”) ”，”，”，”，”一，” ”，” = ”，”， ”t r u e ”，”f a l s e ”，”粕i v o ! ”，”# n a ”，”州蝴e ? ”，”拌n u l l n ”群r e f ! t ，”# l l u e ! - - ”婀、兀m i ! ”。 它们的首字符建立的二叉排序树，也就是第一代二叉排序树如图2 1 所示： 9 图2 - 1 第一代二义排序树 f i g u r e2 - 1f i r s tg e n e r a t i o nb i n a r ys o r tt r e e 首位字符相同的情况统计如下： ” ”，” ” = ” ”# d i v o ! t t ，”# n a ”，”荆a m e ? ”，”舯4 u l l ! t ，”撑r e f ! t ，”撑v a l u e ! t ，”挣n u m ! ” 分别建立第二代二叉树图2 2 所示： 曰 匝巫至习 图2 - 2 第二代二叉排序树 f i g u r e2 - 2s e c o n dg e n e r a t i o nb i n a r ys o r tt r e e 前两位字符相同的情况如下： ”# n a ”，”# n a m e ? ”，”# n u l l ! ”，”# n u m ! ” 建立第三代二叉树如图2 - 3 所示： 1 0 业塞銮通太堂亟堂焦逾童公式蚤法 图2 - 3 第三代二义排序树 f i g u r e2 - 3t h i r dg e n e r a t i o nb i n a r ys o r tt r e e 没有更多位i j 缀相同的情况，以下是前缀唯一的串的前缀树，这些树都只有 一个根结点，如图2 - 4 至2 1 2 所示： t r u e ( 所属状态分别为：”r ，”t r ”，”t r u ”) ： 口田口 图2 - 4 二二义排序树 f i g u r e2 - 4b i n a r ys o r tt r e e f a l s e ( 所属状态分别为：”f ”，”f a ”，”f a l ”，”f a l s ”) ： 口口口口 图2 - 5 二义排序树 f i g u r e2 - 5b i n a r ys o r tt r e e ”# d i v 01 ”( 所属状态分别为：”拌d ”，”# d i ”，”# d i v ”，”# d i v ”，”# d i v 0 ”) ： 田田口田口 图2 - 6 二叉捧序树 f i g u r e2 - 6b i n a r ys o r t t r e e j b 童銮道太堂亟堂僮j 金室公式亟洼 ”# n a ”( 所属状态分别为： # n a ”) ： 囚 图2 7 二义排序树 f i g u r e2 - 7b i n a r ys o r tt r e e # b l a m e ? ”( 所属状态分别为：”# n a ”，”# n a m ”，”# n a m e ”) ： 回田田 图2 - 8 二叉排序树 f i g u r e2 - 8b i n a r ys o r tt r e e ”# n u l l ! ”( 所属状态分别为：”# n u ”，”# n u l ”，”# n u l l ”) ： 口曰口 幽2 - 9 二义排序树 f i g u r e2 - 9b i n a r ys o r tt r e e ”# r e f ! ”( 所属状念分别为：”群r f f ，”# r e ”，”# r e f ”) ： 曰田口 图2 1 0 二叉排序树 f i g u r e2 - 1 0b i n a r ys o r tt r e e ”# v a l u e ! ”( 所属状态分别为：”挣v ”，”# v a ”，”# v a l ”，”# v a l u ”，”# v a l u e ”) ： 囚田团曰口 图2 - 1 1 二叉排序树 1 2 ”# n u m ! ”( 所属状态分别为：”枞u ”，”# n u m ”) ： 回口 图2 一1 2 二义排序树 f i g u r e2 - 1 2b i n a r ys o r tt r e e 所有二叉排序树建立完毕。 匹配过程 匹配过程就是待匹配字符串逐位取出，逐代遍历匹配树的过程。 在匹配时，驭出目标字符串的首字符c h a r i ，遍历第一代二叉排序树，若遍 历结束未能找到与匹配的串的首字符则不必再去比较第二位的字符c h a r 2 。若能 找到取出目标字符串的第二位字符，遍历属于状态c h a r l 的二叉排序树，若遍历 结束未能找到c h a r 2 则不必再去比较第三位的字符c h a r 3 ，若能找到c h a r 2 则继续在属于c h a r i + c h a r 2 的二叉排序树中遍历，这是一个递归过程。 若在一次遍历中未能找到与之相同的字符，则匹配失败，目标串不是合法的 字符串类型终结符号。若每次遍历都能成功，但目标串尚未结束，状态为c h a r n ， 而c h a r n 状态的二叉排序树为空，则匹配失败，目标串不是合法的字符串类型 终结符号，此时意味着，目标串的前缀是合法的字符串类型终结符号。其他的情 况都匹配成功。 例l ：”+ ” 在”t 状态的二叉排序树上遍历时找到此串的第一个字符”，并且此串仅有一 个字符，则此串为合法终结符号。 例2 ：”# r e f ! ” 在m t 状态的二叉排序树上遍历时找到此串的第一个字符”掸”；此串尚未结束， 到”# ”状态的二叉排序树上遍历寻找第二位字符”r ”，找到此字符；此串尚未结束， 到”撑r ”状态的二叉排序树上遍历寻找第二位字符”e f i ，找到此字符；此串尚未结束， 到”# r e ”状态的二叉排序树上遍历寻找第二位字符”f ”，找到此字符；此串尚未结 束，到”# r e f ”状态的二叉排序树上遍历寻找第二位字符”! ”，找到此字符；此串已 结束，则此串为合法终结符号。 例3 ：”撑r e f ! a ” 在”状态的二叉排序树上遍历时找到此串的第一个字符”撑”；此串尚未结束， 到”撑”状态的二叉排序树上遍历寻找第二位字符”r ”，找到此字符；此串尚未结束， j b 塞銮邋太堂亟堂焦i 金塞公式进造 到”根”状态的二叉排序树上遍历寻找第二位字符”f ，找到此字符；此串尚未结束， 到”# r e ”状态的二叉排序树上遍历寻找第二位字符”f 一，找到此字符；此串尚未结 束，到”# r e f ”状态的二叉排序树上遍历寻找第二位字符”! ”，找到此字符；此串尚 未结束，到”# r e f ! ”状态的二叉排序树上遍历寻找第二位字符”a ”，”# r e f i ”状态的 二叉排序树为空，则此串为非法终结符号。 例4 ：”# r e b ” 在”状态的二叉排序树上遍历时找到此串的第一个字符”# ”；此串尚未结束， 到”# ”状态的二叉排序树上遍历寻找第二位字符”掣，找到此字符；此串尚未结束， 到”群r ”状态的二叉排序树上遍历寻找第二位字符”e ”，找到此字符；此串尚未结束， 到”# r e ”状态的二叉排序树上遍历寻找第二位字符”b ”，未找到此字符，则此串为 非法终结符号。 程序实现 为实现上述算法，我们设计了a u t o m a t o n 、a u t o m a t o n t r e e 和s t r i n g t o k e n m a t c h e r 三个类。 有穷状态自动机( f i n i t ea u t o m a t o n ，f a ) m 是一个五元组： m = 旧，j ，q o f j 其中： q 状态的非空又穷集合。v g q ，g 称为吖的一个状念( s t a t e ) 输入字母表( i n p u t a l p h a b e t ) 。输入字符串都是上的字符串。 j 状态转移函数( t r a n s i t i o nf u n c t i o n ) ，有时又叫作状态转移函数或者移动 函数，艿：q x z 寸q 。x 寸v ( q ，4 ) q x x ，6 ( q ，口) = ，表示m 在状态g 读入字? c a ，将 状态变成p ，并将读头向右移动一个带方格而指向输入字符串的下一个字符。 吼肘的开始状态( i n i t i a ls t a t e ) ，也可叫作初始状态或者启动状态，g o q 。 ，m 的终止状念( f i n a ls t a t e ) 集合，f q 。v q f ，g 称为m 的终止状 态。 应当指出的是，我们虽然将f 中的状态称为终止状态，并不是说m 一旦进入 这种状态就终止了，而是说m 一旦在处理完输入字符串时到达这种状态，肘就是 接受当前处理的字符串。所以，有时我们又称终止状态为接受状态( a c c e p ts t a t e ) 。 对于任意的q q ，a ，a ( q ，口) 均有确定的值，所以，我们将这种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 i o n , d f a ) t 1 2 1 1 孔。 a u t o m a t o n 二叉排序树所属状态的类。 1 4 j b 塞交强太堂亟堂焦j 金塞公式蚤洼 此类实现了一个确定性有限状态自动机( d f a ) 。在字符串逐位匹配的过程中， 字符串经历了一系列状态。例如字符串n # n u l l ! ”在匹配过程中要经历如下状态的 变迁：一，”撑”，t 愀”，”# n u ”，”朴l ，”# n u l l ”，”# n u l l ! ”，其中只有最终状 态”# n u l l ! ”状态是合法的终结符号，其余的中间状态都是这个终结符号的前缀。 a u t o m a t o n 实例化后的对象就代表了上述状态，并且它们具有接受输入并变迁 到另一状态的能力。 a u t o m a t o n 类有两个私有属性，一个公有构造函数，两个共有方法。具体如下： 方法： a d d m a t c h o ：v o i d 返回值，为新输入的合法终结符号添加匹配，也就是建立 这个终结符号的所有状态并把它们都添加到各个排序树中。 m a t c h f r o m 0 ：v o i d 返回值，为输入的目标串查找匹配，判断是否为合法终结 符号，也就是在各个排序树中依次寻找目标串的所有状态，若能找到最终状态， 则匹配成功，若未能找到，则匹配失败。 属性： t r e e ：a u t o m a t o n t r e e 类型属性，假如当自口状态非最终状态，其值当前状态的 排序树；假如当前状念非最终状念，其值为空树。 v a l u e ：o b j e c t 类型属性，状念，假如当6 u 状态是最终状念，其值为终结符号； 假如当前状态非最终状态，因为我们并不关心中问状念，所以其值为空。如状态 为”# n u l l ! ”则其值”# n u l l ! ”：如状态为”# n u l ”其值为空。 a u t o m a t o n t r e e 实现了二叉排序树结点的数据结构，它有四个私有属性，一个公有构造函数， 两个共有方法。具体如下： 方法： a d d ( ) ：v o i d 类型返回值。把状态和当前字符封装成一个树结点并插入到当前 树。 f i n d ( ) ：v o i d 类型返回值。在当前树中中序遍历，寻找指定字符的结点。 属性： l e f t ：a u t o m a t o n t r c e ，左子树根结点。 r i g h t ：a u t o m a t o n t r c c ，右子树根结点。 s t a t e ：a u t o m a t o n , 所属的状态。 v a l u e ：c h a r 类型属性，结点中字符的值，初始置”、o ，代表空结点。 s t r i n g t o k e n m a t e