Split View: [컴파일러] 08. 구문 지시 번역 - SDD와 SDT

Production              Semantic Rule
------------------------------------------------------
L -> E '\n'           L.val = E.val
E -> E1 + T           E.val = E1.val + T.val
E -> T                E.val = T.val
T -> T1 * F           T.val = T1.val * F.val
T -> F                T.val = F.val
F -> ( E )            F.val = E.val
F -> digit            F.val = digit.lexval

              L (val = 19)
              |
           E (val = 19)
          / | \
    E(15)   +   T(4)
    |           |
  T(15)       F(4)
  / | \        |
T(3) * F(5)  digit(4)
|       |
F(3)  digit(5)
|
digit(3)

Production              Semantic Rule
------------------------------------------------------
D -> T L              L.inh = T.type
T -> int              T.type = integer
T -> float            T.type = float
L -> L1 , id          L1.inh = L.inh
                      addtype(id.entry, L.inh)
L -> id               addtype(id.entry, L.inh)

       D
      / \
     T    L (inh = float)
     |   / | \
   float L  , id3  -> addtype(id3, float)
        / | \
       L  , id2    -> addtype(id2, float)
       |
      id1          -> addtype(id1, float)

Example: E -> E1 + T  where  E.val = E1.val + T.val

  E1.val ----+
              +--> E.val
  T.val  ----+

Topological sort result (possible evaluation order):
  digit(3).lexval -> F.val -> T.val ->
  digit(5).lexval -> F.val -> T1.val ->
  digit(4).lexval -> F.val -> T2.val ->
  E1.val -> E.val -> L.val

Characteristics:
- Uses only synthesized attributes
- Can be evaluated with post-order traversal of the parse tree
- Naturally combines with Bottom-Up parsing (LR parser)

Condition: For A -> X1 X2 ... Xn,
  Inherited attributes of Xi can only depend on:
  1. Inherited attributes of A
  2. Attributes of X1, X2, ..., Xi-1 (symbols to the left of Xi)
  3. Attributes of Xi itself (as long as there are no cycles)

S-attributed definitions < L-attributed definitions

All S-attributed definitions are L-attributed definitions.
L-attributed definitions naturally combine with Top-Down parsing.

// Converting S-attributed SDD to SDT (actions at end of rule)
E -> E1 + T  { E.val = E1.val + T.val }
E -> T       { E.val = T.val }

// Converting L-attributed SDD to SDT (actions in the middle)
D -> T { L.inh = T.type } L
T -> int  { T.type = integer }
T -> float { T.type = float }

Parsing stack: stores attribute values along with states

+------+------+------+------+------+------+
| s0   | s1   | s2   | s3   | s4   | s5   |
| -    | E    | +    | T    | *    | F    |
| -    | 15   | -    | 4    | -    | 2    |
+------+------+------+------+------+------+
         val          val          val

Rule: T -> T1 * F  { T.val = T1.val * F.val }

Stack before reduction:  ... | T(3) | * | F(5)
Stack after reduction:   ... | T(15)
  -> Computation: 3 * 5 = 15

expr : expr '+' term   { $$ = $1 + $3; }
     | term            { $$ = $1; }
     ;

// D -> T L
// T.type is a synthesized attribute, L.inh is an inherited attribute
void D() {
    String type = T();    // Receive T's synthesized attribute as return
    L(type);              // Pass L's inherited attribute as parameter
}

String T() {
    if (lookahead == INT) {
        match(INT);
        return "integer";
    } else if (lookahead == FLOAT) {
        match(FLOAT);
        return "float";
    }
    throw new SyntaxError("Expected type");
}

void L(String inheritedType) {
    if (lookahead == ID) {
        addType(currentToken, inheritedType);
        match(ID);
        if (lookahead == COMMA) {
            match(COMMA);
            L(inheritedType);  // Pass inherited attribute
        }
    }
}

E -> T R
R -> + T { print('+') } R | - T { print('-') } R | epsilon
T -> num { print(num.val) }

E -> T R
  T: print(9)     -> output: 9
  R -> - T R
    T: print(5)   -> output: 5
    print('-')     -> output: -
    R -> + T R
      T: print(2) -> output: 2
      print('+')   -> output: +
      R -> epsilon

Final output: 9 5 - 2 +

// Grammar: handling array type declarations like int [2][3]
B -> int                 { B.type = integer }
   | float               { B.type = float }

C -> [ num ] C1          { C.type = array(num.val, C1.type) }
   | epsilon             { C.type = B.type }

T -> B C                 { T.type = C.type }

B.type = integer
C -> [2] C1
  C1 -> [3] C2
    C2 -> epsilon
    C2.type = integer        (inherited from B.type)
  C1.type = array(3, integer)
C.type = array(2, array(3, integer))
T.type = array(2, array(3, integer))

// Original SDT
B -> a { action1 } b { action2 }

// Transformation using marker nonterminal
B -> a M b { action2 }
M -> epsilon { action1 }

// Original SDT (L-attributed)
D -> T { L.inh = T.type } L

// Marker nonterminal transformation
D -> T M L
M -> epsilon  { /* copy T.type from stack to use as L.inh */ }

Phase                    Use of Attributes
------------------------------------------------------
Lexical Analysis        Token attribute values (integer, string)
Syntax Analysis         Parse tree / AST construction
Type Checking           Synthesis and verification of type attributes
Intermediate Code Gen.  Synthesis of three-address code
Code Optimization       Data flow attributes
Code Generation         Register allocation, instruction selection

E -> E1 + E2   { E.type = if E1.type == integer and E2.type == integer
                          then integer
                          else if E1.type == float or E2.type == float
                          then float
                          else type_error }

E -> num       { E.type = integer }
E -> num.num   { E.type = float }
E -> id        { E.type = lookup(id.entry) }

+------------------+-------------------+--------------------+
| Characteristic   | S-Attributed Def. | L-Attributed Def.  |
+------------------+-------------------+--------------------+
| Attribute Types  | Synthesized only  | Synthesized + Inh. |
| Evaluation Dir.  | Bottom -> Up      | Left -> Right      |
| Parser Type      | Bottom-Up (LR)   | Top-Down (LL)      |
| Complexity       | Simple            | Moderate           |
| Expressiveness   | Limited           | Rich               |
+------------------+-------------------+--------------------+

Phase 1: Parsing -> AST construction (using synthesized attributes)
Phase 2: AST traversal -> Symbol table construction (simulating inherited attributes)
Phase 3: AST traversal -> Type checking
Phase 4: AST traversal -> Intermediate code generation