정규 언어의 병 교 차

본 고 는 나의 공식 사이트 인 nfabo. cn 에 전재 되 었 다.
정규 언어의 병 교 차
작성 자: 
rockeet 발표 날짜: 
2014 년 09 월 08 일 분류: 
자동 동기 댓 글: 
0 조 읽 기 횟수: 7 회 [편집]
정규 표현 식 은 정규 언어 를 묘사 하고 형식 언어 와 자동 동기 이론 을 배 운 사람 은 모두 알 아야 한다. 정규 언어 는 병, 교, 차, 보 연산 에서 모두 폐쇄 적 이다.하지만 Wikipedia 의 묘 사 는 지금까지 알려 진 정규 문법 (Flavor) 이 정규 문법 에 교차 하 는 것 과 차 이 를 포함 시 키 지 않 았 다.이론 과 실천 사이 에 이렇게 큰 갭 이 있다 니!
Perl 정규 에서 지원 하 는 서 라운드 (Look Around) 는 어떤 의미 에서 교차 와 차 의 제한 부분 집합 이 라 고 볼 수 있 지만 제한 을 받 는 이 유 는 자 유 롭 게 그룹 을 합병 하여 교차 작업 을 할 수 없 기 때 문 입 니 다.다른 한편, 이 엔진 들 을 둘 러 보 는 것 은 모두 역 추적 방식 으로 이 루어 져 효율 이 매우 낮다.
사실은 정규 언어 만 병, 교, 차, 보 연산 에서 모두 폐쇄 된 것 이 아니 라 정규 언어 를 표현 하 는 DFA 는 이러한 조작 을 비교적 효과적으로 실현 할 수 있다. NFA 가 DFA 로 전환 하 는 O (2n) 와 비교 하고 교차 하 는 복잡 도 는 O (n * m) 이 며 보충 하 는 복잡 도 는 O (n) 이다.이것 은  O (2n) 는 낙관적 으로 많이 해 야 한다. 그리고 이것 은 최 악의 상황 에서 의 복잡 도 일 뿐 현실 에서 O (n1 +) 일 때 가 많다.ε)，그 중의ε 흔히 0 에 가 깝 고 NFA 가 DFA 로 전환 하 는 최 악의 O (2n) 는 현실 에서 도 O (n1 +) 이다.ε)，근 데 이거ε 왕왕 좀 커 야 한다.
한 번 의 노력 을 통 해 저 는 교차, 차 라 는 장벽 을 메 웠 습 니 다. 언어의 완비 성과 용이 성 을 위해 전통 적 인 정규 적 인 합병, 연결, 중복 도 실현 하고 전통 적 인 것 과 구별 하기 위해 서 입 니 다. RegEx, 잠시 불 러 주세요. RegEx++。
언어 디자인 에 있어 서 한편 으로 는 복잡 한 전의, 문자 류, 유 니 코드 와 같은 수렁 을 처리 하 는 것 을 피하 기 위해 다른 한편 으로 는 전통 적 인 정규 와 호 환 하기 위해 제 가 디자인 한 것 입 니 다. RegEx++ 언어 는 두 부분 으로 나 뉘 는데, 일 부 는 서 라운드 와 역방향 인용 을 제거 한 Perl 정규 (re2 문법) 이 고, 일 부 는? RegEx++ 특유 의 합치다 연결, 반복.
BNF 패 러 다 임 으로 표현

Union  :=Inter{'||'Union}
Inter  :=ConCat{'&&'ConCat|'&!'ConCat}
ConCat :=Repeat{Repeat}
Repeat :=Atom['?'|'*'|'+'|Range]
Atom   :='{{'Regex'}}'|'('Union')'
Range  :='{'Min[','Max]|','Max'}'

좀 더 통속 적 으로 표현 하 다
우선 순위
조작 부호
설명 하 다.
가장 높다
{{Plain Old Regex}}
{{}} 묶 은 부분 은 전통 적 인 정규 표현 식 입 니 다. re2 의 Parser 로 해석 합 니 다.
비교적 높다
(   )
우선 순위 조정
높다
?
반복: 0 회 또는 1 회
문법 과 의 미 는 전통 정규 와 같다.
*
반복: 0 회 혹은 여러 번
+
반복: 1 회 혹은 여러 번
{min,max}
반복: 최소 min 회, 최대 max 회
중.
조작 부호 없 음
연결
낮다
&&
교차, x & y 는 x 와 일치 할 수 있 고 y 와 일치 할 수 있 음 을 나타 낸다.
&!
차이, x &! y 는 x 와 일치 하지만 Y 와 일치 하지 않 음 을 나타 낸다.
최저한도
||
그리고 x | y 표현 은 x 와 일치 하거나 y 와 일치 할 수 있 습 니 다.
이 안에서 유일 하 게 어색 한 것 은 {{} 을 묶 은 것 이다. Plain Old Regex, 특히, { 화해시키다 }}，정규 표현 식 (re2 문법) 을 묶 는 데 사용 되 며, 문법 이 정확 하고 규범 화 된 정규 표현 식 에는 나타 나 지 않 습 니 다. {{ 화해시키다 }}，예외 만 있 습 니 다: \ {, 이 예 외 는 쉽게 처리 할 수 있 습 니 다. 사실 엄 밀 히 말 하면 문법 이 정확 한 정규 표현 식 에 나타 날 수 있 습 니 다. {{ 화해시키다 }}，그러나 이러한 정규 표현 식 은 종종 문제 가 있다. { 화해시키다 } 비 원 문자 로 사용 할 때 는 전의 (\ {와 \}) 가 필요 합 니 다. { 화해시키다 } 뜻 을 바 꾸 지 않 을 때 는 메타 문자 로 나타 나 지 않 습 니 다. {{ 화해시키다 }}， Plain Old Regex 미 전의 허용 { 화해시키다 } '잘못 을 용인 하기 위해' 전통 정규 문법 은 심지어 이런 정규 까지 용인 한다. [[[] *, 그리고 ]{{1 - 2}, 이게 무슨 뜻 인지 알 아?
마지막.
통과 하 다. 이 테스트 페이지 일부 예시 와 해당 하 는 DFA / NFA 상태 전이 도 를 볼 수 있다.