非贪婪的模式表达

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)...

模式可能是:

• [ 正常*(特殊*)*结束 ]

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

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

1. 它是否正确？
2. 可以证明吗？
3. 可以简化特殊表达吗？
4. 这有更好/更有效的表达方式吗？我不是用perl的非贪婪'*？' 操作员和避免交替.
5. 我在哪里可以找到这类问题的参考资料(弗里德提到但没有公布解决方案).

Answer 1

\n
1. 是的，看起来是正确的。
\n
2. 您想了解有限自动机 \xe2\x80\x94 非确定性 (NFA) 和确定性 (DFA)。简单的正则表达式系统本质上是有限自动机的一种方便的表示法。任何一本关于编译器的好书都会有一章介绍 NFA 和 DFA。
\n
3. 可能没有，或者说不多。你的话越长，你必须允许的回溯就越多。
\n

\n