正则表达式 – 零或多或一个或多个修饰符和回溯
|
我正在为我的
PEG解析器添加零或多和一个或多个修饰符,这很简单,因为PEG中的回溯非常少.之前的迭代从未被重新考虑过,因此简单的while循环就足够了.
但是,在其他情况下,零或多和一个或多个修饰符确实需要回溯.例如,采用以下正则表达式： (aa|aaa)+ 这个表达式应该能够贪婪地匹配七个a的字符串：有几种方法可以将2和3加起来得到7.但要实现这一点,重新考虑早期的迭代是必要的.例如,如果表达式第一次匹配三个a并且第二次匹配三个a,则只剩下一个a,这是无法匹配的.然后回溯最后三个a并匹配两个a,然而,匹配五个a.然后最后两个a也可以匹配(即3 2 2 = 7). 幸运的是,正则表达式在匹配字符串后退出搜索.但是EBNF解析器怎么样？如果语法不明确,解析器将使用回溯来查找所有可能的语法树！如果我们有生产 ( "aa" | "aaa" )* 一个七个字母的字符串,一个完全回溯的解析器将返回所有可能的方式来表达7的2和3.这只是七个a：匹配一个稍长的字符串,N-ary树的可能性增长另一个级别.考虑N = 6： S : ( T )* ; T : A | B | C | D | E | F ; 一个可怕的组合爆炸！ 但是真的可以这样吗？ EBNF中的零或多和一个或多个修饰符没有限制吗？如上所述实现它们比PEG解析器的简单while()循环要多得多,所以我不得不怀疑…… 解决方法
是;回溯可以给你很多结果.我是lepl的作者,这是一个递归的正确解析器,它将很乐意回溯并生成所有可能的AST的“解析林”.并且EBNF没有限制(这只是一种规范语言,并不依赖于任何特定的解析器实现).
但并非所有解析算法都会回溯.正则表达式的许多实现都这样做,但并不总是必要的.事实上,对于一个“简单”的正则表达式(一个实际上仅限于常规语法),它可以在没有回溯的情况下进行匹配 – 从某种意义上说,诀窍是并行运行. 有两种(等效的)方法 – 通过“编译”正则表达式(如果并行工作是显式的那样计算表达式),或者通过在运行时处理并行匹配.编译方法将正则表达式转换为DFA(确定性有限自动机).更确切地说,NFA(非确定性的……)模糊地类似于正则表达式的图形版本,并且可能是您想象正则表达式的工作方式;与NFA匹配确实需要回溯,但您可以将NFA转换为DFA而不是. 但是,在运行时执行此操作更容易理解(并且在实践中往往更有用),并在三篇很棒的文章中进行了解释,如果您想要更好地理解这一点,您应该真正阅读这些文章：http://swtch.com/~rsc/regexp/regexp3.html以及开头的链接. 我不能强调这一点 – 你需要阅读这些文章…… ps模糊相关 – 您可以通过缓存稍后可能需要的结果(当您最终通过不同的路径到达相同的文本和表达式时)来使回溯更有效.这被称为“packrat解析”,当应用于递归正常解析时(虽然说实话它不值得一个单独的名称 – 它实际上只是使用缓存).缓存避免了指数运行时 – 诺维格(谷歌的那个人,但这是之前写的方式)某处有一篇论文解释了：http://acl.ldc.upenn.edu/J/J91/J91-1004.pdf （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |