자바 정규표현식

정규표현식은 주어진 String에서 주어진 패턴에 맞는 캐릭터만 골라내는 검색 엔진이라 표현할 수 있다.

이때 정규표현식의 내부는 유한 오토마타로 구현되어있다. 

내부 동작

먼저 정규표현식은 내부적으로 언어마다의 세부적인 문법 차이를 제외하고 대부분 비슷하게 구현되어있다.

 

패턴과 String이 주어지고 String의 왼쪽부터 시작하여 오른쪽 방향으로 비교를 시작한다.

이때 String을 한 번에 캐릭터 하나씩 파싱하여 패턴과 비교하는데 이때 패턴에서도 왼쪽-오른쪽 방향으로 비교를 하며 나아간다.

 

String의 인풋과 String의 패턴을 비교한다고 가정해보자. 

먼저 String 첫번째 캐릭터와 패턴의 첫번째 캐릭터가 일치하면 두번째 캐릭터끼리 비교한다.

두번째 캐릭터가 일치하면 똑같은 비교가 쭉 이어지고 일치하지 않는 경우에 String의 두번째 캐릭터와 패턴의 첫번째 캐릭터를 비교한다.

위 과정을 첫 번째 패턴을 찾을 때까지 반복하며, 패턴을 찾는 즉시 종료한다.

 

위 설명을 통해 알 수 있는 것은 정규표현식은 greedy하며 eager하게 동작한다는 점이다.

greedy하다는 것은 매순간 최선의 선택을 하려고 한다는 의미이고

eager하다는 것은 전체를 순회하지 않고 패턴에 매치하는 것을 찾는 순간 종료한다는 의미이다.

 

메타문자

정규표현식을 어지럽게 만드는 주요원인인 메타문자가 존재하는 이유를 내부 동작을 통해서 이해할 수 있다.

원래 String과 String끼리 비교하는 용도로 탄생한 것이 정규표현식이다. 이때 String에는 어떤 캐릭터도 들어갈 수 있으므로 특정 캐릭터를 사용하여 이 캐릭터는 이런 경우에 사용합시다.라고 약속한 것이 메타문자라고 할 수 있다.

 

자바에는 다음과 같은 메타 문자 등이 존재한다.

. ^ $ * + ? \ | { } [ ] ( ) 

해당 문자 하나 하나에는 전부 의미가 있고 위에서도 말했듯 약속을 통해 정한 것이라 외우는 (대부분의 경우, 필요할 때마다 검색하는) 수 밖에 없다.

 

"^x" : 인풋이 x로 시작하는지 확인한다. 

주의 - [^x]는 x가 아닌 모든 문자 확인을 의미한다.

"x$" : 인풋이 x로 끝나는지 확인한다.

 

".x" : 임의의 문자 하나 + x가 존재하는지 확인한다.

e.g. "x.z" : "xyz", "xaz" ...

"x|y" : x 또는 y가 존재하는지 확인한다.

주의 - x|y와 같이 빈 공간 없이 작성해야 한다. x | y와 같이 작성 금지.

 

"x*" : x가 0번 이상 반복하는지 확인한다. 0 - n

"x+" : x가 1번 이상 반복하는지 확인한다. 1 - n

"x?" : x가 존재하든 존재하지 않든 상관하지 않는다. 0 - 1

 

"x{n}" : x가 n번 반복하는지 확인한다."x{n,}" : x가 n번 이상 반복하는지 확인한다.
"x{n,m}" : x가 n번 이상 m번 이하 반복하는지 확인한다. 주의 - m이 exclusive가 아님

 

"[xy]" : x, y 중 하나를 의미한다. 주의 - "[a-z]" : 아스키코드를 기준으로 'a'부터 'z'까지 모든 캐릭터 중 하나를 의미한다.

"[^a-z]" : 'a'부터 'z'가 아닌 것. 즉 알파벳 소문자가 아닌 모든 것 중 하나를 의미한다.

 

"(xy)" : 정확히 "xy"를 의미한다.

 

특수문자

* + $ | 의 경우 [] 내부에 작성해야 한다.

( ) { } [ ] ^ 의 경우 \\를 앞에 붙여주어야 한다. 

 

성능

for 루프와 String 메서드와 비교했을때 성능은 기본적으로 어떤 내용을 어떻게 구현하는지에 따라 성능이 좋을 수도 나쁠 수도 있다.정규표현식 엔진은 그저 단순한 알고리즘에 불과하다. 위의 내부 구현에서 확인했듯이"왼쪽에서부터 오른쪽으로" 확인하는 경우와 "특정문자를 찾는" 경우에 최적화된 알고리즘을 제공한다.

정규표현식이 유리하게 작용할 수도, 그렇지 않을 수도 있다는 의미이다. 적절한 경우에 적절하게 사용하는 것이 중요하다.

 

레퍼런스

https://www.youtube.com/watch?v=YBTvrkRg0FA 

https://devopedia.org/regex-engines#:~:text=A%20regex%20engine%20executes%20the,to%20the%20next%20input%20character.

Regex Engines

https://bestowing.github.io/automata/automata4/

[오토마타 이론] 4. 유한 오토마타