LHJ

I'm a FE developer.

17.5 입력 소비

24 May 2020 » js_lj

17.5 입력 소비

정규식을 ‘큰 문자열에서 부분 문자열을 찾는 방법’이라고만 생각해서는 안 됩니다.
물론 원하는 것이 그것일 수도 있겠지만, 그런 사고방식이 굳어지면 정규식의 근본적인 성격을 이해하지 못하게 되고 할 수 있는 일도 제한됩니다.

좀 더 나은 개념은 정규식이 입력 문자열을 소비하는 패턴이라고 생각하는 겁니다.
찾아낸 부분 문자열은 그렇게 소비한 결과 만들어지는 부산물입니다.

어린이들이 글을 배울 때 자주 하는 게임인, 글자를 바둑판 모양으로 늘어놓고 그중에서 단어를 찾는 게임을 떠올리면 정규식이 어떻게 동작하는지 좀 더 쉽게 이해할 수 있습니다.
세로나 대각선은 무시하고, 바둑판의 맨 윗줄에서만 단어를 찾아봅시다.

X J A N L I O N A T U R E J X E E L N P

사람은 이런 게임을 아주 쉽게 할 수 있습니다.
쓱 훑어보기만 해도 LION, ION, NATURE, EEL을 찾을 수 있겠죠.

역주_
eel은 장어입니다.

컴퓨터, 그러니까 정규식은 사람 만큼 똑똑하지 않습니다.
정규식의 입장에서 이 게임을 풀어보면, 정규식이 어떻게 동작하는지 알 수 있고 우리가 주의해야 할 정규식의 한계도 알 수 있습니다.

단순하게 갑시다.
정규식으로 LION, ION, NATURE, EEL을 찾는 겁니다.
달리 말해, 답을 알려주고 그 답을 검증할 수 있는지 보는 겁니다.

정규식은 첫 번째 글자 X에서 시작합니다.
찾으려는 단어 중에서 X로 시작하는 단어가 없으니 일치하는 것이 없다고 판단합니다.
정규식은 거기서 멈추지 않고 다음 글자 J로 이동합니다.
J로 시작하는 단어도 없죠.
A로 이동합니다.
이렇게 이동하는 과정에서, 정규식 엔진이 지나간 글자를 소비했다(consume)고 표현합니다.
자, L에 도착했습니다.
정규식 엔진은 “L? LION이 될 수 있겠군”하고 생각할 겁니다.
L은 일치할 가능성이 있으므로 정규식은 L을 소비하지 않습니다.
이건 꼭 기억해야 할 중요한 점입니다.
계속해서 I, O, N을 만납니다.
이제 일치하는 단어를 찾았습니다!
일치하는 단어를 찾았으니 L, I, O, N은 소비됩니다.

그런데 LION과 NATURE가 겹치는군요.
사람은 여기서 문제를 느끼지 않지만, 정규식은 이미 소비한 것은 절대로 보지 않습니다.
다시 말해, 이미 소비한 것을 가지고 일치하는 것을 찾으려고 ‘뒤로 가는’ 일은 없습니다.
N을 이미 소비했으므로 정규식은 NATURE를 찾지 못합니다.
A T U R E를 확인히지만, 이것으로는 우리가 원하는 단어를 만들 수 없습니다.
하지만 EEL은 찾아냅니다.

다시 돌아가서, 예제의 LION에서 O를 X로 바꿔봅시다.
무슨 일이 일어날까요?
정규식이 L에 도달하면 LION에 일치할 가능성이 있다고 판단하고 L을 소비하지 않습니다.
I도 마찬가지로 소비하지 않고 미뤄둡니다.
다음에는 X를 만납니다.
이 시점에서 정규직은 일치하는 단어를 찾을 수 없다고 판단합니다.
LIX로 시작하는 단어는 없으니까요.
그러면 정규식은 일치할 가능성이 있다고 판단했던 곳, 즉 L로 돌아가서 L을 소비한 후 계속 진행합니다.
이제는 NATURE를 찾습니다.
LION을 찾지 못했으니 N을 소비하지 않았기 때문입니다.

X J A N L I X N A T U R E J X E E L N P
ㄴ X 가능한게 있나? 없군. X를 소비한다.

X J A N L I X N A T U R E J X E E L N P
  ㄴ 가능한게 있나? 없군. J를 소비한다.

X J A N L I X N A T U R E J X E E L N P
    ㄴ 가능한게 있나? 없군. A를 소비한다.

X J A N L I X N A T U R E J X E E L N P
      ㄴ 가능한게 있나? 없군. N를 소비한다.

X J A N L I X N A T U R E J X E E L N P
        ㄴ 가능한게 있나? 있다! L은 소비하지 않는다.

X J A N L I X N A T U R E J X E E L N P
          ㄴ 가능한게 있나? 있다! I는 소비하지 않는다.

X J A N L I X N A T U R E J X E E L N P
            ㄴ 가능한게 있나? 음.. 없네!? 앞에 L I X 모두 소비한다.

X J A N L I X N A T U R E J X E E L N P
              ㄴ 가능한게 있나? 있다! N은 소비하지 않는다.

...
...

이 과정을 다음과 같은 정규식 예제로 묘사했습니다.

X J A N L I O N A T U R E J X E E L N P
ㄴ X 가능한게 있나? 없군. X를 소비한다.

X J A N L I O N A T U R E J X E E L N P
  ㄴ 가능한게 있나? 없군. J를 소비한다.

X J A N L I O N A T U R E J X E E L N P
    ㄴ 가능한게 있나? 없군. A를 소비한다.

X J A N L I O N A T U R E J X E E L N P
      ㄴ 가능한게 있나? 없군. N를 소비한다.

X J A N L I O N A T U R E J X E E L N P
        ㄴ 가능한게 있나? 있다! L은 소비하지 않는다.

X J A N L I O N A T U R E J X E E L N P
          ㄴ 가능한게 있나? 있다! I는 소비하지 않는다.

X J A N L I O N A T U R E J X E E L N P
            ㄴ 가능한게 있나? 있다! O는 소비하지 않는다.

X J A N L I O N A T U R E J X E E L N P
              ㄴ 일치하는 것을 찾았다! 찾은 것을 전부 소비한다. (L I O N)

X J A N L I O N A T U R E J X E E L N P
                ㄴ 가능한게 있나? 없군. A를 소비한다.

... input 전체를 소비할 때까지 계속한다.

정규식 메타 언어에 대해 살펴보기 전에, 정규식이 문자열을 ‘소비’할 때 사용하는 알고리즘을 간단히 살펴봅시다.

  • 문자열 왼쪽에서 오른쪽으로 진행합니다.
  • 일단 소비한 글자에 다시 돌아오는 일은 없습니다.
  • 한 번에 한 글자씩 움직이며 일치하는 것이 있는지 확인합니다.
  • 일치하는 것을 찾으면 해당하는 글자를 한꺼번에 소비한 후 다음 글자로 진행합니다(정규식에 /g 플래그를 써서 전역으로 검색할 때에 해당합니다. 다시 설명합니다).

이것은 일반적인 부분만 훑어본 것이고, 당연히 이것보다 세밀한 알고리즘이 존재합니다.
예를 들어 일치하는 것이 없다고 판단하고 일찍 포기하는 알고리즘도 있습니다(성능이 개선됩니다).

정규식 메타 언어에 대해 설명할 때도 이 알고리즘을 계속 염두에 두십시오.
왼쪽에서 오른쪽으로 진행하면서 한 번에 한 글자씩 소비하고, 일치하는 것을 찾으면 그 전체를 즉시 소비합니다.

Related Posts