This post retrieved from Yonsei University Copiler Design course (CSI4104)
Introduction of Compiler Design
Why we need to know compiler?
Starting Question : High-level로 작성한 code들이 어떻게 machine code로 변환되는가?
C++, C, Fortran등 많은 Programming Language들이 존재한다. 이러한 코드들의 의도에 맞게 hardware들이 작동하게 하는 것은 중요한 문제이다.
Compiler가 Source Progarm들을 Assembly Program으로 변환하고, Assembler가 Assembly Program을 Executable Object Program으로 변환한다. Binary File인 EOP는 Memory에 저장되어 Processor가 해당 file의 instruction을 읽고 해석하여 실행한다(fetch, decode, execution).
Compiler Design(CSI4104)에서는 Assembler 이전의 과정에 집중한다. 내가 작성한 코드가 어떻게 실행이 되는지를 이해하는 첫번째 과정이라고 생각할 수 있다.
Compilation
Compilation은 Analysis와 Synthesis 단계로 나눌 수 있다.
Analysis는 High-level로 작성된 code를 해석하고 tree structure로 기록하는 단계이고, Synthesis는 tree structure를 target program으로 변환하는 단계이다.
Compliler Structure
위 사진은 Compiler의 전체적인 flow를 보여준다. Lexical Analysis는 Scanner 에서 이루어지며 Character string에서 token을 만드는 과정이다.
position = inital + velocity * 60;과 같은 high-level 코드를<id,1> <=> <id,2> <+> <id,3> <*> <intliteral,4>와 같은 형식으로 바꿀 수 있다. 이때 바뀐 형식에서 괄호로 구분한 것들을 Token이라고 부른다. Machine(Hardware) 관점에서는 variable name에는 관심이 없다는 것을 생각하자. 여기서 id는 identifier이다.
이렇게 Token으로 구분한 후에는 Parser 가 Syntax Analysis를 수행한다. 이 과정을 거치면 Abstract Syntax Tree로 나타낸다.
위에서 변환된
<id,1> ...를 고려했을 때 아래와 같은 tree구조를 가진다.
여담으로 Java Virtual Machine에서는 stack을 사용하여 연산을 진행하는데, 위 tree에서 root node인 <=>의 오른쪽 sub tree를 후위순회한 것으로 계산한다. <id,2> <id,3>, <intliteral,4>, <*>, <+>의 순서에서 identifier인 경우에는 stack에 push하고 operator인 경우 operation에 필요한 수 만큼 operand를 stack에서 pop한 후 연산하여 다시 push한다. 이를 수행하는 JVM bytecode는 아래와 같다. JVM에 대해서는 후에 다시 다룰 예정이다.fload_2 fload_3 bipush 60 i2f fmul fadd fstore_1
Semantic Analysis는 program이 의미하는 바를 AST를 통해 확인한다.(라고 적혀있긴 하지만 code의 legal, illegal을 조사하는 것으로 이해했다.) Static한 semantic check와 Dynamic한 semantic check를 진행하는데, Static Semantic Check는 아래의 것들을 확인한다.
- 모든 identifier가 사용되기 전에 선언되었는지
- 모든 identifier가 적절하게 사용되었는지 (ex. int + string)
- call argument가 적절한지
- type checking
Dynamic Semantic check는 run-time에 걸쳐서 진행되고 아래와 같은 것들을 확인한다. segmentation fault 에러의 경우들이라고 이해했다.
- Array index 범위
- Arithmetic Error (ex. divide by zero)
이후의 과정들은 나중에 이어서 자세한 내용들을 작성할 예정이다. 이후 Intermediate Code Generator가 Intermediate Representation(IR)을 만든다. 여기까지가 Compiler Frontend이고 Analysis 과정이다. 그 이후에는 Code Optimizer와 Code Generator를 거쳐 Target Assembly Language를 반환한다.
Code Optimizer의 경우 GCC compiler에서 -O3, -O2와 같은 option으로 활용되는 것이 아닌가 싶다.
Future Road
Reference
Yonsei University CSI4104 - Compiler Design Lecture Slide, L00_Course_Introduction
