컴퓨터/공부(컴파일러)

[공부]컴파일러의 일반적인 구조

sdk 2016. 8. 16. 15:19

컴파일러의 구조는 크게 전단부와 후단부로 나눌 수 있다


전단부는 소스언어에 관계되 있고 후단부는 전단부에서 생성한 중간 코드를

플렛폼에서 돌아갈 수 있게 바꿔주는 역할을 한다.

전단부는 각 언어당 하나씩 필요하며, 후단부는 목적 기계당 하나씩 필요하다.


소스 프로그램은 전단부의 어휘분석, 구문분석, 중간 코드 생성의 과정을 가지고 이 중간코드는 후단부에서 최적화와 목적코드 생성을 하여 목적 프로그램을 만들어 낸다 이 모든 과정은 테이블로 관리한다 .  

어휘 분석기는 소스프로그램을 받아 일련의 토큰을 내놓는데 일련의 토큰은 키워드, 연산자, 구분자 등이다.

예를들어 

a = b  + 10;  으로 되어있다면, a ,  = , b , +, 10, ; 총 6개의 토큰으로 분리해 낸다 여기서  =, + , ; 은 특수 형태의 토큰이며 a, b, 10은 일반 형태의 토큰에 해당한다. 각 토큰은 효과적인 처리를 위하여 고유의 내부번호를 정수 형태로 가지게 되는데 이를 토큰번호 라고 한다. 사용자가 작성한 주석은 모두 이곳에서 처리된다.


구문분석기는 파서라고도 하는데, 어휘 분석단계를 거친 토큰들을 받아 소스 프로그램에 대한 에러를 체크하고 문장에 대해서는 구문 구조를 만든다. 즉 소스프로그램에 에러가 있다면 이를 출력해주고 그렇지 않다면 이를 트리 형태로 만들어 출력한다. 이 방법에는 Parse Tree 와 abstract syntax tree가 있으며 요즘의 컴파일러는 대분 abstract syntax tree 로 처리된다.

 ( 추상 구문 트리는 알아보도록 하자 )


컴파일 과정의 세번째 단계인 중간 코드 생성은 파서의 출력인 추상구문 트리를 입력으로 받아 의미 검사를 하고 그에 해당하는 중간 코드를 생성한다. 


컴파일러에 따라 독립된 의미분석 단계를 가질 수 있다.


의미 분석 단계에서 하는 중요한 일중 하나는 타입 체크이다. 이는 각 연산자가 소스언어의 정의에 맞는 피연산자를 가지는가를 검사하는 것이다. 예를 들면 대부분의 언어에서는 실수가 배열의 첨자로 사용되었을 때 에러로 간주한다. 또한 어떤 언어에서는 실수와 정수연산이 혼합되는데 이를 수행하기 위해 정수를 실수로 바꿔주는 작업이 필요한데 이게 바로 형변환이다.


중간 코드 생성은 구문분석단계에서 만들어진 구문구조를 이용하여 코드를 생성한다. 예를들어 아까의 덧샘연산은 각각의 처리를 거쳐 중간 코드에 도달하면 다음과 같은 꼴이 된다.


lod 1 2

ldc 10

add 

str 1 1

즉 b의 값과 상수 10을 스택에 적재한 다음 덧셈을 해서 a에 저장ㅎ나다. 여기서 사용한 중간 언어는 U-Code 이다. 

이 코드들은 다음 과정인 코드 최적화를 거치게 되는데 이는 선택적인 과정이므로 안거칠떄도 있다고 한다.


최적화는 관점에 따라 지역최적화 또는 전역최적화로 구분 할 수 있다. 지역 최적화는 기본 불록 내에서 행해지며 부분적인 관점에서 일련의 비효율적인 코드를 개선하는 방법이다.

지역 최적화 방법은 주로 컴파일 시간 상수 연산 중복된 load store 명령어 제거, 식의 대수학적 간소화, 연산 강도 경감, 불필요한 일련의 코드 블록 삭제등등의 효과를 얻을 수 있다.



전역 최적화는 기본 블록들 사이에 최적화를 행하는것으로 공통 부분식 축약, 루프 내에서 값이 변하지 않는 코드를 루프 밖으로 이동, 그리고 도달될 수 없는 코드의 제거등이 있다.


Precode Optimizer : 중간코드 최적화

PostCode Optimizer: 기계코드 최적화


목적 코드 생성기는 중간코드를 입력받아 그와 의미적으로 동등한 기계코드를 생성하는 역할을 한다.


목적코드 생성기의 일은 크게 4가지로

1. 목적 코드 선택 및 생성

2. 레지스터의 운영

3. 기역장소 할당.

4. 기계의존적인 코드 최적화로 나뉜다.