재귀 하향 파서 (recursive descent parser)
쉽게 풀면
재귀 하향 파서는 문법 규칙 하나하나를 그대로 프로그램의 함수 하나씩으로 옮겨 적은 것과 비슷하다. 예를 들어 '표현식은 항 더하기 항으로 이루어진다'는 규칙이 있으면, '표현식을 파싱하는 함수'는 내부에서 '항을 파싱하는 함수'를 두 번 호출하는 식으로 구현된다. 문법 자체와 파서 코드의 구조가 거의 일대일로 대응하기 때문에 이해하고 직접 작성하기가 비교적 쉬워, 파서 생성기 없이 손으로 직접 구현하는 컴파일러나 인터프리터에서 흔히 선택되는 방식이다.
왜 중요한가
재귀 하향 파서는 문법 규칙과 코드 구조가 거의 일대일로 대응해 이해하기 쉽고 손으로 직접 구현하기도 편리하기 때문에, 새로운 프로그래밍 언어나 설정 파일 형식, 도메인 특화 언어(DSL)를 설계하는 연구·개발에서 프로토타입 구현체로 자주 채택됩니다. 또한 컴파일러 교육이나 파싱 이론을 다루는 논문에서 다른 파싱 기법(예: LL, LR 파서)과 비교하는 기준점 역할도 합니다.
논문에서는 이렇게 쓰입니다
간단한 문법에 대해 직접 손으로 구현하는 파서 방식을 설명할 때 사용된다.
새로운 프로그래밍 언어나 DSL을 설계하는 논문에서는 문법이 자주 바뀌는 개발 초기 단계에 재귀 하향 파서를 채택했다는 설명이 흔히 등장합니다.
컴퓨터교육 논문에서는 재귀 하향 파서가 문법과 코드의 대응 관계를 눈으로 확인할 수 있어 파싱 개념을 가르치는 교육용 도구로도 활용됩니다.
조금 더 깊게 보면
재귀 하향 파서를 논할 때는 흔히 예측 파싱(predictive parsing)과 함께 다뤄지는데, 이는 다음에 올 입력 토큰을 미리 몇 개 살펴보는 전방탐색(lookahead)을 이용해 어떤 생성 규칙을 적용할지 분기 없이 곧바로 결정하는 방식입니다. 이런 예측 파싱이 가능하려면 문법이 LL(k) 조건(왼쪽에서 오른쪽으로 읽으며 k개의 전방탐색만으로 규칙을 결정할 수 있는 조건)을 만족해야 하며, 이 조건을 만족하지 않는 모호한 문법은 재귀 하향 방식으로 다루기 어렵거나 별도의 처리(예: 역추적)가 필요합니다.
주의할 점
재귀 하향 파서는 좌재귀 문법 규칙(자기 자신을 왼쪽 맨 앞에서 참조하는 규칙)을 직접적으로는 처리할 수 없어, 이런 문법은 우재귀 형태로 변형하거나 다른 파싱 기법을 사용해야 한다.