Pratt 파싱, 직관적으로 이해해보기 — 수식 파서를 만드는 가장 우아한 방법

파싱, 왜 어렵게 느껴질까요?

프로그래밍을 하다 보면 "파서(parser)"라는 단어를 종종 만나게 되는데요, 특히 컴파일러나 인터프리터를 공부하려고 하면 가장 먼저 부딪히는 벽이 바로 이 파싱이에요. 파싱이 뭐냐면, 문자열로 된 코드나 수식을 컴퓨터가 이해할 수 있는 구조(보통 트리 형태)로 바꾸는 과정이에요. 예를 들어 1 + 2 * 3이라는 수식을 보면 우리는 곱셈이 먼저라는 걸 바로 알지만, 컴퓨터한테는 이걸 명시적으로 알려줘야 하거든요.

문제는 이 파싱을 제대로 배우려고 하면 교과서에서 BNF 문법, LL 파서, LR 파서, LALR 같은 용어들이 쏟아져 나온다는 거예요. 학부 컴파일러 수업 트라우마가 있는 분도 많을 거고요. 그런데 실전에서 간단한 수식 파서나 DSL(Domain Specific Language, 특정 분야 전용 언어) 파서를 만들 때 이 무거운 이론이 전부 필요한 건 아니에요. 여기서 등장하는 게 바로 Pratt 파싱이에요.

Pratt 파싱, 이게 대체 뭔가요?

Pratt 파싱은 1973년에 Vaughan Pratt이라는 컴퓨터 과학자가 제안한 파싱 기법인데요, 핵심 아이디어는 놀라울 정도로 간단해요. 각 연산자에 "결합 세기(binding power)"라는 숫자를 부여하고, 이 숫자를 비교해서 어떤 연산이 먼저 수행되는지 결정하는 것이에요.

일상적인 비유로 설명해볼게요. 줄다리기를 생각해보세요. 1 + 2 3에서 숫자 2를 +와 가 서로 잡아당기고 있어요. 의 결합 세기가 +보다 높으니까 2는 쪽으로 끌려가요. 그래서 2 * 3이 먼저 계산되는 거죠. Pratt 파싱의 전부가 이거예요. 연산자마다 힘의 세기를 정해두고, 더 센 쪽이 피연산자를 가져가는 거예요.

코드로 보면 더 와닿는데요, Pratt 파서의 핵심 함수는 보통 이런 구조를 가져요. parse_expression이라는 함수가 현재 결합 세기를 인자로 받고, 토큰을 하나씩 읽으면서 "다음 연산자의 결합 세기가 내가 받은 값보다 높은가?"를 계속 확인해요. 높으면 계속 읽어나가고, 낮거나 같으면 지금까지 읽은 걸 반환하는 거예요. 이 재귀적인 구조 하나로 사칙연산, 괄호, 단항 연산자, 심지어 삼항 연산자까지 처리할 수 있어요.

왜 다른 방식보다 좋은 건가요?

전통적인 파싱 방법인 재귀 하강 파서(recursive descent parser)로 수식을 파싱하려면 연산자 우선순위마다 별도의 함수를 만들어야 해요. 덧셈용 함수, 곱셈용 함수, 거듭제곱용 함수... 우선순위가 10단계면 함수가 10개 필요한 거죠. 코드가 길어지고 새로운 연산자를 추가할 때마다 구조를 바꿔야 해요.

반면에 Pratt 파싱은 핵심 루프가 하나예요. 새 연산자를 추가하고 싶으면 그냥 결합 세기 숫자 하나와 처리 함수 하나만 등록하면 돼요. 확장이 엄청나게 쉽죠. 이런 특성 때문에 실제 프로그래밍 언어 구현에서도 많이 쓰여요. 대표적으로 JavaScript 엔진인 V8의 파서, Rust의 rustc 컴파일러에서 수식 파싱 부분 등이 Pratt 파싱 아이디어를 활용하고 있어요.

또 하나 중요한 장점은 좌결합과 우결합을 처리하는 방식이에요. 이게 뭐냐면, a - b - c는 (a - b) - c로 왼쪽부터 계산해야 하고(좌결합), a = b = c는 a = (b = c)로 오른쪽부터 계산해야 하잖아요(우결합). Pratt 파싱에서는 이걸 결합 세기를 왼쪽과 오른쪽에 살짝 다르게 주는 것만으로 해결해요. 왼쪽 결합 세기와 오른쪽 결합 세기의 차이가 1이면 좌결합, 반대면 우결합. 이 우아한 트릭 하나로 복잡한 결합 규칙을 깔끔하게 처리할 수 있어요.

어디에 써먹을 수 있나요?

사실 대부분의 개발자가 프로그래밍 언어 컴파일러를 만들 일은 드물지만, 파서가 필요한 상황은 생각보다 자주 와요. 설정 파일의 조건식 파싱, 검색 쿼리 문법 구현, 사내 도구용 간단한 스크립트 언어 만들기, 수학 수식 계산기 같은 것들이죠. 이런 상황에서 Pratt 파싱은 yacc나 ANTLR 같은 무거운 파서 생성기를 꺼내지 않고도 깔끔하게 해결할 수 있는 방법이에요.

한국 개발자 분들 중에 사이드 프로젝트로 프로그래밍 언어나 계산기를 만들어보시는 분도 꽤 있을 텐데, Pratt 파싱을 알아두면 수식 파싱에서 삽질하는 시간을 크게 줄일 수 있어요. 50줄도 안 되는 코드로 사칙연산과 괄호를 완벽하게 처리하는 파서를 만들 수 있으니까요.