"9줄짜리 알고리즘 이해하려 애쓰지 마라" 프랫 파싱을 블랙박스로 쓰는 법

요약 해외 개발자 커뮤니티에서 컴파일러 구문 분석 기법 중 하나인 '프랫 파싱(Pratt parsing)'을 바라보는 관점을 다룬 글이 화제가 되었습니다. 글쓴이는 수많은 프랫 파싱 튜토리얼들이 알고리즘 자체의 구현 원리를 장황하게 설명하느라 시간을 낭비하고 있지만, 정작 중요한 것은 알고리즘 내부가 아니라 이를 대하는 '추상화적 사고방식(mindset)'이라고 지적했습니다. 작성자에 따르면 고수준 언어로 작성된 프랫 파싱의 핵심 루프는 단 9줄에 불과하며, 퀵정렬의 내부 구현을 몰라도 라이브러리로 편리하게 쓰듯 파싱 알고리즘 역시 내부 동작을 완전히 이해하지 못해도 블랙박스로 복사해 사용할 수 있다고 강조했습니다. 1973년에 등장한 이후 알고리즘 자체가 변하지 않은 만큼, 복잡한 파서 생성기를 라이브러리로 추가하는 대신 이 9줄의 코드를 프로젝트에 넣고 본질적인 부분에 집중하는 것이 낫다는 주장입니다. 글쓴이가 강조하는 진짜 핵심은 더글러스 크록포드(Douglas Crockford)의 설명처럼 "토큰의 왼쪽에 무엇이 올 것으로 기대되는가?"라는 질문 하나로 파싱을 단순화하는 것입니다. 전통적인 파싱 기법(예: GNU Bison)이 생성 규칙(비단말 기호)에 의미론적 동작을 연결하는 반면, 프랫 파싱은 단말 기호(토큰) 자체에 동작을 연결합니다. 즉, 왼쪽에 아무것도 오지 않는 토큰(nud, null denotation)과 왼쪽에 선행 표현식이 필요한 토큰(led, left denotation)이라는 두 가지 개념 및 바인딩 파워(우선순위) 테이블만 구성하면 복잡한 수식 파서도 쉽게 구현할 수 있다는 점을 실무 코드 예시와 함께 전했습니다.