Compiler 5 - Semantic Analyzer

 Semantic analyzer : semantic error를 체크. 이는 programming language에 따라 달라질 수 있다. 그러나 공용적으로 사용되는 것들도 존재한다.
- 모든 변수는 사용되기 전에 전역/지역적으로 선언되어야 한다.
- 모든 변수는 지역 내에서 한 번만 선언되어야 한다.
- 모든 함수는 전역에서 한 번만 선언되어야 한다.
- 모든 변수는 알맞은 타입으로 사용되어야 한다. (int a = 3.5, char k = 2 등)
- 모든 함수는 알맞은 개수와 타입의 파라미터를 이용하여 호출되어야 한다.
이런 semantic rule은 scope / type checking을 통해 확인 가능하다.

Scope checking
- scope : 어떤 identifier가 access될 수 있는 구간을 해당 id의 scope이라 한다. 따라서 선언과 사용되는 변수의 구간이 scope이 되며, 다른 scope에서는 같은 id가 다른 변수를 가리킬 수도 있다. (each id has it's own id, where we can accesse to that id)

1. Static scope : 대부분의 프로그래밍 언어에서 사용되어 physical structure에 의해 scope이 결정됨. ({}, (), 등등)

2. Dynamic scope : program의 execution 순서에 따라 scope이 결정됨. (Lisp, SNOBOL 등 언어에서 사용)

일반적으로 대부분 programming language에서 scope는 declaration과 함께 결정된다. function/class/variable 등의 declare 될 때 각 id의 scope이 결정된다.
혹은, 함수의 parameter에서 formal parameter 형태로 id가 declare 될 수도 있다.

Most-closely nested scope rule
대부분의 프로그래밍 언어에서 사용되는 scope 판별 방식 (LEGB - Local / Encapsulation / Global / Built - in. 각 scope를 순서대로 확인해본다.) 해당 id가 사용된 가장 가까운 nested scope부터 차례로 더 넓은 범위를 확인하는 방식.

단, oop에서 class 내의 메소드 선언과 상속 등에서는 scope가 알맞은 class 내로 확장될 수 있다. (exception of most-closely nested scope rule)
Implement of scope checking
AST를 traveling 하며 symbol table에 알맞은 scope information을 업데이트한다. 따라서 AST에서 block({})을 만나면 current scope 값을 증가시키고 해당 scope 내에 변수들을 저장한다. 이를 반복하면 symbol table에 값과 scope를 같이 저장할 수 있다. 그리고 해당 구역 내를 모두 순회하면 scope를 빠져나가며 current scope 값을 감소시키면 된다.

따라서 어떤 변수를 사용할 때 symbol table에서 해당 scope를 확인하여 그 값이 있는지 확인하고 사용하면 된다. 만약 없다면 한 단계 상위 scope에서 확인하면 된다. 이를 반복하여 scope checking을 할 수 있다. 만약 모든 scope에서도 선언된 변수가 없다면, error를 반환하게 된다.

그러나 이렇게 간단한 방법을 사용하면, 같은 레벨의 scope가 있을 때 ambiguity가 있을 수 있다. 어떤 함수가 있고, 또 다른 함수가 있을 때, 각 함수의 내부는 서로 다른 scope이지만, current scope의 값은 동일하게 취급되므로 ambiguity가 생길 수 있다. 또한 매 변수에 대해서 전체 table을 다 찾아봐야 하므로 비효율적이다.

이를 해결하는 방법은 각 scope에서 independent symbol table을 만들고, 이들을 사용하여 nesting structure를 표현하는 것이다. 따라서 current scope 같은 전역 변수를 사용하지 않고 현재 위치에 알맞은 symbol table을 찾으면 된다. 그리고 각 scope는 parent scope을 가리키게 하여 전체 table을 찾아보지 않아도 되게 만들 수 있다. (Linked list 형태)

이를 구현하는 방법은 block마다 새로운 symbol table을 만들고, 각 table은 parent scope의 symbol table을 가리키도록 구성하면 된다. 만드는 방법은 위와 동일하게 root-left-right 순서로 AST를 순회하면 된다.

그러나 여전히 class와 상속에 대한 scope 문제는 해결할 수 없다. 이를 해결하기 위해서는 multi pass scope checking을 사용할 수 있다. 먼저 해당 class 내에서 모든 함수의 이름을 확인한 다음에 scope checking을 하는 방법이다. 그래서 이런 문제를 해결하기 위해서는 2 개 이상, 3개 이상의 pass를 가지는 checking을 해야한다. (그리고 semantic analysis는 주로 이런 multi pass를 요구한다)

Type Checking
어셈블리어 이하에서는 type에 대한 정보가 없기 때문에 이런 에러를 발견할 수 없다. 따라서 우리는 higher level representation (AST) 등에서 이 type error를 발견하고 수정해야 한다.

- data type : compiler에게 programmer가 해당 data를 어떻게 사용할 것인지 알리는 데 사용하는 데이터의 정보(attribute).
- type system : program의 construct들에게 type을 부여하는 rule들의 set. 예를 들어 int형 변수에 값을 초기화할 때 필요한 값은 int 값이어야 한다. 이런 rule을 확인하여 알맞으면 진행하고, 틀렸다면 type error를 출력한다.

statically typed language(C, C++, java, GO) : type of variable이 compile time에 알려진 것. 따라서 compile time에 type checking이 이루어진다. 이 경우 explicit type을 가지고 strict rule을 가지므로 버그를 찾기 쉽고 이해하기도 쉽다. 또한 run time performance가 좋다.

Dynamically typed language(python, javascript)  : type of variable이 run time value에 따라 결정된다. 따라서 할당하는 값에 따라 변수의 타입이 변화가능하다. 이 경우 higher flexibility를 가지고 prototyping 하는데 편리하다.

일반적으로 statically type은 compilation 방법을 사용하고, dynamically type은 interpretation 방법을 사용한다.

type checking은 각 expression을 이루는 components들의 type을 infer하고, 이를 결합한 expression의 type을 보고 이와 동일한지 확인한다. 따라서 expected(infer)와 실제 확인이 같은지 아닌지를 확인하는 과정이 type checking 이 된다.

Rule of Inference
if-then statement의 형태를 가진다. 만약 hypothesis가 true 라면, conclusion도 true라고 생각할 수 있다.

예를 들어 c = a+b; 가 있을 때, a와 b의 type을 통해 c의 type을 추측하고, 이 것이 실제 타입이 맞는지 확인하게 된다.
- notation
x:T = 변수 x가 타입T를 가진다.
Hypothesis / conclusion  = if hypothesis is true, conclusion is true.
ㅏ = we can infer

Axiom은 항상 true인 것을 나타낸다. 따라서 hypothesis가 없고 올바른 변수-타입이 연결된 conclusion을 가지는 것을 공리라 한다.
상기 notation과 공리를 통해 다양한 rule을 나타낼 수 있다.

그러나 이런 간단한 inference rule로는 해결할 수 없는 몇 가지 문제가 있다.

free variable : 해당 expression 내에서 type이 define/declare 되지 않는 경우.
예를 들어 int y= x + 3; 과 같은 경우, 3은 int라는 것을 추론할 수 있지만, 다른 곳에서 선언된 x에 대해서는 이의 타입을 알 수 없다.

이를 해결하기 위해서는 scope information을 추가하는 것이다. 따라서 어떤 scope S에서 expression e의 type T를 추론할 수 있다. 이를 나타내면, Sㅏe : T와 같이 된다.
이를 확장하여 변수 뿐 아니라 함수, 배열 등의 expression의 타입도 나타낼 수 있다.

Statements
실제 코드에서는 expression 뿐 아니라 assign, while, if 등의 statement들도 존재한다. 따라서 여전히 해당  statement가 semantically well-formed인지 아닌지 확인할 필요가 있다.
SㅏWF(stmt) ; scope s에서 stmt가 well-formed 라는 것을 표현한다. 따라서 이를 이용하여 inference의 type을 통해 해당 scope의 stmt가 well formed 라는 것을 표현할 수 있다.

예를 들어 Sㅏe1:T, Sㅏe2:T, Sㅏe1 is variable, Sㅏe2 is variable or constant 가 hypothesis라면, 이를 통해 conclusion SㅏWF(e1=e2;) 라는 사실을 이끌어 낼 수 있다. 또한 각 stmt의 WF을 통해 if나 while의 WF도 도출할 수 있다.

따라서 compiler는 inference + scope information + well -formedness rule을 통해 type checking을 할 수 있다. 가장 먼저 scope checking을 하고, AST를 travel하며 inference rule을 이용하여 sub expression의 type checking을 모두 한다. 그리고 child stmt에 대해서도 type checking을 한 후에 마지막으로 전체의 well-formedness를 확인하는 순서로 이를 구현한다. (recursively work through AST)
따라서 이를 통해 semantic analyzer까지 구현할 수 있게 된다.