[컴파일러] 파싱 알고리즘: 하향식(Top-Down) vs 상향식(Bottom-Up)

지난 포스팅에서는 코드의 구조를 검사하는 파싱(Parsing)의 개념과 그 결과물인 파스 트리(Parse Tree), 그리고 문법의 모호성 문제에 대해 다루었다. 파싱이 '문법에 맞는지 검사하는 과정'이라는 점은 이제 명확해졌다.

그렇다면 다음 질문은 이것이다. "컴퓨터는 '어떻게' 이 파싱을 수행하는가?" 오늘은 파스 트리를 구축하는 두 가지 대표적인 전략, 하향식 파싱(Top-Down Parsing)과 상향식 파싱(Bottom-Up Parsing)의 원리와 특징을 알아볼 것이다.

---

1. 하향식 파싱 (Top-Down Parsing)

하향식 파싱은 이름 그대로 파스 트리의 최상단(Top)에서 시작하여 아래(Down)로 내려가는 방식이다. 즉, 문법의 시작 기호(Start Symbol)에서 출발하여 입력된 코드 문자열을 만들어낼 수 있는지 유도 과정을 따라가며 검사하는 전략이다.

 

가장 직관적인 구현 방법은 재귀적 하향 파싱(Recursive-Descent Parsing)이다. 이는 문법의 각 비단말 기호마다 하나의 함수를 할당하고, 해당 함수의 내부에서 문법 규칙에 따라 다른 비단말 기호의 함수를 호출하는 방식이다.

그러나 하향식 파싱에는 치명적인 함정이 있다.

 

바로 좌측 재귀(Left Recursion) 문제이다. 만약 문법 규칙이 A → Aα 와 같은 형태(예: <expr> → <expr> + <term>)를 포함하고 있다면, <expr>를 처리하는 함수가 자기 자신을 무한정 호출하는 무한 루프에 빠지게 된다. 따라서 하향식 파싱을 사용하려면 반드시 문법에서 좌측 재귀를 제거하는 과정이 선행되어야 한다.

이러한 문제와 비효율적인 백트래킹을 해결하기 위해 등장한 것이 예측 파싱(Predictive Parsing),

대표적으로 LL(1) 파서이다.

LL(1)은 코드를 Left-to-right(왼쪽에서 오른쪽으로) 읽고,

Leftmost derivation(최좌측 유도)을 사용하며,

1개의 토큰을 미리 내다보고(lookahead)

 

다음에 적용할 규칙을 예측하여 백트래킹 없이 파싱을 수행하는 똑똑한 방식이다.

---

2. 상향식 파싱 (Bottom-Up Parsing)

상향식 파싱은 하향식과 정반대의 접근법을 취한다. 파스 트리의 가장 아래(Bottom)에 있는 리프 노드(실제 코드)에서 시작하여 위(Up)로 쌓아 올리며 최종적으로 시작 기호 하나로 합쳐지는지 확인하는 방식이다. 이를 축소(Reduction) 과정이라고도 부른다.

상향식 파싱의 가장 일반적인 형태는 Shift-Reduce 파싱이다. 이 파서는 스택(Stack) 자료구조를 이용하여 두 가지 기본 동작을 반복한다.

• Shift: 입력 스트림에서 토큰을 하나 읽어 스택의 맨 위에 쌓는다.
• Reduce: 스택의 맨 위를 살피다가, 특정 문법 규칙의 우변과 일치하는 부분을 발견하면 그것을 해당 규칙의 좌변(비단말 기호)으로 치환(축소)한다.

이 과정을 계속 반복하여 입력 스트림을 모두 소진하고 스택에 시작 기호만 남게 되면 파싱은 성공적으로 완료된다.

상향식 파싱 계열에서 가장 강력하고 널리 쓰이는 알고리즘은 LR 파서이다. LR 파서는 코드를 Left-to-right로 읽고, Rightmost derivation(최우측 유도)의 역순으로 파싱을 수행하며, 미리 만들어진 파싱 테이블을 참조하여 Shift 또는 Reduce 동작을 결정론적으로 수행한다. YACC나 Bison과 같은 파서 생성기(Parser Generator)들이 바로 이 LR 계열의 문법을 기반으로 파서를 자동으로 만들어준다.

---

3. 하향식 vs 상향식, 핵심 차이점 비교

구분	하향식 파싱 (Top-Down)	상향식 파싱 (Bottom-Up)
접근 방식	시작 기호에서 문자열을 유도	문자열에서 시작 기호로 축소
파스 트리 생성	위(루트)에서 아래(리프)로 생성	아래(리프)에서 위(루트)로 생성
대표 알고리즘	재귀적 하향 파서, LL 파서	Shift-Reduce 파서, LR 파서
장점	개념이 직관적이고 손으로 직접 구현하기 용이함	더 넓은 범위의 문법을 처리할 수 있어 강력함
단점	좌측 재귀에 취약하며 처리 가능한 문법에 제약이 있음	동작 원리가 복잡하여 손으로 구현하기 어려움 (주로 도구 사용)

---

마무리하며

오늘은 파스 트리를 만드는 두 가지 핵심 전략인 하향식과 상향식 파싱에 대해 알아보았다. 하향식 파싱이 마치 목적지를 정해두고 길을 예측해 나가는 탐험가 같다면, 상향식 파싱은 눈앞의 재료들을 조립하며 전체 구조를 완성해나가는 건축가와 같다.

결론적으로 두 방식 모두 '코드의 구조가 문법에 맞는가'를 검증하는 동일한 목표를 수행하지만, 그 과정과 장단점에서 차이를 보인다. 현대의 많은 컴파일러는 파서 생성 도구를 이용해 강력하고 효율적인 상향식 LR 파서를 채택하는 경우가 많다.