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

  Token Stream
       |
       v
  +---------+
  |  Parser  | <---> Symbol Table
  +---------+
       |
       v
  Parse Tree / AST

Uppercase:      Nonterminals (A, B, S, E, T, F, ...)
Lowercase:      Terminals (a, b, c, +, *, (, ), ...)
Greek letters:  Strings of grammar symbols (alpha, beta, gamma, ...)

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

Leftmost derivation example: id + id * id
  E => E + T => T + T => F + T => id + T
    => id + T * F => id + F * F => id + id * F => id + id * id

// Ambiguous grammar
stmt -> if expr then stmt
      | if expr then stmt else stmt
      | other

// Disambiguated: else matches the nearest 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

// Left-recursive grammar
A -> A alpha | beta

// After left recursion elimination
A  -> beta A'
A' -> alpha A' | epsilon

// Arithmetic expression grammar with left recursion
E -> E + T | T
T -> T * F | F
F -> ( E ) | id

// After left recursion elimination
E  -> T E'
E' -> + T E' | epsilon
T  -> F T'
T' -> * F T' | epsilon
F  -> ( E ) | id

// Indirect left recursion
S -> A a | b
A -> S c | d

// S -> A a -> S c a (indirectly left-recursive)

// Grammar with common prefix
A -> alpha beta1 | alpha beta2

// After left factoring
A  -> alpha A'
A' -> beta1 | beta2

// if-else grammar
stmt -> if expr then stmt else stmt
      | if expr then stmt

// After left factoring
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 (do nothing)
    }

    // 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
            );
        }
    }
}

Computation rules:
1. If X is a terminal: FIRST(X) = {X}
2. If X -> epsilon is a rule: add epsilon to FIRST(X)
3. If X -> Y1 Y2 ... Yk:
   - Add FIRST(Y1) minus epsilon to FIRST(X)
   - If Y1 derives epsilon, also add FIRST(Y2) (repeat)
   - If all Yi derive epsilon, add epsilon to FIRST(X)

Grammar:
  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 }

Computation rules:
1. If S is the start symbol: add $ to FOLLOW(S)
2. If A -> alpha B beta:
   Add FIRST(beta) minus epsilon to FOLLOW(B)
3. If A -> alpha B, or if A -> alpha B beta
   where epsilon is in FIRST(beta):
   Add FOLLOW(A) to 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')
           = { *, +, ), $ }

For each production A -> alpha:
  1. For each terminal a in FIRST(alpha):
     Add A -> alpha to M[A, a]

  2. If epsilon is in FIRST(alpha):
     For each terminal b in FOLLOW(A):
     Add A -> alpha to M[A, b]

  3. If epsilon is in FIRST(alpha) and $ is in FOLLOW(A):
     Add A -> alpha to M[A, $]

       |  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 )   |             |

Input buffer: id + id * id $
Stack:        $ E

Parsing table: M[A, a]

Push $ and start symbol onto the stack

repeat:
  X = stack top, a = current input token

  if X == a:
    Pop from stack, advance input  (match)
  else if X is a terminal:
    Error
  else if M[X, a] is empty:
    Error
  else if M[X, a] = X -> Y1 Y2 ... Yk:
    Pop X from stack
    Push Yk, ..., Y2, Y1 in order  (reverse order!)

until stack is empty and input is $ (accept)

Stack           Input              Action
$ 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
$             $                Accept!

Synchronizing token selection criteria:
- Use elements of FOLLOW(A) as synchronizing tokens
- Statement delimiters (semicolons, braces, etc.)
- Keywords (if, while, return, etc.)

Input: int x = + 5;

Error message:
  line 1:9 - syntax error: unexpected '+', expected expression

Can find additional errors after recovery by continuing to parse

// Normal grammar
stmt -> if ( expr ) stmt

// Error production added (missing parentheses case)
stmt -> if ( expr ) stmt
      | if expr stmt    { error("missing parentheses") }