主要观点：介绍在 RE2 线性时间正则表达式引擎中添加无捕获回溯的方法。现代正则表达式复杂，以往含回溯的环视算法复杂度高，2023 年实验室展示可在线性时间匹配环视。现提供第三个实现，展示 RE2 可扩展支持线性时间无捕获回溯。
关键信息：

• 算法步骤：传统 NFA 模拟基础上创建空表跟踪回溯位置，编译每个回溯为单独自动机，用 CheckLB 指令检查，各自动机同步运行等。
• RE2 架构：提供两个入口点，通过解析、编译、选择引擎等步骤处理正则表达式匹配，基于混合方法。
• 支持回溯的更改：包括修改解析器、编译器、NFA 引擎和选择引擎的函数，添加新指令和数据结构等。
• 测试：包含相关测试文件，添加和删除部分测试用例以检查解析和匹配。
  重要细节：
• 解析器更改：添加整数跟踪回溯数量，处理回溯语法，处理右括号等。
• 编译器更改：在编译器中处理新的回溯令牌，添加新指令，记录回溯自动机的起始索引。
• NFA 引擎更改：添加 lb_table 跟踪回溯有效性，为每个回溯启动线程，处理新指令。
• 选择引擎更改：在含回溯时强制使用 NFA 引擎。
• 测试用例：添加和删除特定的测试用例，测试解析和匹配功能，还测试了线性时间复杂度。
• 整体补丁：约 300 行代码，相关文件的修改情况如给出的 git diff 信息。
  未来工作方向：支持无捕获前瞻，研究在其他引擎中实现回溯。