假设我有一个正则表达式语言支持文字,正面和负面的字符类,有序的交替,以及贪婪的量词？,*和. (这实际上是PCRE的一个子集,没有反向引用,环顾四周的断言,或者其他一些更高级的位.)是否添加了非同义词量词？,*？和？增加这种形式主义的表现力？
换句话说,给定一个包含非定量量词的模式S,是否可以将该模式重写为不包含非同义量词的等效模式？
如果在文献中考虑过这个问题,我会感谢任何人都可以提供的任何参考资料.我几乎没有关于扩展正则表达式形式主义的表达能力的任何理论工作(超出了关于后向引用如何将你从常规语言转移到无上下文语法的常规事物).
当你说“正则表达式”时,你指的是几种技术 – 这不仅仅是基础理论的问题.考虑一下这个问题“这个字符串是否符合我给定的正则表达式？”对于这样一个问题,“贪婪”的概念仅仅是一个实现细节 – 如果你使用的是一种常见(但效率低下)的回溯实现,这可能会影响性能而不会影响输出.同样,问题“这个字符串是否包含匹配？”不受贪婪与非贪婪量词的影响.第一种类型的正则表达式涉及集合成员资格的抽象概念：定义匹配字符串的语言.
原文链接：https://www.f2er.com/regex/356916.html那么为什么非贪婪量词甚至存在呢？正则表达式不仅用于匹配;常见的实现可以找到匹配的位置以及正则表达式的哪些部分匹配输出的哪些部分.通过这样做,用户依赖于实现的复杂性,这不是微不足道的.第二种类型的正则表达式涉及将一些文本转换为更实际的表示,其中包含其他图灵完备语言的上下文.
一般来说,当你谈到正则表达式形式主义的力量时,你谈论的是第一个世界 – 计算机以简单的是或否回答.这很容易谈,因为规范很明确.当你谈到一个贪婪与非贪婪的量词时,你谈论的是第二个世界 – 在实践中使用了很多,但是规范主要是在没有太多计划来解决实际问题的情况下成长,并且由于向后兼容性而成为标准.这第二个世界正在解决完全不同的问题,我不清楚“表达能力”在这里应该是什么意思.当然,非贪婪是可行的;这就是重点……
非贪婪量词对于第一种表现形式没有做任何事情,而且他们在第二种情况下做了什么,尽管不知道“表现力”在何处意味着什么并不十分清楚.
