#컴파일러 #프로그래밍언어 #의미론 #semantics
![[14. Semantics - Post-lecture.pdf]]
`백틱` ⟦ ⟧
지금까지는 소스코드의 '형태'에 대해 이야기했으면, 이제부터는 '의미'에 대해서 다룸
# 현재 위치는 어디쯤?
## FRONT-END
- front-end: 입력 언어를 이해하는 과정
- tokenize: lexer
- 문법 구조를 만듦: parser
- 남은 작업은 semantic analyzer, IR translator이므로 '의미적'인 것에 대해 다룸
- middle-end부터는 이제 '의미적으로 문제 없는' 게 들어올 것.
## SEMANTIC ANALYZER
- AST가 올바른 의미를 표현하고 있는지 검사
- 타입 분석, 변수 선언 검사
- 이론적 기반: 프로그래밍 언어론
# 프로그래밍 언어의 "의미"는?
## 이 코드의 의미는 어떻게 정의할 수 있을까?
```
if (b == 0) a = b;
// b가 0이랑 같으면, a에 b를 대입한다
```
## 프로그래밍 언어의 구성: SYNTAX & SEMANTICS
- 구문 syntax: 프로그램의 문법적 구조 표현
- 이 코드가 어떻게 문법을 따르고 있는가?
- 의미 semantics: 프로그램의 실질적 행동 표현
- 어떻게 컴퓨터에 의해 실행되는가?
```mermaid
graph TB
subgraph 구현["구현 = 컴파일러"]
A(("구문<br/>= 오토마타"))
B(("의미<br/>= 프로그래밍<br/>언어론"))
end
style A fill:#0b4d3e,stroke:#0b4d3e,color:#ffffff
style B fill:#0b4d3e,stroke:#0b4d3e,color:#ffffff
style 구현 fill:#ffffff,stroke:#000000,color:#000000
```
## 예제: 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
S: Statement (값의 대입, 실행 흐름 변경 등 – Side effects)
a: Arithmetic Expression (산술 계산식 – No Side effects)
b: Boolean Expression (논리 계산식)
x: Variable (변수)
n: Numeral (숫자 값)
```
## 예제: Factorial Program
```
y = 1; while !(x=1) do (y=y*x; x=x-1)
;
/ \
/ \
/ \
/ \
:= while
/ \ / \
y 1 ! ;
| / \
= / \
/ \ := :=
x 1 / \ / \
y * x -
/ \ / \
y x x 1
```
## 상수의 의미
- `n` numeral의 의미: 숫자 그 자체
- 1의 의미: 숫자 1
- 앞의 1: 문자열 "1"
- 뒤의 1: 의미적으로, 개념적 1
- `true`/`false`의 의미: 참/거짓 그 자체
## 약속: 구문 vs. 의미
- 구문을 표현할 때는 특별한 표시 없이 문법 사용해 표현
- y = 1 혹은 y := 1
- 의미를 표현할 때는 ⟦ ⟧ 로 감싸서 표현
- ⟦1⟧, ⟦y=1⟧
## 변수의 의미
```
int x = 1;
// ...
x + 2
```
- 마지막 줄에서 변수 x의 의미는?
- 변수가 존재하는 환경에 따라 달라짐. x=1, x=2에 따라 3, 4가 될 수 있음
## 프로그램의 상태
- `정의` 그 순간에 정의된 **변수**들을 **값**과 함께 기록하고 있는 환경
- `Map<변수, 값>`
- 변수 $\to$ 값
- $\sigma = \text{Var} \to \text{Value}$
- 의미는 항상 상태와 함께함
- $⟦v⟧_\sigma$ 상태가 $\sigma$로 주어졌을 때, 변수 $v$의 의미
- $⟦x⟧_{\{x \mapsto 1\}}$
## 변수의 분류
```
// BOUND VARIABLE
{
int x = 1;
y = x + 1;
}
여기서 y
// FREE VARIABLE
int func(char *arr) {
arr[0] = y;
}
여기서 y
```
1. BOUND VARIABLE: 현재 주어진 코드 안에서 정의된 변수
1. BINDER: 변수를 정의해주는 코드
2. 변수의 이름을 바꿔도 코드의 의미가 바뀌지 않음
2. FREE VARIABLE: 코드와 함께 주어진 상태에 따라 의미가 달라지는 변수
1. 변수의 이름을 바꾸면 코드의 의미도 달라짐
## 변수의 의미
$
[\![ x ]\!]_{\{y \mapsto a\}} := \begin{cases} a & \text{if } x = y \\ x & \text{otherwise} \end{cases}
$
- 변수가 존재하는 환경에 따라 달라짐
- 예: $[\![ x ]\!]_{\sigma = \{x \mapsto 1\}} = [\![ 1 ]\!]_{\sigma}$
## 계산식 EXPRESSION
- `정의` Side-effect가 없는 식
- side-effect: 프로그램의 상태를 변화시키는 것
## 계산식의 의미
- 주어진 상태로부터 계산식의 값을 어떻게 얻어내는지 나타내는 것
- 산술: 숫자 값(=int 타입)의 계산으로 표현
- 논리: 참/거짓 값(=bool 타입)의 계산으로 표현
```
a ::= n | x | a + a | a * a | a - a
b ::= true | false | a = a | a <= a | ! b | b && b
```
## 산술 계산식의 의미
- 연산자 양 쪽의 의미를 먼저 계산한 후에 연산자를 취함
- $[\![ x - 1 ]\!]_{\sigma = \{x \mapsto 1\}} = [\![ x ]\!]_{\sigma} - [\![ 1 ]\!]_{\sigma} = [\![ 1 ]\!]_{\sigma} - [\![ 1 ]\!]_{\sigma} = [\![ 0 ]\!]_{\sigma}$
## 논리 계산식의 의미
- 피연산자 의미를 먼저 계산 후에 연산자를 취함
- $[\![ x \leq 1 ]\!]_{\sigma = \{x \mapsto 1\}} = [\![ x ]\!]_{\sigma} \leq [\![ 1 ]\!]_{\sigma} = [\![ 1 ]\!]_{\sigma} \leq [\![ 1 ]\!]_{\sigma} = [\![ true ]\!]_{\sigma}$
## 구문 STATEMENT
- `정의` side-effect를 유발할 수 있는 식
- 실제로 실행되는 코드의 단위로도 볼 수 있음
```
S ::= x := a | skip | S ; S | if b S S | while b S
```
## STATEMENT의 의미
- STATEMENT가 상태를 *어떻게* 변화시키는가를 나타내는 것
- $[\![ S ]\!]_{\sigma} := \sigma'$
- Cf) Expression에서는 상태 변화 X, 값의 계산
- $[\![ a_1 = a_2 ]\!]_{\sigma} := [\![ a_1 ]\!]_{\sigma} = [\![ a_2 ]\!]_{\sigma}$
- 즉, statement의 상태 변화 과정을 표현해야 함
## Statement의 의미를 나타내기 위한 표기법
$
\frac{\langle S_1, \sigma \rangle \to \sigma_1, \langle S_2, \sigma_1 \rangle \to \sigma_2, \dots, \langle S_n, \sigma_{n-1} \rangle \to \sigma'}{\langle S, \sigma \rangle \to \sigma'} \text{ if cond}
$
- 추론 규칙이라고 함
- 여러 개의 premise + 하나의 conclusion
- 조건이 필요할 수도 있음
- 가정이 없는 추론 규칙을 공리 axiom 이라고 함
- cond 조건이 만족될 때
## skip STATEMENT의 의미
$
\frac{}{\langle skip, \sigma \rangle \to \sigma}
$
- 아무런 상태 변화를 유발하지 않음
- 공리
## assign STATEMENT의 의미
$
\frac{}{\langle x := a, \sigma \rangle \to \sigma[x \mapsto [\![ a ]\!]_{\sigma}]}
$
- x := a statement는 상태에 변수 $x$가 $[\![ a ]\!]_{\sigma}$라는 값을 갖는다는 사실을 추가합니다.
- $\sigma[x \mapsto a]$: 기존 상태 $\sigma$에 $x$가 $a$라는 값을 갖는다는 것을 추가
### 만약 상태에 변수 $x$가 이미 존재한다면?'
```
int func(char *arr) {
int x = 3;
while (x > 1) {
int x = 2;
}
}
```
2번 줄: $\sigma = \{arr \mapsto ?, x \mapsto 3\}$
4번 줄: $\sigma = \{arr \mapsto ?, x \mapsto 2\}$
둘 중에 어떤 걸 봐야 하나?
덮어버림
## SHADOWING
- 기존 상태에 포함되어 있던 변수 $x$가 새롭게 정의되면서 기존 정의를 덮어버리는 것
- 4번 줄의 저걸로!
## SCOPE
- 코드 내에서, 변수의 정의가 영향을 미치는 곳
- 변수를 읽고, 수정할 수 있는 범위
- 밖으로 벗어나면, 가려졌던 기존의 정의가 다시 살아남
```c
int func(char *arr) {
┌─────────────────────────────────┐
│ int x = 3; │ ← outer x (scope A)
│ while (x > 1) { │
│ ┌─────────────────────────┐ │
│ │ int x = 2; │ │ ← inner x (scope B, shadows A)
│ └─────────────────────────┘ │
│ } │
└─────────────────────────────────┘
}
```
## Sequential Statement의 의미
- S ; S statement는 두 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'}
$
- 시그마가 시그마1로 바뀌고, 다음으로 시그마1이 시그마프라임으로 바뀌기 때문에...
- 시그마를 시그마 프라임으로 변화시킨다고 표현할 수 있음
## IF STATEMENT의 의미
- if b S S statement는 조건에 따라 다른 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
$
## WHILE STATEMENT의 의미
- while b S statement는 조건에 따라 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
$
## 인터프리터 구현
### WHILE 언어 정의
```f#
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
```
### WHILE 언어 인터프리터 설계
```f#
val interpArithExp : ArithExp -> State -> int
val interpBoolExp : BoolExp -> State -> bool
val interpStmt : Stmt -> State -> State
```
### STATE 타입 설계
- 튜플 리스트
- singly linked list -> Stack 구조
- Immutable list (Scope를 벗어날 때 유용)
```f#
type State = (var * int) list // 튜플 리스트
module State =
val empty : State
val update : State -> var -> int -> State
val lookup : State -> var -> int
```
### STATE 구현
```f#
module State =
let empty = []
let update state varName value =
(varName, value) :: state
let rec lookup state varName =
match state with
| [] -> failwith "No such variable!" // 정의 안 되어있음!
| (varName_, value) :: state_ ->
if varName = varName_ then value
else lookup state_ varName
```
### interpArithExp 완성 (산수)
```f#
let rec interpArithExp exp state =
match exp with
| Int n -> n // n은 숫자로 정의한다~
| Var varName -> State.lookup state varName // 변수의 이름은 상태에서 lookup해서 있으면 그 값으로 하고, 없으면 에러를 뱉자
| Plus (exp1, exp2) ->
let value1 = interpArithExp exp1 state
let value2 = interpArithExp exp2 state // 각각 interp해서
value1 + value2 // 더하자! 밑에도 반복
| 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
```
### interpBoolExp 완성 (논리)
```f#
let rec interpBoolExp exp state =
match exp with
| True -> true
| False -> false
| Eq (exp1, exp2) ->
let value1 = interpArithExp exp1 state
let value2 = interpArithExp exp2 state // interp 해서
value1 = value2 // 같은지 검사
| Le (exp1, exp2) ->
let value1 = interpArithExp exp1 state
let value2 = interpArithExp exp2 state
value1 <= value2
| Not exp ->
let value = interpBoolExp exp state
not value
| And (exp1, exp2) ->
let value1 = interpBoolExp exp1 state
let value2 = interpBoolExp exp2 state
value1 && value2
```
### interpStmt 완성 (statement)
```f#
let rec interpStmt stmt state =
match stmt with
| Assign (varName, exp) ->
let value = interpArithExp exp state // 값을 계산하고
let state = State.update state varName value // 이름과 값을 가지고 state 업데이트
state
| Skip -> state // 스킵은 암것도 안하니까 그대로 리턴
| Seq (stmt1, stmt2) -> // sequence, 하나하나
let state1 = interpState stmt1 state // 입력s를 s1로,
let state2 = interpState stmt2 state1 // s1을 s2로
state2 // s2를 리턴
| If (exp, stmt1, stmt2) ->
let value = interpboolExp exp state // 값 정의
let state = // 상태 정의
if value then interpState stmt1 state
else interpState stmt2 state
state
| While (exp, stmt_) ->
let value = interpArithExp exp state
if value then
let state = interpState stmt_ state
interpStmt stmt state
else state
```
## 예제: Factorial Diagram
```
y = 1; while !(x = 1) do (y = y * x; x = x - 1)
;
/ \
/ \
/ \
/ \
:= while
/ \ / \
y 1 ! ;
| / \
= / \
/ \ := :=
x 1 / \ / \
y * x -
/ \ / \
y x x 1
```
- x|-> 3
- y=1 -> y|-> 1 추가
- x=1 -> false -> not이 붙었읜까 true로 바뀌어서 while문 실행
- 첫 번째 실행: y에 y곱하기x만남 그래서 상태 업데이트
- x|->3, y|->3
- 옆으로 넘어와서 x-1 -> x|->2
- 두 번쨰 실행: 여전히 x=1아니니까
- x|->1, y|->6
- while문 종료
- 실행 끝. 결국 이거 의미는 x=3의미를 받아서 x=1, y=6이라는 걸 포함하고 있는 상태를 리턴함.
# 의미에 대해서 자세하게 다루는 이유?
## 의미 분석기는 인터프리터 구현 기반
- 인터프리터 구현 기반해서 의미 분석에 대해 다룸
- 기반을 먼저 이해하고 나면 분석의 핵심에 집중 가능
- 그럼 각 분석마다 무엇이 달라짐?
## "의미"는 그 목적에 따라 다르게 정의 가능
- 앞 설명에서의 '**의미**' = '**작동**' 방식에 대해 다룸
- 하지만, 프로그램의 '**성질**'을 살펴보고 싶을 수도 있음
- 예: 값이 0인지 아닌지에만 관심이 있는 경우
### 예제: 값이 0인지에 관심을 둔 "의미"
$
\begin{aligned}
&[\![ a ]\!]_{\sigma} \in \{IsZero, IsNonZero, MaybeZero\} \\
\\
&[\![ 0 ]\!]_{\sigma} = IsZero, \quad [\![ 1 ]\!]_{\sigma} = IsNonZero \\
\\
&[\![ x ]\!]_{\{x \mapsto IsNonZero\}} = IsNonZero \\
\\
&[\![ x + y ]\!]_{\{x \mapsto IsNonZero, y \mapsto IsNonZero\}} = IsNonZero + IsNonZero = ?
\end{aligned}
$
```
int bug(int n) {
if (n != 0) {
printf("Normal behavior!\n");
} else {
printf("The result is %d\n", 100 / n);
}
}
```
divide-by-zero 버그!
buffer overflow같은 버그를 찾을 수도 있음 .
## 의미 분석의 목적 - 에러 검출
- lexer, parser는 입력 프로그램을 변환하는 데 집중
- semantic analyzer는 입력 프로그램이 '올바른지' 확인하는 데 초점
- 목적에 맞게 의미 정리, 의미 검사 인터프리터 구현
- 잘못된 프로그램이라면 에러를, 올바른 프로그램이라면 AST/IR 생성
- "저는 모든 학생들에게 A+을 부여하겠습니다"
- 문법적으로는 OK, 의미적으로는 잘못됨
- 두 가지 종류의 의미 에러를 찾기
- 선언되지 않은 것 체크 undeclared identifier check
- 타입 체크 type check
# Undelcared Indentifier Check
```c
// test.c
int main() {
printf("I'm %d years old!\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);
| ^
test.c:4:33: note: each undeclared identifier is reported only once for each function it appears in
```
수정하자
```c
// test.c
#include <stdio.h>
int n = 260;
int main() {
printf("My foot is %d mm long!\n", n);
return 0;
}
```
컴파일이 됨
# 이 에러를 어떻게 프로그램의 의미 분석으로 설명할 수 있을까?
## 관찰 1: BOUND VARIABLE & FREE VARIABLE
- 어떤 변수가 bound인지, free인지는 scope에 따라 달라짐
## undeclared identifier 분석의 목표
- 코드 내에 등장하는 모든 변수에 대해, 프로그램 전체 scope에서 bound variable인지 확인하는 것
- 이 변수가 어디에서 선언된 변수에 의해 bound된 것인지 확인
- 만약 프로그램 전체 scope을 다 확인해도 free? == 의미적인 문제
-> scope의 정의가 필요!
## 정적 SCOPE vs. 동적 SCOPE
### 정적 SCOPE: 코드 구조 상으로 SCOPE가 정의
```c
int n = 1; // ← 전역 n (정적 스코프에서 참조됨)
// ▲
void f() { // │
int n = 3; // │
g(3); // │
// ... // │
} // │
// │
void g(int k) {// │
int y = n; // ────┘ (여기서 n은 전역 n = 1을 참조)
// ...
}
```
- 대부분의 프로그래밍 언어
### 동적 SCOPE: 실행 흐름에 따라 SCOPE가 정의
```c
int n = 1;
void f() {
int n = 3; // ← 호출자 f의 지역 n (동적 스코프에서 참조됨)
g(3); // ▲
// ... // │
} // │
// │
void g(int k) { // │
int y = n; // ────┘ (여기서 n은 호출자 f의 n = 3을 참조)
// ...
}
```
- Lisp, Bash, Perl
## C--의 정적 scope
- scope의 범위
- 전역 scope (=global variable)
- 함수 scope
- 블록 scope (=함수 body 안에서 {}로 감싸진 코드 영역)
- 각 scope 안에서 같은 이름의 변수는 한 번만 선언 Declare 되어야 함
- 값은 여러 번 할당 assign 가능
- 변수의 scope 범위부터 큰 범위로 확장하면서 선언 확인
- 같은 범위 안에서는 변수의 등장 이전에 존재하는 선언 확인
# (Un-)Declared Identifier를 어떻게 분석?
## UNDECLARED IDENTIFIER 분석에서의 의미
우리 관심사 = 변수가 잘 선언되어 있나요?
- 변수의 의미
- $[\![ x ]\!]_{\sigma} = \begin{cases} true & \text{if } x \in \sigma \\ false & \text{otherwise} \end{cases}$
- 나머지 식의 의미
- $[\![ n ]\!]_{\sigma} = true$
- $[\![ a_1 \oplus a_2 ]\!]_{\sigma} = [\![ a_1 ]\!]_{\sigma} \land [\![ a_2 ]\!]_{\sigma}$
- $\oplus \in \{+, *, -\}$
## UNDECLARED IDENTIFIER 분석기 구현
- stae type과 analyzer*(=interp*) 구현이 필요
- 실제 언어에서는 while언어보다 복잡해서 고려할 요소가 많음... but 큰 맥락에서는 다르지 않음