R使用哪种正则表达式引擎类型作为标准？

Question

Jeffrey Friedl在他的"Mastering Regular Expressions"一书中列出了3种主要的正则表达式引擎:

• 传统的NFA
• POSIX NFA
• DFA(POSIX与否)

R中哪一个用作标准？

Answer 1

该?regex页面引用了TRE文档.在grep.c源头附近,我们看到:

/* As from TRE 0.8.0, tre.h replaces regex.h */
#include <tre/tre.h>

并复制我之前的评论:http://swtch.com/~rsc/regexp说TRE使用NFA.然后PCRE用于perl=TRUE.

Answer 2

我的理解（但我在官方文档中没有找到这一点）是，R 正则表达式函数默认使用 tcl 正则表达式库，它是 DFA 和 NFA 的混合体。

引擎将首先扫描正则表达式以查找任何非 DFA 兼容的部分，并提取 DFA 的部分（因此删除反向引用和其他仅在 NFA 中可用的内容）。然后，它尝试使用 DFA 引擎找到与此（可能）简化模式的匹配项。如果找不到匹配项，则完整的正则表达式将不匹配，并且返回失败。如果它找到匹配项，那么它会返回并使用 NFA 引擎（我认为是传统/非 posix）匹配完整的正则表达式，但从发生简化匹配的位置开始。这比直接的 NFA 引擎要快得多（对于非匹配和匹配），但仍然允许您使用 NFA 中 DFA 不支持的所有内容。

如果您在任何函数中指定perl=TRUE，那么它会切换到最像传统 NFA 的 PCRE 库（尽管我知道它不是 F、A 或传统的）。