구문 분석 (2) - Bottom-Up 파싱과 LR 파서
Bottom-Up 파싱은 입력 문자열에서 출발하여 시작 기호로 축약해 나가는 방식입니다. LL 파서보다 더 넓은 범위의 문법을 처리할 수 있어 실제 컴파일러에서 널리 사용됩니다.
1. Bottom-Up 파싱 개요
기본 아이디어
Bottom-Up 파싱은 **축약(reduction)**을 반복하여 입력 문자열을 시작 기호로 만듭니다.
입력: id * id + id
축약 과정 (우측 유도의 역순):
id * id + id
F * id + id (F -> id)
T * id + id (T -> F)
T * F + id (F -> id)
T + id (T -> T * F)
E + id (E -> T)
E + F (F -> id)
E + T (T -> F)
E (E -> E + T)
이것은 우측 유도를 역순으로 추적한 것입니다.
핸들(Handle)
**핸들**은 축약할 수 있는 부분 문자열과 해당 생성 규칙의 조합입니다. 올바른 핸들을 찾아 축약하면 시작 기호에 도달합니다.
문장 형식: T * F + id
핸들: T * F (생성 규칙: T -> T * F)
축약 결과: T + id
잘못된 핸들을 선택하면 시작 기호에 도달할 수 없습니다. 핸들 선택이 Bottom-Up 파싱의 핵심 과제입니다.
2. 이동-축약 파싱(Shift-Reduce Parsing)
이동-축약 파서는 **스택**과 **입력 버퍼**를 사용합니다.
4가지 동작
1. **이동(Shift)**: 입력의 다음 토큰을 스택에 push합니다.
2. **축약(Reduce)**: 스택 꼭대기의 핸들을 생성 규칙의 좌변 논터미널로 교체합니다.
3. **수락(Accept)**: 파싱 성공입니다.
4. **에러(Error)**: 구문 오류가 발견되었습니다.
파싱 예제: `id * id + id`
스택 입력 동작
$ id * id + id $ 이동
$ id * id + id $ 축약 (F -> id)
$ F * id + id $ 축약 (T -> F)
$ T * id + id $ 이동
$ T * id + id $ 이동
$ T * id + id $ 축약 (F -> id)
$ T * F + id $ 축약 (T -> T * F)
$ T + id $ 축약 (E -> T)
$ E + id $ 이동
$ E + id $ 이동
$ E + id $ 축약 (F -> id)
$ E + F $ 축약 (T -> F)
$ E + T $ 축약 (E -> E + T)
$ E $ 수락!
이동-축약 충돌
때때로 파서가 이동할지 축약할지 결정할 수 없는 상황이 발생합니다.
- **이동-축약 충돌(Shift-Reduce Conflict)**: 이동과 축약 모두 가능한 경우
- **축약-축약 충돌(Reduce-Reduce Conflict)**: 여러 생성 규칙으로 축약이 가능한 경우
이러한 충돌을 해결하는 것이 LR 파싱 기법의 핵심입니다.
3. LR 파싱 개요
LR 파서는 가장 강력한 이동-축약 파서입니다.
LR(k)의 의미
- **L**: 입력을 **왼쪽에서 오른쪽**으로 스캔
- **R**: **우측 유도**를 역순으로 생성
- **(k)**: **k개의 선행 토큰**을 보고 결정
LR 파서의 구성 요소
입력: a1 a2 ... an $
+---+---+---+---+
스택: | s0| X1| s1| X2| s2 ...
+---+---+---+---+
파싱 테이블:
ACTION[s, a] = 이동/축약/수락/에러
GOTO[s, A] = 다음 상태
- **스택**: 상태와 문법 기호가 번갈아 쌓입니다.
- **ACTION 테이블**: 현재 상태와 입력 토큰에 따른 동작을 결정합니다.
- **GOTO 테이블**: 축약 후 전이할 상태를 결정합니다.
LR 파싱 알고리즘
스택에 초기 상태 s0을 push
loop:
s = 스택 꼭대기 상태
a = 현재 입력 기호
case ACTION[s, a]:
이동 sn:
a와 상태 sn을 스택에 push
다음 입력 기호로 전진
축약 (A -> beta):
스택에서 2*|beta|개 기호를 pop
s' = 새로운 스택 꼭대기 상태
A와 GOTO[s', A]를 스택에 push
수락:
파싱 성공, 종료
에러:
에러 처리 루틴 호출
4. LR(0) 항목과 오토마타
LR(0) 항목(Item)
LR(0) 항목은 생성 규칙에 **점(dot)**을 추가한 것으로, 파싱 진행 상태를 나타냅니다.
생성 규칙: A -> X Y Z
가능한 LR(0) 항목:
A -> . X Y Z (아직 아무것도 보지 않음)
A -> X . Y Z (X를 본 상태)
A -> X Y . Z (X Y를 본 상태)
A -> X Y Z . (축약 가능!)
클로저(Closure) 연산
항목 집합의 클로저를 계산합니다.
closure(I):
I의 모든 항목을 결과에 추가
결과에 A -> alpha . B beta 형태의 항목이 있으면:
B -> gamma인 모든 생성 규칙에 대해
B -> . gamma를 결과에 추가 (아직 없으면)
변화가 없을 때까지 반복
GOTO 연산
goto(I, X):
I에서 A -> alpha . X beta 형태의 항목에 대해
A -> alpha X . beta를 모은 집합의 closure
LR(0) 오토마타 구성 예제
문법:
E' -> E (증강 문법의 시작)
E -> E + T
E -> T
T -> T * F
T -> F
F -> ( E )
F -> id
I0 = closure({E' -> . E}):
E' -> . E
E -> . E + T
E -> . T
T -> . T * F
T -> . F
F -> . ( E )
F -> . id
goto(I0, E) = I1:
E' -> E .
E -> E . + T
goto(I0, T) = I2:
E -> T .
T -> T . * F
goto(I0, F) = I3:
T -> F .
goto(I0, '(') = I4:
F -> ( . E )
E -> . E + T
E -> . T
...
goto(I0, id) = I5:
F -> id .
5. SLR 파싱 테이블 구성
**SLR(Simple LR)** 파싱은 LR(0) 항목과 FOLLOW 집합을 사용합니다.
SLR 파싱 테이블 구성 알고리즘
1. 증강 문법의 LR(0) 항목 집합 C를 구성
2. 항목 집합 Ii에 대해:
a) A -> alpha . a beta가 Ii에 있고, goto(Ii, a) = Ij이면:
ACTION[i, a] = shift j
b) A -> alpha .가 Ii에 있으면 (A != S'):
FOLLOW(A)의 모든 a에 대해:
ACTION[i, a] = reduce (A -> alpha)
c) S' -> S .가 Ii에 있으면:
ACTION[i, $] = accept
3. goto(Ii, A) = Ij이면: GOTO[i, A] = j
SLR 파싱 테이블 예제
ACTION GOTO
상태 | id | + | * | ( | ) | $ | E | T | F
-----+-----+-----+-----+-----+-----+---+---+---+---
0 | s5 | | | s4 | | | 1 | 2 | 3
1 | | s6 | | | | acc| | |
2 | | r2 | s7 | | r2 | r2| | |
3 | | r4 | r4 | | r4 | r4| | |
4 | s5 | | | s4 | | | 8 | 2 | 3
5 | | r6 | r6 | | r6 | r6| | |
6 | s5 | | | s4 | | | | 9 | 3
7 | s5 | | | s4 | | | | | 10
8 | | s6 | | | s11 | | | |
9 | | r1 | s7 | | r1 | r1| | |
10 | | r3 | r3 | | r3 | r3| | |
11 | | r5 | r5 | | r5 | r5| | |
여기서 `s5`는 shift 5, `r2`는 reduce by production 2, `acc`는 accept입니다.
6. 정규 LR(1) 항목
SLR 파서로 처리할 수 없는 문법이 있습니다. **정규 LR(1) 항목**은 **선행 기호(lookahead)**를 추가하여 더 강력한 파싱이 가능합니다.
LR(1) 항목의 형태
[A -> alpha . beta, a]
- A -> alpha . beta: LR(0) 항목과 동일
- a: 선행 기호 (이 항목으로 축약할 때 참조)
LR(1) 클로저
closure(I):
[A -> alpha . B beta, a]가 I에 있으면:
B -> gamma인 모든 생성 규칙에 대해
FIRST(beta a)의 모든 b에 대해
[B -> . gamma, b]를 추가
정규 LR(1) 파싱의 장단점
장점: SLR보다 더 많은 문법을 처리 가능
단점: 상태 수가 매우 많아질 수 있음
(LR(0)의 수십~수백 배)
7. LALR 파싱
**LALR(Look-Ahead LR)**은 정규 LR(1)의 강력함과 SLR의 효율성을 절충한 방법입니다.
핵심 아이디어
LR(1) 항목에서 **코어(core)**가 같은 항목 집합을 합칩니다.
LR(1) 상태:
I4: {[C -> .c C, c], [C -> .c C, d], [C -> .d, c], [C -> .d, d]}
I7: {[C -> .c C, $], [C -> .d, $]}
코어가 같으므로 합침:
I47: {[C -> .c C, c/d/$], [C -> .d, c/d/$]}
LALR 파서의 특징
- 정규 LR(1)과 같은 수의 상태를 가지는 SLR과 같은 크기의 테이블
- SLR보다 강력하고, 정규 LR(1)보다 약간 약함
- 대부분의 프로그래밍 언어를 처리할 수 있음
- **Yacc**와 **Bison**이 LALR 파서를 생성
SLR, LR(1), LALR의 관계
LR(0) 문법 ⊂ SLR 문법 ⊂ LALR 문법 ⊂ LR(1) 문법
실용적 선택:
- 간단한 문법: SLR
- 대부분의 프로그래밍 언어: LALR (Yacc/Bison)
- 복잡한 문법: 정규 LR(1)
8. Yacc 파서 생성기
**Yacc (Yet Another Compiler Compiler)**는 LALR(1) 파서를 자동 생성하는 도구입니다. GNU 버전인 **Bison**이 널리 사용됩니다.
Yacc 프로그램 구조
선언부 (declarations)
%%
문법 규칙과 동작 (grammar rules and actions)
%%
보조 C 함수 (supporting C functions)
Yacc 프로그램 예제: 계산기
%{
#include <stdio.h>
#include <ctype.h>
int yylex();
void yyerror(const char *s);
%}
%token NUM
%%
line : expr '\n' { printf("Result: %d\n", $1); }
;
expr : expr '+' term { $$ = $1 + $3; }
| expr '-' term { $$ = $1 - $3; }
| term { $$ = $1; }
;
term : term '*' factor { $$ = $1 * $3; }
| term '/' factor { $$ = $1 / $3; }
| factor { $$ = $1; }
;
factor : '(' expr ')' { $$ = $2; }
| NUM { $$ = $1; }
;
%%
int yylex() {
int c = getchar();
if (isdigit(c)) {
yylval = c - '0';
while (isdigit(c = getchar()))
yylval = yylval * 10 + c - '0';
ungetc(c, stdin);
return NUM;
}
return c;
}
void yyerror(const char *s) {
fprintf(stderr, "Error: %s\n", s);
}
int main() {
return yyparse();
}
Yacc의 충돌 해결 규칙
Yacc는 LALR 파싱 테이블에 충돌이 있을 때 다음 규칙을 적용합니다.
1. **이동-축약 충돌**: 기본적으로 **이동**을 선택합니다 (dangling else 문제 해결).
2. **축약-축약 충돌**: **먼저 나온 규칙**으로 축약합니다.
Yacc의 우선순위 지시어
%left '+' '-' // 왼쪽 결합, 낮은 우선순위
%left '*' '/' // 왼쪽 결합, 높은 우선순위
%right UMINUS // 오른쪽 결합, 단항 마이너스
이 지시어를 사용하면 모호한 문법도 충돌 없이 처리할 수 있습니다.
9. LR 파서의 에러 복구
패닉 모드 복구
1. 스택에서 A를 처리할 수 있는 상태를 찾을 때까지 pop
2. 입력에서 FOLLOW(A)에 속하는 토큰을 찾을 때까지 건너뜀
3. GOTO[s, A]를 push하고 파싱 계속
Yacc의 에러 복구: error 토큰
stmt : expr ';'
| error ';' { yyerrok; printf("Skipping bad statement\n"); }
;
`error`는 Yacc의 특수 토큰으로, 에러 상황에서 자동으로 매치됩니다. `yyerrok`은 에러 복구가 완료되었음을 선언합니다.
정리
| 개념 | 핵심 내용 |
| -------------- | ----------------------------------------------- |
| Bottom-Up 파싱 | 입력에서 시작하여 시작 기호로 축약 |
| 핸들 | 축약할 부분 문자열과 생성 규칙의 조합 |
| 이동-축약 | 스택 기반의 4가지 동작 (이동, 축약, 수락, 에러) |
| LR(0) 항목 | 점(dot)으로 파싱 진행 상태를 표현 |
| SLR | LR(0) 항목 + FOLLOW 집합 사용 |
| 정규 LR(1) | 선행 기호를 포함한 항목, 가장 강력 |
| LALR | 코어가 같은 LR(1) 상태를 합침, 실용적 |
| Yacc/Bison | LALR(1) 파서 자동 생성 도구 |
LR 파싱은 대부분의 프로그래밍 언어를 효율적으로 처리할 수 있는 강력한 기법입니다. 다음 글에서는 파싱 결과를 활용하여 의미 있는 번역을 수행하는 구문 지시 번역을 다루겠습니다.
현재 단락 (1/244)
Bottom-Up 파싱은 입력 문자열에서 출발하여 시작 기호로 축약해 나가는 방식입니다. LL 파서보다 더 넓은 범위의 문법을 처리할 수 있어 실제 컴파일러에서 널리 사용됩니다.