3 regex compiler-construction lexical-analysis dfa
我有一个给定的DFA代表一个正则表达式.我希望将DFA与输入流匹配并获得所有可能的匹配,而不仅仅是最不匹配的匹配.
例如:
正则表达式:a*ba | baa
输入:aaaaabaaababbabbbaa
结果:
Sin*_*ion 14
根据您的问题和以后的评论,您需要一种将句子拆分为非重叠匹配子字符串的通用方法,并将句子的不匹配部分丢弃.您似乎也希望获得最佳的运行时性能.此外,我假设您已经有一个现有的算法将正则表达式转换为DFA表单.我进一步假设您通过首先构建NFA并通过子集构造将其转换为DFA的常规方法来执行此操作,因为我不知道有任何其他方法来实现此目的.
在追逐阴影之前,请确保您尝试为工作应用正确的工具.任何关于正则表达式的讨论几乎总是因为人们使用正则表达式而不是真正最佳的事情而变得混乱.如果您希望获得正则表达式的好处,请确保使用的是正则表达式,而不是更广泛的表达式.如果你想要做的事情不能在某种程度上被编码成正则表达式,那么你就无法从正则表达式算法的优势中受益(完全)
一个明显的例子是,任何数量的聪明都不允许FSM或任何算法预测未来.例如,一个表达式(a*b)|(a),当与字符串匹配时aaa...省略号是尚未扫描的表达式部分,因为用户尚未键入它们,不能为您提供每个可能的正确子组.
有关正则表达式实现的更详细讨论,特别是Thompson NFA,请查看此链接,该链接描述了一个带有一些巧妙优化的简单C实现.
正则表达式算法的O(n)和空间(O(1))保证是一个相当狭窄的主张.具体而言,常规语言是可以在恒定空间中识别的所有语言的集合.这种区别很重要.算法的任何类型的增强都可以在比接受或拒绝句子更复杂的事情上运行.最重要的是,如果您可以证明某些增强需要大于恒定的空间来实现,那么您也不在性能保证之内.话虽如此,如果我们非常小心地将算法保持在这些狭窄的约束内,我们仍然会做很多事情.
显然,这消除了我们可能想要用递归回溯做的任何事情.堆栈没有恒定的空间.即使保留指向句子的指针也会被禁止,因为我们不知道句子可能有多长.足够长的句子会溢出任何整数指针.当我们绕过这个时,我们无法为自动机创建新的状态.在将识别器暴露给任何输入之前,所有可能的状态(以及一些不可能的状态)必须是可预测的,并且该数量必须受某个常量的限制,这可能因我们想要匹配的特定语言而异,但不能通过其他变量.
这仍然允许一些空间来添加额外的行为.获得更多里程的通常方法是为处理中发生某些事件的位置添加一些额外的注释,例如子表达式开始或停止匹配时.由于我们只允许进行常量空间处理,因此限制了我们可以处理的子表达式匹配的数量.这通常表示该子表达式的最新实例.这就是为什么当你要求subgrouped匹配时(a|)*,你总是得到一个空字符串,因为任何序列的a's隐含地跟着无数多个空字符串.
另一个常见的增强是在状态之间做一些聪明的事情.例如,在perl正则表达式中,\b匹配空字符串,但前提是前一个字符是单词字符而下一个字符不是,反之亦然.许多简单的断言都适合这种情况,包括公共线锚操作符,^以及$.Lookahead和lookbehind断言也是可能的,但更难.
在讨论各种常规语言识别器之间的差异时,值得澄清的是,如果我们讨论的是匹配识别或搜索识别,前者只有在整个句子都在语言中时才接受,而后者在句子中接受任何子串.是在语言中.这些是等价的,如果E搜索方法接受某些表达式,则在匹配方法中接受. .*(E).*
这很重要,因为我们可能想要明确表达是否a*b|a接受aa.在搜索方法中,确实如此.两个标记都将与分离的右侧匹配.但是,它不匹配,因为你可能永远不会通过逐步表达并从转换中生成标记来获得该句子,至少在一次通过中.出于这个原因,我只会谈论匹配语义.显然,如果你想要搜索语义,你可以使用.*'s 修改表达式
注意:表达式定义的语言实际上并不是一种非常易于管理的语言,无论其子语言如何,因为它匹配所有可能的句子.这对正则表达式识别器来说是一个真正的挑战,因为它们实际上只适用于识别语言或确认句子不是同一种语言,而不是做更具体的工作. E|.*E
通常有三种方法来处理正则表达式.通过将表达式转换为NFA,所有三个都开始相同.此过程为原始表达式中的每个生产规则生成一个或两个状态.规则非常简单.这是一些原始的ascii艺术:注意这a是语言字母表中的任何单个文字字符,E1并且E2是任何正则表达式.Epsilon(ε)是一个具有输入和输出的状态,但忽略了字符流,也不消耗任何输入.
a ::= > a ->
E1 E2 ::= >- E1 ->- E2 ->
/---->
E1* ::= > --? <-\
\ /
E1
/-E1 ->
E1|E2 ::= > ?
\-E2 ->
就是这样! 诸如E +,E？,[abc]的常见用途分别等同于EE*,(E |),(a | b | c).另请注意,我们为每个生产规则添加了极少数的新状态.实际上,每个规则都会添加零个或一个状态(在此演示文稿中).字符,量词和dysjunction都只添加一个状态,并置连接不添加任何状态.其他一切都是通过更新片段的结束指针来启动其他状态或片段的指针来完成的.
epsilon过渡状态很重要,因为它们含糊不清.遇到时,机器是否应该将状态更改为以下状态或其他状态？它应该改变状态还是留下来？这就是为什么这些自动机被称为不确定性的原因.解决方案是让自动机转换到正确的状态,无论哪个允许它匹配最佳状态.因此,棘手的部分是弄清楚如何做到这一点.
基本上有两种方法可以做到这一点.第一种方法是尝试每一个.按照第一个选择,如果不起作用,请尝试下一个.这是递归回溯,出现在一些(并且值得注意的)实现中.对于精心设计的正则表达式,此实现只需要很少的额外工作.如果表达式有点复杂,递归回溯非常非常糟糕,O(2 ^ n).
另一种方法是并行尝试两个选项.在每个epsilon转换时,将epsilon转换建议的两个状态添加到当前状态集.由于您使用的是一个集合,因此您可以多次出现相同的状态,但您只需要跟踪它一次,无论您是否处于该状态.如果你发现没有特定状态可供选择的选项,那就忽略它,那条路径不匹配.如果没有更多状态,则整个表达式不匹配.一旦任何州达到最终状态,你就完成了.
仅从这个解释来看,我们要做的工作量已经增加了一点点.我们已经从必须跟踪单个州到几个州.在每次迭代中,我们可能必须更新m个状态指针的顺序,包括检查重复项.我们所需的存储量也随之增加,因为现在它不再是指向NFA中一个可能状态的单个指针,而是一整套指针.
然而,这并不像声音那么接近.首先,状态数量受原始正则表达式中的产生数量的限制.从现在开始,我们将这个值称为m,以区别于输入中的符号数,即n.如果两个状态指针最终转换到相同的新状态,则可以丢弃其中一个,因为无论发生什么,它们都将从那里开始遵循相同的路径.这意味着您需要的状态指针的数量受状态数量的限制,因此为m.
与回溯相比,这在最糟糕的情况下是一个更大的胜利.从输入中消耗每个字符后,您将创建,重命名或销毁最多m个状态指针.没有办法制作一个正则表达式,它会导致你执行多于那么多指令(根据你的确切实现,一些常数因素),或者会导致你在堆栈或堆上分配更多的空间.
这个NFA同时在其m个状态的某个子集中,可以被认为是其他状态机,其状态代表它所建模的NFA可以处于的状态集.该FSM的每个状态代表来自状态的幂集的一个元素. NFA.这正是用于匹配正则表达式的DFA实现.
使用此替代表示具有以下优点:不必更新m个状态指针,而只需更新一个.它也有一个缺点,因为它模拟m个州的powerset ,它实际上有多达2 米的状态.这是一个上限,因为你没有模拟不可能发生的状态,例如表达式a|b在读完第一个字符后有两种可能的状态,一个是看过一个a,一个是看过一个b.无论您给出什么输入,它都不能同时处于这两种状态,因此状态集不会出现在DFA中.事实上,因为你正在消除epsilon转换的冗余,许多简单的DFA实际上比它们所代表的NFA更小,但是根本没有办法保证这一点.
为了防止状态爆炸变得太大,在该算法的几个版本中使用的解决方案是仅生成您实际需要的DFA状态,如果您获得太多,则丢弃最近未使用的那些.您始终可以再次生成它们.
正则表达式的许多实际用途涉及跟踪输入的位置.这在技术上是作弊的,因为输入可以是任意长的.即使你使用了64位指针,输入也可能是2 64 +1个符号,你就会失败.您的位置指针必须随着输入的长度而增长,现在您的算法现在需要不止一定的空间来执行.在实践中,这是不相关的,因为如果你的正则表达式确实最终通过那么多的输入,你可能不会注意到它会失败,因为你很久就会终止它.
当然,我们希望做的不仅仅是接受或拒绝整体输入.对此最有用的变化是提取子匹配,以发现输入的哪个部分与原始表达式的某个部分匹配.实现此目的的简单方法是为表达式中的每个开括号和右括号添加epsilon过渡.当FSM模拟器遇到这些状态之一时,它会向状态指针注释有关在遇到特定转换时输入中的位置的信息.如果相同的指针第二次返回到该转换,则旧的注释将被丢弃并替换为新输入位置的新注释.如果具有不同注释的两个状态指针折叠到相同状态,则稍后输入位置的注释再次获胜.
如果你坚持使用Thompson NFA或DFA实现,那么就没有任何关于贪婪或非贪婪匹配的概念.回溯算法需要给出一个暗示,它是否应该首先尝试尽可能多地匹配并递归尝试更少,或尽可能少地尝试并递归尝试更多,当它首次尝试失败时.Thompson NFA方法同时尝试所有可能的数量.另一方面,您可能仍希望使用一些贪婪/不同意的暗示.此信息将用于确定是否应首选较新或较旧的子匹配注释,以便仅捕获输入的正确部分.
另一种实用增强是断言,产品不消耗输入,但基于输入位置的某些方面匹配或拒绝.例如,在perl正则表达式中,a \b表示输入必须在该位置包含单词边界,这样刚刚匹配的符号必须是单词字符,但下一个字符不能是,或反之亦然.同样,我们通过向模拟器添加带有特殊指令的epsilon转换来管理它.如果断言通过,则状态指针继续,否则丢弃.
Lookahead和lookbehind断言可以通过更多的工作来实现.典型的lookbehind断言转换为两个单独的表达式,并且.两个表达式都应用于输入.请注意,我们在断言表达式中添加了一个,因为我们实际上并不关心它的起始位置.当模拟器在第二个生成的片段中遇到epsilon时,它会检查第一个片段的状态.如果该片段处于可以在那里接受的状态,则断言在状态指针流入时传递,否则,它将失败,并且两个片段继续,第二个片段在epsilon转换处丢弃状态指针.r0(?<=r1)r2.*r1r0?r2.*r2
Lookahead也可以通过为断言使用额外的正则表达式片段来工作,但有点复杂,因为当我们到达输入中断言必须成功的点时,没有遇到任何相应的字符(在后面的情况下,它们是已经遇到过).相反,当模拟器到达断言时,它会在断言子表达式的开始状态中启动一个指针,并在模拟的主要部分中注释状态指针,以便它知道它依赖于子表达式指针.在每一步,模拟必须检查它所依赖的状态指针是否仍然匹配.如果它找不到,那么无论它发生在哪里都会失败.你不必再保留断言子表达式状态指针的副本,而不是主要部分,如果断言中的两个状态指针落在同一状态,那么它们各自依赖的状态指针将共享相同的状态指针命运,可以重新注释以指向您保留的单个指针.
在为epsilon过渡添加特殊指令时,建议让模拟器偶尔暂停一下以让用户看到正在发生的事情并不是一个糟糕的主意.每当模拟器遇到这样的转换时,它就会将其当前状态包装在某种类型的包中,该包可以返回给调用者,进行检查或更改,然后在它停止的地方重新开始.这可以用于交互地匹配输入,因此如果用户仅键入部分匹配,则模拟器可以请求更多输入,但是如果用户键入无效的内容,则模拟器是空的,并且可以向用户投诉.另一种可能性是每次匹配子表达式时产生,允许您查看输入中的每个子匹配.但是,这不能用于排除某些子匹配.举例来说,如果你试图匹配((a)*b)打击aaa,你可以看到三个子匹配的一个的,即使整个表达式最终失败,因为没有B,并没有子匹配了相应的B的
最后,可能有一种方法可以修改它以使用反向引用.即使它是优雅的,它肯定是低效的,具体来说,正则表达式和反向引用都是NP-Complete,所以我甚至不会想到一种方法来做到这一点,因为我们只对(这里)感兴趣(渐近) )有效的可能性.