C中的正则表达式

Question

我很好奇,有人知道在C中进行正则表达式匹配的好方法吗？我能想到的唯一方法是通过Flex.这是唯一的方式还是有更好的方法？

谢谢!

Answer 1

呃......最好的方法是

#include <regex.h>

这是正则表达式的POSIX 标准API.

对于非POSIX系统,滚动自己的系统是另一种选择,基本的正则表达式引擎并不难实现.我确信也有现成的解决方案,我还没有找到解决方案.

想想看,我认为glib有一个.

Answer 2

取决于您正在寻找的方言以及您所使用的平台:

• POSIX正则表达式可能位于标准C库中 - 请参阅<regex.h>和regcomp,regerror,regexec,regfree.
• libPCRE提供了perl的大部分扩展正则表达式功能
• glib有GRegex
• Henry Spencer的Tcl Regex图书馆.

Henry Spencer还完成了另一个正则表达式库,由当前版本的TCL和PostgreSQL使用.这个很有意思,因为它是一个混合的NFA/DFA实现.

以多种方式接受相同字符串的正则表达式(如a*a？)本身就需要NFA.通常的实现使用回溯将NFA建模为DFA,对于特别简并的模式,其可以与O(2 ^长度(输入))一样多.但是,简单的递归实现可以通过捕获,反向引用,代码回调以及许多语言提供的除了测试匹配之外的所有常用"额外"功能进行扩展.

"NFA"方法跟踪多个当前状态并使用每个传入字符更新所有状态(有关更多解释,请参阅Ross Cox的Thompson NFA正则表达式的写法).这种方法是O(input.length*pattern.length),它更快 - 在最坏的情况下非常如此 - 但是不能执行backrefs或捕获,因为它不能跟踪它是如何进入状态的.

Spencer的方法是混合方法,将模式的某些部分编译为NFA方法,并仅在必要时使用回溯来实际请求捕获.这通常是一个巨大的胜利(见TCL 在正则表达式 - dna枪战中的位置).