[Compiler Design] Semantic Analysis

 

 

 

컴파일러의 궁극적인 목표는 기계어나 IR을 만드는 것.

어쩌다 보니 IR에 대해 먼저 다뤘는데.. 최종 결과물이 어떻게 구성되는지 알면 Semantic Analysis를 왜 해야 하는지 알 수 있다.

 

IR의 입장에서 x + y 를 번역할 때, 이게 정수 덧셈인지 실수 덧셈인지 알아야 코드를 작성할 수 있음.

그러니 IR 전에 Semantic Analysis를 통해 타입을 설정해 줘야 한다.

 

 

 

---

 

 

 

 

Semantic Analysis는 Syntax는 통과했지만, 실행하면 터질 수 있는 논리적 오류를 IR을 만들기 전에 미리 잡아내는 단계.

 

Lexical Analysis와 Syntax Analysis로 코드를 토큰으로 쪼개고, 문법 구조를 파악해 AST를 생성했다.

이제 만들어진 AST를 사용해 Symbol Table을 만들고, Type을 검사해보자.

 

 

Scope - 변수가 선언되기 전에 사용됐는지? 같은 이름으로 두 번 정의됐는지?

 

변수의 Scope는 프언개에서 모두 다뤘음..

 

컴파일러는 변수의 Scope를 검사하기 위해 Symbol Table을 사용한다.

선언 할 때 정보를 수집 후 테이블에 삽입하고, 사용 할 때 테이블을 참조해 제대로 사용됐는지 확인.

 

각각의 Lexical Scope마다 Symbol Table이 생성되고, 자신의 블록에 없는 변수는 상위 블록에서 찾아서 사용할 수 있다.

블록이 열릴 때 마다 새로운 Symbol Table을 만들고, 이를 상위 테이블과 연결해 Hierarchy를 구성함.

 

Symbol Table이 개념적으로는 트리 구조로 구성되는데, 실제 컴파일러를 작성할 때 모든 노드를 포인터로 연결한 트리를 만드는건 좀 많이 힘들어진다. 좀 더 효율적인 방법을 사용한다.

 

핵심 연산

 

Insertion - int a; 처럼 변수가 선언될 때 테이블에 등록.

Lookup - a = 1; 처럼 변수가 사용될 때 정보를 확인.

 

 

 

 

 

Scope 하나에 대한 테이블은 빠른 검색을 위해 Local Table은 Hash Table로 만든다.

Hash 를 사용하니 Collision이 발생할 수 있음. Chaining 으로 연결하는 일반적인 해시 테이블임.

 

변수명은 문자열인데, 이걸 테이블마다 저장하면 메모리 낭비가 심하다.

변수명을 따로 모아둔 String Pool을 만들고, 테이블에는 그 위치를 가리키는 포인터만 저장한다.

 

함수 실행이 끝나면 Local Table은 필요 없음. 그때그때 만들고 버리는 방식을 사용한다.

 

 

프로그램의 실행 흐름을 생각해보자. Last-In First-Out의 스택 구조가 떠오른다.

함수가 호출되면 그 안에 변수들이 생겼다가 가장 최근에 생긴 변수들부터 사라지니까...

 

Symbol Table도 스택을 활용해서 최적화 할 수 있다.

Scope에 진입 할 때는 새로운 Symbol Table을 만들어 스택에 Push

Scope를 탈출 할 때는 스택의 맨 위에 있는 테이블을 Pop

탐색 할 때는 스택의 Top부터 바닥까지 내려가면서 변수를 찾고, 가장 먼저 발견되는게 유효한 변수. (variable shadowing)

 

Scope마다 Symbol Table 객체를 만들었다가 지우는건 오버헤드가 너무 크다. 

그러니 스택과 해시 테이블을 섞어 사용하는 방식을 사용함.

 

 

 

 

 

(왼쪽이 해시테이블, 오른쪽은 스택 / AVAIL은 다음에 변수가 들어갈 수 있는 곳을 가리키는 포인터)

 

데이터 저장은 스택에 하고, 검색은 해시 테이블로 한다.

 

스택에는 변수 정보가 저장된다. 변수가 선언되면 무조건 TOP에 쌓는다.

해시 테이블은 변수명을 가지고 이 변수명이 스택의 어디에 위치하는지를 가리키는 포인터만 저장한다.

Scope 탈출 및 variable shadowing은 해시 테이블을 업데이트 하는 방식으로 구현함.

 

프로그램이 시작될 때 OS에게 메모리를 크게 할당받는다.

그래서 1000 개의 변수를 만들더라도 시스템 호출은 0번이고.. 배열 인덱스만 1000번 증가시킨다.

 

Top은 스택 Top을 가리키는 포인터이고, AVAIL은 현재 Scope의 시작점을 가리킨다. 

 

 

 

Type - 정수형 변수에 문자열을 넣으려고 하는지?

타입 검사는 연산을 할 자격이 있는지를 따지는 절차라고 보면 됨 

 

컴파일러에게 int x 라는 선언은 x라는 값이 (-2^31 - 1) ~ (2^31  - 1) 까지의 값만 가질 수 있음을 의미한다.

그리고 변수 x는 이 조건을 프로그램 내내 지켜야 함.

 

타입 검사의 목표는 프로그램 실행 중에 정수에 실수를 더하는 작업 처럼.. 식의 타입 오류가 없음을 보장하는 것.

 

Static

컴파일 할 때 타입을 검사한다. (Java, C) 

선언할 때 타입이 고정되고, 서로 다른 타입끼리는 연산이 불가능함.

 

Dynamic

런타임에서 타입을 검사한다. (Python, JS)

값이 들어갈 때 타입이 결정되고, 다른 타입끼리의 연산도 묵시적 형변환으로 처리함.

 

타입 검증을 수행할 때는 Proof Tree를 사용한다.

 

 

 

 

 

프언개에서 맨날 그리던거니까 설명은 패스.. 

그냥 사실 Semantic Analysis 내용이 프언개에서 다룬 내용이랑 똑같음..