Semantic Analyzer

Semantic Analyzer

문법적으로 옳은 문장이라고 하더라도, 의미론적인 것까지 옳다는 이야기는 아니다.

semantic analyzer는 그런 의미론적인 부분을 체크해준다. 

각 프로그래밍 언어마다 문맥은 다 다르지만, 우리 클래스에서는 아래의 의미론을 사용한다.

 

(아마도 C언어의 단순한 문법)

1. 모든 변수는 사용되기 전에 선언되어야 한다.

2. 모든 지역변수는 해당 범위 내에서 딱 한번만 선언될 수 있다.

3. 모든 함수는 전체 코드에서 딱 한번만 선언될 수 있다. 

4. 모든 변수는 해당 상수나, 변수에 대해 옳은 타입으로 사용되어야 한다.

5. 모든 함수는 옳은 타입의 인자나, 옳은 인자 개수와 함께 사용되어야 한다.

 

==> 그렇다면, 이 규칙들을 어떻게 체크할 수 있을까?

1 ~ 3 ==>  Scope checking

4 ~ 5 ==> Type checking

 

 

Scope checking

scope란 프로그램에서 해당 변수에 접근할 수 있는 부분이다. 

 

scope checking에는 두가지 타입이 존재한다,

1) Static scope

=> scope를 physical structure에 의존하여 체크

2) Dynamic scope

=> scope를 프로그램의 execution에 따라 체크 

=> 보통 static을 많이 쓰고, 우리도 그거로 간다. 

 

 

The most - closely nested scope rule

가장 가까운 scope에서 선언된 것을 따라가는 방식

 

예외) function

함수는 physical하게 선언 전에 불러도 상관 없다.

 

예외) OOP 언어

 

scope가 전혀 관계가 없지만, 상속 관계라 가능한듯?

 

Implementation of scope checking

AST를 따라가면서 scope 정보를 업데이트 해준다.

=> 새로운 block을 만나면 현재 scope ++

=> 새로운 선언을 만나면, 해당 변수의 scope를 현재 scope로 저장.

 

여러 문제들

1. 어떤 변수를 해당 scope에서 사용할 때 

=> 그 변수가 해당 scope 내에서 선언 됐나? 확인

==> 맞으면 yes

==> 선언됐지만, 선언하기 전에 사용됨 => 부모의 scope를 확인하고, 가장 가까운 scope의 선언을 사용

==> 선언되지 않았고, 부모의 scope에도 없음 => error

 

 

AST 를 따라가는 방식에는 몇가지 문제가 존재

 

1) ambiguity

{
int a;
    {
    	int b;
    }
    {
    	int c;
        b = 1;
    }
}

 

b와 c는 같은 level의 scope에 존재하지만, 사실 명백하게는 다른 scope이다.

하지만 AST를 따라가다보면, c scope에서 b를 사용하는 것을 옳다고 판단해버린다.

 

2) inefficiency

위와 비슷하게, 같은 scope level 이더라도 다른 scope에 존재하면, 그 다른 부분은 탐색할 필요가 없는 것인데, 

AST를 따라가다보면 전체 table을 매번 체크한다. 

 

Solve

이런식으로 link를 사용하여, 해당 scope의 부모-자식 관계를 확실히 해준다. 

어떤 identifier가 사용 됐을 때, 해당 scope에 있는지 확인, 없으면 부모, 또 없으면 부모의 부모...  

이런식으로 더이상 부모가 없을 때까지 탐색한다. 

 

 

그렇다면, function이나 class는 어떻게 선언 전에 사용할 수 있게 되는걸까?

==> 일단 symbol table list를 다 만들어 놓기 때문에, 똑같이 scope check 하면 된다.

==> Multi-pass scope checking

 

그렇다면, inherited 관계에서 변수/함수는 어떻게 체크하는 걸까?

=> open question

 

 

Type checking

type 이란?

=> 프로그래머가 컴파일러에게 어떤 의도로 데이터를 사용했는지 이야기해주는 데이터의 속성

 

type system 이란?

=> 프로그램의 다양한 construct 에서 특정한 type을 할당하는 rule

ex) a && b, char a = b, a = 3.0f

 

type checking 이란?

=> operator가 기대하는 type과 operand의 type이 매치되는지 검사

 

type checking이 왜 필요한가?

=> 어셈블리 언어 level에선 type checking을 하지 못함. 그래서 higher level에서 해야한다.(AST 같은)

 

마찬가지로 static typed languages와  dynamic typed lanuages가 존재. 우리는 static으로.

 

프로그래머가 keyword를 사용하여 type을 특정하면, 컴파일러가 해당 타입을 confirm한다.

=> HOW?

 

 

Rules of inference

=> if-then statement로 구성됨. 

 

예시를 보자.

A와 B의 type이 int라면, 그 해당 결과인 A+B의 type도 int라고 추론할 수 있다.

즉, "hypothesis 가 true면, conclusion도 true"

=> hypothesis를 만족하지 못한다면, type error가 난다.

(ex, A는 int고 B는 boolean type이라면, 가설 자체가 만족이 되지 못한다.)

 

Notations for rules of inferences

=> 여러 복잡한 예시들

 

 

prob1) free variables

int y = x + 3
y = x + 3
if(a == b)

 

=> expression 내에서 variable이 정의 되지 않았을 경우

 

solution => adding scope information

 

=> 정상적인 변수라면, scope 내에서 어딘가에 선언이 존재할 것.

=> scope를 추가해줘서 type을 검증할 수 있게 해준다.

=> 이 scope는 위에서 검사한 scope checking  table에서 정보를 가져온다

 

prob 2) statements

=> 해당 statement가 semantically 하게 well-fomed인지 어떻게 체크?

 

solution => definfing well - formedness rules

 

=> 이 형태면 semantic 하게 잘 만들어졌다고 증명하는 WF를 정의함.

 

=> Scope S 의 WF은 stmt다. 

=> 해당 stmt가 여러개 있으면, WF는 stmt의 모음이다.

=> S 내의 e가 bool type이다.

=> while loop 내의 scope S' 가 존재한다.

=> S'의 WF은 stmt의 모음이다.

=> 그렇다면 S의 WF은 while(e){stmt1, stmt2 ...} 로 정의할 수 있다.

 

Q. for if-else statements

gpt가 짜줌. 맞는지는 몰?라

 

 

그렇다면 type checking에서 inference rule을 어떻게 이용할까?

1) type checking 전에 scope checking을 먼저 한다.

2) 각 statement에 

 => 포함하고 있는 모든 subexpression에 type checking

 => child statement도 체크

 => 전반적인 well-formedness 체크

 

=> AST 따라가면서 하나하나 다 해봐야 할듯.....

대충 이런 식..

 

그니까 type checking에서 컴파일러는

rules of inference + scope information + well-formedness rules 사용