컴파일러 - 컴파일러 구조
컴파일러 구조
차후 세부적으로 다룰 것이지만 당장은 대략적인 컴파일러의 구조에 대해서 알아보겠다. 컴파일러는 크게 전단부와 후단부로 나뉘어져있다.
1. 전단부
소스 언어에 관계되는 부분으로 소스 프로그램을 분석하고 중간 코드를 생성하는 부분이다.
1) 어휘 분석(lexical analysis)
- 원시 프로그램을 읽어 들여 토큰(Token)이라는 의미 있는 문법적 단위(Syntactic entity)로 분리한다.
- 어휘 분석을 담당하는 도구를 어휘 분석기(lexical analyzer) 또는 스캐너라고 부른다.
- 토큰 : 문법적으로 의미를 갖는 최소의 단위
- 이러한 토큰 표현은 토큰 번호와 토큰 값의 순서쌍으로 표현된다.
- 주석 제거도 이 과정에서 처리 된다.
2) 구문 분석(syntax analysis)
- 어휘 분석 단계에서 토큰들을 받아 이 토큰들이 문법에 맞는지 검사한다.
- 올바른 문법일 경우 Parse Tree(토큰들이 단말 노드로 이루어진 트리)를 구성한다.
- 올바르지 않은 문법은 에러 메세지를 출력한다.
- 검사 및 tree 구성 및 에러 메세지 출력의 일련의 과정을 구문 분석 혹은 파싱이라 한다.
- 구문 분석을 담당하는 도구를 Parser 혹은 구문 분석기(Syntax analyzer)라고 한다.
3) 의미 분석(semantic-analysis)
- 원시 프로그램의 의미적 오류를 검사하고 계속되는 코드 생성 단계를 위한 정보를 모으는 일
- 이러한 의미 분석을 하는 도구를 의미 분석기(Semantic analyzer)라고한다.
- 대표적인 기능은 형 검사(Type checking)으로 허용된 피연산자를 가졌는지 검사와 형변환을 처리하는 것을 말한다.
4) 중간 코드 생성(intermediate code generation)
- 파서의 출력인 추상 구문 트리를 입력으로 받아 그에 해당하는 중간 코드를 생성한다.
- 중간 코드를 생성하는 도구를 중간 코드 생성기(intermediate code generator)라고 한다.
- 해당 부분은 추가적인 포스팅이 있을 예정이다.
2. 후단부
소스 언어보다는 목적 기계에 의존적이며 전단부에서 생성한 중간 코드를 특정 기계를 위한 목적 코드로 번역하는 부분
1) 코드 최적화(code optimization)
- 같은 기능을 유지하면서 코드를 좀 더 효율적으로 만들어 코드 수행 시간이나 메모리 공간을 절약하기 위한 단계
- 생략되는 경우도 있다. 하지만 RISC 구조를 가진 컴퓨터의 특성을 활용하기 위해 많이 사용한다.
- 각 영역에 따른 분류가 있다.
a. 프로그램 영역에 따른 분류
지역 최적화(local optimization or peephole optimization)
분기해 나가거나 분기해서 들어오는 부분이 없는 기본 블록 내에서 행해지며 부분적인 관점에서 일련의 비효율적인 코드들을 구분해 내고 좀 더 효율적인 코드로 개선하는 방법으로 실제로 상당한 수준의 코드 효율화를 취할 수 있음
ex) 공통 부분식 제거, 복사 전파, 죽은 코드 제거, 상수 폴딩, 대수학적 간소화 등전역 최적화(global optimization) 하나의 프로시저 내에서 일련의 비효율적인 코드를 구분해내고 좀 더 효율적인 코드로 만드는 방법으로 일반적으로는 자료 흐름 분석(Data flow analysis)이라는 기법을 사용한다.
ex) 전역적 공통 부분식 제거, 상수 폴딩, 도달 할 수 없는 코드의 제거 등
b. 기능적 분류
실행시간 최적화
메모리 최적화
c. 흐름상 분류
단일문 최적화
루프 최적화
d. 목적 기계의 의존성에 대한 분류
- 기계 독립 최적화
- 기계 종속 최적화
2) 목적 코드 생성기(target code generator)
- 중간 코드를 입력으로 받아 그와 의미적으로 동등한 목적 기계에 대한 코드를 생성하는 일을 한다.
- 연산을 수행할 레지스터를 선택하거나 자료에 기억 장소의 위치를 정해주며 실제로 목적 기계에 대한 코드를 생성한다.
참고자료
This post is licensed under CC BY 4.0 by the author.