컴파일 과정은 사람이 이해할 수 있는 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/
