어떤 입력 문자가 정규식의 어느 부분과 일치하는지 확인할 수 있습니까?

Question

문자열에서 패턴을 찾기 위해 정규식과 같은 것을 사용하는 도구를 만들려고합니다 (텍스트 문자열이 아니지만 지금은 중요하지 않습니다). 저는 automata 이론에 익숙합니다. 즉, 기본 정규식을 구현하는 방법을 알고, 문자열이 내 정규식과 일치하는 경우 true 또는 false를 출력합니다. 교과서 방식으로 자동 연산을 시뮬레이트합니다.

이 정규식을 나는 b의 앞에 더 이상 a들과 함께, b의 앞에 오는 모든 a들에 관심이 있어요 말 : 그래서, a[^a]*b. 하지만 내 문자열에 이러한 부분이 포함되어 있는지 확인하고 싶습니다. 출력을 a으로 가져와서 검사 할 수 있도록하고 싶습니다. (실제로 텍스트를 다루는 것이 아닙니다.) 요약

: 그때 출력과 두 번째 a을 원하는 (a)[^a]*b 입력 문자열 bcadacb에 그것을 실행의 난과 같이 괄호로 a을 표시한다고 가정 해 봅시다.

또는 더 일반적으로 입력 문자열의 어떤 문자가 정규식의 어느 부분과 일치하는지 확인할 수 있습니까? 텍스트 편집기에서 어떻게 이루어 집니까? 그들은 경기가 시작된 곳을 적어도 알고 있습니다. 왜냐하면 경기를 강조 할 수 있기 때문입니다. 백 트랙킹 접근법을 사용해야합니까, 아니면 계산적으로 비용이 적고 똑똑한 방법이 있습니까?

편집 : 적절한 뒤로 참조, 즉 괄호로 캡처하고 \ 1 등으로 참조하는 것은 필요하지 않을 수 있습니다. 역 참조 (back reference)는 역 추적 (backtracking) (또는 이와 유사한 것)의 필요성을 소개하고 문제 (IIRC)를 NP 어렵게 만든다는 것을 알고 있습니다. 내 질문은 본질적으로 다음과 같습니다. 캡처 참조 부분이 역 참조없이 적절한 후 참조보다 계산에 덜 비쌉니까?

Answer 1

대부분의 텍스트 편집기는 역 추적 알고리즘을 사용하여이를 수행합니다.이 경우 일치하는 위치를 기록하면 추가하기가 쉽습니다.

괄호 위치 정보가있는 상태 목록을 보완하여 직접 NFA 시뮬레이션을 수행 할 수도 있습니다. 이는 선형 시간 보증을 유지하는 방식으로 수행 될 수 있습니다. http://swtch.com/~rsc/regexp/regexp2.html#submatch을 참조하십시오.

Timos의 대답은 올바른 방향이지만 DFA 상태는 가능한 NFA 상태 모음에 해당하므로 DFA 상태는 괄호를 통과했을 가능성을 나타낼 수 있습니다. 다른 경우도 마찬가지 임) 사실이 아닌 것으로 밝혀지면 그것을 사실로 기록하는 것은 잘못된 것입니다. 대신 NFA 시뮬레이션을 대신해야합니다.

Answer 2

일치하는 DFA를 구성한 후 정규식의 여는 괄호 뒤에 첫 번째 상태에 해당하는 모든 상태를 표시합니다. 이러한 상태를 방문하면 현재 입력 문자의 색인을 저장하고 닫는 괄호에 해당하는 상태를 방문 할 때 색인을 저장합니다. 수락 상태가되면 두 개의 인덱스를 출력합니다. 이것이 텍스트 편집기에서 사용되는 알고리즘인지는 확실하지 않지만 그렇게 할 것입니다.