regex - 反向应用的正则表达式会产生相同的匹配吗？

Question

假设我们有一些文本和一个与之匹配的正则表达式。问题：如果我将相同的表达式向后应用（从最后一个字母到第一个字母），它仍然匹配吗？

正则表达式 -----> 文本

xereg --?--> txt

在似乎可行的实践中，问题在于理论对一般情况的看法。

Answer 1

如果您使用 Kleene 星号，则不会 - 如果您反转正则表达式，您最终会得到一个无效的正则表达式或匹配不同模式的正则表达式：

• ab*-> *ba（无效语法）
• a*b-> b*a（第一个匹配aaab但不匹配abbb，第二个匹配bbba但不匹配baaa）

另一方面，我很确定有可能设计一个算法，给定一个正则表达式，生成一个匹配反向字符串的正则表达式。以下递归算法应该可以工作（如果r是正则表达式，则rev(r)表示匹配反转字符串的正则表达式）：

• 如果r是单个符号x，则rev(r) = x。
• 如果r是联合A|B，则rev(r) = rev(A)|rev(B)。
• 如果r是串联AB，则rev(r) = rev(B)rev(A)。
• 如果r是 Kleene 星A*，则rev(r) = rev(A)*。

Answer 2

一般来说，我肯定会说“不”，但这实际上取决于表达式的复杂性。

因为不仅需要反转任何简单的（子）表达式，而且如果适用，还需要考虑更复杂的东西，这些东西在任何正则表达式中都不容易“反转”：重复运算符怎么样，懒惰与. 贪婪，或反向引用和环顾，量词和修饰符...... - 例如本教程中解释的项目？

或许如果你有关于这种“逆转”的更具体的例子或问题，可以考虑一个更合适的答案。

Answer 3

一般原因是不会

例如，正则表达式

ab

将匹配

ab

但不是

ba

您为什么认为一般情况下应该这样做？

有匹配反向字符串的正则表达式以及

[a|b]*

将匹配

ab 

和

ba

Answer 4

regex和xeger都会在文本上产生相同匹配的情况是：

1. regex是一个简单的（原子）模式，它是回文。例如，abcba
2. regex由使用交换函数（例如or）的几个原子模式组成，并且您不会反转这些单独的原子模式。如果你这样做了，那么它们也应该是回文。例如，adef|bd881|cdavr如果您不反转原子组件，或者[aba|defed]如果您确实反转了原子组件。