[Compiler] 1. Introduction to Compiler

컴파일러 (Compiler)

언어 X를 언어 Y로 변환해주는 컴퓨터 프로그램이다.

Source Program -> Compiler -> Target Program

ex) 

• Source language : high-level language (C / C++)
• Target language : object code || 어셈블리어

 

컴파일러가 필요한 이유

1. 폰 노이만 아키텍처 (Von Neumann architecture)

• 폰 노이만 아키텍처를 따르기 위해선 코드 또는 프로그램이 순차적으로 작성되어야 한다.

2. Machine language (기계어)

• 기계어로 코드를 작성하는 것은 매우 시간이 많이 걸리고 지루하다.

3. Assembly language (어셈블리어)

Assembler : symbolic code를 machine language에 대응하는 numeric code로 변환한다.

• 명령 및 메모리 위치는 다음과 같은 기호 형식으로 제공된다. MOV X, 2
• 어셈블이어는 기계어보다 속도와 정확도가 크게 향상되었다.
• 하지만 아직 쓰고 읽고 이해하기 어렵다.

4. High-level languages

• 수학적 표기법처럼 간결한 형태로 프로그램을 작성하고나 자연어와 기계를 독립적으로 사용한다. ex) X = 2
• High-level languages로 작성된 코드는 컴파일러에 의해 실행 가능한 코드로 변환된다.

X = 2 -> Mov X, 2 -> C7 06 0000 0002

 

변환 과정

• Front-end : 거의 고정
  * 소스 프로그램 -> 어휘 분석 -> 구문분석 -> 의미 분석 -> 중간단계 코드 생성
• Back-end : 때에 따라 언어가 다르다.

 

Scanner

lexical analysis를 수행한다.

소스 코드를 입력 받아서 Token으로 나눈다.

• Token : 의미 있는 단위
• Token 종류 : identifiers, reserved words, integers, doubles, floats, delimiters, operators, special symbols

ex)

a[index] = 4 + 2

8개의 Token으로 인식

a	identifier
[	left bracket
index	identifier
]	right bracket
=	assignment
4	number
+	plus sign
2	number

 

Parser

Syntax analysis를 수행한다.

Token을 입력받아 Tree를 만든다.

프로그램의 구조를 결정한다. (context-free 문법을 통해 Token을 그룹화한다.)

문법은 프로그래밍 언어에서 유효한 구조를 정의하는 규칙 집합이다.

ex)

 

Semantic analyzer

구문적으로는 올바르지만 의미 규칙에 위배되는 문장

ex)

- 사람이 밥을 먹는다.
- 돌이 밥을 먹는다.

 

구문트리에 주석을 단다.

• 속성과 함께 할당이 이치에 맞는지 확인한다.

 

 Source code optimizer

코드 생성 전 최적화

가장 작고, 빠르고, 효율적인 실행 결과 생성

• 공통 하위 표현식 제거
• 도달 불가능한 code segment 생성 억제
• 루프 최적화
• 컴파일 시간과 최적화 품질 간의 균형
• 최적화로 인해 컴파일러 속도가 느려지기 때문에 (최적화를 많이 할 수록 컴파일 시간이 길어진다),
  대부분의 컴파일러는 기본적으로 이 기능을 억제하거나 종료시킬 수 있다.

ex)

 

Intermediate representation

중간단계 코드

Source Program의 중간 표현이 생성된다.

• 생성하기 쉽고, target 프로그램으로 쉽게 번역할 수 있다.
• 표현에는 다양한 형식이 있지만, 공통적인 것을 3-address code라고 부른다.
• 3-address code : 피연산자 최대 3개를 가질 수 있는 명령어

ex)

a = b * c + b * d
--------------------
_t1 = b * c
_t2 = b * d
_t3 = _t1 + _t2
a = _t3

 

Code generator & target code optimization

• Intermediate code를 가져와 target machine에 대한 코드를 생성한다.
  • target machine의 속성이 주요 요소가 된다.
  • 정수의 byte 또는 words 변수 수
  • 부동소수점 데이터 타입이 메모리를 점유한다.
• target code 최적화 하기도 하고 안 하기도 한다.
  • 느린 명령을 빠른 명령으로 대체
  • 중복되거나 불필요한 작업 제거