Нежадное Выражение

Question

Я читал «Освоение регулярных выражений» Фридла и пытался разработать общее не жадное шаблонное выражение для строки, которая ограничена словом.Начиная с основ, где слово с разделителями представляет собой просто один символ ' 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)...

, из которого может быть шаблон (со ссылкой на Фридла):

• [ нормальный * закрытие ]

Переход к реальному многосимвольному разделителю ' 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 ' выражение special можно расширить до:

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

1. Это правильно?
2. Можно ли это доказать?
3. Можно ли упростить выражение special ?
4. Есть ли лучше/ более эффективные выражения для этого?nb Я не использую не жадный Perl '*?'оператор и избегая чередования.
5. Где я могу найти справочный материал по этому типу проблемы (упомянул Фридл, но остановился на опубликованном решении).

Answer 1

1. Да, выглядит правильно.
2. Вы хотите прочитать о конечных автоматах - недетерминированных (NFA) и детерминированных (DFA). Простые системы регулярных выражений, по сути, удобные обозначения для конечных автоматов. В любой хорошей книге по компиляторам есть глава, посвященная NFA и DFA.
3. Вероятно, нет, или не очень. Чем дольше ваше слово, тем больше отступлений вы должны учитывать.