regex - 可以将包含非贪婪(不情愿)量词的正则表达式重写为仅使用贪婪的量词吗？

Question

假设我有一个支持文字、正负字符类、有序交替和贪婪量词的正则表达式语言 ? , * , 和 + . (这本质上是 PCRE 的子集，没有反向引用、环视断言或其他一些更高级的位。)是否添加非贪婪量词 ?? , *? , 和 +?增加这种形式主义的表现力？

换句话说，给定一个包含非贪婪量词的模式 S，该模式能否重写为不包含非贪婪量词的等效模式 T？

如果在文献中考虑过这个问题，我会很感激任何人都可以提供的任何引用资料。关于扩展正则表达式形式主义的表达能力，我几乎没有提出任何理论工作(除了关于反向引用如何将您从常规语言转移到上下文无关语法的常见事情之外)。

Answer 1

当您说“正则表达式”时，您指的是几种技术——这不仅仅是基础理论的问题。考虑这个问题“这个字符串是否与我给定的正则表达式匹配？”对于这样的问题，“贪婪”的概念只是一个实现细节 - 如果您使用的是一种常见(但效率低下)的回溯实现，这可能会影响性能但不会影响输出。同样，问题“这个字符串是否包含匹配项？”不受贪婪与非贪婪量词的影响。第一种正则表达式与集合成员的抽象概念有关:定义匹配字符串的语言。

那么为什么非贪婪量词甚至存在呢？正则表达式不仅仅用于匹配；常见的实现可以定位匹配的位置以及正则表达式的哪些部分匹配输出的哪些部分。通过这样做，用户依赖于实现的复杂性，这不是微不足道的。第二种类型的正则表达式涉及在其他图灵完备语言的上下文中将少量文本转换为更实用的表示。

一般来说，当你谈到正则表达式形式主义的力量时，你是在谈论第一个世界——计算机以一个简单的是或否来回答。很容易谈论，因为规范很明确。当您谈论贪婪与非贪婪量词时，您是在谈论第二个世界 - 在实践中使用了很多，但其规范主要是在没有太多计划解决实际问题的情况下发展起来的，并且由于向后兼容而成为标准.第二个世界正在解决完全不同的问题，我不清楚“表达能力”在这里应该是什么意思。当然，非贪婪是可行的。这就是重点...

非贪婪量词对第一种表现力没有任何作用，它们对第二种表现力有作用，尽管目前还不太清楚“表现力”在这里的含义。