티스토리 뷰
정규식이 유한상태기계라는 건 알겠는데, 실제로는 어떻게 구현되어 있을까요?
그리고 ,전 글의 예시에서 보여준 [IF문]을 연속으로 쓴거랑 뭐가 다를까요?
실제 Java 정규식 엔진의 내부를 파헤쳐보겠습니다.
Java 정규식 엔진의 진짜 정체
노드 기반 그래프 구조
Java의 정규식 엔진은 실제로 노드들을 연결한 그래프로 구현되어 있어요.
// OpenJDK 내부 구조 (실제)
abstract class Node {
Node next; // 다음 노드로의 포인터
abstract boolean match(Matcher matcher, int i, CharSequence seq);
}
이게 바로 상태기계의 그래프 표현입니다:
- 각 Node = 상태
- next 포인터 = 상태 전이
- match() 메서드 = 전이 조건
패턴에서 노드 그래프로 변환
정규식 "a(b|c)*d"가 어떻게 변환되는지 보면
입력: "a(b|c)*d"
↓
[파서] 토큰 분해
↓
StartNode → SliceNode("a") → LoopNode → SliceNode("d") → AcceptNode
↓
GroupNode
├─ SliceNode("b")
└─ SliceNode("c")
이런식으로 변환됩니다.
실제 노드 구현들
// 개념적인 구조
class SliceNode extends Node { // "abc" 같은 리터럴 문자열
char[] buffer;
boolean match(Matcher matcher, int i, CharSequence seq) {
// 문자열을 직접 비교
for (int j = 0; j < buffer.length; j++) {
if (seq.charAt(i + j) != buffer[j]) return false;
}
return next.match(matcher, i + buffer.length, seq);
}
}
class GroupNode extends Node { // (a|b) 같은 그룹
Node[] alternatives;
boolean match(Matcher matcher, int i, CharSequence seq) {
// 각 대안을 시도
for (Node alt : alternatives) {
if (alt.match(matcher, i, seq)) return true;
}
return false;
}
}
class LoopNode extends Node { // a* 같은 반복
Node body;
int min, max;
boolean match(Matcher matcher, int i, CharSequence seq) {
// 백트래킹으로 최적의 매칭 찾기
for (int count = min; count <= max; count++) {
if (tryMatch(count, matcher, i, seq)) return true;
}
return false;
}
}
순수 정규식 부분 (상태기계)
기본 패턴 매칭은 정말 단순한 상태기계로 동작해요:
// 기본 매칭 로직
Node current = startNode;
int position = 0;
while (current != null && position < input.length()) {
if (current.matches(input.charAt(position))) {
current = current.next; // 다음 상태로 전이
position++;
} else {
return false; // 매칭 실패
}
}
return current == acceptNode; // 최종 상태 도달했나?
이 부분은 정말 우리가 배운 유한상태기계와 동일해요!
어셈블리로의 번역 과정
이제 컴파일러 단에서 어떤식으로 JAVA 코드를 번역해주는지 보러갈까요?
JIT 컴파일러 시점
JIT 컴파일러가 노드 그래프를 어셈블리로 번역해줘요:
// Java 노드 실행 코드
if (current.matches(currentChar)) {
current = current.next;
position++;
}
# JIT이 생성하는 어셈블리
LOAD R1, [current_ptr] # current 노드 로드
LOAD R2, [input_ptr] # 현재 문자 로드
CALL [R1 + matches_offset] # matches() 메서드 호출
TEST RAX, RAX # 결과 체크
JZ BACKTRACK # 0이면 백트래킹으로 점프
# 매칭 성공시
LOAD R3, [R1 + next_offset] # current.next 로드
MOV current_ptr, R3 # current 업데이트
INC input_ptr # position++
JMP MAIN_LOOP # 다음 매칭으로
근데 요즘 Graal 많이 쓰시잖아요?.. JIT과는 어떠한 차이가 있는지 좀더 조사해봤어요.
GraalVM의 혁신적 접근
JIT vs GraalVM
JIT(보수적)
Java 바이트코드 → [C2 컴파일러] → 네이티브 코드
GraalVM (혁신적?.. 방식)
Java 바이트코드 → [Graal 컴파일러] → 그래프 기반 IR → 고도로 최적화된 기계어
그래프 기반 최적화의 위력
GraalVM은 Sea of Nodes라는 그래프 표현을 사용해요..
솔직히.. 제 수준에서는 잘 이해를 못하겠어요.., 궁금하신 분들은 좀더 스스로 찾아보시는걸로..
정규식 패턴 "ab*c" 처리
↓
[Graal] 데이터 플로우 그래프 생성
↓
LoadChar₁ → CompareA → Branch → LoadChar₂ → CompareB → Loop → LoadChar₃ → CompareC
↓
그래프 최적화
- 불필요한 노드 제거
- 공통 부분식 제거
- 루프 언롤링
- 분기 예측 최적화
↓
초고도로 최적화된 기계어
실제 최적화 차이
JIT
# 보통 이런 식으로 번역
CALL matches_method
TEST RAX, RAX
JZ fail_label
CALL next_method
Graal
# 훨씬 더 공격적 최적화
# 메서드 인라이닝 + 루프 언롤링 + 분기 예측 최적화
# 원래 여러 메서드 호출이었던 것이 하나의 최적화된 블록으로
CMP BYTE PTR [R5], 'a' # 첫 번째 문자 비교
JNE fail_fast
INC R5 # position++
# 'b*' 루프를 언롤링
loop_b:
CMP BYTE PTR [R5], 'b'
JNE check_c
INC R5
# 4번까지 언롤링해서 루프 오버헤드 제거
CMP BYTE PTR [R5], 'b'
JNE check_c
INC R5
# ... (반복)
JMP loop_b
check_c:
CMP BYTE PTR [R5], 'c'
JNE fail_fast
# 성공!
벤치마크 결과
실제 성능 차이 (정규식 처리)
- 간단한 패턴: GraalVM이 15-25% 빠름
- 복잡한 백트래킹: GraalVM이 30-50% 빠름
- Native Image: 시작 시간 10-100배 빠름
- 메모리 사용량: Native Image가 2-5배 적음
결론
Java 정규식 엔진의 실제 구현:
- 노드 그래프: 상태기계를 객체 지향적으로 표현
- 백트래킹: 강력한 기능을 위한 복잡성 추가
- JIT 최적화: 런타임에 효율적인 기계어로 변환
- GraalVM: 그래프 기반 분석으로 한 단계 더 진화
순수 정규식 부분은 정말 단순한 상태기계 그래프가 맞아요. 백트래킹과 고급 기능들이 복잡함을 만든 주범이고, GraalVM 같은 차세대 컴파일러는 이 모든 걸 더 똑똑하게 최적화하고 있는 거죠!
정규식 하나 쓸 때마다 이런 복잡한 기계가 돌아간다니... 참 신기하네요.