Regex: Backtrack 이란?

아래에 쓸 개념이 맞는지는 확실히는 모르겠다. 하지만 맞는 듯 하다. 이런 저런 Regex 에 관련된 글을 읽으면서 Backtrack 이란 개념을 여러 번 접했는데, 그간 제대로 정리를 못했다.
여기서, 더 잊기 전에, 자취를 남기도록 한다.

Backtrack 이란 Regex 엔진이 작동하는 방식 중 하나를 일컫는데, Greedy Quantifier 를 쓸 때 나타나는 현상이다. Greedy/Lazy 에 관해서는 예전에 정리한 적이 있다.

위 글에서처럼 <p>.*</p> 를 하면, * Quantifier 가 욕심꾸러기이기 때문에, <p> 를 먼저 찾은 후, 글 끝까지를 모두 매칭시키게 된다. 그리고 나서, 한 글자씩 뒤로 이동(Backtrack)하며 < 가 있는지를 찾게 된다. 이게 바로 Backtracking 이다.

이걸 MS 문서에는 ‘역행검사’ 또는 ‘역추적’등으로 번역을 해놨다. 다음 글이 꽤 유용하니 이해가 가지 않을 때, 뚫어져라 쳐다보면 (아마도) 답이 보일 듯도 하다.

• 정규식의 역행 검사

자연, Backtracking 이 많으면 연산이 느려진다. Regex 를 자주 쓰게 되는 경우라면, 이걸 줄이려는 노력이 필요하겠다. 물론, 전문 프로그래머들에게나 필요하겠으나..