표현식 파서는 계산기부터 컴파일러 프런트엔드까지 거의 모든 언어 도구의 출발점이다. 한 개발자가 C 표현식 파서를 만들려다 결국 컴파일러로 발전시킬 생각으로 '프랫 파싱(Pratt parsing)'을 공부하고 그 과정을 정리한 글은, 파서 구현을 고민해 본 실무자에게 참고할 만한 관점을 던진다. 흥미로운 점은 이 기법이 정규 전산학 커리큘럼에서 거의 다뤄지지 않는다는 사실이다. 파싱을 깊게 설명하는 이른바 '드래곤 북'조차 프랫 파싱을 언급하지 않고, 대부분의 프로그래밍 언어 수업은 학풍에 따라 LR 파싱이나 재귀 하강(recursive descent)을 가르친다. 프랫 파싱은 주로 컴파일러 개발자와 프로그래밍 언어 이론(PLT) 커뮤니티에서 공유되며, 가장 널리 알려진 소개 자료는 『Crafting Interpreters』 정도다.
샨팅 야드의 한계
저자는 이전에 샨팅 야드(shunting yard) 알고리즘으로 계산기를 만든 경험이 있었다. 샨팅 야드는 출력 스트림과 연산자 스택을 두고, 각 연산자에 '결합력(binding power)'을 부여한다. 결합력이 높을수록 피연산자에 더 강하게 결합하는데, 산술식에서 곱셈이 덧셈보다 결합력이 높은 것이 대표적인 예다. 입력 토큰을 하나씩 훑으며 스택을 적절히 비워 후위 표기법 등으로 변환하는 구조는 비교적 단순하고 이해하기 쉽다.
문제는 확장성이다. 샨팅 야드에는 재귀적 의미의 '부분식(subexpression)' 개념이 없다. 괄호를 지원하려면 닫는 괄호 토큰에 '여는 괄호를 만날 때까지 스택을 비우는' 특수 동작을 따로 붙여야 한다. 괄호 자체는 어렵지 않지만, 단항 연산자나 우결합 연산자, 가변 인자 함수처럼 조금만 복잡한 규칙을 더하려 하면 코드가 금세 지저분해진다. 바로 이 지점에서 프랫 파싱으로의 전환이 설득력을 갖는다.
명시적 스택을 호출 스택으로
저자가 정리한 핵심 통찰은 '변환'의 성격이다. 샨팅 야드를 프랫 파서로 바꾸는 열쇠는 연산자용 명시적 스택을 없애고, 대신 프로그램의 호출 스택을 활용해 필요할 때마다 부분식으로 재귀 진입하는 것이다. 이때 중위·후위 연산자의 '왼쪽 결합력(left binding power)'을 재귀 호출에 함께 넘겨주고, 현재 연산자의 결합력이 넘겨받은 왼쪽 결합력보다 작아지면 호출에서 반환한다. 즉 샨팅 야드에서 결합력이 낮은 연산자를 만나 스택을 비우는 동작이, 프랫 파서에서는 재귀 호출에서 돌아 나오는 것과 정확히 대응한다. 저자가 Pratt의 원 논문을 직접 읽으며 한참을 씨름하다가 '한 번에 딸깍 이해됐다'고 말한 순간도 바로 이 대응 관계를 포착했을 때였다.
이 구조에는 재귀 하강과 구별되는 장점이 있다. 재귀 하강은 모든 표현식마다 우선순위 단계를 빠짐없이 거쳐 함수 호출을 중첩시키지만, 프랫 파서는 실제로 부분식에 진입할 때만 중첩한다. 그만큼 약간 더 효율적이면서 코드도 깔끔하다는 것이 저자의 평가다. 다만 변환 과정에 매끄러운 '중간 단계'가 없다는 점은 솔직히 인정한다. 샨팅 야드 코드를 조금씩 리팩터링해 프랫 파서로 만드는 식이 아니라, 전체를 한꺼번에 뒤집어 결과를 놓고 비교하며 받아들여야 한다는 것이다.
확장성이라는 실질적 이득
겉보기에 '스택을 암묵적으로 바꿨을 뿐'이라 대단치 않아 보이지만, 실무적 가치는 확장성에서 드러난다. 괄호를 추가하는 일이 샨팅 야드처럼 특수 처리로 번지지 않고 자연스럽게 녹아든다. 더 나아가 결합력을 조회하는 함수와 실행할 서브루틴 선택 로직을 하나로 합쳐, 각 연산자를 '결합력 + 전위 서브루틴 + 후위 서브루틴'을 담은 규칙(struct)으로 저장하면, 핵심 루프는 단순하게 유지한 채 연산자마다 독립된 작은 함수로 동작을 분리할 수 있다. 이 구성은 『Crafting Interpreters』의 해당 장에 설명돼 있으며, 저자도 자신의 스니펫 저장소에 단항 +·-와 후위 ! 연산자를 더한 확장 예제를 직접 공개해 두었다고 밝혔다.
정리하면 이 글은 새로운 알고리즘의 발견이라기보다, 익숙한 샨팅 야드를 지렛대 삼아 프랫 파싱의 재귀 구조를 이해하는 학습 경로를 보여준다. 표현식 우선순위를 다루는 파서를 직접 손봐야 하는 개발자라면, 명시적 스택과 호출 스택이 어떻게 같은 일을 하는지를 기준점으로 삼는 것이 이 기법을 체화하는 가장 빠른 길일 수 있다. 다만 공식 커리큘럼 바깥의 기법인 만큼 체계적인 교재가 드물고, 전환 과정의 직관을 스스로 세워야 한다는 점은 여전히 진입 장벽으로 남는다.