我最近读了一篇关于正则表达式的精彩文章 (参见 here )这解释了简单性 以及 Thompson NFA 匹配正则表达式的优雅， 以及其他常规方法的绝对复杂性和缓慢性 表达式。给出的图表显示了 Ruby、Python 的取值 比 Thompson NFA 长得多，事实上，Thompson NFA 的匹配时间与众所周知的类似 快速模式匹配 UNIX 程序，例如 grep 和 awk。
我的问题是，对于
我查看了与 Thompson NFA 进行比较的程序的来源 到 (GNU/Busybox grep, GNU/Busybox awk) 并且没有任何实现 使用 regex.h header ，选择他们自己的内部正则表达式匹配 header 。
注意:我并不是指符合 POSIX 标准的正则表达式 - 我是专门谈论 POSIX 兼容(或类 UNIX)系统提供的 header 称为 regex.h，它提供用于编译和匹配正则表达式的函数和结构。
最佳答案
GNU C 库实现 – 这就是您使用 <regex.h> 时得到的结果在 Linux(以及针对 GNU C 库编译时的任何其他操作系统)中 – 位于 glibc git 中: posix/regex.h , posix/regex.c , posix/regex_internal.h , posix/regex_internal.c , posix/regcomp.c ，和posix/regexec.c 。内部文件引用DFA (deterministic finite automaton) ，你可以看看上面的实现，看看它确实实现了一个DFA。 git 的历史只能追溯到 2002 年左右，但基本实现却比那要早；我懒得去读旧的glibc-alpha邮件列表文件以揭示完整的开发历史详细信息。 2018 年似乎有一些改进(与 gnulib 正则表达式实现同步时)。
可以这么说，为了执行，甚至 Thompson NFA 也会转换为 DFA，这就是 glibc 用来实现
uClibc 的 <regex.h> implementation起源于 glibc，大致源自 2002-2006 年时代，基于 git 日志(以及源文件中的版权分配)。 DFA 也在那里。
uClibc-ng是 uClibc 的一个 fork (大约在 2014-2015 年 fork )，并且具有基本相同的 <regex.h> implementation作为 uClibc。
dietlibc使用自己的自定义(回溯)实现，libregex/rx.c ，提供
musl C library有自己的<regex.h> implementation另外，基于 Ville Laurikari 的 TRE (近似的正则表达式)库。我还没有仔细阅读代码来正确分类它，但因为它的时间复杂度是线性的。输入字符串(但直到正则表达式的二次)，我确实相信它也是基于有限自动机。
Musl的作者比较了不同C库的各种特性，包括简单的正则表达式，here 。除此之外，它表明 GNU C 库实现在测试的 C 库中具有最佳的 regcomp()+regexec() 运行时，并且除了 Dietlibc 之外的所有库都具有大致相似的时间行为。
那么，为什么人们要实现自己的正则表达式功能，而不依赖标准 C 库提供的功能呢？
我认为的原因是可移植到 C 库没有正则表达式功能的系统(例如 Windows 上的 GNU grep、sed、awk)，并确保正则表达式功能的正确性和效率。
就我个人而言，当我编写 POSIX C 代码(系统编程 – 用于 Linux 或 *BSD 的守护进程或实用程序或库)时，我使用 <regex.h>由 C 库提供。如果我要编写一个新的 grep/sed/awk 实用程序，我会将正则表达式库合并到源中，以便该实用程序可以跨操作系统移植，包括那些不提供 <regex.h> 的操作系统。作为他们的 C 库的一部分。我相信这就是您看到一些专用实用程序也包含自己的正则表达式库的原因。
关于c - POSIX 系统上 regex.h header 的不同实现背后的算法类型，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/68533062/