#优质博文 #前端 #正则
编译原理回忆在攻击我
译文 | 正则表达式的真正实力
AI 摘要：本文探讨了现代正则表达式（主要指 PCRE 风格）的实际能力，远超其原始定义中的「正则语言」范畴。作者通过形式语言理论，介绍了乔姆斯基层次结构，说明正则表达式不仅可以匹配正则语言，还能处理上下文无关语言（如编程语言语法）甚至部分上下文相关语言（如 {a^n b^n c^n, n>0}）。
核心观点包括：
1. 形式语言基础：正则表达式原本仅适用于正则语言，但现代实现支持递归和子模式引用，使其超越该范畴。
2. 解析上下文无关语言：PCRE 支持递归子模式，使其能匹配几乎所有上下文无关语言，如 HTML 及编程语言语法。
3. 有限支持上下文相关语言：尽管某些上下文相关模式可用断言和子模式引用匹配，但非固定宽度的后行断言限制了其能力。
4. NP 完全性：支持反向引用的正则表达式匹配问题是 NP 完全问题，可解决如 3-CNF SAT 这样的复杂计算问题。
5. 实际应用：「可行」不等于「最佳」，解析 HTML 仍应首选 DOM 解析器，而非正则。
总结而言，现代正则表达式极为强大，但应根据具体需求选择合适工具。
via 少数派 PlatyHsu
编译原理回忆在攻击我
译文 | 正则表达式的真正实力
AI 摘要：本文探讨了现代正则表达式（主要指 PCRE 风格）的实际能力，远超其原始定义中的「正则语言」范畴。作者通过形式语言理论，介绍了乔姆斯基层次结构，说明正则表达式不仅可以匹配正则语言，还能处理上下文无关语言（如编程语言语法）甚至部分上下文相关语言（如 {a^n b^n c^n, n>0}）。
核心观点包括：
1. 形式语言基础：正则表达式原本仅适用于正则语言，但现代实现支持递归和子模式引用，使其超越该范畴。
2. 解析上下文无关语言：PCRE 支持递归子模式，使其能匹配几乎所有上下文无关语言，如 HTML 及编程语言语法。
3. 有限支持上下文相关语言：尽管某些上下文相关模式可用断言和子模式引用匹配，但非固定宽度的后行断言限制了其能力。
4. NP 完全性：支持反向引用的正则表达式匹配问题是 NP 完全问题，可解决如 3-CNF SAT 这样的复杂计算问题。
5. 实际应用：「可行」不等于「最佳」，解析 HTML 仍应首选 DOM 解析器，而非正则。
总结而言，现代正则表达式极为强大，但应根据具体需求选择合适工具。
via 少数派 PlatyHsu
