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

생성 규칙              의미 규칙
------------------------------------------------------
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)

생성 규칙              의미 규칙
------------------------------------------------------
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)

예: E -> E1 + T  에서  E.val = E1.val + T.val

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

위상 정렬 결과 (가능한 평가 순서):
  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

특징:
- 합성 속성만 사용
- 파스 트리를 후위 순회(post-order)로 평가 가능
- Bottom-Up 파싱 (LR 파서)과 자연스럽게 결합

조건: A -> X1 X2 ... Xn 에서
  Xi의 상속 속성은 다음에만 의존할 수 있음:
  1. A의 상속 속성
  2. X1, X2, ..., Xi-1의 속성 (Xi 왼쪽의 기호들)
  3. Xi 자신의 속성 (단, 순환이 없어야 함)

S-속성 정의 ⊂ L-속성 정의

모든 S-속성 정의는 L-속성 정의입니다.
L-속성 정의는 Top-Down 파싱과 자연스럽게 결합합니다.

// S-속성 SDD를 SDT로 변환 (동작이 규칙 끝에)
E -> E1 + T  { E.val = E1.val + T.val }
E -> T       { E.val = T.val }

// L-속성 SDD를 SDT로 변환 (동작이 중간에)
D -> T { L.inh = T.type } L
T -> int  { T.type = integer }
T -> float { T.type = float }

파싱 스택: 상태와 함께 속성값을 저장

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

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

축약 전 스택:  ... | T(3) | * | F(5)
축약 후 스택:  ... | T(15)
  -> 계산: 3 * 5 = 15

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

// D -> T L
// T.type은 합성 속성, L.inh는 상속 속성
void D() {
    String type = T();    // T의 합성 속성을 반환받음
    L(type);              // L의 상속 속성을 매개변수로 전달
}

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);  // 상속 속성 전달
        }
    }
}

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

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

최종 출력: 9 5 - 2 +

// 문법: 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        (B.type 상속)
  C1.type = array(3, integer)
C.type = array(2, array(3, integer))
T.type = array(2, array(3, integer))

// 원래 SDT
B -> a { action1 } b { action2 }

// 마커 논터미널을 사용한 변환
B -> a M b { action2 }
M -> epsilon { action1 }

// 원래 SDT (L-속성)
D -> T { L.inh = T.type } L

// 마커 논터미널 변환
D -> T M L
M -> epsilon  { /* T.type을 스택에서 복사하여 L.inh로 사용 */ }

단계                    속성의 활용
------------------------------------------------------
어휘 분석              토큰의 속성값 (정수값, 문자열값)
구문 분석              파스 트리/AST 구성
타입 검사              타입 속성의 합성과 검증
중간 코드 생성          3주소 코드의 합성
코드 최적화             데이터 흐름 속성
코드 생성              레지스터 할당, 명령어 선택

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

+------------------+-------------------+--------------------+
| 특성              | S-속성 정의        | L-속성 정의         |
+------------------+-------------------+--------------------+
| 속성 종류         | 합성만            | 합성 + 상속         |
| 평가 방향         | 아래 -> 위        | 왼쪽 -> 오른쪽      |
| 파서 종류         | Bottom-Up (LR)   | Top-Down (LL)      |
| 구현 복잡도        | 단순             | 중간               |
| 표현력            | 제한적           | 풍부               |
+------------------+-------------------+--------------------+

1단계: 파싱 -> AST 구성 (합성 속성 사용)
2단계: AST 순회 -> 심볼 테이블 구축 (상속 속성 흉내)
3단계: AST 순회 -> 타입 검사
4단계: AST 순회 -> 중간 코드 생성