现代程序员使用的正则表达式实现已经远远超越了形式语言理论中的经典定义[1]。根据Chomsky层次结构分析，PCRE等当代正则表达式引擎能够匹配上下文无关语言，这意味着它们可以处理包括格式良好的HTML在内的复杂结构[1]。通过递归子模式和命名子模式等构造方式，正则表达式实现了类似语法规则的功能[1]。此外，左递归语法可以转换为右递归形式以适配正则表达式的处理需求[1]。
带有回溯引用的正则表达式具有更加强大的计算能力，实际上属于NP完全问题的范畴，甚至能够求解3-CNF SAT等经典NP完全问题[1]。然而，这种理论上的强大能力仍存在实际限制，例如后向断言必须保持固定宽度，这对某些上下文敏感语言的直接转换造成了约束[1]。鉴于这些技术限制，尽管正则表达式在理论上可以匹配上下文无关语言，但在实际处理HTML等标记语言时，仍建议使用DOM库等专用工具，特别是在需要处理格式不良的HTML的情况下[1]。
Modern regular expressions wield significantly greater capabilities than their theoretical foundations suggest. [1] While classical formal language theory restricts regular expressions to matching only regular languages, the implementations programmers actually use—such as PCRE—far exceed these limitations. [1] These contemporary systems can match all context-free languages, enabling them to handle well-formed HTML structures. [1]
The gap between theory and practice stems from advanced features built into modern regex engines. [1] Through recursive subpatterns and named capture groups, regular expressions can construct patterns equivalent to grammatical rules, effectively transcending their formal language category. [1] Left-recursive grammars can be converted into right-recursive forms to accommodate regex syntax requirements. [1] However, certain constraints remain: lookbehind assertions must maintain fixed width, which limits direct conversion of some context-sensitive language patterns. [1]
The computational complexity of modern regex implementations underscores their power and limitations alike. [1] Regular expressions with backreferences achieve NP-completeness, allowing them to solve NP-complete problems such as 3-CNF SAT. [1] Despite these theoretical capabilities for context-free language matching, practical HTML processing is still recommended to use dedicated DOM libraries rather than regex alone, particularly when handling malformed HTML. [1]