컴파일러는 프로그래밍 언어를 기계어로 번역하는 도구로, 구성 요소로 어휘 분석기와 구문 분석기, 의미 분석기, 코드 생성기를 갖는다. 어휘 분석기, 구문 분석기, 의미 분석는 컴파일러의 프론트엔드(Front-End), 코드 생성기는 백엔드(Back-End)에 해당한다. 해당 게시물은 각 구성 요소에 대해서 간략하게 설명한다.
1. 어휘 분석기
어휘 분석기(Lexical Analyzer)는 소스 코드에서 어휘를 분석하는 도구로, 문자열 형태로 주어진 소스 코드를 문법적인 의미가 있는 토큰(Token)으로 분해한다. 해당 소스 코드에서 크게 의미가 없는 공백, 개행, 탭 등의 문자는 제거하고 문법적 의미가 있는 식별자, 연산자, 키워드, 상수만 토큰화(Tokenization)해서 저장한다.
#include <stdio.h>
int main(void) {
int a;
a = 3 + 4;
printf("%d", a);
return 0;
}위와 같은 코드를 어휘 분석기는 아래와 같이 토큰화해서 저장한다. 각 토큰을 구분하는 문자로 /(슬래시)를 활용했다.
#include/</stdio.h/>/int/main/(/void/)/int/a/;/a/=/3/+/4/;/printf/(/"/%d\n/"/,/a/)/return/0/;/}이후 어휘 분석기는 각 토큰을 문법적으로 분석한 뒤 문법적으로 적합하지 않은 토큰을 발견하면 문법 오류(Syntax Error)를 내게 된다. 예를 들자면, 문자열을 시작하는 " 토큰을 컴파일러가 읽어들인 다음 모든 토큰을 다 읽어들였음에도 불구하고 문자열을 끝내는 " 토큰을 발견하지 못한다면 컴파일러는 문법 오류를 내게 된다.
2. 구문 분석기
구문 분석기(Syntax Analyzer)는 어휘 분석기에서 생성한 토큰들을 추상 구문 트리(AST, Abstract Syntax Tree)로 만든다. 추상 구문 트리를 의미 분석해서 위키백과 추상 구문 트리 페이지(https://en.wikipedia.org/wiki/Abstract_syntax_tree)를 확인해 보면 어떤 방식으로 추상 구문 트리가 생성되는지에 대한 적절한 예시가 하나 있다.
while b ≠ 0:
if a > b:
a := a - b
else:
b := b - a
return a위와 같은 소스 코드를 토큰화한 뒤, 문법적인 오류가 발견되지 않는다면 아래와 같은 추상 구문 트리를 생성하게 된다. 표현식(Expression)의 경우는 연산자가 부모 노드에, 연산의 Destination과 Source는 각각 왼쪽 자식 노드와 오른쪽 자식 노드에 위치시켜서 표현한다.
과정을 순서대로 정리하자면 다음과 같다.
- 토큰 분석 중 while을 발견한다.
- while을 추상 구문트리의 자식 노드에 삽입한다.
- while의 condition에 해당하는 표현식을 while의 자식 노드에 삽입한다. 여기서 표현식은 b != 0이다.
- while의 body에 해당하는 부분에서 if를 발견한다.
- if를 while의 자식 노드에 삽입한다(while-body의 표현식에 해당함).
- if의 condition에 해당하는 표현식 a > b를 if의 자식 노드에 넣는다.
- 표현식이 참일 경우 실행될 if-body에 해당하는 표현식을 자식 노드에 넣는다.
- 표현식이 거짓일 경우 실행될 else-body에 해당하는 표현식을 자식 노드에 넣는다.
대략적으로 위와 같은 과정을 거친다. 이후 생성된 추상 구문 트리를 활용해 중간 표현을 생성한다.
3. 의미 분석기
의미 분석기(Sementic Analyzer)는 구문 분석기에서 생성한 추상 구문 트리를 활용해서 중간 표현(IR, Intermediate Representation)을 만든다. 대략적으로 아래와 같은 행위를 통해 생성한다.
- 예약어와 같은 코드의 의미에 따라서 추가적으로 필요한 정보를 유추/분석
- 자료형이 존재하는 언어의 경우 자료형 검사 또한 수행
- 구문, 표현식, 항을 평가
- 분석 결과를 토대로 중간 표현 생성
4. 코드 생성기
코드 생성기(Code Generator)는 생성된 중간 표현을 기계어에 1:1 대응되는 어셈블리어로 변환한다. 또한 해당 과정에서는 코드에 대한 최적화 또한 적용되게 되는데, 최적화는 다음과 같은 과정을 통해서 진행되게 된다.
1. 불필요한 연산을 제거한다.
1-1. 변수에 대한 의존관계를 분석한다
1-2. 불필요한 상수연산을 결과로 대체한다
1-3. 반복문 내부의 불필요한 코드를 제거한다
2. 함수 호출이 필요하지 않도록 inline화한다 (함수 호출 연산 또한 오버헤드가 존재함)
변수에 대한 의존관계 분석이 의미하는 바는, 어떤 변수가 사용되는 경우 변수 값을 평가했을 때 변수의 값을 특정할 수 있는 경우를 따지는 것이라고 생각하면 된다. 예를 들어, int a = 7; printf("%d\n", a);와 같은 구문이 주어졌을 때 컴파일러는
printf에서 사용되는 a의 값이 7임을 역추적을 통해 추정할 수 있으므로 printf("%d\n", 7);과 같은 형태로 최적화한다.
불필요한 상수연산을 결과로 대체하는 것은 어떤 방식인가 하면 a = 4+3;과 같은 연산을 a = 7;과 같은 형태로 대체하는 행위를 의미한다.
위와 같은 최적화를 거쳐 어셈블리 코드를 형성하고, 생성한 어셈블리 코드를 어셈블러로 번역해 목적 코드(Object Code)를 생성하게 된다.
댓글