貪欲でないパターン式

Question

私はFriedlの "Mastering Regular Expressions"を読んでいて、単語で区切られた文字列の共通の非貪欲パターン表現を考案しようとしています。 （Friedlのを基準とした）パターンがあるかもしれない

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 '区切り文字speciaリットル式はに拡張することができます。

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

  1. これは正しいですか？
  2. それは証明できますか？
  3. 特別の式を簡略化できますか？
  4. このために、より優れた/より効率的な表現がありますか？ n.b.私はperlの非貪欲な「*？」を使用していません。オペレータと交代を避ける。
  5. このタイプの問題の参考資料はどこにありますか（Friedlは言及しましたが、公表された解決策には至りませんでした）。

Answer 1

1. はい、正しく表示されます。
2. 有限オートマトン - 非決定的（NFA）と確定的（DFA）について読んでみたいです。単純な正規表現システムは基本的に有限オートマトンの便利な表記法です。コンパイラに関する良い本には、NFAとDFAを扱う章があります。
3. おそらくそうではない、あまりないかもしれません。あなたの言葉が長ければ長いほど、あなたが許すべきバックトラックが増えます。