regex实现背后的理论

解答动态

• 

  这不是实施的问题。不幸的是，不同的解析方法具有相似的名称。
  NFAs和DFAs（有限状态机）只能识别常规语言。正则表达式是一种指定正则语言的方法，它们可以被编译成有效的nfa或dfa来识别该语言。这些都是在本科CS课程中教授的。
  Perl中所谓的“regexes”及其许多模仿者的名字听起来像“regular expression”的缩写，它们在语法上类似于sed和awk的正则表达式，但它们不是正则表达式。它们实际上是回溯解析器的规范。回溯解析器并不局限于识别常规语言。（regex这个名字是拉里·沃尔的错。他慎重地决定不称它们为“正则表达式”，因为他知道它们不是，但他应该发明一个完全不同的名称。）
  您不需要基于NFA/DFA的正则表达式匹配的侏罗纪实现；流行语言可以使用现代维护的库。但是它们缺少Perl风格regex的许多特性，而且它们也没有提供太多的交换。它们当然有更好的最坏情况性能，但是回溯解析器的病态最坏情况可以通过修改regex来修复，而不会失去回溯的额外灵活性。他显然想让你相信，regex库的作者对正规语言的理论一无所知，如果他们刚刚学习了标准的本科CS课程，那么他们将以一种不同的方式实现他们的库，并使它们变得更快。那是假的。这样实现Perl风格的正则表达式是不可能的，他知道这一点。Perl风格正则表达式的流行在很大程度上可能是由于其灵活的特性集远远超出了任何真正的正则表达式库中可用的特性集。关键的引语是一：大部分实际上，Perl中的正则表达式匹配已经足够快了。不过，如图所示，可以编写Perl非常慢地匹配的所谓“病态”正则表达式。相反，对于Thompson NFA实现来说，没有病理性的正则表达式。
  在后面的文章中，Cox给出了与实际应用相关的示例世界：
  示例包括使用（.*）（.*）（.*）（.*）（.*）拆分五个空格分隔的字段，或者在不首先列出常见情况的情况下使用替换项。
  
• End