컴파일러의 개념 + 어떻게 컴파일러가 작동하는지(How Compiler works)

컴파일 과정은 사람이 이해할 수 있는 High Level Programming Language 로 구성된 소스코드를 기계가 이해할 수 있는 Lower Level Language 로 바꾸는 과정이다.

컴파일러는 다음과 같은 과정을 통해 컴파일을 수행한다.

[출처 : https://www.programcreek.com/2011/02/how-compiler-works/]

위의 그림은 컴파일의 단계를 간략하게 설명한다. 다음은 그림에 대한 설명이다.

(1) Lexical Analysis 

소스코드를 Token 으로 분할한다. 모든 키워드와 Parenthesis, 변수들 및 괄호들을 분리해낸다.

(2) Syntax Analysis

앞선 단계에서의 스캔으로 만들어진 토큰들(Token Stream)의 문법을 분석하기 위한 자료구조료 변형한다.

이렇게 만들어지는 자료구조를 Parse Tree 라고 한다.

이 단계에서는 Token 이 Valid 한지 검출하지 못하며, Token 이 사용되기 이전에 정의 또는 초기화되어있는 지 등 정적분석은 불가능하다.

또한 이단계에서 파싱이 일어난다. Parsing 작업은 Top-Down, Bottom-Up 두가지 방식으로 나뉜다.

Top-Down Parsing 은 Parse Tree 의 윗쪽부터 파싱을 수행하며, Bottom-Up Parsing 은 트리의 아래쪽부터 파싱이 수행된다.

유명한 파서의 종류로 Top-Down 방식의 Non-Backtracking Predictive Parser 인 LL Parser와 Bottom-Up 방식의 LR Parser 가 존재한다.

(3) Semantic Analysis

각 기호들 및 구문들을 의미있는 값들로 변경한다. 가령 기호 < 는 bool 을 Return 하는 Operand 함수로,

While 과 같은 키워드는 반복 구조를 이루는 void 함수로, 각 변수는 메모리로 치환한다.

이 단계에서 Type 의 Mismatch 나, 변수의 미정의, 파리미터 미정의 등 문법적 요소들이 검증된다.

(4) IR Generation

구문 분석으로 이루어진 자료를 중간 언어로 변경하는 작업을 수행한다.

IR 은 Intermediate Representation 의 약어로 소스코드에 근접한 기계어인 High Level IR, 타겟 머신에 종속적으로 디자인된 Low Level IR 이 존재한다.

컴파일러는 소스코드를 High Level IR -> Low Level IR 로 변경한 뒤 Target Machine Code 로 해석한다.

(5) IR Optimization

중간 언어를 최적화한다. 불필요한 루프를 없애거나, 사용하지 않는 변수의 정리 등이 수행된다.

(6) Code Generation

Syntax Analyzer 및 Semantic Analyzing 된 출력값을 Low level Code 로 해석한다.

이 단계를 거쳐서 Assembly Code 등의 Object Code 로 번역된다.

이 단계에서 수행되는 작업들은 다음과 같다.

 - Instruction Selection : 어떤 명령어를 사용할 것인지

 - Instruction Scheduling : 어떤 명령어를 먼저 실행할지 (최적화)

 - Register Allocation : 변수들을 프로세서 레지스터에 할당

 - Debug data generation : 디버그 모드인 경우 디버그를 위한 코드를 생성

(7) Optimization

위의 과정에서 생성된 코드를 한단계 더 최적화한다.

이 단계의 최적화는 두단계로, Machine 에 종속되지 않은 일반적인 형태의 최적화와 Machine 에 종속된 최적화가 이루어진다.

이 과정을 거치면서 중복 제거, 메모리 확보, 코드 정리, 루프 최적화, Control Flow 개선이 일어난다.

위의 단계들을 거치면 High Level Source Code 는 Machine Code 로 변환된다.

Generating 되는 코드는 대게 머신별로 다르게 되며, 세부로직 및 최적화의 과정 역시 컴파일러에 따라 차이가 존재하게 된다.

본 포스팅은 컴파일러에 대한 간략한 소개를 다루고 있으며 더 자세한 내용은 다음 링크들을 참조한다.

(이해해야할 분량이 많다.)

참조

https://www.tutorialspoint.com/compiler_design/index.htm

https://www.programcreek.com/2011/02/how-compiler-works/