'Pratt parsing is a black box'(Pratt 파싱은 블랙박스다)라는 제목의 블로그 글이 올라왔어요. 파서를 직접 짜본 분이라면 제목만으로도 고개를 끄덕일 수 있을 텐데요. 코드는 짧고 잘 돌아가는데, 왜 돌아가는지 설명해보라고 하면 말문이 막히는 알고리즘이거든요. 이 글은 원문 요약이 아니라, Pratt 파싱이 무엇이고 왜 그렇게 느껴지는지를 처음부터 풀어보는 글이에요.
먼저 파서가 뭐냐면, 1 + 2 * 3 같은 글자 덩어리를 컴퓨터가 다룰 수 있는 나무 구조로 바꿔주는 프로그램이에요. 어려운 건 순서인데요. 사람은 곱셈을 먼저 한다는 걸 알지만, 코드는 왼쪽부터 차례로 읽을 뿐이라 이 규칙을 따로 알려줘야 해요. Pratt 파싱은 이 연산자 우선순위 문제를 푸는 기법으로, 1973년에 본 프랫(Vaughan Pratt)이 논문으로 발표했어요.
핵심 아이디어: 숫자를 두고 벌이는 줄다리기
1 + 2 3에서 숫자 2는 +와 사이에 끼어 있죠. 양옆의 연산자가 2를 서로 자기 쪽으로 당긴다고 상상해보세요. 이 당기는 힘을 결합력(binding power)이라고 불러요. 의 힘이 더 세니까 2는 에게 끌려가고, 그래서 2 * 3이 먼저 묶이는 거예요.
이걸 코드로 옮기면 놀랄 만큼 짧아요.
# 연산자별 (왼쪽 힘, 오른쪽 힘)
BP = {'+': (1, 2), '-': (1, 2), '*': (3, 4), '/': (3, 4), '^': (6, 5)}
def parse_expr(tokens, min_bp=0):
left = tokens.pop(0) # 숫자 하나 읽기
while tokens and tokens[0] in BP:
l_bp, r_bp = BP[tokens[0]]
if l_bp < min_bp: # 왼쪽 연산자가 더 세면 멈춤
break
op = tokens.pop(0)
right = parse_expr(tokens, r_bp) # 오른쪽은 재귀로 읽기
left = (op, left, right) # 지금까지를 하나로 묶기
return left
parse_expr([1, '+', 2, '', 3])을 돌리면 ('+', 1, ('', 2, 3))이 나와요. 곱셈이 안쪽으로 잘 들어갔죠. 핵심은 min_bp예요. 재귀로 들어갈 때 "나를 이길 수 있는 연산자만 계속 진행해"라는 기준선을 넘겨주는 셈이거든요.
왼쪽 힘과 오른쪽 힘을 따로 두는 것도 영리한 부분이에요. 1 - 2 - 3은 (1 - 2) - 3으로 묶여야 하는데, -의 오른쪽 힘(2)이 왼쪽 힘(1)보다 세서 왼쪽부터 묶여요. 거듭제곱 ^은 반대로 (6, 5)라서 2 ^ 3 ^ 2가 2 ^ (3 ^ 2)로 오른쪽부터 묶이고요.
토큰의 역할도 두 가지로 나눠요. 앞에 아무것도 없을 때의 동작(nud)과 왼쪽에 이미 식이 있을 때의 동작(led)인데요. -가 -5에서는 부호이고 3 - 5에서는 뺄셈인 걸 이 구분으로 깔끔하게 처리해요. 위 코드에선 첫 줄이 nud, while 안쪽이 led 자리예요. 함수 호출 f(x)나 배열 인덱스 a[i], 삼항 연산자도 같은 틀에 끼워 넣을 수 있어요.
왜 블랙박스처럼 느껴질까
크게 세 가지 이유를 꼽을 수 있어요. 첫째, 문법이 코드에 안 보여요. 재귀 하강 파서는 parse_add가 parse_mul을 부르는 식이라 함수 구조가 곧 문법인데, Pratt에서는 문법이 숫자 표 안으로 숨어버려요. 둘째, 실행 흐름이 머릿속에 잘 안 그려져요. while 루프와 재귀가 얽혀 있어서, 어떤 연산자가 어느 깊이에서 처리되는지 따라가려면 손으로 써봐야 하거든요. 셋째, 숫자의 의미가 상대적이에요. 값 자체엔 뜻이 없고 크기 비교만 의미가 있어서, 표를 고쳤을 때의 영향을 코드만 보고 짐작하기 어려워요.
다른 방식과 비교하면
재귀 하강은 읽기 쉽지만 우선순위 단계마다 함수가 하나씩 필요해서, 연산자가 많으면 코드가 길어져요. 다익스트라의 Shunting-yard 알고리즘은 재귀 없이 스택으로 처리해 동작이 눈에 보이지만, 단항이나 삼항 연산자를 얹기가 번거로운 편이고요. yacc이나 ANTLR 같은 파서 생성기는 문법이 명세로 남는 대신, 에러 메시지를 세밀하게 다듬기가 어려워요.
Precedence Climbing이라는 기법도 있는데, 이름만 다를 뿐 Pratt 파싱과 사실상 같은 알고리즘이라는 분석이 있어요. Pratt 파싱은 오랫동안 묻혀 있다가 더글러스 크록포드(Douglas Crockford)와 밥 나이스트롬(Bob Nystrom)의 글로 널리 알려졌고, 나이스트롬의 책 『Crafting Interpreters』에도 나와요. Rust 언어 서버인 rust-analyzer도 표현식 파싱에 이 방식을 쓰고 있고요.
실무에서는 어떻게 써먹을까
컴파일러를 만들 일이 없어도 쓸모가 있어요. 검색 필터(status:open AND (tag:a OR tag:b)), 권한 규칙, 스프레드시트풍 수식처럼 사용자가 식을 입력하는 기능은 생각보다 많거든요. 이런 곳에 eval을 쓰면 보안 사고로 이어지기 쉬운데, 작은 Pratt 파서를 두면 허용할 연산자를 표 하나로 통제할 수 있어요.
블랙박스가 걱정된다면 두 가지만 챙겨보세요. 먼저 파싱 결과를 (+ 1 (* 2 3))처럼 괄호 문자열로 출력해서 테스트로 고정하세요. 표를 고쳤을 때 뭐가 달라졌는지 바로 보여요. 그리고 재귀 깊이만큼 들여쓰기한 로그를 찍어보면 흐름이 한눈에 들어와요. 이 알고리즘은 읽어서 이해하기보다 돌려보면서 이해하는 편이 훨씬 잘 맞거든요.
마무리
Pratt 파싱은 "연산자끼리 숫자를 당기는 줄다리기"를 재귀 하나로 옮긴 기법이고, 코드가 짧은 대신 문법이 숫자 표 속으로 숨는다는 대가가 있어요. 여러분은 어떠세요? 코드가 조금 길어도 구조가 문법을 그대로 보여주는 쪽과, 짧고 확장하기 쉽지만 한 번 더 생각해야 하는 쪽 중 팀 코드베이스에 어느 쪽을 들이시겠어요?
🔗 출처: Hacker News