욕심이없는 패턴 표현

Question

저는 Friedl이 "Mastering Regular Expressions"를 읽고 단어로 구분 된 문자열에 공통적 인 욕심이없는 패턴 표현을 고안하려고했습니다.

이

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 '구분 기호 specia L 식으로 확장 할 수 있습니다

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

  1. 이 맞습니까?
  2. 증명할 수 있습니까?
  3. 특별 표현을 단순화 할 수 있습니까?
  4. 더 좋고/더 효율적인 표현식이 있습니까? n.b. 나는 펄의 비 탐욕스러운 '*?'을 사용하지 않고있다. 교환 및 회피.
  5. 이 유형의 문제에 대한 참조 자료는 어디에서 찾을 수 있습니까 (Friedl은 언급했지만 출판 된 솔루션에 미치지 못함).

Answer 1

1. 예, 올바르게 표시됩니다.
2. 유한 비표준 (NFA) 및 결정 론적 (DFA)에 대해 읽고 싶습니다. 간단한 정규 표현식 시스템은 근본적으로 유한 오토마타를위한 편리한 표기법입니다. 컴파일러에 관한 좋은 책은 NFA와 DFA를 다루는 장을 가질 것이다.
3. 아마도 그렇지 않거나별로는 아닙니다. 단어가 길수록 더 많은 백 트랙을 허용해야합니다.