정규식 대신 파서 컴비네이터 — 6~7배 느려도 읽히는 파서를 함수 조립으로 만든다

작은 함수 조각을 레고처럼 조립해서 문자열을 구조화된 데이터로 바꾸는 "파서 컴비네이터(parser combinator)"를 TypeScript로 밑바닥부터 만들어 보는 글이에요.

• 파서는 함수 하나예요. 문자열을 받아 앞부분을 잘라 값으로 바꾸고, [값, 남은 문자열]을 돌려줍니다. 함수 안에서 정규식을 써도 돼요.
• 조합기는 세 개면 충분해요. 파서를 순서대로 잇는 pSeq, 결과의 모양을 바꾸는 pMap, 더 이상 안 될 때까지 반복하는 pRepeat(정규식의 *에 해당)입니다. 파서를 받아 새 파서를 돌려주는 함수라서 "컴비네이터"라고 불러요.
• 실전 예제로 ping 출력을 파싱해요. 명령 출력 전체를 헤더, 패킷 목록, 통계가 담긴 객체로 바꿉니다. 같은 일을 정규식으로 하면 읽을 수 없는 코드가 된다는 게 기사의 주장이에요.

핵심 아이디어는 "남은 문자열을 다음 파서에 넘긴다"는 것 하나입니다.

기사는 파서 컴비네이터를 정규식과 tree-sitter 사이의 빈자리를 메우는 도구로 소개합니다. 정규식은 복잡해지면 금방 엉키고, tree-sitter처럼 에디터 문법 강조에 쓰이는 본격 파서 라이브러리는 웬만한 일에는 과하다는 거예요.

출처: Parser Combinators — T3

기사에는 성능 이야기가 없어서, 기사의 코드를 그대로 옮겨 Node 24에서 직접 재 봤어요. 결론은 정규식보다 6~7배 느리지만, 보통 쓰는 양에서는 체감하기 어려운 수준입니다.

• 측정 조건: ping 패킷 줄 2,000개를 같은 객체 배열로 바꿨고, 두 방식의 결과가 똑같은지도 확인했어요.
• 결과: 기사의 컴비네이터는 약 11~14ms, 정규식 한 줄로 반복 매칭한 쪽은 약 2ms였습니다. 줄 하나당 몇 마이크로초 차이라, 로그 몇천 줄을 파싱하는 정도면 신경 쓸 일이 아니에요.

느린 이유는 기사가 이해하기 쉬운 쪽을 택했기 때문입니다.

• 실패를 예외로 알려요. throw new Error() 한 번에 약 22µs가 들었는데, 성공한 줄 하나를 파싱하는 시간(약 6µs)의 몇 배예요. 여러 후보를 차례로 시도하는 문법이라면 실패가 잦아서 이 비용이 크게 불어납니다.
• 매 단계 남은 문자열을 새로 잘라요(substring). 실전 라이브러리는 대개 문자열은 그대로 두고 읽는 위치(인덱스)만 옮기며, 실패도 예외 대신 값으로 돌려줍니다.

반대로 정규식에는 특정 입력에서 되돌아가기(backtracking)가 폭발해 멈춰 버리는 ReDoS 위험이 있어요. 성능만 보면 정규식이 빠르지만, 문법이 복잡해질수록 읽기 쉬움과 예측 가능성 쪽에서 컴비네이터가 유리해집니다.

제가 한 기기에서 한 번 잰 마이크로벤치마크라 수치는 참고용입니다. 파서 라이브러리 간 비교로는 Chevrotain 벤치마크 페이지가 있는데, 결과 표가 브라우저에서 직접 실행돼야 나와서 숫자는 확인하지 못했어요.

출처: Parser Combinators — T3 · Chevrotain 성능 비교