假设我有一个正则表达式语言支持文字,正面和负面的字符类,有序的交替,贪婪的量词？,*,和,以及非正确的量词??,*？和？. (这实际上是PCRE的一个子集,没有反向引用,环视断言或其他一些更高级的位.)用无序交替替换有序交替是否会降低这种形式主义的表达能力？
(无序交替—有时也称为“无序选择”—是L(S | T)= L(S)L(T),而有序交替是L(S | T)= L( S)(L(T) – {a in L(T)：a在L(S)中延伸一些b}}.具体地说,如果交替是无序的,模式a | aa将匹配字符串a和aa,但仅限于a如果订购了更改.)
换句话说,给定包含有序交替的模式S,该模式是否可以重写为不包含有序替换的等效模式T(但可能是无序替换)？
如果在文献中考虑过这个问题,我会感谢任何人都可以提供的任何参考.我几乎没有关于扩展正则表达式形式主义的表达能力的任何理论工作(除了关于后向引用如何将你从常规语言转移到无上下文语法之外).
在
http://swtch.com/~rsc/regexp/regexp3.html [部分“正则表达式是否匹配字符串的子字符串？如果是,在哪里？”]有必要在“DFA”中引入优先级的想法(我需要阅读整个系列以理解,我怀疑,但有问题的“DFA”从NFA图“动态”扩展到处理有序的替换.虽然这只是对权威的诉求,而不是证据,但我认为如果russ cox不能这样做(将有序的替代表达为纯粹的DFA),那么没有人知道怎么做.
原文链接：https://www.f2er.com/regex/356788.html