The true power of regular expressions (2012)
4 hours ago
- 编程中的正则表达式远比形式化的“正则语言”理论所暗示的更加强大，能够匹配上下文无关甚至部分上下文敏感的语言。
- 乔姆斯基层级对形式语言进行分类，而像PCRE这样的现代正则表达式实现可以处理超出正则语言范围的语言，包括具有递归模式的语言。
- 使用递归子模式（例如 (?1)）允许正则表达式匹配上下文无关语言，如 {a^n b^n}。
- 语法定义可以直接使用DEFINE和命名子模式转换为正则表达式，如RFC 5322电子邮件正则表达式所示。
- 正则表达式支持将左递归语法转换为右递归，同时保持表达力。
- 通过前瞻断言和反向引用可以部分匹配上下文敏感语言，尽管存在诸如固定长度后视断言之类的限制。
- 反向引用使正则表达式匹配成为NP完全问题，从而使正则表达式能够解决NP问题，例如3-CNF SAT。
- 尽管正则表达式功能强大，但将其用于像HTML解析这样的复杂任务往往不现实；通用处理时建议使用DOM库。
- 对于定义明确且具体的模式，正则表达式可以成为简单有效的解决方案。