semantic analysis 를 공부하기 전에 lexical 과 syntax analysis 를 배웠는데, lexical analysis 를 통해 캐릭터 스트림을 토큰 스트림으로 만들어 내고 이를 기반으로 syntax analysis 를 통해 문법을 체크했다.
위 과정을 거친 문제가 없는 프로그램들에 다른 추가적인 문제가 있을 수 있다. 예를 들어, 변수 사용에서 어떤 타입인지는 syntax analysis 에서 알 수 없고, 이미 정의된 것인지 여부도 알 수 없다.
이러한 추가적인 오류들을 체크하는 것이 semantic analysis 이다. 의미적으로 문제가 없는지 체크하는 것이다. 즉, context 를 본다는 것인데, context 는 지금 우리가 알고 있는 상황을 말한다. context 는 시스템적으로 memory 에 저장을 하는데, 보통 룩업 테이블 형태로 저장한다.
* Categories of Semantic Analysis
> semantic 규칙의 예 )
- 변수는 사용되기 전에 정의되어야 한다.
- 변수는 여러번 정의되면 안된다.
- 할당할 때, 변수와 수식은 같은 타입이어야 한다.
- if 문은 bool 형태를 가져야 한다.
> 2 major categories : types / scopes 와 관련된 규칙
* Type Information / Checking
semantic analysis 의 메인 카테고리는 type 과 scope information 이다.
> Type information은 다양한 구조체에서 어떤 종류의 값들을 가질 수 있는지 설명해주는 것이다.
예를 들어 다음과 같이 값들의 정보를 알려준다고 보면 된다.
- variables : int a; -> integer
- expressions : (a+1) == 2 -> boolean
- statements : a = 1.0; -> floating-point
- functions : int pow(int n, int m) -> int = int, int
> Type checking 은 실제로 정해진 타입의 룰을 따르는지 확인하는 것이다. 파이썬과 C를 비교했을 때 파이썬이 더 느린데, 런타임에서 한줄씩 번역해서 가기 때문에 그 중에서 타입 체킹때문에 느리다. 타입 체킹을 빠르게 하는 것은 중요한 부분이다.
* Scope Information
identifier 가 선언되고 프로그램의 어느 부분에서 사용될 수 있는지 지정하는 것이다. lexical scope 로 많이 지정되는데, 이는 코드를 보는 것이다. statement block, function body 등 프로그램에서 코드를 보고 region 을 정한다.
identifier 의 scope 는 선언된 lexical scope 를 지정해서 만든다.
* Variable Scope
global variable 의 경우에는 scope 가 현재 파일이고, external variable 의 경우에는 scope 가 전체 프로그램이 된다.
* Semantic Rules for Scopes
> rule 1 : 각각의 identifier 는 각각의 scope 안에서만 사용된다.
> rule 2 : lexical scope 안에서는 같은 이름을 가진 같은 종류의 identifier 는 만들어지면 안된다.
이러한 규칙을 어떻게 체크할까? 컴파일러는 scope 문제를 symbol table 을 이용해 해결한다. symbol table 은 symbol 을 저장하는 lookup table 이고, identifier 들의 특성을 저장한 테이블이다. semantic analysis 를 위해서는 identifier 에 대한 정보를 저장해야 하고, symbol table 를 활용해 저장한다. symbol table 의 각 entry 가 identifier 의 이름과 종류, 타입, 특수정보 등을 저장한다.
* Scope Information
symbol table 에 어떻게 scope information 을 저장할 수 있을까?
> Idea
- 프로그램에는 scope 계층이 있기 때문에 symbol table 을 계층 구조로 만들어 보자.
- 각 scope 에 하나의 symbol table 을 가진다.
- 각 symbol table 은 lexical scope 에서 선언된 symbol 들을 포함한다.
=> 내가 있는 scope 에서 어떤 변수가 지정되고 사용할 수 있는지 알 수 있다.
예를 보자.
각각의 scope 별로 symbol table 을 가지고 있다. global scope 는 파일이므로 int x 와 function f, g 가 symbol table 에 들어간다. function f 의 scope 에는 파라미터인 m 과 변수 x, y 가 있고, 이 함수 안에는 두 개의 scope 가 존재한다. function g 도 마찬가지로 파라미터 n 과 변수 t 가 symbol table 에 들어간다.
이렇게 symbol table 을 여러 계층으로 만들었기 때문에 이름 충돌 문제 (name collision) 를 해결할 수 있다. identifier 를 찾을 때, 현재 scope 의 symbol table 에서 먼저 찾고 없다면 계층 구조에서 위로 올라가서 찾는다. (없으면 에러)
>> 코드가 주어지고 계층 구조를 가진 symbol table 를 만들 수 있어야 한다.
* Symbol Table Operations
> symbol table 은 2개의 operation 으로 이루어져 있다.
- table 을 만들 때, 새로운 identifier 를 추가해야 한다. (Insert)
- 컴파일러가 프로그램을 보면서 table 에 있는지 찾아봐야 한다. (lookup function)
table 을 만드는 것은 lexical analysis 중에는 불가능하다. lexical analysis 는 토큰을 추출하는 것인데, 토큰이 identifier 가 되기 때문에 그때그때 symbol 을 알 수 없다.
symbol table 을 만들 때는 parsing 할 때 AST (Abstract Syntax Tree) 를 만들면서 insert 를 하고, 만들어진 후에 lookup 을 한다.
* Forward References
class A {
int m() { return n(); }
int n() { return 1; }
}
identifier 가 선언되기 전에 사용되는 경우를 말하는데, 문제가 되지 않으려면 AST 를 만들고 symbol table 을 만들어 나중에 타입 체킹을 한다. 즉, 컴파일러가 table 이 만들어지고 lookup 을 수행하도록 한다. type check 와 table build 는 동시에 할 수 없기 때문에 type check 를 나중에 한다.
* Back to Type Checking
타입은 프로그램이 실행되는 동안 사용 가능한 변수를 말한다.
타입 에러는 프로그램 실행 동안 어떤 operation 이 잘못 동작하거나 특성이 바뀌는 경우이다.
> Type-Safety 를 어떻게 보장할 수 있을까?
타입을 바인딩(binding) 하고 타입을 체크한다.
타입 바인딩은 프로그램에서 어떤 구조들의 타입을 정의하는 것이다. 명시적으로 정의하거나 (int x), 암묵적으로 정의할 수 있다. (x = 1) Type consistency (safety) 는 타입이 맞게 잘 사용되고 있는지 체크한다.
타입 체킹은 어떤 프로그램에서 구조체가 타입 바인딩 정보에 따라서 올바르게 사용되고 있는지 체크하는 것이고, 타입 체킹 규칙에 의해 체크한다.
* Type Checking
semantic 체킹인데, 프로그램에서 type safety 를 체크하는 과정이다.
예를 들어,
어떤 operator 가 있을 때, operand 가 올바른 타입으로 들어가야 한다.
function 은 올바른 개수와 타입의 argument 가 들어와야 한다.
return statement 는 return type 을 맞춰야 한다.
assignment 할 때, 왼쪽에 있는 타입과 호환가능한 타입이어야 한다.
* 4 Concepts Related to Types / Languages
1. static vs dynamic checking
(타입 체킹이 컴파일타임 / 런타임 에 이루어짐)
(빠르다. / 프로그램 짜기 쉽지만 성능저하가 있다.)
2. static vs dynamic typing
(타입 define 이 컴파일타임 / 런타임 에 이루어짐)
3. strong vs weak typing
(얼마나 정밀하게 타입을 체크할 것인지)
4. sound type systems
(모든 타입 에러를 static 하게 잡을 수 있는 시스템)
(컴파일타임에 타입적으로 문제가 없는 것을 보장해준다.)
위 개념에 따라 언어를 분류하면 다음과 같다.
그렇다면 왜 static checking 을 할까?
런타임에서의 체킹(dynamic) 은 프로그램이 느려지기 때문이다. 또한, static checking 은 프로그램이 실제 동작할 때 문제가 없다고 보장할 수 있는 것이다.
'컴파일러' 카테고리의 다른 글
| Control Flow - 1 (0) | 2022.12.17 |
|---|---|
| Intermediate Representation - 2 (stack frame) (0) | 2022.12.16 |
| Intermediate Representation - 1 (0) | 2022.12.15 |
| Semantic Analysis - 2 (0) | 2022.12.14 |
