4. Semantic Analysis

Semantic Analysis는 의미론적 분석으로 문장에서 의미를 파악해 프로그램의 의미를 분석하여 맞는지 확인한다.

그리고 결과적으로 abstract syntax tree를 intermediate representation(IR)로 변환한다.

Semantic Analysis에서는 구조는 맞지만 identifier가 1번만 정의 되었는지, 상속 관계가 잘 되었는지, type이 잘 정의 되었는지 등을 확인한다.

 

Symbol Table

식별자를 그들의 type과 location에 mapping시킨것이다.

symbol table 예시

위와 같이 화살표를 통해서 표기를 하는데 식별자는 해당 type으로 묶여있다는 것을 나타낸다.

 

▪ Imperative Style

1개의 global environment를 가지고 table에 entry를 넣고 scope가 끝나면 제거하여 원래대로 돌려놓는 것을 반복한다.

imperative style 예시

imperative style은 위처럼 생기기 때문에 식별자가 어떤 type을 가지고 있는지 빠르게 찾기 위해서 hash table을 사용해서 찾는다.

만약 같은 hash값을 가지면 같은 bucket을 사용하여 linked list로 연결되어 관리가 된다.

 

▪ Functional Style

새로운 scope가 들어오면 환경을 새로 만들어 해당 부분에 접근을 하고 끝나면 제거하여 끝나는 방식이다.

functional style의 예시

functional style에서는 새로 table을 만들어 연결하기 때문에 위와 같이 구성이 된다.

이때 새로 table을 만들기 위해서 전부 복사하는 것이 아니라 새로 들어오는 것만 추가하고 이전것에 연결하는 방식을 사용한다.

이러한 방식은 메모리가 추가로 드는 단점이 있지만 binary search tree를 사용해 더 빠르게 찾을 수 있다.

다만 새로운 것을 추가할 때 위의 노드들 까지 복사해야 될 수도 있어 추가 오버헤드가 발생할 수 있다.

 

Type System

구문에서의 typing규칙을 정하는 것으로 expression에 대해 type을 부여한다.

그리고 type checking에서는 type system아래에서 구문의 type을 결정할 수 있는지 본다.

 

Typing Rule

특정한 가정 아래서 어떤 결과가 true인지 판단하는 형태이다.

위의 이미지를 보면 e1이 int이고 e2가 int인 가정아래에서 e1 + e2가 int인지 보는 것으로 이는 참이 된다.

이때 만약 위와같이 가정이 없는 것은 axiom으로 무조건 참이 된다.

 

Type Environment

식별자의 type을 정할 때 감마 함수를 이용해서 환경에 어떤 변수가 어떤 type을 가지는지 확인할 수 있다.

예를들어 위와 같은 예시에서 e1의 type이 t1이고 x가 t1타입일 때 e2의 type이 t2인 가정 아래에서 x=e1에서 e2의 type은 t2가 된다는 것을 볼 수 있다.

Γㅏ(fn x: int -> x + 1)3:t 에 대한 type을 구하는 과정이다.

Subtyping

B가 A의 subtype이라면 A type으로 실행가능한 함수가 있으면 B type으로도 실행 가능해야 한다.

이는 B <: A 이렇게 표기한다.

예를들어 f:<int> -> int, g:<int,int> -> int이고 a:<1>, b:<2, 3>이 있으면 f(a), g(b), f(b)는 다 가능하지만 g(a)는 불가능하다.

따라서 여기서는 g가 f의 subtype이다.

 

▪ Reflectivity: 자기 자신은 자신의 subtype이 된다.

▪ Transitivity: a <: b이고 b <: c이면 a <: c가 된다.

▪ Depth: 각각의 요소들의 type이 subtype이 되면 튜플로 합친 전체도 subtype이 된다.

▪ Width: <a1, a2, ..., ak, ..., an> <: <a1, a2, ..., ak>가 된다.

▪ Join: if then else문처럼 조건에 따라 다른 type이 나올 수 있는 경우 전체의 type을 무엇으로 해야할 지 결정할 수 있어야 한다.

즉, 공통의 subtype을 찾아서 해당하는 것을 type으로 지정해야한다.

▪ Meet: 가장 큰 subtype을 구하는 것이다.

 

Static Typing vs Dynamic Typing

▪ Statically Typed Language : compile시간에 type checking이 끝나는 것으로 버그를 줄이려면 이것을 쓰면 된다.

▪ Dynamically Typed Language : 프로그램 실행중에 type을 결정하는 것으로 python과 같은 것이 존재한다.

▪ Untyped Language : assemble언어 같은 것으로 type checking을 따로 하지 않는 언어이다.