少数派
·
译文 | 正则表达式的真正实力
💡
原文中文，约13800字，阅读约需33分钟。
📝
内容提要
正则表达式的真正力量在于其超越传统正则语言的能力。现代实现（如PCRE）能够匹配上下文无关语言，甚至某些上下文相关语言。正则表达式的匹配是NP完全问题，意味着它可以解决其他NP问题。使用时需谨慎，选择合适的方法处理特定问题。
🎯
关键要点
- 正则表达式超越传统正则语言的能力，现代实现能匹配上下文无关语言和某些上下文相关语言。
- 正则表达式的匹配是NP完全问题，可以解决其他NP问题。
- 正则语言的定义基于形式语言理论，包含特定的产生式规则。
- 正则表达式可以简洁地表示复杂的文法，例如自然数的定义。
- 正则表达式在编程语言中实现的功能远超形式文法的定义。
- PCRE正则表达式实现能够匹配上下文无关语言，且可以匹配某些上下文相关语言。
- 上下文相关语言的产生式规则依赖于上下文，通常在自然语言处理中使用。
- 正则表达式不支持左递归，但可以通过右递归实现相同的功能。
- 正则表达式能匹配某些上下文相关语言，但不一定能匹配所有。
- 无限制文法是图灵完备的，能够形成所有递归可枚举语言。
- 反向引用使得正则表达式的匹配成为NP完全问题，能够解决其他NP问题。
- 程序员所说的正则表达式与形式语言理论中的原始概念几乎没有共同之处。
- 正确使用正则表达式时，应选择合适的方法解决特定问题，并保持代码的整洁和可读性。
➡️
