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

Input: id * id + id

Reduction process (reverse of rightmost derivation):
  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)

Sentential form: T * F + id
Handle: T * F (production: T -> T * F)
After reduction: T + id

Stack          Input              Action
$            id * id + id $   Shift
$ id         * id + id $      Reduce (F -> id)
$ F          * id + id $      Reduce (T -> F)
$ T          * id + id $      Shift
$ T *        id + id $        Shift
$ T * id     + id $           Reduce (F -> id)
$ T * F      + id $           Reduce (T -> T * F)
$ T          + id $           Reduce (E -> T)
$ E          + id $           Shift
$ E +        id $             Shift
$ E + id     $                Reduce (F -> id)
$ E + F      $                Reduce (T -> F)
$ E + T      $                Reduce (E -> E + T)
$ E          $                Accept!

Input: a1 a2 ... an $

        +---+---+---+---+
Stack:  | s0| X1| s1| X2| s2 ...
        +---+---+---+---+

Parsing table:
  ACTION[s, a] = shift/reduce/accept/error
  GOTO[s, A]   = next state

Push initial state s0 onto the stack

loop:
  s = top state on stack
  a = current input symbol

  case ACTION[s, a]:
    shift sn:
      Push a and state sn onto the stack
      Advance to next input symbol

    reduce (A -> beta):
      Pop 2*|beta| symbols from the stack
      s' = new top state on stack
      Push A and GOTO[s', A] onto the stack

    accept:
      Parsing success, terminate

    error:
      Call error handling routine

Production: A -> X Y Z

Possible LR(0) items:
  A -> . X Y Z    (nothing seen yet)
  A -> X . Y Z    (X has been seen)
  A -> X Y . Z    (X Y have been seen)
  A -> X Y Z .    (ready to reduce!)

closure(I):
  Add all items in I to the result
  If A -> alpha . B beta is in the result:
    For all productions B -> gamma:
    Add B -> . gamma to the result (if not already present)
  Repeat until no changes

goto(I, X):
  For items A -> alpha . X beta in I,
  collect A -> alpha X . beta, then take their closure

Grammar:
  E' -> E       (augmented grammar start)
  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 .

1. Construct the LR(0) item set collection C for the augmented grammar

2. For item set Ii:
   a) If A -> alpha . a beta is in Ii and goto(Ii, a) = Ij:
      ACTION[i, a] = shift j

   b) If A -> alpha . is in Ii (A != S'):
      For all a in FOLLOW(A):
      ACTION[i, a] = reduce (A -> alpha)

   c) If S' -> S . is in Ii:
      ACTION[i, $] = accept

3. If goto(Ii, A) = Ij: GOTO[i, A] = j

       ACTION                          GOTO
State | 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|   |   |

[A -> alpha . beta, a]

- A -> alpha . beta: Same as LR(0) item
- a: Lookahead symbol (consulted when reducing with this item)

closure(I):
  If [A -> alpha . B beta, a] is in I:
    For all productions B -> gamma:
    For all b in FIRST(beta a):
    Add [B -> . gamma, b]

Pros: Can handle more grammars than SLR
Cons: Number of states can become very large
      (tens to hundreds of times more than LR(0))

LR(1) states:
  I4: {[C -> .c C, c], [C -> .c C, d], [C -> .d, c], [C -> .d, d]}
  I7: {[C -> .c C, $], [C -> .d, $]}

Same core, so merge:
  I47: {[C -> .c C, c/d/$], [C -> .d, c/d/$]}

LR(0) grammars < SLR grammars < LALR grammars < LR(1) grammars

Practical choices:
- Simple grammars: SLR
- Most programming languages: LALR (Yacc/Bison)
- Complex grammars: Canonical LR(1)

Declarations
%%
Grammar Rules and Actions
%%
Supporting C Functions

%{
#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();
}

%left '+' '-'       // Left-associative, lower precedence
%left '*' '/'       // Left-associative, higher precedence
%right UMINUS       // Right-associative, unary minus

1. Pop the stack until a state that can handle A is found
2. Skip input until a token in FOLLOW(A) is found
3. Push GOTO[s, A] and continue parsing

stmt : expr ';'
     | error ';'   { yyerrok; printf("Skipping bad statement\n"); }
     ;