uck*_*man 8 regex theory pcre non-greedy
假设我有一个正则表达式语言支持文字,正面和负面的字符类,有序交替,和贪婪的量词?,*和+.(这基本上是一个没有反向引用PCRE的子集,环视断言,或其他一些票友位.)是否加入nongreedy量词??,*?以及+?增加这种形式主义的表现力？
换句话说,给定一个包含非定量量词的模式S,该模式是否可以重写为不包含非同义量词的等效模式？
如果在文献中考虑过这个问题,我会感谢任何人都可以提供的任何参考.我几乎没有关于扩展正则表达式形式主义的表达能力的任何理论工作(除了关于后向引用如何将你从常规语言转移到无上下文语法之外).
当您说“正则表达式”时，您指的是多种技术 - 这不仅仅是基础理论的问题。考虑这个问题“这个字符串与我给定的正则表达式匹配吗？” 对于这样的问题，“贪婪”的概念仅仅是一个实现细节 - 如果您使用一种常见（但效率低下）的回溯实现，这可能会影响性能，但不会影响输出。类似地，问题“这个字符串包含匹配项吗？” 不受贪婪量词与非贪婪量词的影响。第一种类型的正则表达式涉及集合成员资格的抽象概念：定义匹配字符串的语言。
那么为什么非贪婪量词会存在呢？正则表达式不仅仅用于匹配；常见的实现可以定位匹配的位置以及正则表达式的哪些部分与输出的哪些部分匹配。通过这样做，用户依赖于实现的复杂性，这并不是微不足道的。第二种类型的正则表达式涉及在图灵完整语言的上下文中将一些文本位转换为更实际的表示形式。
一般来说，当你谈论正则表达式形式主义的力量时，你谈论的是第一个世界——计算机用简单的是或否来回答。因为规范很明确，所以很容易谈论。当您谈论贪婪量词与非贪婪量词时，您谈论的是第二个世界 - 在实践中使用了很多，但其规范大多是在没有太多计划来解决实际问题的情况下增长的，并且凭借向后兼容性成为标准。第二个世界正在解决完全不同的问题，我什至不清楚“表达力”在这里应该意味着什么。当然，非贪婪是可行的；这就是重点......
非贪婪量词对第一种表达能力没有任何作用，但对第二种表达能力却有作用，尽管“表达能力”在这里意味着什么还不太清楚。