非贪婪模式表达式

Question

我一直在阅读Friedl的《精通正则表达式》，并尝试为由单词分隔的字符串设计一个通用的非贪婪模式表达式。 从基础开始，当被分隔的单词只是一个单字符 'a' 时，表达式：

sed -r 's/([^a]*)(a)/\                                                                  
(1)\1(2)\2(ALL)&(END)/g' <<<"xaxxaxxxaxxx...aa..."

(1)x(2)a(ALL)xa(END)
(1)xx(2)a(ALL)xxa(END)
(1)xxx(2)a(ALL)xxxa(END)
(1)xxx...(2)a(ALL)xxx...a(END)
(1)(2)a(ALL)a(END)...

可能来自 Friedl 的模式是：

• [ 正常*关闭 ]

接下来是一个真正的多字符'ab'分隔符：

sed -r 's/([^a]*)((a[^b]*)*)(ab)/\                          
(1)\1(2)\2(3)\3(4)\4(ALL)&(END)/g' <<<"xabxxabxxxabxxx...abxxx...aabxxx...axxx...aaabxaabaxabaxaxabxaxaabxxaaabaaxxab..."

(1)x(2)(3)(4)ab(ALL)xab(END)
(1)xx(2)(3)(4)ab(ALL)xxab(END)
(1)xxx(2)(3)(4)ab(ALL)xxxab(END)
(1)xxx...(2)(3)(4)ab(ALL)xxx...ab(END)
(1)xxx...(2)a(3)a(4)ab(ALL)xxx...aab(END)
(1)xxx...(2)axxx...aa(3)axxx...aa(4)ab(ALL)xxx...axxx...aaab(END)
(1)x(2)a(3)a(4)ab(ALL)xaab(END)
(1)(2)ax(3)ax(4)ab(ALL)axab(END)
(1)(2)axax(3)axax(4)ab(ALL)axaxab(END)
(1)x(2)axa(3)axa(4)ab(ALL)xaxaab(END)
(1)xx(2)aa(3)aa(4)ab(ALL)xxaaab(END)
(1)(2)aaxx(3)aaxx(4)ab(ALL)aaxxab(END)...

可能的模式为：

• [ normal* (special*)* closing ]

对于后续的'abc'分隔符，特殊表达式可以扩展为：

(a[^b]*)*(ab[^c]*)*

1. 这个正确吗？
2. 可以证明吗？
3. 这个特殊的表达式能简化吗？
4. 是否有更好/更有效的表达式？请注意，我没有使用perl的非贪婪'*?'运算符并避免交替。
5. 我在哪里可以找到此类问题的参考资料（Friedl暗示了但未公布解决方案）。

- potong

---

我离“掌握正则表达式”还差得远呢，甚至一点都不好笑。但我很感兴趣。你能解释一下为什么不想使用这两个运算符：？和|吗？非常感谢。 - Gaute Løken

为什么不使用负向先行断言？ - Ludovic Kuty

@Ikuty，恐怕这不是sed的报告范围之内。 - potong

@potong 你说得对，我忘记考虑上下文了。 - Ludovic Kuty

@potong 是时候放出赏金了。 :) - jaypal singh

第二个例子：如果输入是 abacabc 呢？ - Benoit

Answer 1

1. 是的，看起来正确。
2. 你想要了解有限自动机 - 非确定性（NFA）和确定性（DFA）。简单的正则表达式系统本质上是有限自动机的方便注释。任何一本好的编译器书籍都会有一章介绍NFA和DFA。
3. 可能不是或者很少。你的单词越长，你就必须允许更多回溯。

- Anton Tykhyy