Ruby로 구현하는 DFA 기반 정규 표현식 엔진의 원리와 구축

도입

본 기사는 SmartHR의 엔지니어이자 CRuby 기여자인 타카다 유다이(@ydah)의 발표를 바탕으로, 정규 표현식 엔진의 내부 작동 원리를 Ruby로 직접 구현하며 탐구하는 과정을 담고 있습니다. 흔히 블랙박스로 취급되는 정규 표현식이 실제로는 어떤 수학적 모델을 기반으로 하며, 왜 현대적인 확장 기능들이 엄밀한 의미의 '정규' 언어 범주를 벗어나는지에 대한 깊이 있는 통찰을 제공합니다.

정규 표현식 매칭의 주요 접근 방식

발표에서는 정규 표현식 매칭을 위한 네 가지 주요 기법을 제시하며, 특히 DFA 기반 엔진의 단순함과 속도를 강조합니다.

DFA 기반 엔진: RE2, Hyperscan 등에서 사용하며, 선형 시간(O(n)) 매칭을 보장하여 백트래킹 문제를 방지합니다.
백트래킹 NFA 엔진: Ruby, Python, PCRE 등 대다수 범용 언어에서 채택하고 있는 방식입니다.
VM/바이트코드 기반 및 정규 표현식 미분(Derivatives) 방식.

컴파일 파이프라인: 패턴에서 기계로

정규 표현식 엔진은 패턴을 파싱하여 고속 매칭 머신으로 변환하는 일련의 파이프라인으로 구성됩니다.

AST(추상 구문 트리): 연산자 우선순위의 모호함을 제거합니다.
NFA(비결정적 유한 오토마타): Thompson 구성법을 사용하여 리터럴, 연결, 선택( ), 반복(*) 구조를 재귀적으로 결합하여 구축합니다.
DFA(결정적 유한 오토마타): 부분집합 구성법(Subset Construction)을 통해 NFA의 비결정성을 제거합니다. 하나의 DFA 상태가 NFA 상태들의 집합을 나타내게 함으로써 매칭 시 모호함을 없앱니다.

Ruby를 활용한 구현의 이점

Ruby는 알고리즘 그 자체에 집중할 수 있게 해주는 최적의 언어입니다. Set, Hash와 같은 강력한 내장 데이터 구조와 자동 메모리 관리 기능을 통해, 저수준 언어보다 훨씬 우아하고 명확하게 복잡한 전산학 개념을 코드로 옮길 수 있습니다.

결론

DFA 기반 엔진 구축 과정은 복잡한 시스템을 명확한 이론적 근거를 바탕으로 제어하는 방법을 보여줍니다. 타카다 유다이는 'Hoozuki'라는 참조 구현체를 통해 이론이 실제 코드로 구체화되는 과정을 증명했으며, 이는 개발자들이 정규 표현식을 단순한 도구가 아닌 깊이 있는 컴퓨터 과학의 학습 대상으로 인식하게 하는 계기를 제공합니다.

Ruby로 구현하는 DFA 기반 정규 표현식 엔진의 원리와 구축

Building a DFA-Based Regular Expression Engine in Ruby

핵심 요약

도입

정규 표현식 매칭의 주요 접근 방식

컴파일 파이프라인: 패턴에서 기계로

Ruby를 활용한 구현의 이점

결론

관련 글들

Ruby와 파서 이론을 활용한 대만어 로마자-한자 정렬 문제 해결

Ruby 정규 표현식 엔진 Exreg

Ruby World Conference 2025에서 얻은 교훈

Ruby 출시 30주년 회고: 불완전함에서 시작된 커뮤니티와 Ruby 4를 향한 여정

댓글 0

로그인이 필요합니다

아직 댓글이 없습니다