컴공 전공서에도 잘 안 나오는 '프랫 파싱' 쉽게 이해하는 팁

요약 한 해외 개발자가 C 언어 수식 파서를 만들다 션팅 야드(Shunting-yard) 알고리즘에서 프랫 파싱(Pratt parsing)으로 전환하며 깨달은 핵심 원리를 정리한 기술 블로그 글입니다. 작성자는 컴퓨터공학 정규 교육 과정이나 유명 전공서적인 '드래곤북' 등에서는 프랫 파싱을 거의 다루지 않고 LR 파서나 재귀 하강(Recursive Descent) 위주로 가르치지만, 실제 컴파일러 개발이나 프로그래밍 언어 이론계(PLT)에서는 프랫 파싱이 널리 쓰인다고 설명합니다. 그는 기존 션팅 야드 알고리즘의 경우 스택과 결합 강도(binding power)를 이용해 후위 표기법(Postfix)으로 변환하기 쉽지만, 부분식(subexpression) 개념이 없어 괄호, 단항 연산자, 우결합 연산자, 가변 인자 함수 등을 처리할 때 코드가 복잡해지는 한계가 있다고 지적했습니다. 반면 프랫 파싱은 명시적인 연산자 스택 대신 함수의 '호출 스택(Call Stack)'을 암시적인 부분식 영역으로 활용하는 것이 핵심입니다. 모든 우선순위 레벨을 일일이 중첩 호출하는 재귀 하강과 달리, 부분식에 진입하고 복귀할 때만 스택을 타기 때문에 구현이 매우 직관적이고 가볍다는 점을 C 언어 예제 코드와 함께 소개하고 있습니다.