Skip to content
Published on

[컴파일러] 07. 구문 분석 (2) - Bottom-Up 파싱과 LR 파서

🇰🇷KO🇺🇸EN🇯🇵JA
Authors

구문 분석 (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)으로 파싱 진행 상태를 표현
SLRLR(0) 항목 + FOLLOW 집합 사용
정규 LR(1)선행 기호를 포함한 항목, 가장 강력
LALR코어가 같은 LR(1) 상태를 합침, 실용적
Yacc/BisonLALR(1) 파서 자동 생성 도구

LR 파싱은 대부분의 프로그래밍 언어를 효율적으로 처리할 수 있는 강력한 기법입니다. 다음 글에서는 파싱 결과를 활용하여 의미 있는 번역을 수행하는 구문 지시 번역을 다루겠습니다.

Discuss on Twitter • View on GitHub