c - POSIX 系统上 regex.h header 的不同实现背后的算法类型

Question

我最近读了一篇关于正则表达式的精彩文章
(见 here )解释了简单性
和优雅的 Thompson NFA 匹配正则表达式，
以及其他规则的绝对复杂性和缓慢
表达式。给出的图表显示了 Ruby 和 Python
远比 Thompson NFA 长，事实上，Thompson
NFA 的匹配时间与众所周知的相似
快速模式匹配 UNIX 程序，例如 grep 和
哦。
我的问题是，对于 header (需要
POSIX 标准)musl、glibc 和 uclibc 使用什么算法？
我查看了我比较 Thompson NFA 的程序的来源
到(GNU/Busybox grep、GNU/Busybox awk)和没有任何实现
使用 regex.h header ，选择他们自己的内部正则表达式匹配 header 。
注意:我不是指符合 POSIX 标准的正则表达式 - 我是专门谈论由符合 POSIX 标准(或类 UNIX)的系统提供的 header
称为 regex.h，它提供用于编译和匹配正则表达式的函数和结构。

Answer 1

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 年左右 forked)，与 <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 库没有正则表达式功能的系统(考虑例如 GNU grep、sed、Windows 上的 awk)，并确保正则表达式功能的正确性和效率。
就我个人而言，当我编写 POSIX C 代码(系统编程 – 守护进程或实用程序或用于 Linux 或 *BSD 的库)时，我使用 <regex.h>由 C 库提供。如果我要编写一个新的 grep/sed/awk 实用程序，我会将正则表达式库合并到源代码中，以便该实用程序可以跨操作系统移植，包括那些不提供 <regex.h> 的操作系统。作为他们 C 库的一部分。我相信这就是您看到一些专用实用程序也包含自己的正则表达式库的原因。