现代正则表达式引擎解析什么样的正式语言？

发布时间：2020-12-14 06:40:09 所属栏目：百科来源：网络整理

导读：在这里，人们有时会说“你不能用正则表达式解析X，因为X不是常规语言”。从我的理解，然而，现代正则表达式引擎可以匹配比 Chomsky’s sense的常规语言。我的问题：给定一个支持的正则表达式引擎反向引用无限宽度的回顾断言递归，如(？R) 什么样的语言可

在这里，人们有时会说“你不能用正则表达式解析X，因为X不是常规语言”。从我的理解，然而，现代正则表达式引擎可以匹配比 Chomsky’s sense的常规语言。我的问题：

给定一个支持的正则表达式引擎

>反向引用
>无限宽度的回顾断言
>递归，如(？R)

什么样的语言可以解析？它可以解析任何上下文无关的语言，如果没有，什么是反例？

(确切地说，“解析”我的意思是“构建一个单一的正则表达式，接受语法X生成的所有字符串并拒绝所有其他字符串”)。

添加：我特别感兴趣地看到一个上下文无关的语言的例子，现代regex引擎(Perl，Net，python regex模块)将无法解析。

我最近写了一篇相当长的文章关于这个话题： The true power of regular expressions。

总结：

>支持递归子模式引用的正则表达式可以匹配所有无上下文的语言(例如a ^ n b ^ n)。
>具有环视断言和子模式引用的正则表达式可以匹配至少一些上下文敏感的语言(例如ww和a ^ n b ^ n c ^ n)。
>如果断言具有无限宽度(如你所说)，那么所有上下文相关的语法都可以匹配。我不知道任何正则表达式风味，虽然没有固定宽度限制在lookbehind(同时支持子模式引用)。
>具有反向引用的正则表达式是NP完全的，因此任何其他NP问题可以使用正则表达式(应用多项式时间变换后)求解。

一些例子：

>匹配上下文无关语言{a ^ n b ^ n，n> 0}：

/^(a(?1)?b)$/
# or
/^ (?: a (?= a* (1?+ b) ) )+ 1 $/x

>匹配上下文敏感语言{a ^ n b ^ n c ^ n，n> 0}：

/^
    (?=(a(?-1)?b)c)
    a+(b(?-1)?c)
$/x
# or
/^ (?: a (?= a* (1?+ b) b* (2?+ c) ) )+ 1 2 $/x

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!