Pratt 파싱, shunting yard와 비교하면 쉽게 이해된다: 연산자 스택을 호출 스택으로 바꾸기
들어가며
수식 파서나 컴파일러를 직접 만들어 본 분이라면 연산자 우선순위 처리에서 한 번쯤 막혔을 거예요. 흔히 쓰이는 방법은 shunting yard 알고리듬이지만, 기능을 하나씩 더할수록 코드가 금세 복잡해집니다.
오늘 소개할 글은 C 표현식 파서를 만들던 개발자가 Pratt 파싱을 공부하며 정리한 기록입니다. 핵심은 단순합니다. Pratt 파싱은 shunting yard가 쓰는 명시적 연산자 스택을 호출 스택(재귀)으로 바꾼 것이라고 이해하면 된다는 것이죠.
핵심 요약
- Pratt 파싱은 결합력(binding power) 으로 연산자 우선순위를 처리합니다.
- 연산자에 필요한 부분 표현식을 재귀 호출로 파싱하고, 다음 연산자의 결합력에 따라 계속 진행할지 복귀할지 정합니다.
- 일반적인 재귀 하강 파서처럼 표현식마다 모든 우선순위 단계를 거치지 않고, 부분 표현식에 들어갈 때만 호출을 중첩합니다. 그래서 코드가 더 짧고 조금 더 효율적이에요.
- 연산자별 처리 함수를 두는 구조라서 괄호, 단항 연산자, 후위 연산자를 추가하기 쉽습니다.
배경: 왜 Pratt 파싱인가
글쓴이는 예전에 계산기를 만들 때 shunting yard를 사용했습니다. 이번에는 나중에 컴파일러로 키울 수도 있는 C 표현식 파서를 만들면서 Pratt 파싱을 살펴봤다고 해요.
Pratt 파싱은 컴퓨터 과학 정규 과정에서는 잘 다루지 않는 주제입니다. 글쓴이는 다음 자료로 공부했다고 합니다.
- Crafting Interpreters로 기본기 다지기
- 형식적인 논문 읽기 연습을 겸해 Pratt의 원 논문 읽기
- 이미 알고 있던 shunting yard와 하나씩 대응시키며 재귀와 우선순위의 관계 이해하기
Shunting yard 다시 보기
shunting yard는 출력 스트림과 연산자 스택을 사용합니다. 결합력이 높은 연산자일수록 피연산자와 더 강하게 묶이고, 산술 연산에서는 *가 +보다 결합력이 높습니다.
처리 규칙
- 숫자나 식별자처럼 단독으로 쓰이는 토큰은 바로 출력합니다.
- 새 연산자의 결합력이 스택 맨 위 연산자보다 높으면 스택에 넣습니다.
- 결합력이 같거나 낮으면, 스택에서 결합력이 같거나 높은 연산자를 모두 꺼내 출력한 뒤 새 연산자를 넣습니다.
- 입력이 끝나면 스택에 남은 연산자를 모두 출력합니다.
3번 규칙은 모든 연산자가 왼쪽 결합이라고 가정한다는 점을 기억해 두세요.
원문의 최소 C 예제는 연산자 스택 크기를 32로 잡고, +와 -의 결합력을 1, *와 /의 결합력을 2로 둡니다. 숫자는 한 글자 단위로 읽고, 나머지 입력은 모두 올바른 연산자라고 가정합니다. 이 예제에 1+5*2+6을 넣으면 후위 표기법 1 5 2 * + 6 +가 출력됩니다.
기능을 늘리기 어려운 이유
shunting yard에는 재귀적인 부분 표현식이라는 개념이 없습니다. 그래서 기능을 추가할 때마다 특수 처리가 늘어납니다.
- 괄호:
)를 만나면 짝이 되는(가 나올 때까지 스택을 꺼내는 처리가 따로 필요합니다. - 단항 연산자, 오른쪽 결합 연산자, 가변 인자 함수: 지원하려고 할수록 처리 로직이 복잡해집니다.
명시적 스택을 재귀 호출로 바꾸기
Pratt 파싱으로 넘어가는 핵심은 연산자 스택을 호출 스택으로 대신하는 것입니다.
- 중위/후위 연산자를 만나면 그 연산자의 결합력을 인자로 넘겨 오른쪽 부분 표현식을 재귀 파싱합니다.
- 재귀 호출 안에서는 다음 연산자의 결합력을 보고 계속 파싱할지, 호출한 쪽으로 돌아갈지 정합니다.
- shunting yard에서 낮은 결합력의 연산자를 만나 스택을 꺼내던 동작이 Pratt 파서에서는 재귀 호출에서 복귀하는 동작에 해당합니다.
구조를 간단히 그려 보면 다음과 같습니다.
void expr(Parser *parser, int left_bindpower) {
// 접두 처리 (nud): 최소 예제에서는 숫자만 출력, 숫자가 아니면 오류 후 중단
...
// 중위/후위 처리 (led)
while (left_bindpower < get_bindpower(cur(parser))) {
char op = cur(parser);
advance(parser);
expr(parser, get_bindpower(op)); // 오른쪽 표현식을 먼저 재귀 파싱
printf("%c ", op); // 그다음 연산자 출력
}
}
구현 포인트를 정리하면 이렇습니다.
Parser구조체에는 현재 입력 위치를 저장합니다.- 조건이
left_bindpower < get_bindpower(...)이므로, 결합력이 같거나 낮으면 복귀합니다. 이 비교 덕분에 연산자가 왼쪽 결합으로 처리됩니다. - 입력 종료 토큰(널 문자)의 결합력은 0이고, 최초 호출도 결합력 0으로 시작합니다.
1+5*2+6을 넣으면 shunting yard와 똑같이1 5 2 * + 6 +가 출력됩니다.
접두 처리로 괄호 지원하기
expr()은 두 부분으로 나뉩니다. Pratt의 원 논문에서 쓰는 이름도 함께 적어 둡니다.
| 부분 | 역할 | 원 논문 용어 |
|---|---|---|
| 앞부분 | 접두 토큰 처리 | nud |
| 뒷부분 | 중위/후위 연산자 처리 | led |
재귀 하강 파서처럼 연산자를 만나는 즉시 그 연산자만의 코드를 실행할 수 있다는 점이 장점입니다. 접두 토큰을 따로 처리하는 구조와 함께 쓰면 기능을 늘리기가 훨씬 쉬워집니다.
괄호는 여는 괄호를 접두 토큰으로 다루는 방식으로 추가합니다.
(의 결합력은 0으로 둡니다.(를 만나면 입력을 한 칸 전진한 뒤 안쪽 표현식을 재귀 파싱합니다.- 파싱이 끝난 위치에
)가 없으면 오류를 내고 중단합니다.
이 처리는 별도의 paren() 함수로 빼도 되고 expr() 안에 직접 넣어도 됩니다. 1+5*(2+6)을 넣으면 1 5 2 6 + * +가 출력됩니다. shunting yard처럼 스택을 거슬러 꺼내는 특수 처리가 필요 없어요.
규칙 구조체로 유지보수하기 쉬운 파서 만들기
연산자가 늘어나면 결합력 조회와 처리 함수 선택을 규칙 구조체 하나로 묶는 것이 좋습니다. 이렇게 하면 파서의 핵심 루프는 거의 그대로 두고, 규칙 테이블에 항목만 추가하면 됩니다.
원문에 공개된 구조화된 C 예제는 같은 표현식 문법에 다음 연산자를 더 지원합니다.
- 단항
+,- - 후위
!
실제 코드베이스에서 Pratt 파서를 유지보수하기 쉬운 형태로 키워 가는 방법을 보여 주는 예제입니다.
마무리
Pratt 파싱이 어렵게 느껴졌다면, shunting yard의 연산자 스택을 호출 스택으로 옮긴 것이라고 생각해 보세요. 스택을 꺼내던 동작은 재귀 복귀가 되고, 괄호와 단항 연산자는 연산자별 처리 함수로 자연스럽게 들어갑니다. 직접 언어나 DSL을 만들 계획이라면 이 글의 최소 예제부터 따라 짜 보는 것을 추천합니다.