# 1. 컴파일러 Front-End에서 Semantics의 위치
> 지금까지 Lexer와 Parser를 통해 소스코드의 **형태**를 다뤘다.
> 이제부터는 **의미**를 다룬다.
>
> Front-End의 나머지 단계인 Semantic Analyzer와 IR Translator가 그 대상이다.
> Middle-End부터는 '의미적으로 문제 없는' 프로그램이 입력으로 들어온다고 가정한다.
## 1.1 Front-End 구조 복습
```mermaid
flowchart TD
SRC([Source Program])
subgraph FE["Front-End"]
direction LR
LEX[Lexer] -->|Tokens| PAR[Parser] -->|AST| SEM[Semantic Analyzer] -->|AST| IRT[IR Translator]
end
IR([IR Program])
SRC --> FE
FE --> IR
```
## 1.2 Semantic Analyzer의 역할 복습
- AST가 올바른 의미를 표현하고 있는지 검사
- 타입 분석, 변수 선언 검사
- 이론적 기반: **프로그래밍 언어론**
# 2. 프로그래밍 언어의 "의미"란? - 변수와 상수
> 코드 `if (b == 0) a = b;`의 **의미**를 어떻게 정의할 수 있을까? 이 물음에 답하려면 먼저 "의미"가 무엇인지를 명확히 해야 한다. §2.1에서 Syntax와 Semantics를 구분하고, §2.2~2.5에서 While 언어를 예제로 삼아 상태(State), 변수, 계산식의 의미를 차례로 정의한다. 이렇게 쌓은 의미의 기초가 §4~5의 인터프리터 구현과 §6~7의 의미 분석 전체의 토대가 된다.
## 2.1 Syntax vs. Semantics
|구분|정의|이론적 기반|핵심 질문|
|---|---|---|---|
|**Syntax (구문)**|프로그램의 문법적 구조|오토마타 이론|이 코드가 어떻게 문법을 따르는가?|
|**Semantics (의미)**|프로그램의 실질적 행동|프로그래밍 언어론|이 코드가 컴퓨터에 의해 어떻게 실행되는가?|
둘 다 **컴파일러**로 구현된다.
## 2.2 예제 언어: While 언어 Abstract Syntax
```
S ::= x := a | skip | S ; S | if b S S | while b S
a ::= n | x | a + a | a * a | a - a
b ::= true | false | a = a | a <= a | ! b | b && b
```
|기호|의미|Side-effect|
|---|---|---|
|`S`|Statement (값 대입, 실행 흐름 변경 등)|**있음**|
|`a`|Arithmetic Expression (산술 계산식)|없음|
|`b`|Boolean Expression (논리 계산식)|없음|
|`x`|Variable (변수)|—|
|`n`|Numeral (숫자 값)|—|
**예제: Factorial Program AST**
```
y = 1; while !(x=1) do (y=y*x; x=x-1)
;
/ \
/ \
:= while
/ \ / \
y 1 ! ;
| / \
= := :=
/ \ / \ / \
x 1 y * x -
/ \ / \
y x x 1
```
## 2.3 상수의 의미 → 구문 표기 약속
**상수의 의미**
- `n` (numeral)의 의미: 숫자 그 자체
- `1`의 의미: 숫자 1 (앞의 `1`은 문자열 "1", 뒤의 `1`은 개념적 숫자 1)
- `true` / `false`의 의미: 참 / 거짓 그 자체
**구문 vs. 의미 표기 약속**
|표현 대상|표기법|예시|
|---|---|---|
|구문 (Syntax)|특별한 표시 없이|`y = 1` 또는 `y := 1`|
|의미 (Semantics)|`⟦ ⟧` 로 감쌈|`⟦1⟧`, `⟦y = 1⟧`|
> 💡 `1`(문자열)과 `⟦1⟧`(의미/개념적 숫자)는 엄연히 다른 것이다.
## 2.4 프로그램 상태 State와 변수의 의미
**프로그램 상태 (State)**
> **정의**: 어떤 순간에 정의된 변수들을 값과 함께 기록하고 있는 환경
$\sigma = \text{Var} \to \text{Value}$
즉, `Map<변수, 값>` 구조다.
- 의미는 **항상 상태와 함께** 한다:
- $⟦v⟧_\sigma$: 상태가 $\sigma$로 주어졌을 때, 변수 $v$의 의미
- 예: $⟦x⟧_{{x \mapsto 1}}$ = 상태에서 x를 찾으면 1
**변수의 의미**
변수의 의미는 현재 상태(환경)에 따라 달라진다:
$⟦x⟧_{{y \mapsto a}} := \begin{cases} a & \text{if } x = y \\ x & \text{otherwise} \end{cases}$
예: $⟦x⟧_{\sigma = {x \mapsto 1}} = ⟦1⟧_{\sigma}$
```
int x = 1;
// ...
x + 2 ← 여기서 x의 의미는? 상태에 {x↦1}이 있으면 → 3
상태에 {x↦2}이 있으면 → 4
```
## 2.5 Bound Variable vs. Free Variable
|구분|정의|이름 변경 시|
|---|---|---|
|**Bound Variable**|현재 코드 안에서 정의된 변수 (Binder가 있음)|의미 변하지 않음|
|**Free Variable**|코드 외부 상태에 따라 의미가 달라지는 변수|의미 달라짐|
```c
// BOUND VARIABLE 예시
{
int x = 1; ← Binder
y = x + 1; ← x는 위에서 정의됐으므로 Bound
}
// x를 z로 바꿔도 의미가 같음
// FREE VARIABLE 예시
int func(char *arr) {
arr[0] = y; ← y는 이 코드 안에서 정의된 적 없으므로 Free
}
// y를 다른 이름으로 바꾸면 의미가 달라짐
```
# 3. 계산식 Expression의 의미
> §2에서 변수와 상수의 의미를 정의했다. 이제 그 위에 쌓아서 **계산식**의 의미를 정의한다. 계산식은 Side-effect가 없는 식이므로, 상태를 변화시키지 않고 **값을 반환**한다. §4에서 다룰 Statement는 반대로 상태를 변화시킨다.
**계산식(Expression)의 정의**: Side-effect(프로그램 상태 변화)가 없는 식
- 산술 계산식(`a`): 숫자 값(int 타입) 반환
- 논리 계산식(`b`): 참/거짓 값(bool 타입) 반환
## 3.1 산술 계산식의 의미
연산자 양 쪽의 의미를 **먼저 계산**한 후, 연산자를 적용한다:
$⟦a_1 + a_2⟧_\sigma = ⟦a_1⟧_\sigma + ⟦a_2⟧_\sigma$ $⟦a_1 * a_2⟧_\sigma = ⟦a_1⟧_\sigma * ⟦a_2⟧_\sigma$ $⟦a_1 - a_2⟧_\sigma = ⟦a_1⟧_\sigma - ⟦a_2⟧_\sigma$
**예시:** $⟦x - 1⟧_{\sigma = {x \mapsto 1}} = ⟦x⟧_\sigma - ⟦1⟧_\sigma = ⟦1⟧_\sigma - ⟦1⟧_\sigma = ⟦0⟧_\sigma$
## 3.2 논리 계산식의 의미
마찬가지로 피연산자 의미를 먼저 계산 후 연산자를 적용:
$⟦a_1 = a_2⟧_\sigma = ⟦a_1⟧_\sigma = ⟦a_2⟧_\sigma$ $⟦a_1 \leq a_2⟧_\sigma = ⟦a_1⟧_\sigma \leq ⟦a_2⟧_\sigma$ $⟦\neg b⟧_\sigma = \neg ⟦b⟧_\sigma$ $⟦b_1 \land b_2⟧_\sigma = ⟦b_1⟧_\sigma \land ⟦b_2⟧_\sigma$
**예시:** $⟦x \leq 1⟧_{\sigma = {x \mapsto 1}} = ⟦x⟧_\sigma \leq ⟦1⟧_\sigma = ⟦1⟧_\sigma \leq ⟦1⟧_\sigma = ⟦true⟧_\sigma$
# 4. Statement의 의미 — 상태 변화를 어떻게 기술할까?
> §3의 Expression은 상태를 변화시키지 않고 값만 반환했다. 반면 **Statement**는 상태 자체를 변화시킨다. 이 절에서는 Statement의 의미를 표현하는 **추론 규칙(Inference Rule)** 표기법을 도입하고(§4.1), 각 Statement 종류별 의미를 정의한다(§4.2~4.6). 이 정의들이 §5 인터프리터 구현의 직접적 기반이 된다.
**Statement(구문)의 정의**: Side-effect를 유발할 수 있는 식. 프로그램이 실제로 실행되는 코드 단위.
$⟦S⟧_\sigma := \sigma'$
(cf. Expression: $⟦a_1 = a_2⟧_\sigma := ⟦a_1⟧_\sigma = ⟦a_2⟧_\sigma$ — 상태 변화 없이 값 계산)
## 4.1 추론 규칙 Inference Rule 표기법
$\frac{\langle S_1, \sigma \rangle \to \sigma_1,; \langle S_2, \sigma_1 \rangle \to \sigma_2,; \ldots,; \langle S_n, \sigma_{n-1} \rangle \to \sigma'}{\langle S, \sigma \rangle \to \sigma'} \text{ if cond}$
|구성 요소|설명|
|---|---|
|**분자 (Premises)**|가정 — 이것들이 성립할 때|
|**분모 (Conclusion)**|결론 — 이것이 성립한다|
|**if cond**|추가 조건|
|**공리 (Axiom)**|가정 없는 추론 규칙 (분자 비어있음)|
## 4.2 skip Statement
```
S ::= ... | skip | ...
```
아무런 상태 변화 없음 (공리):
$\frac{}{\langle skip, \sigma \rangle \to \sigma}$
## 4.3 assign Statement — Shadowing과 Scope
```
S ::= x := a | ...
```
$\frac{}{\langle x := a, \sigma \rangle \to \sigma[x \mapsto ⟦a⟧_\sigma]}$
- $\sigma[x \mapsto a]$: 기존 상태 $\sigma$에 "x가 a라는 값을 갖는다"는 정보를 **추가(덮어쓰기)**
**만약 x가 이미 상태에 존재한다면? → Shadowing**
```c
int func(char *arr) {
int x = 3; ← σ = {arr↦?, x↦3}
while (x > 1) {
int x = 2; ← σ = {arr↦?, x↦2} (x↦3을 덮어씀)
}
}
```
**Shadowing**: 기존 상태에 있던 변수 x가 새롭게 정의되면서 기존 정의를 덮어버리는 것.
**Scope**: 코드 내에서 변수의 정의가 영향을 미치는 범위.
```c
int func(char *arr) {
┌─────────────────────────────────┐
│ int x = 3; │ ← outer x, σ={arr↦?, x↦3}
│ while (x > 1) { │
│ ┌─────────────────────────┐ │
│ │ int x = 2; │ │ ← inner x, σ={arr↦?, x↦2}
│ └─────────────────────────┘ │
│ } ← Scope B 끝, x↦3 되살아남 │ σ={arr↦?, x↦3}
└─────────────────────────────────┘
}
```
> 💡 Scope 밖으로 벗어나면, Shadowing으로 가려졌던 기존 정의가 다시 살아난다.
## 4.4 sequential Statement
$\frac{\langle S_1, \sigma \rangle \to \sigma_1, \langle S_2, \sigma_1 \rangle \to \sigma'}{\langle S_1; S_2, \sigma \rangle \to \sigma'}$
- $\sigma$가 $\sigma_1$으로 바뀌고, $\sigma_1$이 $\sigma'$으로 바뀐다
- 전체로 보면: $\sigma$를 $\sigma'$으로 변화시킨다
## 4.5 if Statement
$\frac{\langle S_1, \sigma \rangle \to \sigma'}{\langle if b S_1 S_2, \sigma \rangle \to \sigma'} \text{ if } ⟦b⟧_\sigma = true$
$\frac{\langle S_2, \sigma \rangle \to \sigma'}{\langle if b S_1 S_2, \sigma \rangle \to \sigma'} \text{ if } ⟦b⟧_\sigma = false$
## 4.6 while Statement
$\frac{\langle S, \sigma \rangle \to \sigma'', \langle while b S, \sigma'' \rangle \to \sigma'}{\langle while b S, \sigma \rangle \to \sigma'} \text{ if } ⟦b⟧_\sigma = true$
$\frac{}{\langle while; b; S,; \sigma \rangle \to \sigma} \text{ if } ⟦b⟧_\sigma = false$
- `true` case: S를 실행해 $\sigma''$ 얻고, 다시 while 전체를 $\sigma''$ 위에서 재귀 실행
- `false` case: 상태 변화 없이 그대로 반환 (공리)
# 5. 인터프리터 구현 — 의미 정의를 코드로
> §4에서 추론 규칙으로 Statement의 의미를 정의했다. 이 정의는 인터프리터로 그대로 번역된다. §5는 While 언어 인터프리터를 F# 스타일 코드로 구현하는 전 과정이다. 이 인터프리터 구현 패턴은 §6~7의 의미 분석기 구현의 직접적 기반이 된다.
## 5.1 While 언어 타입 정의
```fsharp
type var = string
type ArithExp =
| Int of int
| Var of var
| Plus of ArithExp * ArithExp
| Mult of ArithExp * ArithExp
| Minus of ArithExp * ArithExp
type BoolExp =
| True
| False
| Eq of ArithExp * ArithExp
| Le of ArithExp * ArithExp
| Not of BoolExp
| And of BoolExp * BoolExp
type Stmt =
| Assign of var * ArithExp
| Skip
| Seq of Stmt * Stmt
| If of BoolExp * Stmt * Stmt
| While of BoolExp * Stmt
```
**인터프리터 함수 시그니처**
|함수|타입|대응하는 의미|
|---|---|---|
|`interpArithExp`|`ArithExp -> State -> int`|$⟦a⟧_\sigma \in \mathbb{Z}$|
|`interpBoolExp`|`BoolExp -> State -> bool`|$⟦b⟧_\sigma \in {true, false}$|
|`interpStmt`|`Stmt -> State -> State`|$⟦S⟧_\sigma = \sigma'$|
## 5.2 State 타입 설계 및 구현
**State 타입**: `(var * int) list` — 튜플의 Singly Linked List
```
State: [(varName₁, value₁); (varName₂, value₂); ...]
↑ 가장 최근에 추가된 것이 앞에 (Stack 구조)
```
> 💡 Immutable list를 사용하는 이유: Scope를 벗어날 때 이전 상태로 돌아가기 편리하다. 상태를 변경하는 게 아니라 새 리스트를 만들어 반환하면 된다.
```fsharp
type State = (var * int) list
module State =
let empty = []
let update state varName value =
(varName, value) :: state // 앞에 prepend → O(1)
let rec lookup state varName =
match state with
| [] -> failwith "No such variable!" // 선언 안 된 변수
| (varName_, value) :: state_ ->
if varName = varName_ then value
else lookup state_ varName
```
`lookup`은 리스트 앞에서부터 탐색하므로, 가장 최근에 `update`된 값(=shadowing된 값)이 먼저 반환된다.
## 5.3 interpArithExp 구현
```fsharp
let rec interpArithExp exp state =
match exp with
| Int n -> n // ⟦n⟧ = n
| Var varName -> State.lookup state varName // ⟦x⟧σ = σ(x)
| Plus (exp1, exp2) ->
let value1 = interpArithExp exp1 state
let value2 = interpArithExp exp2 state
value1 + value2 // ⟦a₁+a₂⟧σ = ⟦a₁⟧σ + ⟦a₂⟧σ
| Mult (exp1, exp2) ->
let value1 = interpArithExp exp1 state
let value2 = interpArithExp exp2 state
value1 * value2
| Minus (exp1, exp2) ->
let value1 = interpArithExp exp1 state
let value2 = interpArithExp exp2 state
value1 - value2
```
## 5.4 interpBoolExp 구현
```fsharp
let rec interpBoolExp exp state =
match exp with
| True -> true // ⟦true⟧σ = true
| False -> false
| Eq (exp1, exp2) ->
let value1 = interpArithExp exp1 state
let value2 = interpArithExp exp2 state
value1 = value2 // ⟦a₁=a₂⟧σ = ⟦a₁⟧σ = ⟦a₂⟧σ
| Le (exp1, exp2) ->
let value1 = interpArithExp exp1 state
let value2 = interpArithExp exp2 state
value1 <= value2
| Not exp ->
let value = interpBoolExp exp state
not value // ⟦¬b⟧σ = ¬⟦b⟧σ
| And (exp1, exp2) ->
let value1 = interpBoolExp exp1 state
let value2 = interpBoolExp exp2 state
value1 && value2 // ⟦b₁∧b₂⟧σ = ⟦b₁⟧σ ∧ ⟦b₂⟧σ
```
## 5.5 interpStmt 구현
```fsharp
let rec interpStmt stmt state =
match stmt with
| Assign (varName, exp) ->
let value = interpArithExp exp state // ⟦a⟧σ 계산
let state = State.update state varName value // σ[x↦⟦a⟧σ]
state
| Skip -> state // ⟨skip, σ⟩ → σ
| Seq (stmt1, stmt2) ->
let state1 = interpStmt stmt1 state // ⟨S₁, σ⟩ → σ₁
let state2 = interpStmt stmt2 state1 // ⟨S₂, σ₁⟩ → σ₂
state2
| If (exp, stmt1, stmt2) ->
let value = interpBoolExp exp state
let state =
if value then interpStmt stmt1 state // b=true → S₁ 실행
else interpStmt stmt2 state // b=false → S₂ 실행
state
| While (exp, stmt_) ->
let value = interpBoolExp exp state
if value then
let state = interpStmt stmt_ state // S 실행 → σ''
interpStmt stmt state // while 재귀
else state // b=false → σ 그대로
```
## 5.6 예제: Factorial 실행 추적
### 예제: Factorial Program AST 분석 (p.93)
대상 프로그램:
```
y = 1; while !(x = 1) do (y = y * x; x = x - 1)
```
AST:
```
;
/ \
/ \
:= while
/ \ / \
y 1 ! ;
| / \
= := :=
/ \ / \ / \
x 1 y * x -
/ \ / \
y x x 1
```
초기 조건:
- `scope = Block 0`
- `state = []`
- 변수 `x`, `y` 선언 없이 시작한다고 가정
> 슬라이드에서 x와 y가 미리 선언됐다고 가정하지 않는다.
> analyzeStmt가 Assign을 만날 때 비로소 state에 추가된다.
> 단, **우변(rhs)에서 쓰이는 변수는 그 시점에 이미 state에 있어야** 한다.
### STEP 1 — 루트 노드 `Seq(y:=1, while)` 진입
$\frac{\langle S_1,; lv,; \sigma \rangle \to \sigma_1,\quad \langle S_2,; lv,; \sigma_1 \rangle \to \sigma'}{\langle S_1;; S_2,; lv,; \sigma \rangle \to \sigma'}$
```
analyzeStmt (Seq(Assign(y,1), While(...)), Block 0, [])
```
Seq이므로 왼쪽(`S1`)부터 처리한다. 결과 state를 오른쪽(`S2`)에 넘긴다.
```
; ← 지금 여기
/ \
/ \
:= while
```
### STEP 2 — 왼쪽: `Assign(y, 1)` 처리
$\frac{}{\langle x := a,; lv,; \sigma \rangle \to \sigma[x \mapsto lv]}$
```
analyzeStmt (Assign(y, Int 1), Block 0, [])
```
**① 우변 `Int 1` 검사**
$\llbracket 1 \rrbracket_{\sigma} = true$
```
analyzeArithExp (Int 1) [] = true → OK
```
**② `y`가 현재 state에 있나?**
```
State.lookup [] "y" = Undeclared → 현재 scope에 없음 → Redeclare 아님
```
**③ state 업데이트**
```
state1 = [("y", Block 0)]
```
```
:= ← 처리 완료, y 등록됨
/ \
y 1
```
### STEP 3 — 오른쪽: `While(!(x=1), Seq(...))` 진입
$\frac{\langle S,; lv+1,; \sigma \rangle \to \sigma'',\quad \langle while; b; S,; lv+1,; \sigma'' \rangle \to \sigma'}{\langle while; b; S,; lv,; \sigma \rangle \to \sigma'}$
```
analyzeStmt (While(Neg(Eq(Var x, Int 1)), Seq(...)), Block 0, [("y", Block 0)])
```
**① 조건식 `!(x = 1)` 검사**
```
analyzeBoolExp (Neg (Eq (Var "x", Int 1))) [("y", Block 0)]
```
```
while ← 지금 여기
/ \
! ;
|
=
/ \
x 1
```
---
### STEP 4 — 조건식 분해: `Neg(Eq(Var x, Int 1))`
$\llbracket \neg b \rrbracket_{\sigma} = \llbracket b \rrbracket_{\sigma}$
```
analyzeBoolExp (Neg(...))
→ analyzeBoolExp (Eq(Var "x", Int 1))
```
$\llbracket a_1 \oplus a_2 \rrbracket_{\sigma} = \llbracket a_1 \rrbracket_{\sigma} \wedge \llbracket a_2 \rrbracket_{\sigma}$
```
analyzeBoolExp (Eq(Var "x", Int 1)) [("y", Block 0)]
→ analyzeArithExp (Var "x") [("y", Block 0)]
→ analyzeArithExp (Int 1) [("y", Block 0)]
```
**`Var "x"` lookup 결과:**
```
State.lookup [("y", Block 0)] "x" = Undeclared
→ analyzeArithExp (Var "x") = false
```
$\llbracket x \rrbracket_{{y \mapsto Block,0}} = false \quad (x \notin \sigma)$
**AND 계산:**
```
false && true = false
```
**→ analyzeBoolExp 결과 = false**
```
if not isValid then failwith "Undeclared Variable!"
```
> **`x`가 선언되지 않아 에러 발생.**
> 분석이 여기서 중단된다.
```
! ← 여기서 x 조회 실패
|
=
/ \
x 1
^
Undeclared!
```
---
### STEP 5 — x를 미리 선언한 경우로 재시도
> 실제 컴파일러는 x도 전역 혹은 함수 scope에서 미리 선언되어 있다고 가정한다.
> 초기 state에 x도 포함된 상태에서 다시 추적한다.
초기 조건 (재설정):
- `scope = Block 0`
- `state = [("x", Block 0)]` — x가 미리 선언된 상태
---
### STEP 6 — 다시 STEP 1: `Seq(y:=1, while)` 진입
```
analyzeStmt (Seq(Assign(y,1), While(...)), Block 0, [("x", Block 0)])
```
---
### STEP 7 — 다시 STEP 2: `Assign(y, 1)` 처리
```
analyzeArithExp (Int 1) [("x", Block 0)] = true → OK
State.lookup [("x", Block 0)] "y" = Undeclared → Redeclare 아님
state1 = [("y", Block 0), ("x", Block 0)]
```
---
### STEP 8 — 다시 STEP 3: `While` 조건식 `!(x=1)` 검사
```
analyzeArithExp (Var "x") [("y", Block 0), ("x", Block 0)]
→ State.lookup → ("x", Block 0) → true
analyzeArithExp (Int 1) = true
true && true = true → 조건식 OK
```
$\llbracket x = 1 \rrbracket_{\sigma} = \llbracket x \rrbracket_{\sigma} \wedge \llbracket 1 \rrbracket_{\sigma} = true \wedge true = true$
---
### STEP 9 — While 바디: `increaseScope` 적용 후 `Seq(:= y*x, := x-1)` 진입
$\frac{\langle S,; lv+1,; \sigma \rangle \to \sigma''}{\langle while; b; S,; lv,; \sigma \rangle \to \sigma'}$
```
analyzeStmt (Seq(Assign(y, y*x), Assign(x, x-1)),
Block 1, ← increaseScope: 0→1
[("y", Block 0), ("x", Block 0)])
```
Seq이므로 왼쪽부터.
```
while
/ \
! ; ← 지금 여기 (Block 1)
/ \
:= :=
/ \ / \
y * x -
/ \ / \
y x x 1
```
---
### STEP 10 — Seq 왼쪽: `Assign(y, y * x)` 처리
```
analyzeStmt (Assign("y", Mult(Var "y", Var "x")),
Block 1,
[("y", Block 0), ("x", Block 0)])
```
**① 우변 `y * x` 검사**
$\llbracket y * x \rrbracket_{\sigma} = \llbracket y \rrbracket_{\sigma} \wedge \llbracket x \rrbracket_{\sigma}$
```
analyzeArithExp (Mult(Var "y", Var "x")) [("y", Block 0), ("x", Block 0)]
→ analyzeArithExp (Var "y") → Block 0 → true
→ analyzeArithExp (Var "x") → Block 0 → true
→ true && true = true → OK
```
**② `y`가 현재 scope(Block 1)에 이미 있나?**
```
State.lookup [("y", Block 0), ("x", Block 0)] "y" = Block 0
Block 0 ≠ Block 1 → 다른 scope이므로 Redeclare 아님
```
**③ state 업데이트**
```
state2 = [("y", Block 1), ("y", Block 0), ("x", Block 0)]
↑ 새로 추가 (Block 1 레벨로)
```
```
:= ← 처리 완료
/ \
y *
/ \
y x
```
---
### STEP 11 — Seq 오른쪽: `Assign(x, x - 1)` 처리
```
analyzeStmt (Assign("x", Minus(Var "x", Int 1)),
Block 1,
[("y", Block 1), ("y", Block 0), ("x", Block 0)])
```
**① 우변 `x - 1` 검사**
$\llbracket x - 1 \rrbracket_{\sigma} = \llbracket x \rrbracket_{\sigma} \wedge \llbracket 1 \rrbracket_{\sigma}$
```
analyzeArithExp (Minus(Var "x", Int 1))
→ analyzeArithExp (Var "x")
State.lookup → ("x", Block 0) → true
→ analyzeArithExp (Int 1) → true
→ true && true = true → OK
```
**② `x`가 현재 scope(Block 1)에 이미 있나?**
```
State.lookup → Block 0 ≠ Block 1 → Redeclare 아님
```
**③ state 업데이트**
```
state3 = [("x", Block 1), ("y", Block 1), ("y", Block 0), ("x", Block 0)]
```
```
:= ← 처리 완료
/ \
x -
/ \
x 1
```
---
### STEP 12 — While 바디 분석 완료, 외부 state 반환
While은 내부 분석 결과를 버리고 **진입 직전 state를 반환**한다.
```
While 분석 종료:
내부 state3 = [("x", Block 1), ("y", Block 1), ...] → 버림
반환값 = [("y", Block 0), ("x", Block 0)] ← 진입 전 state
```
> 이것이 Immutable list의 핵심.
> 블록 내부 선언(`Block 1`)이 블록 밖으로 새어나가지 않는다.
$\frac{\langle S,; lv+1,; \sigma \rangle \to \sigma''}{\langle while; b; S,; lv,; \sigma \rangle \to \sigma} \quad \text{(외부 } \sigma \text{ 반환)}$
---
### STEP 13 — 전체 분석 완료
```
최종 반환 state = [("y", Block 0), ("x", Block 0)]
```
모든 변수 참조에서 `Undeclared`가 발견되지 않았으므로 **프로그램 통과**.
---
## 전체 흐름 한눈에 보기
```
analyzeStmt(Seq, Block 0, [x→B0])
│
├── STEP 7: Assign(y, 1)
│ 우변 Int 1 → true
│ y 없음 → 등록
│ state → [y→B0, x→B0]
│
└── STEP 8~12: While(!(x=1), Seq)
│
├── STEP 8: 조건식 !(x=1) 검사
│ x→B0 존재 → true OK
│
└── STEP 9~11: body = Seq, Block 1 (increaseScope)
│
├── STEP 10: Assign(y, y*x)
│ y, x 모두 존재 → true OK
│ y→B1 등록
│ state → [y→B1, y→B0, x→B0]
│
└── STEP 11: Assign(x, x-1)
x 존재 → true OK
x→B1 등록
state → [x→B1, y→B1, y→B0, x→B0]
↓
내부 state 버림
while 반환: [y→B0, x→B0] ← 외부 state 복원
```
최종 결과: **에러 없음. 분석 통과.**
```
y = 1; while !(x = 1) do (y = y * x; x = x - 1)
```
```
;
/ \
/ \
:= while
/ \ / \
y 1 ! ; ← Seq
| / \
= := :=
/ \ / \ / \
x 1 y * x -
/ \ / \
y x x 1
```
**analyzeStmt 적용 흐름** (초기 state = `[]`, scope = `Block 0`):
```
① Seq의 왼쪽: Assign(y, 1)
analyzeArithExp (Int 1) [] = true → OK
y가 state에 없음 → state = [(y, Block 0)]
② Seq의 오른쪽: While(!(x=1), ...)
analyzeBoolExp (Neg (Eq (Var x, Int 1))) state
→ analyzeArithExp (Var x) [(y, Block 0)]
x가 없음 → false! → "Undeclared Variable!" 에러
```
> x가 선언되지 않았으므로 이 프로그램은 Undeclared Identifier 에러를 낸다.
> x를 전역에서 먼저 선언해야 통과한다.
---
## 전체 구조 요약
```
analyzeStmt (scope=Block 0, state=[])
│
├─ Assign → 우변 expr 검사 → state에 (varName, scope) 추가
│ (같은 scope 재선언이면 에러)
│
├─ Seq → stmt1 먼저, 그 결과 state로 stmt2
│
├─ If → 조건식 검사 → 양 branch를 increaseScope로 분석
│ → 내부 state는 버리고 외부 state 반환
│
├─ While → 조건식 검사 → body를 increaseScope로 분석
│ → 내부 state는 버리고 외부 state 반환
│
└─ 모든 Var 참조 → State.lookup
Undeclared면 에러, Block(n)이면 OK
```
| 함수 | 입력 | 출력 | 핵심 의미 |
| ----------------- | ---------------------- | ------- | ----------------------- |
| `analyzeArithExp` | `ArithExp * State` | `bool` | 산술식 내 모든 변수가 선언됐는가 |
| `analyzeBoolExp` | `BoolExp * State` | `bool` | 논리식 내 모든 변수가 선언됐는가 |
| `analyzeStmt` | `Stmt * Scope * State` | `State` | 선언 정보를 누적하며 검사, 에러 시 예외 |
| `increaseScope` | `Scope` | `Scope` | 블록 진입 시 레벨 +1 |
# 6. 의미 분석 Semantic Analysis — 의미를 목적에 맞게 재정의하기
> §5까지는 소스코드가 실제로 **어떻게 작동하는지**를 기술하는 의미를 다뤘다. 그런데 컴파일러가 항상 프로그램을 실행해봐야 에러를 찾을 수 있는 건 아니다. **실행 전에** 프로그램의 특정 성질을 분석하고 싶은 경우가 있다. §6.2에서 그 예시를 보이고, §6.3에서 의미 분석기가 에러 검출을 위해 존재함을 확인한다. §7에서 그 첫 번째 구체적 분석인 Undeclared Identifier Check를 다룬다.
## 6.1 의미 분석기는 인터프리터 구현 기반
- Lexer, Parser: 입력 프로그램을 **변환**하는 데 집중
- Semantic Analyzer: 입력 프로그램이 **올바른지 확인**하는 데 집중
의미 분석의 핵심 아이디어:
1. **목적에 맞게 의미를 재정의**한다 (§5의 의미와 다를 수 있다)
2. **재정의된 의미를 바탕으로 인터프리터를 구현**한다
3. 잘못된 프로그램이면 **에러**, 올바른 프로그램이면 **AST/IR** 생성
> 💡 기반(§5 인터프리터 구현 패턴)을 먼저 이해하면, 각 분석마다 "무엇이 달라지는가"에만 집중할 수 있다. (예: LR(0) 먼저 이해하면 LR(1)에서는 LR(1) item에만 집중하면 되는 것처럼)
## 6.2 예제: "값이 0인가?" 를 목적으로 한 의미 재정의
실행 값 그 자체 대신 "0인지 아닌지"라는 **성질**에만 관심을 두는 의미:
$⟦a⟧_\sigma \in {IsZero,; IsNonZero,; MaybeZero}$
|표현식|재정의된 의미|
|---|---|
|$⟦0⟧_\sigma$|$IsZero$|
|$⟦1⟧_\sigma$|$IsNonZero$|
|$⟦x⟧_{{x \mapsto IsNonZero}}$|$IsNonZero$|
|$⟦x+y⟧_{{x \mapsto IsNonZero,; y \mapsto IsNonZero}}$|$IsNonZero + IsNonZero = ?$|
**왜 이런 분석이 필요한가?**
```c
int bug(int n) {
if (n != 0) {
printf("Normal behavior!\n");
} else {
printf("The result is %d\n", 100 / n); // ← n=0일 때 divide-by-zero!
}
}
```
`n`이 0인지 아닌지를 추적하면 **divide-by-zero 버그**를 실행 전에 탐지할 수 있다. 이와 같은 방식으로 buffer overflow 같은 버그도 찾을 수 있다.
## 6.3 의미 분석의 목적 — 에러 검출
> "저는 모든 학생들에게 A+를 부여하겠습니다." → 문법적으로는 OK, **의미적으로는 잘못된** 문장.
프로그램도 마찬가지다. Syntax 검사를 통과했더라도 의미적으로 잘못된 경우가 있다.
## 6.4 우리가 다룰 의미 에러 — Undeclared Identifier Check & Type Check
이 수업에서 다루는 두 가지 의미 에러:
|에러 종류|설명|
|---|---|
|**Undeclared Identifier Check**|선언되지 않은 변수 사용|
|**Type Check**|타입이 맞지 않는 연산|
# 7. Undeclared Identifier Check
> §6.3에서 의미 에러의 두 종류를 제시했다.
> §7에서는 그 첫 번째인 **Undeclared Identifier Check**를 다룬다.
>
> §7.1에서 목표를 정하고, §7.2~7.3에서 Scope 규칙을 명확히 하며,
> §7.4~7.5에서 §5의 인터프리터 구현 패턴을 그대로 따라 분석기를 구현한다.
**문제 예시**:
```c
// test.c — 컴파일 에러 발생
int main() {
printf("I'm %d years old!\n", n); // n이 선언된 적 없음!
return 0;
}
```
```
test.c:4:33: error: 'n' undeclared (first use in this function)
4 | printf("I'm %d years old!\n", n);
^
```
수정 후:
```c
// test.c — 컴파일 성공
#include <stdio.h>
int n = 260; // n 선언 추가
int main() {
printf("My foot is %d mm long!\n", n);
return 0;
}
```
## 7.1 분석 목표: 모든 변수가 Bound Variable인가?
코드 내에 등장하는 **모든 변수**에 대해, 프로그램 전체 scope에서 **Bound Variable**인지 확인:
- = 이 변수가 어디에서 선언된 변수에 의해 bound된 것인지 확인
만약 프로그램 전체 scope를 다 확인해도 **Free Variable**이면 → 의미적 문제
이를 위해 **Scope의 명확한 정의**가 필요하다.
## 7.2 정적 Scope vs. 동적 Scope
|구분|정의 방식|대표 언어|
|---|---|---|
|**정적 Scope (Static Scope)**|코드 구조(텍스트)상으로 Scope 결정|C, Java, Python 등 대부분|
|**동적 Scope (Dynamic Scope)**|실행 흐름(호출 스택)에 따라 Scope 결정|Lisp, Bash, Perl|
**정적 Scope 예시** — `g` 안의 `n`은 전역 `n=1`을 참조:
```c
int n = 1; ← 전역 n (정적 스코프: 코드 구조상 g에서 보임)
│
void f() { │
int n = 3; │ (f 지역 n, g와 구조적으로 무관)
g(3); │
} │
▼
void g(int k) {
int y = n; ← 여기서 n은 전역 n = 1
}
```
**동적 Scope 예시** — `g` 안의 `n`은 호출자 `f`의 `n=3`을 참조:
```c
int n = 1;
void f() {
int n = 3; ← f가 g를 호출하는 시점의 n
g(3); │
} ▼
void g(int k) {
int y = n; ← 여기서 n은 호출자 f의 n = 3
}
```
## 7.3 C-- 언어의 정적 Scope 규칙
Scope의 범위 (좁은 것 → 넓은 것):
```
블록 Scope ⊂ 함수 Scope ⊂ 전역 Scope
{} function global var
```
규칙:
- 각 Scope 안에서 같은 이름의 변수는 **한 번만 선언(declare)** 가능
- 값은 여러 번 **할당(assign)** 가능
- 변수의 **자신 Scope**부터 시작해 **더 큰 Scope**로 확장하며 선언 확인
- 같은 범위 안에서는 **변수 등장 이전에** 존재하는 선언만 확인
```c
int n; // ← 전역 Scope
int main() { // ← 함수 Scope
int n; // (전역 n을 shadow)
for ( ; ; ) { // ← 블록 Scope
int n; // (함수 n을 shadow)
{
int n; // (for-블록 n을 shadow)
// ...
}
n + 1; // 여기서 n은 for-블록의 n
}
}
```
## 7.4 Undeclared Identifier 분석에서의 의미 재정의
**우리의 관심사**: 변수가 잘 선언되어 있는가?
§5의 인터프리터에서 "값"을 반환하던 것 대신, 이 분석에서는 **bool(선언됐는지 여부)**을 반환한다.
**변수의 의미 (재정의)**:
$⟦x⟧_\sigma = \begin{cases} true & \text{if } x \in \sigma \\ false & \text{otherwise} \end{cases}$
**나머지 식의 의미**:
$⟦n⟧_\sigma = true \qquad \text{(숫자 리터럴은 항상 OK)}$
$⟦a_1 \oplus a_2⟧_\sigma = ⟦a_1⟧_\sigma \land ⟦a_2⟧_\sigma \qquad (\oplus \in {+, *, -})$
즉, 계산식 전체가 유효하려면 모든 하위 식이 유효해야 한다.
## 7.5 분석기 구현 — analyzeArithExp / analyzeBoolExp / analyzeStmt
**State 타입 재정의** (값 대신 Scope 레벨을 저장):
```fsharp
type Scope =
| Block of int // 블록 레벨 번호
| Undeclared // 선언되지 않음
type State = (var * Scope) list // 변수 → Scope 레벨 매핑
module State =
let empty = []
let update state varName scope =
(varName, scope) :: state
let rec lookup state varName =
match state with
| [] -> varName, Undeclared // 선언 안 됨!
| (varName_, scope) :: state_ ->
if varName = varName_ then scope
else lookup state_ varName
```
**analyzeArithExp**:
```fsharp
let rec analyzeArithExp exp state =
match exp with
| Int _ -> true // ⟦n⟧σ = true
| Var varName ->
let scope = State.lookup state varName
match scope with
| Undeclared -> false // ⟦x⟧σ = false (선언 안 됨)
| _ -> true // ⟦x⟧σ = true (선언됨)
| Plus (exp1, exp2)
| Mult (exp1, exp2)
| Minus (exp1, exp2) ->
let isValid1 = analyzeArithExp exp1 state
let isValid2 = analyzeArithExp exp2 state
isValid1 && isValid2 // ⟦a₁⊕a₂⟧σ = ⟦a₁⟧σ ∧ ⟦a₂⟧σ
```
**analyzeBoolExp**:
```fsharp
let rec analyzeBoolExp exp state =
match exp with
| True | False -> true // ⟦true⟧σ = ⟦false⟧σ = true
| Eq (exp1, exp2)
| Le (exp1, exp2) ->
let isValid1 = analyzeArithExp exp1 state
let isValid2 = analyzeArithExp exp2 state
isValid1 && isValid2 // ⟦a₁⊕a₂⟧σ = ⟦a₁⟧σ ∧ ⟦a₂⟧σ
| Not exp ->
analyzeBoolExp exp state // ⟦¬b⟧σ = ⟦b⟧σ
| And (exp1, exp2) ->
let isValid1 = analyzeBoolExp exp1 state
let isValid2 = analyzeBoolExp exp2 state
isValid1 && isValid2 // ⟦b₁∧b₂⟧σ = ⟦b₁⟧σ ∧ ⟦b₂⟧σ
```
**analyzeStmt** — §5 interpStmt와의 비교:
```fsharp
let rec analyzeStmt stmt scope state =
match stmt with
| Assign (varName, exp) ->
let isValid = analyzeArithExp exp state
if not isValid then failwith "Undeclared Variable!"
let varScope = State.lookup state varName
if varScope = scope then failwith "Redeclared Variable!" // 같은 scope 재선언 금지
else State.update state varName scope
| Skip -> state // ⟨skip, lv, σ⟩ → σ
| Seq (stmt1, stmt2) ->
let state1 = analyzeStmt stmt1 scope state
let state2 = analyzeStmt stmt2 scope state1
state2
| If (exp, stmt1, stmt2) ->
let isValid = analyzeBoolExp exp state
if not isValid then failwith "Undeclared Variable!"
let _ = analyzeStmt stmt1 (increaseScope scope) state // 블록 내부는 scope+1
let _ = analyzeStmt stmt2 (increaseScope scope) state
state // if 자체는 외부 scope 변경 없음
| While (exp, stmt_) ->
let isValid = analyzeBoolExp exp state
if not isValid then failwith "Undeclared Variable!"
let _ = analyzeStmt stmt_ (increaseScope scope) state // 블록 내부는 scope+1
state // while 자체는 외부 scope 변경 없음
```
**increaseScope** (블록에 진입할 때 scope 레벨 증가):
```fsharp
let increaseScope scope =
match scope with
| Block level -> Block (level + 1)
| _ -> failwith "Invalid scope!"
```
> 💡 **interpStmt와 analyzeStmt의 차이**: interpStmt는 실제 값을 계산해 state를 업데이트하지만, analyzeStmt는 **선언 여부**만 추적한다. If/While 블록 내부는 `increaseScope`로 레벨을 높여 분석하되, 블록을 나오면 내부에서 선언한 변수가 외부에 영향을 주지 않도록 분석 전의 state를 반환한다. Immutable list 덕분에 이것이 자연스럽게 구현된다.
**전체 분석기 흐름 요약**:
```
AST 입력
│
▼
analyzeStmt (scope=Block 0, state=[])
├─ Assign: 우변 expression 검사 → state에 변수 추가 (선언 기록)
├─ Seq: 순차 실행
├─ If/While: 블록 내부를 increaseScope로 분석 → 내부 선언은 외부에 영향 없음
└─ 모든 Var 참조 시 state에서 lookup → Undeclared이면 에러
│
▼
에러 없으면 → AST 통과 (다음 단계로)
에러 있으면 → "Undeclared Variable!" 에러 발생
```
# 8. Type Check
> §7에서 Undeclared Identifier Check를 다뤘다. §8에서는 두 번째 의미 에러인 **Type Check**를 다룬다.
>
> §8.1에서 Type의 개념을 복습하고, §8.2에서 언어 설계 선택지를 정리한다. §8.3~8.4에서 Symbol Table을 도입하고, §8.5~8.9에서 Type 의미를 형식적으로 정의한다. §8.10~8.11에서 실제 예제를 통해 전체 흐름을 확인하며, §8.12에서 실전에서의 고민거리를 짚는다.
## 8.1 Type이란?
**두 가지 측면에서 이해할 수 있다:**
|측면|설명|예시|
|---|---|---|
|**값의 범위 한정**|특정 타입에 속하는 값의 집합을 제한|`unsigned int` → ${0, 1, \ldots, 2^{32}-1}$|
|**연산 한정**|해당 타입에 적용 가능한 연산을 제한|`(char *) x + (float) y` → Type 에러|
```c
// 범위 예시
unsigned int x = -1; // 컴파일은 되지만 의미가 달라짐 (wrap-around)
// 연산 예시
char *p = "hello";
float f = 3.14f;
p + f; // ← Type 에러! 포인터 + float은 정의되지 않음
```
## 8.2 언어의 Type에 대한 Design Choice
실제 언어 설계에서는 Type에 관해 여러 선택지가 존재한다:
|축|한쪽 끝|다른 쪽 끝|설명|
|---|---|---|---|
|**Weakly vs. Strongly Typed**|Weakly (느슨함)|**Strongly** (엄격함)|Type으로 인한 제약이 얼마나 강한가|
|**Statically vs. Dynamically Typed**|**Statically** (컴파일 타임)|Dynamically (런타임)|Type이 언제 결정되는가|
|**Explicitly vs. Implicitly Typed**|**Explicitly** (명시)|Implicitly (추론)|Type을 코드에 직접 적어야 하는가|
**예시 비교:**
|언어|Weak/Strong|Static/Dynamic|Explicit/Implicit|
|---|---|---|---|
|JavaScript|Weakly|Dynamically|Implicitly|
|Python|Strongly|Dynamically|Implicitly|
|C|Strongly|Statically|Explicitly|
|F#|Strongly|Statically|**Implicitly** (타입 추론)|
> 💡 C와 F#은 둘 다 Statically Typed지만, C는 타입을 직접 명시해야 하고 F#은 타입 추론을 지원한다.
## 8.3 Symbol Table
### 8.3.1 Identifier 파악의 중요성
프로그램의 의미를 분석하는 과정에서 함수나 변수에 대한 정보 파악은 필수적이다:
```c
int n = 260;
int main(int argc, char **argv) {
// ↑ n: int형 변수 ↑ argc: int ↑ argv: char* 변수
printf("My foot is %d mm long!\n", n);
// ↑ 여기서 n의 타입은? → Symbol Table에서 조회
return 0;
}
```
- `n`의 타입은 `int`인가? `float`인가?
- `argc`는 상수인가, 변수인가?
- 함수 `main`의 시그니처는?
이 모든 정보를 기록하는 자료구조가 **Symbol Table**이다.
### 8.3.2 Symbol Table 정의
> **Symbol Table**: 파악한 변수나 함수 등에 대한 정보를 기록하는 테이블
**예시 — 위 코드에 대한 Symbol Table:**
|이름|종류|타입|위치|
|---|---|---|---|
|`n`|변수|`int`|line 1|
|`main`|함수|`int × char* → int`|line 3|
|`argc`|변수|`int`|line 3|
|`argv`|변수|`char*`|line 3|
|…|…|…|…|
### 8.3.3 Scope별 Symbol Table
Symbol Table은 **Scope별로 나누어서 관리**하기도 한다:
```c
int n; // 전역 Scope
int main() { // main 함수의 Block Scope 0
int n;
for ( ; ; ) { // Block Scope 1 (for-문)
int n;
{ // Block Scope 2 (중첩 블록)
int n;
}
n + 1;
}
}
```
|Scope|이름|타입|위치|
|---|---|---|---|
|전역|`n`|`int`|line 1|
|Block 0|`n`|`int`|line 4|
|Block 1 (for)|`n`|`int`|line 8|
|Block 2 (중첩)|`n`|`int`|line 10|
> 💡 **§7의 State와 Symbol Table의 관계**: Symbol Table ≈ Undeclared Identifier 분석의 State + 추가 정보(타입, 위치 등)
### 8.3.4 Symbol Table 인터페이스
```fsharp
module SymbTab =
val enterScope : SymbTab -> CurLocation -> Scope * SymbTab
// 새 블록에 진입할 때 Scope를 열고 새 SymbTab 반환
val addSymbol : SymbTab -> Scope -> string -> Info -> SymbTab
// 현재 Scope에 심볼(이름, 정보)을 추가
val checkSymbol : SymbTab -> string -> bool
// 현재 Scope에 해당 이름이 이미 선언되어 있는가? (재선언 검사용)
val findSymbol : SymbTab -> string -> Info option
// 이름으로 심볼 조회 (None이면 Undeclared)
val exitScope : SymbTab -> Scope -> SymbTab
// 블록을 벗어날 때 해당 Scope의 심볼을 제거하고 이전 SymbTab 반환
```
**각 연산의 역할:**
|연산|역할|언제 사용|
|---|---|---|
|`enterScope`|새 블록 진입, Scope 레벨 증가|`{` 블록 시작 시|
|`addSymbol`|변수/함수 선언 기록|`int x;` 등 선언 처리 시|
|`checkSymbol`|같은 Scope 내 중복 선언 검사|선언 처리 전|
|`findSymbol`|변수 참조 시 정보 조회|`x + 1` 등 Var 처리 시|
|`exitScope`|블록 탈출, 내부 선언 제거|`}` 블록 종료 시|
### 8.3.5 Symbol Table을 활용한 Undeclared Identifier 분석
§7.5의 분석기를 Symbol Table 기반으로 재작성하면:
```fsharp
let rec analyzeArithExp exp symbTab =
match exp with
// ...
| Var varName ->
match SymbTab.findSymbol symbTab varName with
| Some _ -> true // 선언됨
| _ -> false // 선언 안 됨
// ...
let rec buildSymbTabStmt stmt scope symbTab =
match stmt with
| Assign (varName, exp) ->
let isValid = analyzeArithExp exp symbTab
if not isValid then failwith "Undeclared Variable!"
let isDeclared = SymbTab.checkSymbol symbTab varName
if isDeclared then failwith "Redeclared Variable!"
let symbTab = SymbTab.addSymbol symbTab scope varName (...)
symbTab
| If (exp, stmt1, stmt2) ->
let isValid = analyzeBoolExp exp symbTab
if not isValid then failwith "Undeclared Variable!"
let scope_, symbTab1 = SymbTab.enterScope symbTab (...)
let symbTab1 = buildSymbTabStmt stmt1 scope_ symbTab1
let symbTab1 = SymbTab.exitScope symbTab1 scope_
let scope_, symbTab2 = SymbTab.enterScope symbTab1 (...)
let symbTab2 = buildSymbTabStmt stmt2 scope_ symbTab2
let symbTab2 = SymbTab.exitScope symbTab2 scope_
symbTab2
| While (exp, stmt_) ->
let isValid = analyzeBoolExp exp symbTab
if not isValid then failwith "Undeclared Variable!"
let scope_, symbTab = SymbTab.enterScope stmt scope symbTab
let symbTab = buildSymbTabStmt stmt_ scope_ symbTab
let symbTab = SymbTab.exitScope symbTab scope_
symbTab
```
> 💡 **§7.5 analyzeStmt와의 차이**: State 대신 SymbTab을 들고 다니며, `increaseScope` 대신 `enterScope`/`exitScope` 쌍으로 블록을 관리한다. Symbol Table에는 타입·위치 등 추가 정보도 함께 기록된다.
## 8.4 Type 분석의 큰 그림
Type 분석은 두 단계로 이루어진다:
```
(1) Symbol Table 구축
│ 변수/함수의 타입 정보를 Symbol Table에 기록
▼
(2) Type 검사 (= 인터프리터)
│ 프로그램을 순회하며
│ Symbol Table의 타입 정보와 실제 사용이 일치하는지 확인
▼
에러 없음 → AST 통과
에러 있음 → Type Error 발생
```
**우리의 관심사**: 값이 타입에 맞게 잘 사용되고 있는가?
- **Expression의 의미**: 연산이 타입에 맞게 적용되었는가?
- **Statement의 의미**: 구성요소(Expression, Statement)들이 타입에 맞게 정의되어 있는가?
## 8.5 Type 분석을 위한 표기 약속
전통적으로 Type 분석의 의미는 §2~4의 $⟦\cdot⟧_\sigma$ 표기와 다른 형태를 사용한다.
### 8.5.1 Type 표현 — Γ ⊢ E : τ
> **"Γ라는 Type 상태에서, E는 τ라는 타입을 갖는다."**
$\Gamma \vdash E : \tau$
|기호|의미|
|---|---|
|$\Gamma$ (Gamma)|Type 상태 = Symbol Table (변수 → 타입 매핑)|
|$\vdash$ (turnstile)|"~에서 ~이 성립한다"|
|$E$|분석 대상 Expression 또는 Statement|
|$\tau$ (tau)|타입 (`int`, `bool` 등)|
### 8.5.2 Type 상태에 변수의 타입 기록 — Γ[x ↦ τ]
> **"Type 상태 Γ에 변수 x의 타입이 τ라는 사실을 추가한다."**
$\Gamma[x \mapsto \tau]$
구현 대응: `SymbTab.addSymbol`
### 8.5.3 Type 상태에서 변수의 타입 조회 — Γ(x) = τ
> **"Type 상태 Γ에서 변수 x의 타입이 τ임을 확인한다."**
$\Gamma(x) = \tau$
구현 대응: `SymbTab.findSymbol`
### 8.5.4 가정과 결론 — Inference Rule 형태
§4.1의 추론 규칙과 같은 형태지만, Type 검사에서는 다음처럼 쓴다:
$\frac{\Gamma \vdash P_1, \ldots}{\Gamma \vdash C}$
|구성 요소|의미|
|---|---|
|분자 (Premises)|이것들이 타입 검사를 통과할 때|
|분모 (Conclusion)|이것도 타입 검사를 통과한다|
## 8.6 예제 언어: TWhile (Typed-While)
While 언어에 타입 선언을 추가한 언어:
```
S ::= t x | x := a | x := b | skip | S ; S | if b S S | while b S
a ::= n | x | a + a | a * a | a - a
b ::= true | false | x | a = a | a <= a | ! b | b && b
t ::= int | bool
```
**§2.2 While 언어와의 차이:**
|차이점|While|TWhile|
|---|---|---|
|변수 선언|`x := a` 로 암묵적 생성|`t x` 로 명시적 선언 필요|
|bool 변수|bool 식만 존재|`x`가 bool 타입 변수가 될 수 있음|
|타입 키워드|없음|`int`, `bool`|
## 8.7 상수와 변수의 타입
### 8.7.1 상수의 타입
타입 상태 Γ에 무관하게 항상 정해진 타입을 갖는다 (공리):
$\Gamma \vdash n : int$
$\Gamma \vdash true : bool$
$\Gamma \vdash false : bool$
### 8.7.2 변수의 타입
변수의 타입은 현재 Type 상태(Symbol Table)에 따라 결정된다:
$\frac{\Gamma(x) = \tau}{\Gamma \vdash x : \tau}$
즉, Symbol Table에서 x의 타입을 찾아 반환한다. x가 없으면 Undeclared 에러.
## 8.8 계산식의 타입
### 8.8.1 산술 계산식
양 쪽 피연산자가 모두 `int` 타입이어야 결과도 `int`:
$\frac{\Gamma \vdash a_1 : int,\quad \Gamma \vdash a_2 : int}{\Gamma \vdash a_1 + a_2 : int}$
곱셈, 뺄셈도 동일한 규칙.
### 8.8.2 비교 계산식
`int` 두 개를 비교해 `bool`을 반환:
$\frac{\Gamma \vdash a_1 : int,\quad \Gamma \vdash a_2 : int}{\Gamma \vdash a_1 \leq a_2 : bool}$
### 8.8.3 논리 계산식
```
¬b: b가 bool이면 결과도 bool
b₁ && b₂: 양 쪽 모두 bool이면 결과도 bool
```
$\frac{\Gamma \vdash b : bool}{\Gamma \vdash \neg b : bool}$
$\frac{\Gamma \vdash b_1 : bool,\quad \Gamma \vdash b_2 : bool}{\Gamma \vdash b_1 \land b_2 : bool}$
**타입 규칙 요약표:**
|식|필요 조건|결과 타입|
|---|---|---|
|$n$|—|`int`|
|`true`, `false`|—|`bool`|
|$x$|$\Gamma(x) = \tau$|$\tau$|
|$a_1 \oplus a_2$|양 쪽 모두 `int`|`int`|
|$a_1 \leq a_2$|양 쪽 모두 `int`|`bool`|
|$a_1 = a_2$|양 쪽 모두 `int`|`bool`|
|$\neg b$|`b`가 `bool`|`bool`|
|$b_1 \land b_2$|양 쪽 모두 `bool`|`bool`|
## 8.9 Statement의 타입 규칙
Statement는 Expression처럼 값을 반환하지 않으므로, "$\Gamma \vdash S
quot; 형태로 "S가 타입에 맞게 잘 정의되어 있다"를 표현한다.
### 8.9.1 skip
항상 타입 문제 없음 (공리):
$\overline{\Gamma \vdash skip}$
### 8.9.2 선언 Statement — `t x ; S`
x의 타입 τ를 Γ에 추가한 상태에서 S가 타입 검사를 통과해야 전체가 OK:
$\frac{\Gamma[x \mapsto \tau] \vdash S}{\Gamma \vdash \tau\ x\ ;\ S}$
> 💡 **선언 이후의 코드(S)는 x의 타입 정보가 추가된 Γ[x↦τ] 상태에서 검사된다.** 이것이 "선언이 그 이후의 코드에만 영향을 미친다"는 Scope 규칙의 타입 표현이다.
### 8.9.3 assign Statement — `x := a`
변수 x의 기존 타입과 대입하는 식 a의 타입이 **일치**해야 OK:
$\frac{\Gamma(x) = \tau_1,\quad \Gamma \vdash a : \tau_2,\quad \tau_1 = \tau_2}{\Gamma \vdash x := a}$
### 8.9.4 sequential Statement — `S₁ ; S₂`
두 Statement 모두 타입 검사를 통과해야 OK:
$\frac{\Gamma \vdash S_1,\quad \Gamma \vdash S_2}{\Gamma \vdash S_1 ; S_2}$
### 8.9.5 if Statement
조건 b가 `bool` 타입이고, 두 분기 모두 타입 검사를 통과해야 OK:
$\frac{\Gamma \vdash b : bool,\quad \Gamma \vdash S_1,\quad \Gamma \vdash S_2}{\Gamma \vdash if\ b\ S_1\ S_2}$
### 8.9.6 while Statement
조건 b가 `bool` 타입이고, 루프 바디 S가 타입 검사를 통과해야 OK:
$\frac{\Gamma \vdash b : bool,\quad \Gamma \vdash S}{\Gamma \vdash while\ b\ S}$
**타입 규칙 요약표 — Statement:**
|Statement|조건|판정|
|---|---|---|
|`skip`|—|OK|
|`τ x ; S`|$\Gamma[x \mapsto \tau] \vdash S$|OK|
|`x := a`|$\Gamma(x) = \tau$, $\Gamma \vdash a : \tau$|OK|
|`S₁ ; S₂`|$\Gamma \vdash S_1$, $\Gamma \vdash S_2$|OK|
|`if b S₁ S₂`|$\Gamma \vdash b : bool$, 양 분기 OK|OK|
|`while b S`|$\Gamma \vdash b : bool$, $\Gamma \vdash S$|OK|
## 8.10 예제 — 간단한 TWhile 프로그램 타입 검사
```
int x;
bool y;
x := 10;
y := true;
x := x + y; ← Type Error!
if (y)
x := 1
else
x := 0
```
**단계별 검사 과정:**
**Step 1: `int x`** — 선언 규칙 적용
$\Gamma[,] \xrightarrow{int\ x} \Gamma_1 = {x \mapsto int}$
**Step 2: `bool y`** — 선언 규칙 적용
$\Gamma_1 \xrightarrow{bool\ y} \Gamma_2 = {x \mapsto int,\ y \mapsto bool}$
**Step 3: `x := 10`** — assign 규칙 적용
$\Gamma_2(x) = int, \quad \Gamma_2 \vdash 10 : int \quad \Rightarrow \quad \tau_1 = \tau_2 = int \quad \checkmark$
**Step 4: `y := true`** — assign 규칙 적용
$\Gamma_2(y) = bool, \quad \Gamma_2 \vdash true : bool \quad \Rightarrow \quad \tau_1 = \tau_2 = bool \quad \checkmark$
**Step 5: `x := x + y`** — assign + 산술식 타입 검사
$\Gamma_2 \vdash x : int, \quad \Gamma_2 \vdash y : bool$
$\Gamma_2 \vdash x + y : \text{???} \quad \leftarrow int + bool \text{ → 규칙 없음!}$
$\boxed{\text{Type Error: int + bool is undefined}}$
**Step 6: `if (y) x := 1 else x := 0`** — (Step 5에서 이미 에러이지만 확인용)
$\Gamma_2 \vdash y : bool \quad \checkmark$
$\Gamma_2(x) = int, \quad \Gamma_2 \vdash 1 : int \quad \checkmark$
$\Gamma_2(x) = int, \quad \Gamma_2 \vdash 0 : int \quad \checkmark$
**전체 결론**: `x := x + y`에서 **Type Error** 발생.
## 8.11 Type Check 구현 — typeCheckArithExp / typeCheckBoolExp / typeCheckStmt
§7.5 analyzeStmt와 같은 구조로 구현하되, **State 대신 Symbol Table**, **bool 대신 타입(τ)**을 반환한다.
**typeCheckArithExp** — 타입을 반환하거나 에러:
```fsharp
let rec typeCheckArithExp exp symbTab =
match exp with
| Int _ -> Some TInt // Γ ⊢ n : int
| Var varName ->
match SymbTab.findSymbol symbTab varName with
| Some info -> Some info.typ // Γ(x) = τ → Γ ⊢ x : τ
| None -> failwith "Undeclared Variable!"
| Plus (exp1, exp2)
| Mult (exp1, exp2)
| Minus (exp1, exp2) ->
let t1 = typeCheckArithExp exp1 symbTab
let t2 = typeCheckArithExp exp2 symbTab
match t1, t2 with
| Some TInt, Some TInt -> Some TInt // int ⊕ int → int
| _ -> failwith "Type Error!"
```
**typeCheckBoolExp**:
```fsharp
let rec typeCheckBoolExp exp symbTab =
match exp with
| True | False -> Some TBool // Γ ⊢ true/false : bool
| Eq (exp1, exp2)
| Le (exp1, exp2) ->
let t1 = typeCheckArithExp exp1 symbTab
let t2 = typeCheckArithExp exp2 symbTab
match t1, t2 with
| Some TInt, Some TInt -> Some TBool // int = int → bool
| _ -> failwith "Type Error!"
| Not exp ->
match typeCheckBoolExp exp symbTab with
| Some TBool -> Some TBool // ¬bool → bool
| _ -> failwith "Type Error!"
| And (exp1, exp2) ->
let t1 = typeCheckBoolExp exp1 symbTab
let t2 = typeCheckBoolExp exp2 symbTab
match t1, t2 with
| Some TBool, Some TBool -> Some TBool // bool ∧ bool → bool
| _ -> failwith "Type Error!"
```
**typeCheckStmt**:
```fsharp
let rec typeCheckStmt stmt symbTab =
match stmt with
| Decl (typ, varName, rest) -> // t x ; S
let isDeclared = SymbTab.checkSymbol symbTab varName
if isDeclared then failwith "Redeclared Variable!"
let symbTab' = SymbTab.addSymbol symbTab currentScope varName { typ = typ; ... }
typeCheckStmt rest symbTab' // Γ[x↦τ] ⊢ S
| Assign (varName, exp) -> // x := a
let varTyp =
match SymbTab.findSymbol symbTab varName with
| Some info -> info.typ
| None -> failwith "Undeclared Variable!"
let expTyp =
match typeCheckArithExp exp symbTab with
| Some t -> t
| None -> failwith "Type Error!"
if varTyp <> expTyp then failwith "Type Error!"
symbTab
| Skip -> symbTab // skip은 항상 OK
| Seq (stmt1, stmt2) -> // S₁ ; S₂
let symbTab' = typeCheckStmt stmt1 symbTab
typeCheckStmt stmt2 symbTab'
| If (exp, stmt1, stmt2) -> // if b S₁ S₂
match typeCheckBoolExp exp symbTab with
| Some TBool -> ()
| _ -> failwith "Type Error: condition must be bool"
let _ = typeCheckStmt stmt1 symbTab
let _ = typeCheckStmt stmt2 symbTab
symbTab
| While (exp, stmt_) -> // while b S
match typeCheckBoolExp exp symbTab with
| Some TBool -> ()
| _ -> failwith "Type Error: condition must be bool"
let _ = typeCheckStmt stmt_ symbTab
symbTab
```
> 💡 **§7.5 analyzeStmt와 typeCheckStmt의 차이**: analyzeStmt는 "선언됐는가"(bool)만 추적하지만, typeCheckStmt는 "어떤 타입인가"(τ)를 추적한다. 반환 타입이 `State` → `SymbTab`으로 바뀌고, 각 Expression 검사에서 타입 일치 여부를 추가로 확인한다.
**전체 검사기 흐름 요약:**
```
AST 입력
│
▼
typeCheckStmt (symbTab = [])
├─ Decl: Symbol Table에 타입 정보 추가 → 이후 코드를 새 SymbTab으로 검사
├─ Assign: 변수 타입 조회 + 우변 타입 계산 → 불일치 시 Type Error
├─ Seq: 순서대로 검사, 이전 검사 결과 SymbTab을 다음에 전달
├─ If/While: 조건이 bool인지 확인 + 각 분기/바디 검사
└─ 모든 Var 참조 시 Symbol Table에서 타입 조회 → 없으면 Undeclared Error
│
▼
에러 없으면 → AST 통과 (IR Translator로)
에러 있으면 → Type Error 또는 Undeclared Error 발생
```
## 8.12 실전에서의 고민거리들
### 8.12.1 더 세밀한 타입 정의가 필요하다
TWhile은 `int`와 `bool` 두 가지만 있지만, 실제 언어들은 훨씬 다양하다.
**같은 종류의 크기가 다른 타입:**
```c
char x; // 8-bit
short y; // 16-bit
int z; // 32-bit
long long w; // 64-bit
(char) x + (short) y = ? // ← 결과 타입은?
```
C에서는 **정수 승격(Integer Promotion)** 규칙에 따라 두 피연산자 모두 최소 `int`로 올려서 연산한다. 이런 규칙도 타입 규칙으로 정의할 수 있다.
**복잡한 구조체 타입:**
```c
struct MyType {
int Field1;
char Field2;
};
struct MyType a;
struct MyType b;
a = b; // OK — 같은 타입
a.Field1 = 1; // OK — Field1은 int
a.Field1 = 'x'; // ? — char를 int에 대입 → 언어 설계에 따라 OK 또는 Error
```
struct 타입을 어떻게 Symbol Table에 기록하고, 필드 접근 연산(`a.Field1`)의 타입을 어떻게 추론할지 추가로 정의해야 한다.
### 8.12.2 Implicitly Typed 언어의 타입 검사
F# 같은 언어는 타입을 명시하지 않아도 컴파일러가 타입을 추론한다:
```fsharp
let add x y = // x와 y의 타입을 명시하지 않음
x + y // 사용 패턴으로부터 x: int, y: int, 반환: int 추론
```
이 경우 Symbol Table에 처음부터 타입 정보가 없으므로, **타입 추론(Type Inference)** 알고리즘이 필요하다.
- 대표적인 방법: **Hindley-Milner 타입 추론** (F#, Haskell, OCaml 등에서 사용)
- 핵심 아이디어: 타입을 변수로 두고, 사용 패턴에서 **제약 조건(Constraint)**을 모은 뒤, **Unification**으로 타입을 결정
> 💡 TWhile은 Explicitly Typed이므로 Symbol Table 구축이 단순하다. Implicitly Typed 언어에서는 타입 추론이 의미 분석의 핵심 문제가 된다.
---
**§8 요약:**
| 개념 | 핵심 내용 |
| ---------------- | ----------------------------------------- |
| **Type** | 값의 범위 + 연산 한정 |
| **Symbol Table** | 변수/함수의 타입·위치 등 정보를 Scope별로 관리하는 테이블 |
| **Γ ⊢ E : τ** | 타입 상태 Γ에서 E의 타입이 τ |
| **Γ[x ↦ τ]** | Γ에 x의 타입 τ를 추가 |
| **Γ(x) = τ** | Γ에서 x의 타입이 τ임을 확인 |
| **타입 규칙** | 각 식/문장의 타입이 올바른 조건을 Inference Rule로 정의 |
| **구현** | §7.5 analyzeStmt 패턴 그대로, bool 대신 타입 τ를 반환 |