Açgözlü Olmayan Desen İfadesi

Question

Friedl tarafından "Mastering Regular Expressions" (İleri Düzeyli İfadeleri İfade Etme) adlı kitabını okuyorum ve bir kelime ile sınırlandırılmış bir dize için yaygın bir açgözlü olmayan desen ifadesi tasarlamaya çalışıyorum.

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

olan (Friedl referansla) model aşağıdaki gibi olabilir::

• [ayrılmış kelime sentezleme 'birsadece bir tek karakteri burada temel başlayarak Normal * kapanış gerçek çoklu karakteri 'için taşıma]

ab 'ayırıcı:

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

olan model aşağıdaki gibi olabilir: için sonradan

• [ kapatma Normal * (özel *)]' abc 'sınırlayıcı specia l ifade uzatılabilir:

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

  1. Bu doğru mu?
  2. Kanıtlanabilir mi?
  3. Özel ifadesi basitleştirilebilir mi?
  4. Bunun için daha iyi/daha etkili ifadeler var mı? N.B. Perl’in açgözlü olmayanı kullanmıyorum * operatör ve alternasyondan kaçınmak.
  5. Bu tür bir sorunla ilgili referans materyalleri nerede bulabilirim (Friedl alınıp yayınlanmış bir çözümden kısa bir süre sonra durduruldu).

Answer 1

1. Evet, doğru görünüyor.
2. Sonlu otomata - nondeterministik (NFA) ve deterministik (DFA) hakkında bilgi edinmek istiyorsunuz. Basit regexp sistemleri esas olarak sonlu otomata için kullanışlı bir göstergedir. Derleyicilerle ilgili iyi bir kitabın NFA ve DFA'yı kapsayan bir bölümü olacaktır.
3. Muhtemelen çok fazla değil. Sözünüz ne kadar uzun olursa, izin vermeniz gereken daha fazla geriye dönüş var.