파서 생성기 (Parser Generator)
1. 개요
파서 생성기(Parser Generator)란 프로그래밍 언어의 문법을 정의한 명세서를 입력받아, 해당 문법에 맞는 구문 분석기(Parser) 소스 코드를 자동으로 생성해 주는 개발 도구이다.
컴파일러의 전처리 과정은 일반적으로 어휘 분석(Lexical Analysis) $\rightarrow$ 구문 분석(Syntax Analysis) 단계로 진행된다. 어휘 분석기가 소스 코드를 의미 있는 최소 단위인 토큰(Token)으로 분리하면, 파서는 이 토큰들의 배열이 정의된 문법 규칙에 맞는지 검사하고 구조화한다. 이러한 도구는 컴파일러 제작뿐만 아니라 JSON, XML과 같은 데이터 포맷 파싱이나 복잡한 설정 파일 분석 등 다양한 도메인에서 활용된다.
파서를 수동으로 작성(Hand-written Parser)할 경우 언어의 복잡도가 증가함에 따라 코드 유지보수가 매우 어려워지지만, 파서 생성기를 사용하면 문법 정의 파일만 수정함으로써 파서의 동작을 빠르게 변경할 수 있다는 장점이 있다.
2. 동작 메커니즘
2.1 CFG와 BNF
파서 생성기는 기본적으로 CFG(Context-Free Grammar, 문맥 자유 문법)를 기반으로 동작한다. CFG는 언어의 구조를 정의하는 수학적 형식이며, 이를 사람이 읽고 쓸 수 있도록 표기하기 위해 BNF(Backus-Naur Form)라는 메타 언어가 널리 사용된다.
2.2 처리 흐름
파서 생성기의 작동 프로세스는 다음과 같은 파이프라인을 갖는다.
| 단계 |
입력/처리 |
내용 |
출력 |
| 입력 |
문법 정의 파일 |
BNF 또는 EBNF 형식으로 작성된 언어 규칙 |
.g4, .y 등의 파일 |
| 처리 |
파서 생성기 엔진 |
문법 분석 $\rightarrow$ 상태 전이 표(State Transition Table) 생성 $\rightarrow$ 코드 템플릿 적용 |
생성기 내부 로직 |
| 출력 |
파서 소스 코드 |
특정 프로그래밍 언어로 구현된 구문 분석기 클래스/함수 |
.java, .cpp, .py 등 |
3. 주요 파싱 알고리즘 및 유형
파서 생성기는 구현 방식에 따라 크게 하향식(Top-down)과 상향식(Bottom-up)으로 나뉜다. 두 방식 모두 다음 토큰을 몇 개까지 미리 보느냐를 의미하는 Lookahead(k) 값에 따라 문법의 결정력과 처리 능력이 달라진다.
3.1 LL (Left-to-right, Leftmost derivation)
루트 노드에서 시작하여 잎 노드(Leaf node) 방향으로 분석하는 하향식 방식이다. 가장 왼쪽의 비단말 기호부터 유도(Derivation)하는 과정을 거치며, 예측 파싱(Predictive Parsing)을 수행하여 구조가 직관적이다.
[LL 파싱 트리 구조]
Root (S) $\rightarrow$ Non-terminal (A) $\rightarrow$ Terminal (a) (하향식 확장)
3.2 LR (Left-to-right, Rightmost derivation)
잎 노드에서 시작하여 루트 노드 방향으로 병합하며 분석하는 상향식 방식이다. 가장 오른쪽의 유도 과정을 역순으로 추적하여 분석하며, LL보다 더 넓은 범위의 문법을 처리할 수 있어 강력하다. 다만, 상태 전이 표(State Transition Table)의 크기가 매우 커서 수동 작성이 비효율적이며 생성기 의존도가 높다.
[LR 파싱 트리 구조]
Terminal (a) $\rightarrow$ Non-terminal (A) $\rightarrow$ Root (S) (상향식 축약)
3.3 LL vs LR 비교
| 비교 항목 |
LL (Top-down) |
LR (Bottom-up) |
| 분석 방향 |
루트 $\rightarrow$ 잎 (하향식) |
잎 $\rightarrow$ 루트 (상향식) |
| 유도 방식 |
최좌단 유도 (Leftmost Derivation) |
최우단 유도 역순 (Reverse Rightmost) |
| 결정론적 특성 |
Lookahead를 보고 규칙을 예측 |
스택에 쌓인 토큰을 보고 규칙을 축약(Reduce) |
| 문법 범위 |
상대적으로 좁음 (좌재귀 불가) |
매우 넓음 (대부분의 프로그래밍 언어 가능) |
| 장점 |
디버깅이 쉽고 구현이 단순함 |
강력한 표현력, 효율적인 처리 |
| 단점 |
좌재귀(Left Recursion) 처리 불가 |
생성된 코드의 가독성이 매우 낮음 |
4. 대표적인 파서 생성기 도구
| 도구 |
기반 알고리즘 |
지원 언어 |
주요 특징 |
| Yacc |
LALR |
C |
유닉스 표준 파서 생성기, 고전적인 도구 |
| Bison |
LALR, GLR |
C, C++, Java |
Yacc의 GNU 호환 버전, 현대적 기능 추가 |
| ANTLR |
LL(*) |
Java, C#, Python, Go |
강력한 툴링, 자동 AST 생성, LL의 한계 극복 |
| JavaCC |
LL(k) |
Java |
Java 전용, 통합된 렉서/파서 생성 |
4.1 라이선스 및 설치 방법
| 도구 |
라이선스 |
설치 방법 (OS별 일반적 경로) |
| Bison |
GPL |
sudo apt-get install bison (Ubuntu), brew install bison (macOS) |
| ANTLR |
BSD |
Java 설치 후 antlr-4.x-complete.jar 다운로드 및 클래스패스 설정 |
| JavaCC |
Apache 2.0 |
Maven/Gradle 의존성 추가 또는 .jar 파일 직접 실행 |
5. 사용 예시 및 워크플로우
5.1 워크플로우 단계
- 문법 정의: BNF/EBNF를 사용하여 언어 규칙 작성.
- 코드 생성: 파서 생성기를 실행하여 타겟 언어의 소스 코드 생성.
- 컴파일: 생성된 소스 코드를 컴파일하여 실행 파일 생성.
- 입력 처리: 텍스트 입력을 넣어 구문 분석 수행.
5.2 문법 정의 예시 (ANTLR4 .g4 파일)
간단한 산술 연산식을 처리하는 문법 정의이다.
grammar Calc;
// 렉서 규칙 (Tokens)
NUMBER : [0-9]+ ;
PLUS : '+' ;
MINUS : '-' ;
MUL : '*' ;
DIV : '/' ;
WS : [ \t\r\n]+ $\rightarrow$ skip ;
// 파서 규칙 (Grammar)
expr : term ((PLUS | MINUS) term)* ;
term : factor ((MUL | DIV) factor)* ;
factor : NUMBER | '(' expr ')' ;
파서가 입력을 분석하면 단순한 구문 확인을 넘어 AST(Abstract Syntax Tree)를 생성한다. AST는 소스 코드의 구문 구조를 트리 형태로 추상화한 데이터 구조이다.
- 파싱: 입력 토큰 스트림을 문법 규칙에 따라 분석한다.
- 노드 생성: 각 규칙(예:
expr, term)이 일치할 때마다 해당 규칙을 루트로 하는 노드를 생성한다. 이때, 연산자나 키워드가 노드의 타입이 된다.
- 계층 구조 형성: 하위 규칙(예:
factor)을 자식 노드로 연결하여 트리 구조를 완성한다. 예를 들어 1 + 2는 + 노드를 루트로 하고 1과 2를 자식으로 갖는 트리가 된다.
- 최적화: 불필요한 구문 기호(괄호, 세미콜론 등)를 제거하고 의미론적 구조만 남긴다. 괄호는 트리의 깊이(우선순위)로 이미 표현되므로 AST에서는 삭제된다.
- 활용: 생성된 AST는 이후 세만틱 분석(Semantic Analysis)에서 타입 체크를 수행하거나, 최종적으로 기계어/바이트코드로 변환하는 코드 생성 단계의 입력값으로 사용된다.
6. 최신 파서 라이브러리와의 비교
최근에는 무거운 생성기 대신, 코드 내에서 직접 문법을 정의하는 Parser Combinator나 PEG(Parsing Expression Grammar) 기반 라이브러리가 선호되기도 한다.
| 구분 |
파서 생성기 (Generator) |
파서 라이브러리 (Combinator/PEG) |
| 방식 |
외부 도구 $\rightarrow$ 코드 생성 $\rightarrow$ 컴파일 |
라이브러리 함수 호출 $\rightarrow$ 런타임 분석 |
| 빌드 과정 |
빌드 파이프라인에 생성 단계 필요 |
일반적인 코드 작성과 동일 |
| 유연성 |
문법 변경 시 재생성 필요 |
코드 수정 후 즉시 반영 가능 |
| 성능 |
최적화된 상태 표 사용으로 매우 빠름 |
함수 호출 오버헤드로 인해 상대적으로 느림 |
| 예시 |
ANTLR, Bison |
Parsec (Haskell), PyParsing (Python) |
7. 한계 및 고려사항
파서 생성기는 강력하지만 다음과 같은 한계가 존재한다.
- 가독성 및 디버깅: 생성된 코드는 사람이 읽기 힘든 상태 전이 표나 거대한
switch-case 문으로 구성되어 있어, 파싱 에러 발생 시 정확한 지점을 찾기 어렵다.
- 빌드 복잡도: 빌드 프로세스에 외부 도구(Generator)를 통합해야 하므로 CI/CD 파이프라인이 복잡해진다.
- 핸드-라이팅(Hand-writing)으로의 회귀: 최근 GCC, Clang, Rust 컴파일러 등 대규모 프로젝트들은 정교한 에러 메시지 출력과 최적화를 위해 생성기 대신 재귀 하강 파서(Recursive Descent Parser)를 직접 작성하는 추세이다. 이는 개발자가 파싱 과정을 완전히 제어하여 사용자 친화적인 구문 오류 메시지를 제공하기 위함이다.
# 파서 생성기 (Parser Generator)
## 1. 개요
**파서 생성기(Parser Generator)**란 프로그래밍 언어의 문법을 정의한 명세서를 입력받아, 해당 문법에 맞는 구문 분석기(Parser) 소스 코드를 자동으로 생성해 주는 개발 도구이다.
컴파일러의 전처리 과정은 일반적으로 **어휘 분석(Lexical Analysis)** $\rightarrow$ **구문 분석(Syntax Analysis)** 단계로 진행된다. 어휘 분석기가 소스 코드를 의미 있는 최소 단위인 토큰(Token)으로 분리하면, 파서는 이 토큰들의 배열이 정의된 문법 규칙에 맞는지 검사하고 구조화한다. 이러한 도구는 컴파일러 제작뿐만 아니라 JSON, XML과 같은 데이터 포맷 파싱이나 복잡한 설정 파일 분석 등 다양한 도메인에서 활용된다.
파서를 수동으로 작성(Hand-written Parser)할 경우 언어의 복잡도가 증가함에 따라 코드 유지보수가 매우 어려워지지만, 파서 생성기를 사용하면 문법 정의 파일만 수정함으로써 파서의 동작을 빠르게 변경할 수 있다는 장점이 있다.
## 2. 동작 메커니즘
### 2.1 CFG와 BNF
파서 생성기는 기본적으로 **CFG(Context-Free Grammar, 문맥 자유 문법)**를 기반으로 동작한다. CFG는 언어의 구조를 정의하는 수학적 형식이며, 이를 사람이 읽고 쓸 수 있도록 표기하기 위해 **BNF(Backus-Naur Form)**라는 메타 언어가 널리 사용된다.
### 2.2 처리 흐름
파서 생성기의 작동 프로세스는 다음과 같은 파이프라인을 갖는다.
| 단계 | 입력/처리 | 내용 | 출력 |
| :--- | :--- | :--- | :--- |
| **입력** | 문법 정의 파일 | BNF 또는 EBNF 형식으로 작성된 언어 규칙 | `.g4`, `.y` 등의 파일 |
| **처리** | 파서 생성기 엔진 | 문법 분석 $\rightarrow$ 상태 전이 표(State Transition Table) 생성 $\rightarrow$ 코드 템플릿 적용 | 생성기 내부 로직 |
| **출력** | 파서 소스 코드 | 특정 프로그래밍 언어로 구현된 구문 분석기 클래스/함수 | `.java`, `.cpp`, `.py` 등 |
## 3. 주요 파싱 알고리즘 및 유형
파서 생성기는 구현 방식에 따라 크게 하향식(Top-down)과 상향식(Bottom-up)으로 나뉜다. 두 방식 모두 다음 토큰을 몇 개까지 미리 보느냐를 의미하는 **Lookahead(k)** 값에 따라 문법의 결정력과 처리 능력이 달라진다.
### 3.1 LL (Left-to-right, Leftmost derivation)
루트 노드에서 시작하여 잎 노드(Leaf node) 방향으로 분석하는 하향식 방식이다. 가장 왼쪽의 비단말 기호부터 유도(Derivation)하는 과정을 거치며, 예측 파싱(Predictive Parsing)을 수행하여 구조가 직관적이다.
**[LL 파싱 트리 구조]**
`Root (S) $\rightarrow$ Non-terminal (A) $\rightarrow$ Terminal (a)` (하향식 확장)
### 3.2 LR (Left-to-right, Rightmost derivation)
잎 노드에서 시작하여 루트 노드 방향으로 병합하며 분석하는 상향식 방식이다. 가장 오른쪽의 유도 과정을 역순으로 추적하여 분석하며, LL보다 더 넓은 범위의 문법을 처리할 수 있어 강력하다. 다만, 상태 전이 표(State Transition Table)의 크기가 매우 커서 수동 작성이 비효율적이며 생성기 의존도가 높다.
**[LR 파싱 트리 구조]**
`Terminal (a) $\rightarrow$ Non-terminal (A) $\rightarrow$ Root (S)` (상향식 축약)
### 3.3 LL vs LR 비교
| 비교 항목 | LL (Top-down) | LR (Bottom-up) |
| :--- | :--- | :--- |
| **분석 방향** | 루트 $\rightarrow$ 잎 (하향식) | 잎 $\rightarrow$ 루트 (상향식) |
| **유도 방식** | 최좌단 유도 (Leftmost Derivation) | 최우단 유도 역순 (Reverse Rightmost) |
| **결정론적 특성** | Lookahead를 보고 규칙을 예측 | 스택에 쌓인 토큰을 보고 규칙을 축약(Reduce) |
| **문법 범위** | 상대적으로 좁음 (좌재귀 불가) | 매우 넓음 (대부분의 프로그래밍 언어 가능) |
| **장점** | 디버깅이 쉽고 구현이 단순함 | 강력한 표현력, 효율적인 처리 |
| **단점** | 좌재귀(Left Recursion) 처리 불가 | 생성된 코드의 가독성이 매우 낮음 |
## 4. 대표적인 파서 생성기 도구
| 도구 | 기반 알고리즘 | 지원 언어 | 주요 특징 |
| :--- | :--- | :--- | :--- |
| **Yacc** | LALR | C | 유닉스 표준 파서 생성기, 고전적인 도구 |
| **Bison** | LALR, GLR | C, C++, Java | Yacc의 GNU 호환 버전, 현대적 기능 추가 |
| **ANTLR** | LL(*) | Java, C#, Python, Go | 강력한 툴링, 자동 AST 생성, LL의 한계 극복 |
| **JavaCC** | LL(k) | Java | Java 전용, 통합된 렉서/파서 생성 |
### 4.1 라이선스 및 설치 방법
| 도구 | 라이선스 | 설치 방법 (OS별 일반적 경로) |
| :--- | :--- | :--- |
| **Bison** | GPL | `sudo apt-get install bison` (Ubuntu), `brew install bison` (macOS) |
| **ANTLR** | BSD | Java 설치 후 `antlr-4.x-complete.jar` 다운로드 및 클래스패스 설정 |
| **JavaCC** | Apache 2.0 | Maven/Gradle 의존성 추가 또는 `.jar` 파일 직접 실행 |
## 5. 사용 예시 및 워크플로우
### 5.1 워크플로우 단계
1. **문법 정의**: BNF/EBNF를 사용하여 언어 규칙 작성.
2. **코드 생성**: 파서 생성기를 실행하여 타겟 언어의 소스 코드 생성.
3. **컴파일**: 생성된 소스 코드를 컴파일하여 실행 파일 생성.
4. **입력 처리**: 텍스트 입력을 넣어 구문 분석 수행.
### 5.2 문법 정의 예시 (ANTLR4 `.g4` 파일)
간단한 산술 연산식을 처리하는 문법 정의이다.
```antlr4
grammar Calc;
// 렉서 규칙 (Tokens)
NUMBER : [0-9]+ ;
PLUS : '+' ;
MINUS : '-' ;
MUL : '*' ;
DIV : '/' ;
WS : [ \t\r\n]+ $\rightarrow$ skip ;
// 파서 규칙 (Grammar)
expr : term ((PLUS | MINUS) term)* ;
term : factor ((MUL | DIV) factor)* ;
factor : NUMBER | '(' expr ')' ;
```
### 5.3 추상 구문 트리(AST) 생성 과정
파서가 입력을 분석하면 단순한 구문 확인을 넘어 **AST(Abstract Syntax Tree)**를 생성한다. AST는 소스 코드의 구문 구조를 트리 형태로 추상화한 데이터 구조이다.
1. **파싱**: 입력 토큰 스트림을 문법 규칙에 따라 분석한다.
2. **노드 생성**: 각 규칙(예: `expr`, `term`)이 일치할 때마다 해당 규칙을 루트로 하는 노드를 생성한다. 이때, 연산자나 키워드가 노드의 타입이 된다.
3. **계층 구조 형성**: 하위 규칙(예: `factor`)을 자식 노드로 연결하여 트리 구조를 완성한다. 예를 들어 `1 + 2`는 `+` 노드를 루트로 하고 `1`과 `2`를 자식으로 갖는 트리가 된다.
4. **최적화**: 불필요한 구문 기호(괄호, 세미콜론 등)를 제거하고 의미론적 구조만 남긴다. 괄호는 트리의 깊이(우선순위)로 이미 표현되므로 AST에서는 삭제된다.
5. **활용**: 생성된 AST는 이후 세만틱 분석(Semantic Analysis)에서 타입 체크를 수행하거나, 최종적으로 기계어/바이트코드로 변환하는 코드 생성 단계의 입력값으로 사용된다.
## 6. 최신 파서 라이브러리와의 비교
최근에는 무거운 생성기 대신, 코드 내에서 직접 문법을 정의하는 **Parser Combinator**나 **PEG(Parsing Expression Grammar)** 기반 라이브러리가 선호되기도 한다.
| 구분 | 파서 생성기 (Generator) | 파서 라이브러리 (Combinator/PEG) |
| :--- | :--- | :--- |
| **방식** | 외부 도구 $\rightarrow$ 코드 생성 $\rightarrow$ 컴파일 | 라이브러리 함수 호출 $\rightarrow$ 런타임 분석 |
| **빌드 과정** | 빌드 파이프라인에 생성 단계 필요 | 일반적인 코드 작성과 동일 |
| **유연성** | 문법 변경 시 재생성 필요 | 코드 수정 후 즉시 반영 가능 |
| **성능** | 최적화된 상태 표 사용으로 매우 빠름 | 함수 호출 오버헤드로 인해 상대적으로 느림 |
| **예시** | ANTLR, Bison | Parsec (Haskell), PyParsing (Python) |
## 7. 한계 및 고려사항
파서 생성기는 강력하지만 다음과 같은 한계가 존재한다.
* **가독성 및 디버깅**: 생성된 코드는 사람이 읽기 힘든 상태 전이 표나 거대한 `switch-case` 문으로 구성되어 있어, 파싱 에러 발생 시 정확한 지점을 찾기 어렵다.
* **빌드 복잡도**: 빌드 프로세스에 외부 도구(Generator)를 통합해야 하므로 CI/CD 파이프라인이 복잡해진다.
* **핸드-라이팅(Hand-writing)으로의 회귀**: 최근 GCC, Clang, Rust 컴파일러 등 대규모 프로젝트들은 정교한 에러 메시지 출력과 최적화를 위해 생성기 대신 **재귀 하강 파서(Recursive Descent Parser)**를 직접 작성하는 추세이다. 이는 개발자가 파싱 과정을 완전히 제어하여 사용자 친화적인 구문 오류 메시지를 제공하기 위함이다.