[컴파일러] 06. 구문 분석 (1) - Top-Down 파싱과 LL 파서

  토큰 스트림
       |
       v
  +---------+
  |  파서    | <---> 심볼 테이블
  +---------+
       |
       v
  파스 트리 / AST

대문자:     논터미널 (A, B, S, E, T, F, ...)
소문자:     터미널 (a, b, c, +, *, (, ), ...)
그리스 문자: 문법 기호의 문자열 (alpha, beta, gamma, ...)

E -> E + T | T
T -> T * F | F
F -> ( E ) | id

좌측 유도 예시: id + id * id
  E => E + T => T + T => F + T => id + T
    => id + T * F => id + F * F => id + id * F => id + id * id

// 모호한 문법
stmt -> if expr then stmt
      | if expr then stmt else stmt
      | other

// 모호성 해결: else는 가장 가까운 if에 매치
matched_stmt   -> if expr then matched_stmt else matched_stmt
                | other
unmatched_stmt -> if expr then stmt
                | if expr then matched_stmt else unmatched_stmt
stmt           -> matched_stmt | unmatched_stmt

// 좌재귀 문법
A -> A alpha | beta

// 좌재귀 제거 후
A  -> beta A'
A' -> alpha A' | epsilon

// 좌재귀가 있는 산술 표현식 문법
E -> E + T | T
T -> T * F | F
F -> ( E ) | id

// 좌재귀 제거 후
E  -> T E'
E' -> + T E' | epsilon
T  -> F T'
T' -> * F T' | epsilon
F  -> ( E ) | id

// 간접 좌재귀
S -> A a | b
A -> S c | d

// S -> A a -> S c a (간접적으로 좌재귀)

// 공통 접두사가 있는 문법
A -> alpha beta1 | alpha beta2

// 좌인수분해 후
A  -> alpha A'
A' -> beta1 | beta2

// if-else 문법
stmt -> if expr then stmt else stmt
      | if expr then stmt

// 좌인수분해 후
stmt       -> if expr then stmt else_part
else_part  -> else stmt | epsilon

public class RecursiveDescentParser {
    private Token lookahead;
    private Lexer lexer;

    public RecursiveDescentParser(Lexer lexer) {
        this.lexer = lexer;
        this.lookahead = lexer.nextToken();
    }

    // E -> T E'
    void E() {
        T();
        Eprime();
    }

    // E' -> + T E' | epsilon
    void Eprime() {
        if (lookahead.type == TokenType.PLUS) {
            match(TokenType.PLUS);
            T();
            Eprime();
        }
        // else: epsilon (아무것도 하지 않음)
    }

    // T -> F T'
    void T() {
        F();
        Tprime();
    }

    // T' -> * F T' | epsilon
    void Tprime() {
        if (lookahead.type == TokenType.STAR) {
            match(TokenType.STAR);
            F();
            Tprime();
        }
        // else: epsilon
    }

    // F -> ( E ) | id
    void F() {
        if (lookahead.type == TokenType.LPAREN) {
            match(TokenType.LPAREN);
            E();
            match(TokenType.RPAREN);
        } else if (lookahead.type == TokenType.ID) {
            match(TokenType.ID);
        } else {
            throw new SyntaxError("Unexpected token: " + lookahead);
        }
    }

    void match(TokenType expected) {
        if (lookahead.type == expected) {
            lookahead = lexer.nextToken();
        } else {
            throw new SyntaxError(
                "Expected " + expected + ", got " + lookahead.type
            );
        }
    }
}

계산 규칙:
1. X가 터미널이면: FIRST(X) = {X}
2. X -> epsilon이 규칙이면: epsilon을 FIRST(X)에 추가
3. X -> Y1 Y2 ... Yk이면:
   - FIRST(Y1)에서 epsilon을 제외한 것을 FIRST(X)에 추가
   - Y1이 epsilon을 유도하면, FIRST(Y2)도 추가 (반복)
   - 모든 Yi가 epsilon을 유도하면, epsilon도 FIRST(X)에 추가

문법:
  E  -> T E'
  E' -> + T E' | epsilon
  T  -> F T'
  T' -> * F T' | epsilon
  F  -> ( E ) | id

FIRST(F)  = { (, id }
FIRST(T') = { *, epsilon }
FIRST(T)  = FIRST(F) = { (, id }
FIRST(E') = { +, epsilon }
FIRST(E)  = FIRST(T) = { (, id }

계산 규칙:
1. S가 시작 기호이면: $를 FOLLOW(S)에 추가
2. A -> alpha B beta이면:
   FIRST(beta)에서 epsilon을 제외한 것을 FOLLOW(B)에 추가
3. A -> alpha B이면, 또는 A -> alpha B beta에서
   epsilon이 FIRST(beta)에 포함되면:
   FOLLOW(A)를 FOLLOW(B)에 추가

FOLLOW(E)  = { ), $ }
FOLLOW(E') = FOLLOW(E) = { ), $ }
FOLLOW(T)  = FIRST(E') - {epsilon} + FOLLOW(E) + FOLLOW(E')
           = { +, ), $ }
FOLLOW(T') = FOLLOW(T) = { +, ), $ }
FOLLOW(F)  = FIRST(T') - {epsilon} + FOLLOW(T) + FOLLOW(T')
           = { *, +, ), $ }

각 생성 규칙 A -> alpha에 대해:
  1. FIRST(alpha)의 각 터미널 a에 대해:
     M[A, a]에 A -> alpha를 추가

  2. epsilon이 FIRST(alpha)에 포함되면:
     FOLLOW(A)의 각 터미널 b에 대해:
     M[A, b]에 A -> alpha를 추가

  3. epsilon이 FIRST(alpha)에 포함되고 $가 FOLLOW(A)에 포함되면:
     M[A, $]에 A -> alpha를 추가

       |  id         |  +          |  *          |  (           |  )          |  $
-------+-------------+-------------+-------------+--------------+-------------+--------
  E    | E -> T E'   |             |             | E -> T E'    |             |
  E'   |             | E' -> +TE'  |             |              | E' -> eps   | E' -> eps
  T    | T -> F T'   |             |             | T -> F T'    |             |
  T'   |             | T' -> eps   | T' -> *FT'  |              | T' -> eps   | T' -> eps
  F    | F -> id     |             |             | F -> ( E )   |             |

입력 버퍼: id + id * id $
스택:      $ E

파싱 테이블: M[A, a]

스택에 $와 시작 기호를 push

repeat:
  X = 스택 탑, a = 현재 입력 토큰

  if X == a:
    스택에서 pop, 입력 전진  (match)
  else if X가 터미널:
    에러
  else if M[X, a]가 비어있음:
    에러
  else if M[X, a] = X -> Y1 Y2 ... Yk:
    스택에서 X를 pop
    Yk, ..., Y2, Y1을 순서대로 push  (역순!)

until 스택이 비고 입력이 $ 일 때 (수락)

스택           입력              동작
$ E           id + id * id $   E -> T E'
$ E' T        id + id * id $   T -> F T'
$ E' T' F     id + id * id $   F -> id
$ E' T' id    id + id * id $   match id
$ E' T'       + id * id $      T' -> epsilon
$ E'          + id * id $      E' -> + T E'
$ E' T +      + id * id $      match +
$ E' T        id * id $        T -> F T'
$ E' T' F     id * id $        F -> id
$ E' T' id    id * id $        match id
$ E' T'       * id $           T' -> * F T'
$ E' T' F *   * id $           match *
$ E' T' F     id $             F -> id
$ E' T' id    id $             match id
$ E' T'       $                T' -> epsilon
$ E'          $                E' -> epsilon
$             $                수락!

동기화 토큰 선택 기준:
- FOLLOW(A)의 원소를 동기화 토큰으로 사용
- 문장 구분자 (세미콜론, 중괄호 등)
- 키워드 (if, while, return 등)

입력: int x = + 5;

에러 메시지:
  line 1:9 - syntax error: unexpected '+', expected expression

복구 후 계속 파싱하여 추가 에러 발견 가능

// 정상 문법
stmt -> if ( expr ) stmt

// 에러 프로덕션 추가 (괄호 빠뜨린 경우)
stmt -> if ( expr ) stmt
      | if expr stmt    { error("missing parentheses") }