제5장 기초 의미론 (Basic Semantics)

Presentation on theme: "제5장 기초 의미론 (Basic Semantics)"— Presentation transcript:

1 제5장 기초 의미론 (Basic Semantics)
5.1 간단한 의미론 5.2 이름 및 바인딩 5.3 선언, 블록 및 유효범위 5.4 심볼 테이블 5.5 이름 해결 및 중복 정의 5.6 메모리 할당

2 5.1 간단한 의미론

3 의미론의 필요성 프로그램 의미의 정확한 이해 소프트웨어의 정확한 명세 소프트웨어 시스템에 대한 검증 혹은 추론
컴파일러 혹은 해석기 작성의 기초

4 의미론의 종류 Operational Semantics Denotational Semantics
프로그램의 동작 과정을 정의 Denotational Semantics 프로그램의 의미를 함수 형태로 정의 Axiomatic Semantics 프로그램의 시작 상태와 종료 상태를 논리적 선언(assertion) 형태로 정의

5 동작 의미론(Operational Semantics)
기본 아이디어 프로그램의 의미를 (변수 값들의) 상태 전이 과정으로 설명한다. 예제 y := 1; while (x != 1) do (y := x*y; x := x-1) y에 1 배정 x 값이 1이 아닌지 검사 참이면 종료 거짓이면 y 값을 x 값과 현재 y 값의 곱으로 변경 x 값 1 감소 2 번부터 반복

6 While 언어 정수 변수 식 문장 S → x := e | skip | S1 ; S2 | if e then S1 else S2
n  Int 변수 x  Var 식 e  Exp 문장 S → x := e | skip | S1 ; S2 | if e then S1 else S2 | while b do S

7 상태(State) 상태(A state) 모든 상태들의 집합 상태에서 변수 값 검색 상태 갱신: s’ = s[y -> v]
변수들의 현재 값 s  Var  Int 모든 상태들의 집합 State = Var  Int 상태에서 변수 값 검색 s(x) 상태 갱신: s’ = s[y -> v] s’ (x) = s(x) if x != y v if x = y

8 상태 전이 기본 아이디어 상태 전이(State transition) 계산 과정을 (변수 값들의) 상태 전이 과정으로 기술한다.
(S,s)  s’ where S is a statement s is the initial state s’ is the final state

9 상태 전이 시스템(State Transition System)
(, T, ) where Configuration  = {(S,s) | S  While, s  State}  State State T Transition relation   {(S,s) | S  While, s  State}  State

10 전이 관계(Transition Relation)
Assignment (x := a, s)  s[x -> [[a]]s] skip (skip, s)  s sequence (S1 , s)  s’, (S2 , s’)  s” (S1; S2, s)  s” if-then-else (S1 , s)  s’ (if e then S1 else S2, s)  s’ (S2 , s)  s’ if [[e]]s = true if [[e]]s = false

11 전이 관계 while (S, s)  s’, (while e do S, s’)  s”
if [[e]]s = true if [[e]]s = false

12 Denotational Semantics
y := 1; while (x != 1) do (y := x*y; x := x-1) The program computes a function from states to states: The final state will be equal to the initial state except that the value of x will be 1 and the value of y will be equal to the factorial of the value of x in the initail state.

13 Axiomatic Semantics 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

14 Pre- and post conditions
예제 { x=n } y:=1; { x=n and y=1} while (x !=1) do (y:=x *y; x := x-1) { y=n! }

15 5.2 이름 및 바인딩

16 기본 개념 프로그램의 의미를 정의하는데 가장 기본적인 개념은 무엇일까? 이름(name) 혹은 식별자(identifier)
변수, 프로시져, 상수, 타입 위치(Location) 변수를 저장할 곳의 위치 주소(address) 값 정수 값 등의 저장 가능 값

17 속성(Attributes) 이름의 의미는 어떻게 결정할까? 예 const int n = 5; int x;
double f(int n) { … } 다음 이름들의 속성은 무엇일까? n x f

18 속성의 종류 속성의 종류 선언의 역할은 무엇인가 ? 값, 타입, 크기, 위치, 등 이름의 의미는 속성에 의해서 결정된다.
이름에 속성을 연관시키는 과정

19 바인딩(Binding) 바인딩은 무엇인가? 바인딩은 왜 필요할까? 바인딩 시간
이름이 의미하는 대상 혹은 이름의 속성을 결정하는 것 바인딩은 왜 필요할까? 프로그램에 등장하는 이름들이 다양하다. 변수, 상수, 클래스, 메쏘드, 인터페이스, 매개변수 등. 하나의 이름이 여러 용도로 사용될 수도 있다. 따라서 이름이 나타나면 그 대상 및 속성이 결정되어야 한다. 바인딩 시간 정적 바인딩 compile time 동적 바인딩 execution time

20 정적 바인딩(Static Binding)
컴파일 시간에 이루어지는 바인딩 정적 속성(Static attribute) 정적으로 바인딩 되는 속성 예제 const int n=2; int x; 정적으로 결정되는 것은 무엇인가?

21 동적 바인딩(Dynamic Binding)
실행 시간에 이루어진 바인딩. 동적 속성 동적으로 바인딩 되는 속성 Java 예제 C x; if (…) x = new C( ); /* memory allocation */ else x = new C1( ); /* C1 is a subclass of C */ x.m( … ); /* method dispatch */ 동적으로 바인딩되는 것은 무엇인가?

22 바인딩 시간 세분화 언어 정의 시간(Language definition time)
boolean, true, false, char, integer,maxint 언어 구현 시간(Language implementation time) integer, maxint 컴파일 시간(Compile- time) 링크/로드 시간(Link/load time) external definition/the location of a global variable 실행 시간(Runtime)

23 심볼 테이블 바인딩을 유지하기 위한 자료 구조 이름 속성 왜 바인딩을 유지하는가? 누가 유지하는가
이름을 해당 속성에 대응시킨다. 이름 속성 n 상수 2 x int 변수 f 함수 : int  double 왜 바인딩을 유지하는가? 누가 유지하는가 컴파일러 인터프리터 실행시간 시스템

24 5.3 선언, 블록 및 유효 범위 (Declarations, Blocks, and Scope)

25 선언(Declarations) 선언은 무엇인가? 무엇을 선언하는가? 어디에 선언하는가? 어떻게 선언하는가?
바인딩 정보를 제공한다. 무엇을 선언하는가? 상수, 변수, 함수, 클래스 어디에 선언하는가? 블록 내 혹은 밖 구조체(struct) 클래스 어떻게 선언하는가? 명시적 선언: Pascal,C, C++, Java, … 묵시적 선언: Lisp, partly in FORTRAN

26 블록(Blocks) Pascal C, C++, Java Ada ML procedure or function { . . . }
{ } Ada declare . . . begin …. End ML let … in … end

27 블록 구조 언어 (Block Structured Languages)
블록의 중첩을 허용하는 언어 Algol, Pascal, Modula, Ada, C, ... A B D C

28 C의 블록 void p (void) { double r, z; /* p의 블록 */ …
{ int x,y; /* 또 하나의 중첩 블록 */ x = 2; y = 0; x += 1; } int x; double y; main() { int i, j; /* main 블록 내 */

29 Ada 블록 declare x:integer; y: boolean; begin x := 2; y := true;
x := x+1; … end

30 Pascal의 블록 program ex; (* main 프로그램 *) var x: integer; (* 전역 선언 *)
procedure p; (* 전역 선언 *) var y: boolean; (* p 내의 선언 *) begin if x = 2 then begin … end; end; begin (* main *) (* 선언할 수 없음 *) … end. (* 프로그램 *)

31 구조체 내의 선언 struct A { int x; /* A 내의 지역 선언*/ double y; struct
char y; } z; }

32 클래스 내의 선언 public class IntWithGcd
{ private int value; /* value 필트 지역 선언 */ public int intValue() /* intValue 메쏘드 지역 선언 */ { return value; } public int gcd(int v) /* gcd 메쏘드 지역 선언 */ { …

33 선언의 영역(유효범위) 선언된 식별자(이름)의 유효범위(Scope) 유효범위 규칙
그 선언된 이름이 유효한(사용 가능한) 프로그램의 범위 혹은 영역 유효범위 규칙 정적 유효범위(Static scope or Lexical scope) 선언된 블록 내에서 유효함 대부분 언어에서 표준 규칙으로 사용됨 동적 유효범위(Dynamic scope) 실행 순서에 따라 유효범위가 결정된다. 선언은 선언된 블록의 실행이 끝날 때까지 유효함 Old Lisp와 SNOBOL에서 사용됨

34 예: C 언어의 유효범위 규칙 핵심 아이디어 지역 변수의 유효 범위 전역 변수의 유효범위
사용 전 선언(Declaration before use) 선언의 유효범위는 선언된 지점부터 선언된 블록 끝까지 지역 변수의 유효 범위 선언된 지점부터 함수 끝까지 전역 변수의 유효범위 선언된 지점부터 파일 끝까지

35 예제 void p( ) p { char y; y … } int x; x void q( ) q { double z; z
main() main { int w[10]; w

36 예: Ada 언어의 유효범위 규칙 핵심 아이디어 예제 선언의 유효범위는 선언된 블록 내 B1: declare
x: integer; y: boolean; begin x := 2; y := false; B2: declare a, b: integer; if y then a := x; else b := x; end if end B2; … end B1;

37 중첩 블록에서 선언 최중첩 우선 규칙(Most closely nested rule) 예
한 식별자가 여러 번 선언된 경우 최중첩된 선언을 우선한다. 예 int x; void p( ) { char x; x = ‘a’; /* */ … } main() { x = 2; /* */

38 동적 유효범위 핵심 아이디어 프로그램을 실행하면서 선언이 나타나면 처리되고 선언된 블록(함수)의 실행이 끝날 때까지 그 선언은 유효하다. 실행 경로에 따라 유효범위가 달라질 수 있다. 예제 int g( ) { int a = 4; f(3); } int f(x) { a = a+1; return(a) }

39 5.4 심볼 테이블

40 시작 질문 바인딩 정보는 무엇 하는데 사용되는가? 컴파일러는 왜 바인딩 정보를 저장해야 하는가?
바인딩 정보를 어디에 저장해야 하는가? 바이딩 정보를 어떻게 저장해야 하는가 ?

41 심볼 테이블은 왜 필요한가? 현재 유효한 바인딩을 유지/관리하기 위한 자료 구조 환경(environment)이라고도 함

42 심볼 테이블 관리 다음 블록을 살펴보자 아이디어 { int x = 0 ; x = x+1; printf(x); }
블록의 시작에서 선언의 바인딩을 유지한다. 문장들을 컴파일 한다. 블록의 끝에서 선언은 더 이상 유효하지 않으므로 바인딩을 유지할 필요가 없다.

43 심볼 테이블 관리 다음 중첩 블록을 살펴보자 void p (void) { double r, z; /* p의 블록 */
int x; … { int x,y; /* 또 하나의 중첩 블록 */ x = 2; y = 0; x += 1; }

44 블록 구조를 위한 심볼 테이블 선언은 스택 형태로 처리한다. 블록 시작 블록의 끝 블록 내의 선언을 처리한다.
해당 바인딩을 심볼 테이블에 추가한다. 블록의 끝 블록 내의 선언의 바인딩을 제거한다. 더 이상 필요 없다.

45 심볼 테이블 구현 Structure is a stack. Operations:
S_table S_empty(void) | Make a new S_table S_enter(S_table t, S_symbol sym, void *value) Push sym and its info. on the symbol table t. S_look(S_table t, S_symbol sym) Search the symbol table from the top, looking for sym. Return first sym found; NULL if none. S_remove(S_table t) | Pop the stack Searching the stack from the top guarantees the most recently added (i.e., most closely nested) definition is found. Pushing hides old definitions; popping exposes old definitions.

46 5.5 이름 해결 및 중복정의

47 이름 해결(Name Resolution)
하나의 이름이 여러 다른 것을 나타낼 수 있는가? 이 경우 어떻게 해결할 것인가? 중복정의(Overloading) 함수 중복정의 연산자 중복정의 이름 중복정의

48 함수(메쏘드) 중복정의 함수 중복 정의 함수 호출 { return x > y ? x : y; }
int max(int x, int y) // max #1 { return x > y ? x : y; } double max(double x, double y) // max #2 int max(int x, int y, int z) // max #3 { return x > y ? (x > z ? x : z) : (y > z ? y : z); } 함수 호출 max(2,3); max(2.1, 3.0); max(2.1,3); max(2,4,3);

49 연산자 중복 정의 연산자 중복정의 예 컴파일러에서 구현 하나의 연산자가 여러 다른 연산들을 나타내도록 중복해서 정의된 것.
s1 + s2 S1 + S2 정수 덧셈 실수 덧셈 스트링 접합 합집합 컴파일러에서 구현 피연산자의 타입을 이용해서 해당 연산자를 결정 ?

50 연산자 중복정의 예 #include <iostream> using namespace std;
typedef struct { int i; double d;} IntDouble; bool operator < (IntDouble x, IntDouble y) { return x.i < y.i && x.d < y.d; } IntDouble operator + (IntDouble x, IntDouble y) { IntDouble z; z.i = x.i + y.i; z.d = x.d = y.d; return z; } int main() { IntDouble x = {1,2.1}, y = {5, 3.4}; if (x <y) x = x + y; else y = x + y; cout << x.i << “ “ << x.d << endl; return 0;

51 이름 중복정의 하나의 이름이 여러 가지 다른 것들을 나타내는 경우 Java의 예 class A { static A A(A A)
for(; ;) { if (A.A(A) = A) break A; } return A; }

52 5.6 메모리 할당

53 메모리 할당 메모리 할당은 무엇인가 ? 메모리 할당은 언제 하는가 ? Names → Locations
(컴파일 시간) 정적 할당(static allocation) (실행 시간) 동적 할당(dynamic allocation) 두 가지 혼합

54 메모리 할당 예 FORTRAN LISP Pascal, C, Modula-2, Java
all locations are bound statically LISP all locations are bound dynamically Pascal, C, Modula-2, Java some allocation statically, others dynamically

55 메모리 할당 전역 변수(global variables) 지역 변수(local variables)
static allocation at compile-time 지역 변수(local variables) dynamic allocation on runtime stack when execution reaches the block 동적 메모리 할당(dynamic memory allocation) malloc() in C, new() in Pascal, Java dynamic allocation on heap when executing the function

56 메모리 배치 static(global) area runtime stack (unallocated) heap