描绘，更多精彩；缔造，一个神话！
字号：大 中 小
XPATH 所使用的表达式语言，主要由两个部分组成: 表达式语言和xpath的路径搜索表达式.&&& 1. 表达式语言, 由+, -, *, /, or, and, not和数值,字符串,函数等组成, 符合正规语法.&&& 2. XPath路径搜索表达式, 是指在xml文档中搜索某个xml node的表达式.比如/books/book,搜索books节点下的所有book字节点. 具体可以参考中关于xpath的描述。
要实现一个完整的xpath解析器，基础就是实现其表达式语言解析和xpath路径搜索。由于目前只实现了xpath路径搜索部分，这儿只简单介绍路径搜索的实现办法。
xpath路径表达式的主要组成部分是3个：&&&& 分隔符："//", "/", '[', ']', ":",...&&&& 节点名：如/books/book路径， books和book都是节点名。&&&& 属性名：如/books/book[@title="123*"], title就是一个属性名xpath路径表达式也完全符合正规表达式，其词法分析和语法分析有3种实现办法：状态机语法分析，正则表达式比配，以及lex/yacc. 状态机语法分析实现和维护都很方便，缺点是要代码实现不是很容易扩展;正则表达式匹配容易实现，也容易扩展，缺点是性能交差；lex/yacc也容易实现和扩展，缺点是对Unicode支持不好，而xpath是xml的一个组成部分，支持Unicode是基本要求。由于xpath语法已经比较完善，个人选择状态机的方式实现词法和语法分析。简单的构架如下：&&&& xpathtoken, 用于从输入的xpath表达式中取出一个token, 可能是一个分隔符，一个节点名，或者一个属性名；&&&& xpathparser, 使用xpathtoken读出每个token,然后将这些token组装成有意义的xpath语法，同时进行语法检查；&&&& xpathdocument, 根据解析出的xpath语法，从一个xml文档中搜索相应的节点;xpathdocument的实现是xpath路径搜索的难点所在，由于xpathdocument需要根据xpath表达式去遍历xml节点，因此xml parser最好完整实现xml dom level2中关于遍历xml树的功能部分，举例如下：一个简单的xml 文档结构如下：&books&&&&& &book&&&&&&&&&&& &title&book1&/title&&&&&&&&&&& &author&author1&/author&&&&& &/book&&&&& &book&&&&&&&&&&& &title&book2&/title&&&&&&&&&&& &author&author2&/author&&&&& &/book&&books&然后使用如下xpath表达式：//book/title, 目标是搜索所有的book的title.在xpath解析器解析该xpath表达式并进行搜索的时候，具体的步骤可以做如下分割：1.&& 创建一个xpathparser对象，导入xpath表达式//book/title.2.&& 创建一个xmldocument对象，导入xml文档3.&& 根据xpathparser去遍历xmldocument, 首先xmlparser找到"//book",其意义是找到所有名字叫"book"的节点。可以使用xmldocument的getelementbyname来取得所有的book节点；然后xmlparser找到"/title", 其意义是取得当前结果集下的所有title节点。需要遍历当前结果集，查询其下的title节点。
上叙就是个人在实现一个xpath路径解析器中的细节记录。整体来说，实现xpath路径解析器算是比较容易，而xpath的表达式语言部分就相对复杂多了，个人正在努力中。
function open_phone(e) {
var context = document.title.replace(/%/g, '％');
var url = document.location.
open("/ishare.do?m=t&u=" + encodeURIComponent(url) + "&t=" + encodeURIComponent(context) + "&sid=70cd6ed4a0");
！觉得精彩就顶一下，顶的多了，文章将出现在更重要的位置上。
请根据下图中的字符输入验证码：
(您的评论将有可能审核后才能发表)
已成功添加“”到
请不要超过6个字trackbacks-0
这篇文章阐述了如何用正则表达式构造语法树并生成ε-NFA，去除ε边转换到NFA，最后转换到DFA的所有过程。学习编译原理的朋友们如果遇到什么问题不妨看下这篇文章。
阅读(2914)
&re: 用正则表达式构造词法分析器
跟我写过的那篇真是像啊。&&&&&&
&re: 用正则表达式构造词法分析器
@陈梓瀚(vczh)
参照了你那篇写出来的..不过代码出入比较大..&&&&&&
&re: 用正则表达式构造词法分析器
@lwch
连图都……&&&&&&
2017年10月
24252627282930123456789101112131415161718192021222324252627282930311234
随笔分类(92)
随笔档案(91)
积分与排名
阅读排行榜
评论排行榜[编译原理读书笔记][第3章 词法分析] - DDUPzy - 博客园
[编译原理读书笔记][第3章 词法分析]
标签（空格分隔）： 未分类
本章我们主要讨论如何构建一个词法分析器
首先建立起每个词法单元的词法结构图或其他描述.
编写代码识别输入中出现的每个词素,并返回识别到词法单元的有关信息
词法分析器生成工具(lexical-analyzer generator)
描述出词素模式,然后将这些模式编译为具有词法分析功能的代码.
程序员只要在抽象很高的层次上描述软件,就能生成代码.
3.5节将介绍一个名为Lex分析器生成工具
正则表达式
正则表达式是一种很方便描述词素模式的方法.
我们将介绍正则表达式进行转换:
首先转换为不确定有穷自动机.
然后转换为确定又穷自动机.
驱动程序就是模拟这些自动机的代码,使用自动机确定下一个词法单元.
驱动程序和自动机的规约形成词法分析器的核心部分.
3.1 词法分析器的作用
词法分析是编译的第一阶段.
词法分析器的主要任务是
1.读入源程序的输入字符
2.将他们组成词素,生成并输出一个词法单元序列,每个词法单元对应一个词素.
词法分析,语法分析,符号表的交互
getNextToken所指示的调用使得词法单元从它的输入不断读取字符,直到识别到下一个词素为止.
词法单元根据词生成一个词法单元返回给语法分析.
词法分析其余任务
过滤注释和空白
编译器生成的错误信息,和源代码的位置练习起来
有时候,词法分析分成两个级联处理
扫描阶段: 不生成词法的单元的简单处理:删除注释和将多个空白压缩成一个
分析极端:处理扫描阶段的输出,返回词法单元
3.1.1 词法分析及语法分析
把编译阶段的分析部分化为词法分析和语法分析阶段有如下几个原因:
最重要的考虑是简化编译器设计
提高编译器效率(因为能专精)
增强编译器的可移植性.
3.1.2 词法单元,模式和词素
三个相关但有区别的术语.
词法单元:由一个词法单元名和一个可选属性组成.
词法单元名:是一种表示某种词法单元的抽象符号.
比如一个关键词,标识符的输入字符序列.
词法单元名是由语法分析处理的输入符号.
通常用黑体字表示词法单元名
模式:描述一个词法单元的词素可能具有的形式.
词法单元是关键词时:
模式是组成这个关键词的字符序列
对于标识符和其他词法单元:
模式是一个更加复杂的结构,可以和很多符号串匹配.
正则表达式
词素:是源程序的一个字符序列.
和某个词法单元的模式匹配
被词法分析器识别为该词法单元的一个实例.
在很多程序设计语言中,下面类别覆盖了大多数词法单元
每个关键词有一个词法单元.
一个关键词的模式是他本身.
表示运算符的词法单元
表示所有标识符的词法单元
一个或多个表示常量的词法单元
每一个标点符号 有一个词法单元
3.1.3 词法单元的属性
词法单元的属性:如果多个词素可以和一个模式匹配,那么词法分析器必须向编译器的后续阶段提供被匹配词素的附加信息.
一个标识符的属性值是一个指向符号表中该标识符条目的指针.
3.1.4 词法错误
如果没有其他组件帮助,词法分析器很难发现源代码的错误.
fi(a==f(x))
词法分析器会当做一个标识符作为词法单元传给语法分析器
这个错误将由语法分析器处理.
恐慌模式:所有词法单元都无法和剩余输入的某个前缀相匹配时的策略
我们从剩余的输入不断删除字符,直到词法分析器能够在剩余的开头发现一个正确的词法单元为止.
3.1.5 练习
&float& &id, limitedSquaare& &(& &id, x& &)& &{&
&float& &id, x&
&return& &(& &id, x& &op,"&="& &num, -10.0& &op, "||"& &id, x& &op, "&="& &num, 10.0& &)& &op, "?"& &num, 100& &op, ":"& &id, x& &op, "*"& &id, x&
&text, "Here is a photo of"& &nodestart, b& &text, "my house"& &nodeend, b&
&nodestart, p& &selfendnode, img& &selfendnode, br&
&text, "see"& &nodestart, a& &text, "More Picture"& &nodeend, a&
&text, "if you liked that one."& &nodeend, p&
3.2 输入缓冲
讨论几种可以加快源程序读入速度的方法.
我们将介绍一种双缓冲区方案
这种方案能安全处理向前看多个符号问题.
-,=,& 可能是-&,==,&=这样双字符运算符的开始.
我们将考虑一种改进方法,这种方法用哨兵标记来节约检查缓冲区末端的时间.
3.2.1 缓冲区对
何为缓冲区对?
由于在编译一个大型程序需要处理大量的字符,处理这些字符需要很多时间,由此开发了一些特殊的缓冲技术来减少用于处理单个输入字符的时间开销.一种重要机制是利用两个交替读入的缓冲区.
缓冲区具体
每个缓冲区容量都是N个字符,通常N是一块磁盘块大小,如4096字节
程序为输入维护了两个指针
lexemeBegin指针:该指针指向当前词素的开始处.当前我们正试图确定这个词素的结尾.
forward指针:它一直向前扫,直到发现某个模式被匹配到为止
做出这个决定的策略在之后描述.
一旦确定下一个词素,forward指针将指向该词素结尾的字符.
词法分析器将这个词素作为某个词法单元记录下来并返回.
然后使lexemeBegin指针指向刚找到词素后的第一个位置
处理完后,forward指针也会前移一个位置
如果forward指针前移超过缓冲区末尾(哨兵标记优化的地方)
将N个新字符读到另一个缓冲区末尾,且将forward指针指向这个新载入符的头部.
3.2.2 哨兵标记
如何优化检测缓冲区末尾呢?
思考之前的有两步操作
检查是否到了末尾
确定读入的字符
将两步合二为一
在缓冲区末尾扩展一个绝对不会使用的符号,叫做哨兵(sentinel)字符,一个自然的选择是eof.
3.3 词法单元的规约
正则表达式是一种用来描述词素模式的重要表示方法.
虽然不能表达所有可能的模式,但能高效描述在处理词法单元时要用到的模式类型.
这一节我们将研究正则表达式的形式化表示方法
在3.5节中 我们将看到如何将正则表达式用到词法分析生成工具中.
在3.7节中 我们将学到如何能将正则表达式转换为能够识别词法单元的自动机,并由此建立一个词法分析树.
3.3.1 串和语言
字母表(alphabet)是一个有限的符号集合.
如{0,1},ASCII,Unicode .
某个字母表的串(string)是该字母表符号的有穷序列.
语言(language)是某个给定字符表上任意的可数的串的集合.
字符串的指数运算
3.3.2 语言上的运算
在词法分析,最重要的语言上的运算是并,连接,和闭包运算.
3.3.3 正则表达式
正则表达式可以由较小的正则表达式按照如下规则递归地构建.
每个正则表达式r表示一个语言L(r),也是根据r的子表达式所构建的语言递归构造.
某个字母表Σ上的正则表达式以及这些表达式所表示的语言
根据优先级丢掉括号
一元运算符*是最高级,并且是左结合.
链接运算符次高的优先级,也是左结合
|的游戏级最低,也是左结合.
将 (a)|((b)*(c))改写为a|b*c
可以用同一个正则表达式定义的语言叫做正则集合(regular set)
如果两个正则表达式r和s表示的语言相同的语言,则称两者等价,记做r=s.
正则表达式遵守一定的代数定律
3.3.4 正则定义
为方便表示,我们可能希望给某些正则表达式命名,并在之后像使用符号一样使用这些名字,这叫做正则定义(regular definition)是具有如下形式的定义序列:
每个di都是一个新符号,不在Σ中,并且各不相同.
每个ri是字母表`Σ U {d1,d2,...di-1}上的正则表达式.
可以看出 递归定义是正则表达式的很重要的性质
3.3.5 正则表达式的扩展
除了以上的运算,在现代像Lex这样的实用Unix程序都有对正则的扩展
一个或多个实例:+
单目后缀运算符+表示一个正则表达式及其语言的正闭包.
(r)+ 意思为 (L(r))+
+与*有相同的优先级
零个或一个实例:?
单目后缀运算符?的意思是零个和一个出现.
r?等价于r|空集
?与+与*有相同的运算集
一个正则表达式 a1 | a2 |...|an可以缩写为[a1a2...an]
如果a1,a2,a2还具有逻辑关系,可以缩写为[a1-an]
例如[1-9],[a-z]
3.3.6 3.3练习
\/\*([^*"]*|".*"|\*+[^/])*\*\/
先解决比较简单的{0,1,2}
0?1?2?|0?2?1?|1?0?2?|1?2?0?|2?0?1?|2?1?0?|
want -& 0|A?0?1(A0?1|01)A?0?|A0?
A -& 0?2(02)
证明如下面的图
b* | b*a+ | b*a+ba*
###Lex的扩展方法:
###如何引用这些被使用的符号
#3.4 词法单元的识别
我们学习如何根据各个需要识别的词法单元的模式来构造一段代码.
识别检查输入的串,并找到匹配的词素.
3.4.1 状态转换图
词法分析器的中间步骤,将模式转换为状态转换图
本节用人工方式,将正则表示的模式转换为状态图
3.6节介绍一种使用自动化方法来进行
状态转换图有一组被称为状态的结点和圆圈.
3.4.2 保留字和标识符的识别
我们可以用两种方法处理像标识符的保留字.
初始化时将保留字填入符号表
为每个关键字建立单独的状态转换图
3.4.3 完成我们的例子
3.4.4 基于状态转换图的词法分析器的体系结构
有几种方法根据一组状态图构造出词法分析器.
根据这个状态图,写出getRelop()函数
函数fail()具体操作依赖于全局恢复策略
将forward指针重置为lexemeBegin的值
使用另一个状态图从尚未处理的输入部分的真实位置开始识别.
将state改为另一状态图的初始状态,将寻找别的词法单元
当所有状态图都已经试过,fail()启动一个错误纠正步骤.
状态8,带有*,输入指针会回退,c放回输入流
由retract()完成
状态图的执行
合并(麻烦)
3.4.5 3.4的练习
3.5 词法分析器生成工具 Lex
介绍一个名为Lex的工具,在最近的实现中也称为Flex.
支持使用正则表达式来描述词法单元的模式,给出一个词法分析器的规约
输入表示方法叫做Lex语言,工具本身是Lex编译器.
核心部分: 根据模式,生成转换图,生成相应代码,存放到lex.yy.c中
3.5.1 Lex的使用
a.out 通常是语法分析器调用的子例程
子例程通常返回一个整数值,代表词法单元的编码
词法单元的属性值,保存在全局变量yylval中
这个变量由语法分析器,词法分析器共享.
3.5.2 Lex 程序的结构
声明部分包括变量和明示常量(manifest con-stant)和正则定义
明示常量,表示一个常数的标识符
Lex的转换规则有如下形式
模式 {动作}
每个模式是一个正则表达式,可以使用声明部分的正则定义.
动作部分是代码片段,一般是C语言
Lex第三个部分包含各个动作要的辅助函数.
还有一种方法将这些代码单独编译,一起装载
lex词法分析器和语法分析器的协同
当词法分析器被语法分析器调用时,词法分析从余下输入逐个读取字符.
直到发现最长的与某个模式Pi匹配的前缀.
然后词法分析器执行动作Ai.
通常Ai会返回语法分析器
如果不返回控制,继续寻找其他词素,直到某个动作返回
词法分析器只返回一个值,即词法单元名
在需要时,通过yylval传递词素附加信息
处理名为ID的词法单元的时候
3.5.3 Lex中的冲突解决
总是选择最长的前缀
如果最长的前缀与多个模式匹配,选择声明靠前的那个.
3.5.4 向前看运算符
某些时候,我们希望仅仅词素后面跟随特定字符,才能和模式匹配.
这种情况,我们使用/之后跟随表示一个附加的模式.
附加部分能匹配,但最后不属于词素
3.6 有穷自动机
揭示Lex如何将输入程序转换为词法分析器,核心在于有穷自动机
这些自动机本质和转换状态图类似,但也有以下不同
有穷自动机是识别器(recognizer).
只能对每个输入串简单的回答 是,否.
有穷自动机分为两类
不确定的有穷自动机(NFA):对其边上的标号没有任何限制,一个符号可以标记离开同一个状态的多条边.
确定的有穷自动机(DFA):对于每个符号,有且一条离开该状态的边.
确定和不确定的能识别的语言的集合是相同的,恰好也是正则表达式能识别的集合,这个集合的语言叫做正则语言
3.6.1 不确定的有穷自动机
一个NFA由以下部分组成
一个有穷状态集合S
一个输入符号集合Σ,即输入字母表.
假设空串不在这个集合.
一个转换函数,他为每个状态给出了相应的后继状态.
S中的s0被称为开始状态
S的一个子集F被称为接受状态
跟转换图有以下区别
同一个符号可以标记同一状态到达多个目标状态的多条边.
一个边的标号不仅可以是输入字母表的字符,也可是空串
(a|b)*abb的NFA转换图
3.6.2 转换表
3.6.3 自动机输入字符串的接受
一个NFA接受输入字符串x,**当且仅当对应的转换图中存在一条开始状态到某个接受状态的路径,使得路径中各条变上的标号组成字符串x.
注意:路径的ε被忽略
我们可以用L(A)表示自动机A接受的语言
3.6.4 确定的有穷自动机
在构造词法分析器时,我们真正实现和模拟的是DFA.
?幸运的是,每个正则表达式和每个DFA都可以转变为接受相同语言的DFA.
如何用DFA进行串的识别(十分简单)
3.7 从正则表达式到自动机
首先介绍如何把NFA转换为DFA.
利用子集构造法的技术给出一个直接模拟NFA的算法
这个算法可用于那些将NFA转化为DFA比直接模拟NFA更加耗时的(非词法分析)情形
接着,我们介绍正则表达式转为NFA
在必要时刻,根据这个NFA构造DFA
最后讨论不同正则表达式实现技术的时间-空间权衡,并说明如何选择正确的方法.
3.7.1 从NFA到DFA的自动转换
子集构造法的基本思想:是让构造得到的DFA的每个状态对应于NFA的一个状态集合.
DFA在读入输入a1a2...an之后到达的状态对应于相应NFA从开始状态出发,沿着以a1a2...an为标号走到的路径能够到达状态的集合.
DFA状态数可能是NFA状态数的指数,此时试图实现这个DNA有点困难.
然而,基于自动机的词法分析方法的处理能力部分基于这个事实:
对于一个真实的语言,它的NFA和DFA的状态数量大致相同,状态数量呈指数尚未在实践中出现
子集构造算法
输入: 一个NFA N
输出: 一个接受同样语言的 DFA D
方法: 我们的算法为D构造一个转换表Dtran.
D的每个状态是一个NFA状态集合,我们将构造Dtran,使得D "并行的" 模拟N在遇到一个给定输入串可能执行的所有动作.
第一个问题:正确处理N的`转换.
给出一些基本操作 s表示N的单个状态,T表示一个状态集.
算法代码(有ACM功底很容易懂):
D的开始状态是ε-closure(s0),D的接受状态是所有至少包含N的一个接受状态的状态集合,
ε-closure(T)代码,一个简单的深搜而已
A和C可以合并,将在后面介绍DFA的最小化问题.
3.7.2 NFA的模拟
许多的文本编辑器使用的策略是根据一个正则表达式构造出相应的NFA,然后使用类似于on the fly(边构造边)的子集构造法来模拟这个NFA的执行.
算法:模拟一个NFA的执行
也类似广搜,一步一步把所有情况跑一遍.
3.7.3 NFA模拟的效率
更详细的介绍这个算法
需要以下数据结构
两个堆栈,其中每个堆栈都存放了一个NFA状态集合.
堆栈oldStates存放 "当前状态集合"
堆栈newStates存放 "下一个状态集合"
一个以NFA状态为下标的布尔数组 alreadyOn,指示那个状态已经在newStates.
一个二维数组 move[s,a],保存了这个NFA的转换表,是一个邻接表(因为转换表单元格有多个元素).
既然书说他是O(k(m+n))复杂度...那就是吧
3.7.4 从正则表达式构造NFA
现在给出一个算法,它可以将任何正则表达式转为接受相同语言的NFA
这个算法是语法制导的,沿着正则表达式的语法分析树自底向上递归处理.
对于每个子表达式,该算法构造一个只有一个
算法 3.23 将正则表达式 转换为一个NFA的McMaughton-Yamada-Thompson算法
几个有趣的性质
N(r)的状态数最多是 r中出现的运算符和运算分量的总数的2倍.
N(r)有且只有一个开始状态,接收状态没有出边,开始状态没有入边.
除接受状态,都最多有一条带字符的出边,最多有两条空边
3.7.5 字符串处理算法的效率
子集构造法 : O(|r|^2 * DFA状态数) DFA状态数一般是|r|
模拟算法: O(|r|*|x|)
3.8 词法分析器生成工具的设计
应用3.7中介绍的技术,讨论Lex这样生成工具的体系
将讨论基于NFA和DFA的方法,后者实质上就是Lex的实现方法
3.8.1 生成的词法分析器的结构
3.8.2 基于NFA的模式匹配
沿着状态集回头寻找直到有一个完成状态
3.8.3 词法分析器使用的DFA
3.8.4 实现向前看运算符/
3.9 基于DFA 的模式匹配器的优化
本节给出三个算法,用于实现和优化根据正则表达式构建的模式匹配器
第一个算法可以用于Lex编译器
可以不用经过构造中间NFA就能构建DFA,
得到的DFA状态数也比经过中间NFA得到的DFA状态数少
第二个算法,可以将任何DFA未来具有相同行为的状态合并.
算法复杂度O(nlogn)
第三个算法,可以生成比标准二维表更加紧凑的转换表方式.
3.9.1 NFA的重要状态
如果一个NFA状态有一个标号非ε的离开转换,则称这个状态是重要状态(important state)
ε-closure(move(T,a)),它只使用了集合T中的重要状态.
只要当集合s是重要状态时,move(s,a)才可能是非空的.
在子集构造法中,两个NFA状态可以被认为是一致的的条件是:
1.具有相同的重要状态
2.要么包含接受状态,要么都不包含接受状态.
一致的意思是把它们当做同一个集合来处理.
正则转换的NFA
如果NFA由正则表达式生成,还有更多关于重要状态的性质
重要状态只包括在基础规则部分为正则表达式中某个特定符号位置引入的初始状态.
也就是说,每个重要状态对应于正则表达式某个运算分量.
在正则表达式后面加一个#变为(r)#,使得原本的接受状态变为重要状态,使得在构造过程中,不要考虑接受状态.
(r)#又叫扩展的正则变道时
使用抽象语法树表示扩展的正则表达式.
叶子节点代表运算分量
内部节点表示运算符号
整数叫做叶子节点的位置,也表示他对应符号的位置
一个符号可以有两个位置:比如a有1和3
3.9.2 根据抽象语法树计算的到的函数
要做一个正则表达式直接构造出DFA,我们首先要构造它的抽象语法树
然后计算如下四个函数:nullable,firstpos,lastpos和followpos.
都是在(r)#下进行的.
nullable(n):对于一个节点n当且仅当此节点代表的子表达式中包含空串ε返回真
子表达式可以生成空串或者自己就是空串,即使能生成一些其他串
firstpos(n):以节点n为根的子树中的位置集合.
这些位置对应于以n为根的子表达式的语言中某个串的第一个符号.
lastpos(n):以节点n为根的子树中的位置集合.
这些位置对应于以n为根的子表达式的语言中某个串的最后一个符号.
followpos(p):定义了一个和位置p相关的,某些位置的集合.
一个位置q在 followpos(p)中当且仅当存在L((r)#)中的某个串x=a1a2...an,使得我们在解释为什么x属于L((r)#)时,可以将x中某个ai可以和位置p匹配,且将位置ai+1和位置q匹配
3.9.3 计算nullable,firstpos和lastpos
直接树形递归就行
3.9.4 计算followpos
只有两种情况,正则表达式某个位置会跟在另一个位置之后
如果n是一个cat节点,且左右节点是c1,c2.
那么对于lastpos(c1)中的每个位置i,firstpos(c2)中的所有位置都在followpos(i)中.
如果 n 是 star节点,并且i是 lastpos(n)中的一个位置,那么firstpos(n)中的所有位置都在followpos(i)中.
3.9.5 根据正则表达式构建DFA
算法3.3.6 从一个正则表达式r构造DNF
根据扩展表达式(r)#构造出一颗抽象语法树T
计算T的函数nullable,firstpos,lastpos,followpos
使用下列程序,构造出D的状态集Dstates和D的转换函数Dtran
3.9.6 最小化一个DFA的状态数
(数电中有提及)
任何正则语言都一个唯一的(不计同构)状态数目最少的DFA.,从任意一个接受相同语言的DFA出发,通过分组合并等价的状态,我们总是构建这个状态数最少的DFA.
该算法首先创建输入DFA的状态的集合的划分.
输入串如何区分各个状态:
如果分别从状态s和t出发,沿着标号为x的路径到达的两个状态中只有一个是接受状态,我们说串x区分状态s和状态t的串
如果存在一个串能区分s和t,那么他们是可区分的.
DFA状态最小化的工作原理是将一个DFA的状态集合分划成多个组,每个组中的各个状态之间相互不可区分.
之后就类似于缩点的算法.
3.9.8 DFA模拟中的时间和空间权衡
转换链表压缩
一种方式,即有数组的便携,又有链表压缩的默认状态.
如何保存base值比较好
随笔 - 306编写自己的正则表达式解析器_算法_编程通用_或代码
| 文章 >> 编程通用 >> 算法
编写自己的正则表达式解析器
{S0}简介你有没有想过正则表达式的详细工作如何？如果答案是肯定的，那么这篇文章适合你。我会设法引导你一步一步如何创建自己的迷你正则表达式库。本文的目的是不给你一个高度优化，测试和伟大的正则表达式库，但解释后面的文本文件中的模式匹配的校长。如果你只想要一个好的图书馆，并不在乎它是如何工作的，您可能需要升压的regex库，你可以找到。我必须承认，我没有完全阅读文章，但在我看来，文章的重点主要是关于如何使用正则表达式库，由作者提供。在这篇文章中，笔者采用类似的技术（虽然我可能是错误的），以创建一个更复杂的库。您现在正在阅读的文章，可以被看作是为我刚才提及的文章的先决条件。正则表达式的MS。NET库或Java SDK（如果你写在Java代码中）。正如你可以看到，正则表达式在许多不同的编程语言和技术。其实的文章，不注重在具体的语言编写的库。我写在C代码，使用STL主要是因为它是我最喜欢的语言/库，但是从文章的原则可以适用于任何语言（显然）。我会尝试尽可能独立的语言，如可能的话使用伪代码。如果你想在Java代码中，请给我发送电子邮件。本文提供的代码是免费的（显然），但如果你喜欢它，并在您的应用程序中使用它，将是巨大的，如果你给我什么我应得的信贷。也请给我发电子邮件，所以我可以炫耀我的同行和/或潜在的雇主。概述那么如何我们要做到这一点？之前，我们开始与编码，这是必要的，需要充分了解这里本文中使用的方法来解释数学的背景的。我会强烈建议阅读和理解数学的背后，因为一旦我们克服了数学的一部分，其余的将是非常简单的。但是请注意，我不会有任何数学证明。如果你是在证明有兴趣，请检查出的引用，可以在本文的部分发现。此外，请注意，正则表达式解析器，我们将在这里创建将支持这三个操作:KLEEN封闭或星空运营商("*")级联（例如:"AB"）UNION运算符（与字符表示"|"）然而，许多额外的运营商可以模拟相结合，这三家运营商。例如:A = AA *（至少有一个一）[0-9] =（0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9）[Z] =（A |乙|...| Z）等。实施只有三家运营商的原因非常简单。当我开始打算写这篇文章时，我很快就认识到，我不得不限制自己在很多方面。主题是如此之大，它需要一本书来解释每一个小细节（也许我有一天会写）。正如我以上所述，本文的目的是，装备库，但向您介绍正则表达式背后的原则。如果你想知道更多关于如何使用正则表达式，那么你可以检查出书:精通正则表达式 - 奥赖利。以下为文章概述:
NFA的代表不确定的有限状态自动机。 NFA的可以被看作是一种特殊的最终状态机，这在某种意义上是一个抽象的模型与原始的内部存储器的机器。如果你想知道有关有限状态机的更多信息，请参阅下面一节。让我们来看看在NFA的数学上的定义。 NFA的一个组成:有限集我输入符号国家有限集S一个从S X我的下一个状态函数为P（S）一个接受状态的S的子集Q从S的初始状态S0表示为A（I，S，F，Q，S0）如果我们能解释12岁以上的定义，我们可以说，一个NFA是一个集合S的函数f连接的状态（可能是一个更聪明的12岁）。 NFAS代表两种格式:表和图。例如，让我们来看看表表示:输入国一b彗星ðEPSILONS0S1，S3
相当于图:表/图上面，我们可以看到，有特殊的转换称为EPSILON过渡，这是NFA的特色之一。过渡是一个从一个状态到另一个事件。 EPSILON过渡是一个从一个状态到另一个空字符串过渡。换句话说，我们会从一个状态到另一个上没有的字符输入。例如，我们可以看到从上面的表/图，我们可以从S3到S4和S5，这意味着我们有一个选择的输入。同样，有是有选择的字符输入A从状态S0，S1或S3国因此，名称不确定性，因为在某些时候，我们能去的路径是不是唯一的，但我们有一个选择。双盘旋像例如S6（或在"{}"中的表附后），最后接受国家制定。一旦达到这些国家之一，我们有一个接​​受的状态，因此一个接受字符串。在一个NFA，喜欢的数学上的定义定义，总是启动状态。我Graphvis，一个伟大的工具绘制不同类型的图表（见节），用于绘图NFAS和的DFA（见后）。由于Graphvis奠定了自身的图形的节点，它在我看来，启动状态总是在图的顶部绘制的状态。因此，我们将按照该公约。 DFA的代表确定性有限状态自动机。 DFA是非常密切的关系到NFA。事实上，NFA的数学定义为DFA的太。但明显存在着差异，从中我们就会乘虚而入。一个很大的区别是，在一个DFA有没有EPSILON转换。此外，每个国家，从这种状态下，所有过渡在不同的输入字符。换句话说，如果我们在状态s，然后输入一个字符，该字符从第一个独特的转型此外，所有国家在一个DFA，必须有一个输入字符有效的过渡。这里输入字符是有限的我输入符号（如在数学上的定义）。例如，在上面的图表（下DFA的），符号，我将{A，B，C，D}。现在，我们了解NFAS和的DFA，我们可以说，任何NFA的，有一个等价的DFA（您将不得不信任我，因为我不认为这是给你出发这句话的数学证明）。作为人类，通常它是我们更容易构造一个NFA，以及解释一个NFA的接受的语言。但是，为什么我们需要的DFA然后呢？那么，如果我们想对电脑，这是很难的"教"他们做的很好的教育的猜测（有时甚至是我们不能做出明智的猜测）。而这正是计算机需要做的，当遍历一个NFA的。如果我们写一个算法，它会使用NFA检查接受的字符组合，它会涉及检查的选择，它并没有使以前的回溯。显然，正则表达式解析器的工作使用NFAS，但他们通常比那些使用的DFA慢。这是由于这一事实，DFA有独特的道路，为每个接受字符串，所以没有涉及回溯。因此，我们要使用一个DFA，以检查是否输入字符的组合，是由一个自动机接受。注意:如果你真的想了解NFAS和的DFA的，我会建议做进一步阅读这些主题。它作为一个练习是有用的转换从一个到另一个，要充分理解上的差异，这里使用的算法转换NFA到DFA的（见后）。现在，我们所有数学的背景下，我们需要了解正则表达式，我们需要开始思考什么是我们的目标。作为第一步，我们意识到，我们需要从正则表达式的方式（如AB *（一个| B）*）的数据结构，这将是容易操作和使用模式匹配。但是，让我们先寻找一个正则表达式转换到NFA的方法。也许最有名的算法做这种转换是汤普森的算法。这种算法是不是最有效的，但它确保任何正则表达式（假设它的语法是正确的），将成功地转换为一个NFA的。随着从下图看到的基本NFA的的帮助下，我们可以构造任何其他:使用上述的基本要素，我们将构建三个操作，这是我们想实现我们像下面的正则表达式解析器:但是，我们如何从类似（A | B）* AB上面的图？如果我们认为我们真正需要做的，我们可以看到，评估正则表达式类似评估算术表达式。例如，如果我们想评价R = AB *光盘，我们可以做到这一点像:推 PUSH乙按C MUL添加 PUSH ð子的POP ř PUSH和POP栈和MUL，ADD和SUB采取从堆栈中的2个操作数，并做相应的操作。从正则表达式构造NFA的，我们可以使用这方面的知识。让我们来看看为了构造NFA的正则表达式（A | B），需要执行的操作序列* CD:推 PUSH b联盟之星按C CONCAT PUSH ð CONCAT的POP ř我们可以看到，这是非常相似的算术表达式的评价。不同的是明星操作，在正则表达式从堆栈中弹出只有一个元素，并评估星级操作员。此外，串联操作是没有任何符号表示，所以我们就检测到它。的文章中提供的代码，从而简化了前处理正则表达式，每当检测到串联插入一个字符的ASCII代码0x8问题。显然，这是可以做这个"飞"，在正则表达式的评价，但我想尽可能简化评估。前处理什么也不做，但检测的符号，例如一样，会导致在串联的组合:AB，（，），*，*（，）（。 PUSH和POP操作的实际工作与简单的NFA对象的堆栈。如果我们将推动在堆栈上的标志，操作将在堆上创建两个状态的对象，并创建一个过渡的象征，从状态1到状态2对象。这里是推动在栈上的一个字符的代码部分:无效CAG_RegEx:推（chinput的字符）{
/ /创建2堆新的国家
CAG_State * S0 =新CAG_State（m_nNextStateID）;
CAG_State * S1 =新CAG_State（m_nNextStateID）;
/ /添加输入字符S1从S0 - GT的过渡;
S0 - GT; AddTransition（chinput的，S1）;
/ /创建一个NFA的这2个国家
60; FSA_TABLE NFAT
NFATable.push_back（S0）;
NFATable.push_back（S1）;
/ /推入操作数栈
m_OperandStack.push（NFATable）;
/ /添加这个字符输入字符集
m_InputSet.insert（chinput的）;}我们可以看到，字符转换为一个简单的NFA，然后由此产生的NFA是添加到堆栈。 CAG_State类是一个简单的类，它可以帮助我们的结构，因为我们需要一个NFA的。它包含一个转换到其他国家的特定字符数组。 EPSILON过渡字符0x0的过渡。在这一点上，很容易看到背后NFA的结构。一个NFA和DFA存储作为一个国家的顺序（CAG_State deque的指针）。每个州作为一个成员，所有的转换存储在multimap中。过渡是没有别的比从字符映射到一个国家（CAG_State *）。 CAG_State类的详细定义，请参阅代码。现在回到正则表达式到NFA的转换。现在我们知道如何入栈NFA的，在弹出的操作实在是微不足道。检索从堆栈中的NFA，就是这样。正如我刚才所说，NFA的表被定义为一个双端队列（STL容器 CAG_State * GT）。这样，我们知道，数组中的第一个国家总是起始状态，而最后的状态是最后/接受状态。维护这个顺序，我们可以迅速获得的第一个和最后一个国家以及作为追加在前面加上更多的国家在执行操作时（如星运营商）。下面是代码评估每一个人的操作:BOOL CAG_RegEx:CONCAT（）{
/ /弹出2个元素
FSA_TABLE甲，乙;&
如果（POP（乙）| |！流行（一））
返回FALSE;
/ /现在评估AB
/ /基本上采取从最后状态
/ /添加一个EPSILON过渡到 
/ / B的商店，结果到的第一个国家
/ /新NFA_TABLE和入栈
[A.size（）-1] - GT; AddTransition（0，B [0]）;
B.end A.insert（A.end（），B.begin（），（））;
/ /入栈结果
m_OperandStack.push（一）;
返回TRUE;}我们可以看到，串联是从堆栈中弹出两个NFAS。第一NFA是改变，所以，现在是新的NFA，然后将其压入堆栈。请注意，我们第一个弹出第二个操作数。这是因为在正则表达式中，操作数的顺序的重要性是因为AB = BA（不可交换）BOOL CAG_RegEx:！:星（）{
/ /弹出1元
FSA_TABLE甲，乙;
;如果（！流行（一））
返回FALSE;
;/ /现在评估*
/ /创建2个新的国家，这将是插入&
/ /在每个deque的结束。还需要A和
/ /从去年EPSILON过渡到第一
/ /在队列中的状态。添加EPSILON过渡
/ /两个新的国家之间，插入一个
/ /在开始将源和一个
/ /插到底，将目标
CAG_State * pStartState =新CAG_State（m_nNextStateID）;
CAG_State * pEndState =新CAG_State（m_nNextStateID）;
pStartState - GT; AddTransition（0，pEndState）;
/ /添加EPSILON从开始的状态过渡到第一状态
pStartState - GT; AddTransition（0，A [0]）;
/ /添加从最后一个状态EPSILON过渡到最终状态
[A.size（）-1] - GT; AddTransition（0 pEndState）;
/ /从最后一个到第一个状态
[A.size（）-1] - GT; AddTransition（0，A [0]）;
/ /构造新的DFA和存储到堆栈
A.push_back（pEndState）;
A.push_front（pStartState）;
/ /入栈结果
m_OperandStack.push（一）;
星运营商从堆栈中弹出一个元素，改变它根据汤普森的规则（见上文），然后把它stack.BOOL CAG_RegEx:联盟（）{
/ /弹出2个元素
FSA_TABLE甲，乙;
如果（POP（乙）| |！流行（一））
返回FALSE;
/ /现在评估|乙
/ /创建2个新的国家，一开始状态和
/ /一个结束状态。从创建EPSILON过渡
/ /启动状态，一开始国家和B
60;/ /创建结束EPSILON过渡
/ /状态A和B的新的最终状态
CAG_State * pStartState =新CAG_State（m_nNextStateID）;
CAG_State * pEndState =新CAG_State（m_nNextStateID）;
pStartState - GT; AddTransition（0，A [0]）;
pStartState - GT; AddTransition（0，B [0]）;
#160; [A.size（）-1] - GT; AddTransition（0 pEndState）;
;乙 - GT; AddTransition（0，pEndState）;
60; / /创建一个新的NFA
B.push_back（pEndState）; &#
A.push_front（pStartState）;
B.end A.insert（A.end（），B.begin（），（））;
/ /入栈结果 &#
m_OperandStack.push（一）;
返回TRUE;}最后，联盟弹出两个元素，使改造，并将结果在栈上。请注意，我们在这里要留意的经营秩序。最后，我们现在能够评估正则表达式。如果一切顺利，我们将在堆栈上的单一的NFA，这将是我们造成的NFA。下面的代码，利用上述functions.BOOL CAG_RegEx::CreateNFA（字符串strRegEx）/ /解析定期expresion使用类似
/ /方法来计算算术表达式
/ /但是，首先我们会检测连接和
/ /插入CHAR（8）的位置
60; / /级联需求发生
strRegEx = ConcatExpand（strRegEx）;
（我= 0; ILT; strRegEx.size（）;我） 
/ /得到的charcter
字符C = strRegEx [I];
（IsInput（C））
160;PUSH（C）;
否则，如果（m_OperatorStack.empty（））
m_OperatorStack.push（C）;
否则，如果（IsLeftParanthesis（C））
m_OperatorStack.push（C）;
否则，如果（IsRightParanthesis（C））
/ /评估括号everyting
而（！IsLeftParanthesis（m_OperatorStack.top（）））
（EVAL（））
返回FALSE;
#160;/ /删除左括号后的评价
m_OperatorStack.pop（）;
（！m_OperatorStack.empty（）放大器;放大器; Presedence（C，m_OperatorStack.top（）））
（EVAL（））
返回FALSE;
#160; m_OperatorStack.push（C）;
/ /评估其余的运营商
而（！m_OperatorStack.empty（））
（EVAL（））
返回FALSE;
/ /从堆栈中弹出结果
如果（！流行（m_NFATable））
返回FALSE;
/ /最后NFA的状态始终是接受状态
m_NFATable [m_NFATable.size（）-1] - GT; m_bAcceptingState = TRUE;
返回TRUE;}函数eval实际上是评估在栈上的下一个经营者。函数eval（）从操作栈中弹出未来的运营商，使用switch语句，它决定使用哪个操作。括号被视为运营商，因为他们判断评估的顺序。功能Presedence（CHAR左右，CHAR）确定的两家运营商，并返回TRUE，如果的优先级优先级的左边的运算符LT =右运算符的优先级。请检查执行的代码。现在，我们知道如何将任何一个NFA的正则表达式，下一步是将其转换NFA到DFA的。起初，这个过程似乎是非常具有挑战性。我们有一个与零个或多个EPSILON转换图形，和多个单个字符的转换，我们需要一个没有EPSILON转换的等效图和每个输入字符的接受顺序的唯一路径。就像我说的，这似乎是非常具有挑战性的，但它是真的不。数学家实际上已经为我们解决了这个问题，然后使用结果，计算机科学家创建的子集构造算法。我不知道谁在这里给予信贷，但子集构造算法是这样的:首先，让我们定义两个功能:EPSILON封闭:此函数作为参数，一套美国T，并再次返回一个包含所有这些国家，可以从每个个别国家EPSILON过渡的集合T达到的国家。移动:移动采取了一套美国T和输入字符a和返回可以在给定的输入字符形式达成的所有国家在T使用这些功能，我们可以进行改造:DFA的开始状态是通过NFA的开始状态EPSILON封闭对于每一个新的DFA状态，请执行以下为每个输入字符:执行移动到新创建的状态EPSILON封闭的结果（一）创建新的状态。请注意，在这里我们可以得到一个国家，这已经是在我们现有的设置。这将导致在一组状态，这将形成新的DFA状态。请注意，这里从一个或多个NFA的国家，我们正在建设一个单一的DFA状态。对于每一个新创建的的状态，执行步骤2。DFA的接受状态，所有这些国家中，至少包含从NFA的接受国之一。请记住，我们在这里从一个或多个NFA的国家建设一个单一的DFA状态。是不是很简单吗？如果没有，那么进一步阅读。以下是伪代码本书的118-121页的"编译器 - 原理，技术和工具"阿霍，Sethi和乌尔曼。下面的算法是相当于上述算法，但以不同的方式表达出来。首先，让我们的定义EPSILON封闭功能:S EpsilonClosure（T）{&
#160; 所有国家在T入栈
初始化的结果为T 
而堆栈不为空
从堆栈弹出吨
每一个从T边缘的状态u，ü标示EPSILON
如果U是不EpsilonClosure（T）
添加u到结果
推入堆栈的U
返回结果}基本上，这个函数的是，经过T和其他国家可以从这些没有输入达成的检查中的所有国家。请注意，每个国家可以达到至少有一个国家没有投入，即本身。然后在功能上没有投入，通过进一步转换所有这些国家和检查。例如，让我们看看下面的:如果我们称之为EPSILON转型的国家{S0，S2}产生的状态将{S0，S2，S1，S3}。这是因为从S0，我们可以达到S1上没有投入，但是从S1，我们可以达到S3上没有投入，因此，从S1，我们可以达到S3没有输入。现在我们知道EPSILON过渡是如何工作的，让我们看看在伪代码转换NFA到一个DFA:国家= EpsilonClosure（NFA的启动状态），它是无人盯防同时也有在D国的任何无人盯防的状态{
每个输入的象征
U = EpsilonClosure（移动（T，A））;
如果U是不是在D -国
添加ü作为一个无人盯防的状态为D -国
DTran [T] U =
}}最后的DTran是DFA表，相当于NFA的。之前，我们去下一个步骤，让我们转换NFA到一个DFA的手，用这个过程。如果你想掌握这个过程中，我会强烈建议您执行更多类似的转换，使用此方法。让我们转换以下的NFA到其相应的DFA使用的子集构造算法:{五}使用的子集构造算法，我们将做如下（每个新创建的的国家会以粗体显示）:创建通过采取EPSILON关闭NFA的开始状态开始DFA的状态。这一步产生的国家:{S1，S2，S4}执行移动（'A'，{S1，S2，S4}），在结果集:{S3，S4}执行EpsilonTransition（{S3，S4}），它创建了一个新的DFA状态:{S3，S4}执行移动（'B'，{S1，S2，S4}），结果集:执行EpsilonTransition（），创建新的DFA状态:注:在这里，我们必须记录2个新的DFA {S3，S4}和，DFA的开始状态{S1，S2，S4}。同时，我们也必须记录字符过渡从{S1，S2，S4} {S3，S4}和{S1，S2，S4字符b} 。执行移动（'A'，{S3，S4}），它返回:{S4}执行与结果EpsilonTransition（{S4}）:{S4}执行移动（'B'，{S3，S4}），在结果集:{S3，S5}执行结果EpsilonTransition（{S3，S5}）:{S3，S5}{S3，S4} - > {S4}上{S3，S4} - GT;对b {S3，S5}执行移动（'A'，），它返回一个空集，所以我们并不需要检查EPSILON转换执行移动（'B'，），它返回一个空集，就这样算了吧。执行移动（'A'，{S4}），它返回:{S4}。但是，这不是一个新的状态，就这样算了吧。但是，我们必须记录的过渡:{S4} - > {S4}上执行移动（'B'，{S4}）返回:执行EpsilonTransition（）返回:（不新，但我们必须创记录的转变）{S4} - > 对B执行移动（'A'，{S3，S5}）返回一个空集，就这样算了吧。执行移动（'B'，{S3，S5}），其中生产:EpsilonTransition（）:，一个新的DFA状态{S3，S5} - GT; 对B移动（'A'，）是一个空集移动（'B'，）这是不是新的，但必须记录过渡！ - > 对B有没有新的国家，所以我们所做的一切。以下是绘制的DFA:{中六}起始状态是{S1，S2，S4}，因为那是EpsilonClosure（NFA的开始状态）。接受状态，{S3，S4}和{S3，S5}，因为它们包含S3和/或S5，这是接受NFA的状态。，现在，我们已经所有的知识转换成一个NFA正则表达式，然后将其转换的NFA等价的DFA，我们实际上可以停止在这一点上，它使用模式匹配。最初，当我准备写这篇文章，以保持它作为简单的只显示原则可能时，DFA的优化没有考虑。但它发生，我认为，首先所有大的正则表达式，我们正在创造非常大的NFAS（汤普森的算法的性质），这反过来又偶尔会产生复杂的DFA。如果我们将搜索模式，这可能会降低大幅降低，所以我决定把优化作为一个正则表达式解析器的一部分。这里的优化是一个复杂的。因此，让我们来看看下面的例子: {七}，如果我们看一下在这个DFA，我们注意到，状态3，首先是所有不是最终状态。此外，我们注意到有从这个国家没有出边除循环。换句话说，一旦我们进入状态3，有没有机会去接受状态。这是由于这样的事实:一个DFA，除了事实，它具有独特的路径，并为每个接受字符串不包含EPSILON转换，它也必须对所有输入字符从一个特定的状态过渡（这里所有输入字符的意思是，可能会接受输入的字符集，例如:A | B | C，输入字符集为{A，B，C}）。下面是我们滥用数学一点点，为了使一个DFA简单。删去状态3，我们的DFA变得更简单，它仍然接受同一套模式。在这种情况下，我们的DFA不再正是一个DFA。如果你问自己，为什么这是重要的，很好的回答是:是不是！至少我们！我们将利用这一非常基本的优化机制，以删除所有国家具有这样的特点，所以我们将获得更小，致密的DFA的模式匹配。总之，我们将删除状态（导致这些国家从其他国家和所有转换）以下特点:国家不接受状态国家没有任何转换到任何其他的不同的状态。因此，结果如下: 上面的DFA，肯定似乎比前一个小。我仍然会调用这个一个DFA，尽管事实上，它是不是真的一个DFA。最后，我们准备使用的所有部件，从上面一些文字模式匹配。一旦我们的DFA，所有我们需要做的的是采取输入字符和对初始状态运行。这里是这样做的伪代码:查找（字符串s）{
s中的每个字符c
每个活跃状态
如果有对C的过渡
进入下一个状态吨
如果T是接受状态
作为活跃的标志吨
标记小号为非活动
如果有从开始C状态的过渡
去下一个状态
如果S是接受状态
马克作为活跃
}}上面的代码可以发现，在查找(...)函数的正则表达式类。要跟踪活动状态，我使用一个链表，所以我可以快速添加和删除活动/非活动状态，分别。之后的所有字符都处理，所有结果都存储在一个向量，它包含模式匹配。使用功能FINDFIRST (...)和FindNext (...),你可以遍历的结果。请参阅CAG_RegEx类文档如何使用类的信息。此外，在这一点上，我要强调，演示程序加载到丰富的编辑控制的完整的文件，然后搜索完成时，它存储为一个字符串，使用FindFirst函数的一个参数传递。根据您的RAM大小，我想避免巨大的文件加载，因为它可以采取了大量的时间来复制数据从一个字符串到另一个，因为虚拟内存的使用。就像我刚才说的，计划的目的是显示在文本文件中的模式匹配背后的原则。根据时间，未来的版本可能包含一个更完整的正则表达式分析器，搜索任意大小的文件，并提供以不同的方式结果。在这一点上，文章的完整性，我必须注意，有一个正则表达式直接转换成一个DFA的方式。这种方法是没有解释，但但如果时间允许，将在以后的文章（或文章更新）。此外，还有一些不同的方法构造一个正则表达式的NFA的。好了，这就是它！我希望你喜欢阅读尽可能多的文章，因为我喜欢写。请使用在任何类型的应用程序的演示代码，但给我的地方当之无愧的信贷。如果你想建立一个更完整的资料库，使用这里介绍的演示代码，请给我增加的副本。注:类CAG_RegEx SaveDFATable（包含两个函数）和SaveNFATable，这在调试模式下保存NFA与DFA到C:\ NFATable.txt和C:\ DFATable.txt分别。由于名称已经透露，这些都是NFA与DFA表。此外，类SaveNFAGraph（）功能和SaveDFAGraph（），这在调试模式下创建两个文件C:\ NFAGraph.dot和C:\ DFAGraph.dot。这些文件是简单的文本文件，包含使用graphviz的（退房下面的参考文献4）绘制这些图形的指示。小号放大器;使用的工具"离散数学" - 理查德Johnsonbaugh（第五版）"离散数学及其应用" - 肯尼斯H.罗森（第四版）"编译器 - 原理，技术和工具" - 阿霍，Sethi和乌尔曼graphviz的从AT＆T（任何类型的图表的绘图工具）。你可以找到它。
关于作者：
中国我是一名编程爱好者，谢谢为我们提供一个学习和分享的平台。有什么问题。可以就本内容回复，我看到时。会尽量回复的。
评论会员：
时间：伟大的代码，感谢一百万评论会员：
时间：！欢迎您有一个很好的！阿米尔Gerzic
评论会员：
时间：无用的代码评论会员：
时间：！太多的编译器错误一旦编译崩溃每次。大多数成员没有初始化正则表达式的结果==零很多文本（eplanations），但代码是没用的评论会员：
时间：我印象非常深刻，你的正则表达式内部的知识，并怀疑如果你也许可以帮助我学习如何我们可以比较一下正则表达式模式，以确定是否一个正则表达式是另一个的子集，或者如果它们是等价的。例如，"*"的格局是".*".的一个子集任何方向，资源或见解将赞赏评论会员：
时间：！这听起来像是有趣的（非常复杂）问题。我从来没有跑进，poblem，因此，也没有提供任何资源。我最初的想法是要找出如果一个正则表达式字符串是另一个正则表达式字符串的一个"部分"。我会做的比较正则表达式字符串的解析树，然后寻找匹配的子树。如果您发现子树，然后你可以看到字符子集，如"。"是任何其他的字符表达式等的超集
希望这有助于！阿米尔
有一个很好的！阿米尔Gerzic
评论会员：
时间：伟大的教程！ 我这篇文章翻译成越南？我们正在做一个关于编译器的excercise，我觉得这是一个很好的的文章，这是很容易理解。再次感谢^ ^ 评论会员：
时间：是的，不是一个问题... ...使用它，你的愿望。很高兴我能帮助！
有一个很好的！阿米尔Gerzic
评论会员：
时间：另外，我也设计一个编译器，可在/post/TinyPascal.aspx发现。这篇文章可能会更有帮助。
有一个很好的！阿米尔Gerzic
评论会员：
时间：您好，
我已经发布了一篇文章，代码项目"在C＃中的regurlar表达implemenation"
，米赞评论会员：
时间：看起来不错，谢谢！
有一个很好的！阿米尔Gerzic
评论会员：
时间：您好，这里的网站链接
乌戈Moschini
日，12:17 修改评论会员：
时间：嗯...没有提及原来的工作？
有一个很好的！阿米尔Gerzic
再次感谢。
最好的问候，
&桌面&网页开发&移动开发&数据库&多媒体&编程语言&平台，框架和库&编程通用&图形/设计&开发周期&一般阅读&第三方产品&作者资源&其他
快速解答标签
价值作最多
