이 글에서는 컴파일러 이론의 핵심 개념인 하향식(top-down) 구문 분석과 상향식(bottom-up) 구문 분석의 차이점에 대해 자세히 알아보겠습니다.
구문 분석(parsing)은 입력 문자열이 주어진 문법 규칙에 부합하는지 검사하고 파스 트리(parse tree)를 구성하는 과정입니다. 이 과정은 트리를 탐색하는 방향에 따라 두 가지 방식으로 나뉘며, 각 방식의 특징은 아래와 같습니다.
하향식(Top-down) 구문 분석
- 파스 트리의 최상위 노드(루트)에서 시작하여 아래로 내려가며 트리를 구성하는 구문 분석 기법입니다.
- 문법(grammar)의 생성 규칙을 이용해 전개(derivation)를 수행합니다.
- 좌측 유도(leftmost derivation) 방식을 사용합니다.
- 입력 문자열에 대한 좌측 유도 과정을 찾아내는 것을 목표로 합니다.
- 분석은 파스 트리의 루트에서 잎 노드(leaf node) 방향으로, 즉 위에서 아래로 진행됩니다.
- 이 기법의 핵심 결정 사항은 문자열을 구성하기 위해 어떤 생성 규칙(production rule)을 적용할지 선택하는 것입니다.
상향식(Bottom-up) 구문 분석
- 하향식 구문 분석과 정반대로, 파스 트리의 최하위 노드(잎 노드)에서 시작하여 위로 올라가며 트리를 구성하는 기법입니다.
- 마찬가지로 문법 규칙을 기반으로 동작합니다.
- 우측 유도(rightmost derivation)의 역과정을 적용합니다.
- 입력 문자열에 대한 우측 유도를 역추적하는 방식으로 분석을 수행합니다.
- 입력 문자열을 문법의 시작 기호(start symbol)로 축소(reduce)하는 것을 목표로 합니다.
- 생성 규칙을 거꾸로 적용하여 문자열을 단계적으로 줄여나가 시작 기호에 도달하는 방식으로 진행됩니다.
두 방식의 핵심 차이점 비교
| 구분 | 하향식 구문 분석 | 상향식 구문 분석 |
|---|---|---|
| 탐색 방향 | 루트 → 잎 노드 (위→아래) | 잎 노드 → 루트 (아래→위) |
| 유도 방식 | 좌측 유도 | 우측 유도의 역과정 |
| 처리 목표 | 시작 기호에서 입력 문자열로 전개 | 입력 문자열을 시작 기호로 축소 |
| 핵심 연산 | 생성 규칙 선택 및 적용 | 축소(reduce) 연산 |
| 대표적인 파서 | LL 파서, 재귀 하강 파서 | LR, SLR, LALR 파서 |
정리하면, 하향식 구문 분석은 문법의 시작 기호에서 출발해 입력 문자열을 향해 전개해 나가는 반면, 상향식 구문 분석은 입력 문자열에서 출발해 시작 기호를 향해 축소해 나간다는 점이 가장 큰 차이입니다. 실제 컴파일러 설계에서는 하향식 방식이 LL 계열 파서에, 상향식 방식이 LR 계열 파서에 활용됩니다.