제3장 시맨틱스(Semantics)
Reading Chap 13
3.1 Operational Semantics
시맨틱스의 필요성
프로그램 의미의 정확한 이해
소프트웨어의 정확한 명세
소프트웨어 시스템에 대한 검증 혹은 추론
컴파일러 혹은 해석기 작성의 기초
의미론의 종류
Operational Semantics
프로그램의 동작 과정을 정의
Denotational Semantics
프로그램의 의미를 함수 형태로 정의
Axiomatic Semantics
프로그램의 시작 상태와 종료 상태를 논리적 선언(assertion) 형태로 정의
동작 시맨틱스
(Operational Semantics) 기본 아이디어
프로그램의 의미(실행)를 상태 전이 과정으로 설명한다.
각 문장 S마다 상태 전이 규칙 정의
예제 read x;
y = 1;
while (x != 1) do
(y = y*x; x = x-1)
1. x 값을 읽는다.
2. y에 1 배정
3. x 값이 1이 아닌지 검사
4. 거짓이면 종료
5. 참이면 y 값을 x 값과 현재 y 값의 곱으로 변경
6. x 값 1 감소 3 번부터 반복
언어 S
정수
n ∈ Int
변수
x ∈ Var
식
E ∈ Exp
Stmt S Æ x = E
| S; S
| if E then S
| if E then S else S
| while E do S
| read x
| print E
Expr E Æ n | x | true | false
| E + E | E – E | E * E | E / E
기초 지식
합집합
A + B = { a | a ∈ A ∨ a ∈ B}
곱집합
A x B = {(a,b)| a ∈A ∧ b∈B}
함수집합
A → B = {f | f : A → B} = {f | f ∈A → B}
함수 f ∈A → B
{a1↦b1, a2↦b2, …, an↦bn}
함수 수정 f[a ↦b]
f[a ↦ b](x) = { b f(x) otherwiseif x = a
변수 및 상태
[23 + 5] vs [x + y]
[x + y]의 의미는 ?
변수 x, y의 현재 값에 따라 다르다.
변수들의 현재 값을 무엇이라고 할까요 ?
상태(State)
상태(State)
상태(A state)
변수들의 현재 값
하나의 함수로 생각할 수 있다.
s ∈ Var → Int
모든 상태들의 집합
State = Var → Int
상태 s에서 변수 값
s(x)
상태 갱신: s’ = s[y ↦ v]
s’ (x) = { s(x) v if x != yif x = y
수식의 의미
수식 E의 의미
상태 s에서 수식 E의 값
[E]s
s = {x ↦1, y ↦ 3}
[x+y]s = 4
상태 s에서 수식 E의 의미
[true]s = T [false]s = F
[n]s = n
[x]s = s(x)
[E1 + E2]s = [E1]s + [E2]s
[E1 == E2]s = T if [E1]s == [E2]s
문장의 의미
문장 S의 의미
문장 S가 상태 s를 s’으로 변경시킨다.
상태 전이(state transition)라고 한다.
(s, S) → s’
상태 전이(State transition)
(s, S) → s’ where
s is the initial state
S is a statement
s’ is the final state
동작 시맨틱스
각 문장 S마다 상태 전이 규칙 정의
프로그램의 의미를 상태 전이 과정으로 설명한다. S
s
s’
추론 규칙
조상 추론 규칙
X parent Y X ancestor Y Y parent Z X ancestor Y X ancestor Z
a parent b b parent c
전이 규칙
(Transition Relation)
assignment (s, x = E) → s[x ↦ [E]s]
sequence (s, S1) → s’, (s’, S2) → s”
(s, S1; S2) → s”
S1 s
S2 s’
s”
전이 규칙
(Transition Relation)
if-then-else (s, S1) → s’
(s, if E then S1 else S2) → s’
(s, S2) → s’
(s, if E then S1 else S2) → s’
if [E]s = T
if [E]s = F
S1 s’
S2 s
s’
E T
F
예1
x = 1;
y = 2;
if x > y then max =x;
else max =y;
s0 = { }
(s0, x = 1) → s1 s1 = {x ↦ 1}
(s1, y = 2) → s2 s2 = {x ↦ 1, y ↦ 2}
(s2, if x >y …) → s3 [x>y] s2= F
(s2, max=y) → s3 s3 = {x ↦ 1, y ↦ 2, max ↦ 2}
전이 규칙
while
(s, S) → s’, (s’, while E do S) → s”
(s, while E do S) → s”
(s, while E do S) → s
if [E]s = T
if [E]s = F
S S . . . S
s s’ s”
전이 규칙
read
READ n
(s, read x) → s[x ↦ n]
PRINT [E]s (s, print E) → s
예2
read x;
y = 1;
while (x != 1) do
(y = y*x; x = x-1)
s0 = { }
(s0, read x) → s1 s1 = {x ↦ 3}
(s1, y = 1) → s2 s2 = {x ↦ 3, y ↦ 1}
(s2, while …) → s’ [x != 1]s2= T
(s2, y =x*y; x = x-1) → s3 s3 = {x ↦ 2, y ↦ 3}
(s3, while …) → s’ [x != 1]s3= T
(s3, y =x*y; x = x-1) → s4 s4 = {x ↦ 1, y ↦ 6}
(s4, while …) → s’ [x !=1]s4 = F
지금까지 한 것/앞으로 할 것!
Topic Logic Implementation ---
Syntax Grammar Parser
Semantics Semantics rules Interpreter
Type Typing rules Type checker
3.2 Other Semantics
Axiomatic Semantics
read x;
y = 1;
while (x != 1) do (y = x*y; x = x-1)
If x = n holds before the program is executed then y = n! will hold when the execution terminates.
Properties of programs are specified as assertions { P } S { Q } where
S is a statement
P is the precondition and
Q is the postcondition
Pre- and post conditions
예제
read x;
{ x=n } y =1;
{ x=n and y=1}
while (x !=1) do
(y =x *y; x = x-1) { x=1 and y=n! }
Denotational Semantics
Describe meaning of programs by mathematical
Function from states to states for each statement
Operational semantics
(s, S) Æ s’ for each statement S
Denotational semantics
s’ = f(S,s) for each statement S
Denotational Semantics
read x;
y = 1;
while (x != 1) do
(y = y*x; x = x-1)
The program’s computation is
a function from states to states:
The final state will be equal to the initial state except that
the value of x = 1 and
the value of y = the factorial of the value of x in the initial state.
3.3 Interpreter for Lang. S
언어 S의 인터프리터
언어 S의 인터프리터 구현
동작 시맨틱스(Operational Semantics)에 따라 구현
Recursive Descent Parsing 방식을 확장해서 구현
구성 요소
어휘 분석(lexical analyzer)
변수들의 상태(state)
각 식, 문장에 대한 해석(실행) 함수
언어 S in EBNF
Stmt S Æ x = E
| (S {; S})
| if E then S else S
| while E do S
| read x
| print E
Expr E Æ true | false
| T {+T | -T}
| T == T | T != T | T < T | T > T | !E Term T Æ F {*F | /F}
Factor F Æ n | x | (E) Prgm P Æ S
언어 S 인터프리터
기본원리
Recursive Descent Parsing 스타일로 진행하면서
한 문장씩 읽어서 해석한다.
어휘분석
HW#2 확장해서 구현
getToken( ) 입력 프로그램을 토큰들로 분리해서 리턴
변수들의 상태(state)
Symbol table에 변수 상태 저장
각 식, 문장에 대한 해석(실행) 함수
각 식, 문장마다 하나의 해석(실행) 함수 작성
while 문 처리
자료 구조
M[]
입력 프로그램 저장을 위한 배열 M[]
pc M[]의 인덱스
symtable[]
변수 이름과 그 값을 저장하기 위한 심볼 테이블
스택 형태로 구현
어휘 분석
getToken()
Lexical Analyzer로 M[]에 저장된 입력 프로그램을 읽어서 토큰을 반환한다.
키워드, 수, 변수 이름, 기타 문자 처리하도록 확장
토큰의 종류
keyword: if return IF;
…
keyword: print return PRINT
number return NUM;
tokenval = val of the number
name return ID;
tokenval = i such that
symtable[i] contains the name
other char c return c;
심볼 테이블
심볼 테이블
식별자(변수 이름)을 저장하기 위한 자료구조
변수 이름, 토큰 번호, 값 저장
코드
struct entry { char *lexptr;
int token;
int val;
}struct entry symtable[ ] int lookup(char[] s)
return position of entry for s int push(char[] s, int tok)
심볼 테이블
token val lexptr ID
ID ID
x = 1;
y = 2;
if x > y then max =x;
else max =y;
lastchar lastentry
1 2 2 symtable[]
…
수식 해석
수식 E
변수를 포함한 수식 값을 계산하도록 HW#2 확장
변수 값은 symtable[]에 저장되어 있음
실행 과정
1. E을 읽으면서 값을 계산한다.
2. 변수 이름 x를 만나면 symtable[]에서 해당 위치를 lookup()해서 찾고 저장되어 있는 값을 사용한다.
문장 해석기 구조
void stmt( )
{ int loc, result;
switch(token)
{ case ID: loc = tokenval;
match(ID);
if (token == ‘=‘) { match(‘=‘);
result = expr( );
symtable[loc].val = result;
}break;
case ‘(‘:
case IF:
case WHILE:
case READ:
대입문 해석
대입문 x = E
E 값을 symtable[] 내의 변수 x에 저장
실행 과정
1. 변수이름 x를 읽으면 symtable[] 내의 해당 위치를 lookup()해서 찾는다.
2. E을 읽으면서 값을 계산한다.
3. 계산된 E 값을 symtable[i].val에 저장한다.
조건문 해석
조건문 if E then S1 else S2
E 값에 따라 S1 혹은 S2 실행
실행 과정
1. E을 읽으면서 값을 계산한다.
2. E 값이 true 이면 S1를 읽고 실행한다.
3. E 값이 false 이면 S1를 건너 뛰고 S2를 읽어서 실행한다.
반복문 해석
반복문
while E do S E와 S를 반복적으로 읽으면서 해석
Stack W[]이용해서 구현
실행 과정
1. while 문을 처음 만나면 시작 위치, 끝 위치를 W[] 스택에 push() (위치는 M[]의 인덱스 i)
2. E을 읽으면서 값을 계산한다.
3. E 값이 true 이면 S를 읽고 실행한다.
스택 W[]에 저장된 시작위치로 돌아가서 2부터 반복
4. E 값이 false 이면 스택을 pop()하고 스택에 저장된 끝 위치로 가서 진행한 다.
HW #3
언어 S에 대한 인터프리터 구현