C 컴파일러 구현

최종 프로젝트로 컴파일러 프로젝트를 해야한다.
가장 친숙한 c를 선택해서(사실 c++의 상속, 다형성을 구현할 자신이 없어서;) ANSI 에서 조금 더 간략화한
small C를 target language로 선택하였다.

생성된 프로그램 source를 컴파일 할 수 있는 컴파일러를 설계하고 구현하는 것이 목표이다. 기존의 Compiler들과 마찬가지로 Text 형태의 source code를 받아들여 오류를 찾고, 오류가 없다면 중간 code를 생성하여 code 최적화를 수행한 후 목적 code를 생성하고 실제 실행이 가능한 실행 파일까지 만드는 것이 구현 최종 목표이다. 컴파일러를 설계하고 구현하기 위해서는 실제 코딩보다 Yacc를 통한 문법 정의 및 실제 심볼 테이블 설계, 컴파일 프로세스 정의 등 설계 및 리서치 과정이 훨씬 더 중요하다고 판단하였다.

최종적으로 목표한 target grammar 및 함수호출(재귀, 멀티 콜 포함), if-else, while-break, 변수 할당, 사칙 연산 등 대부분의 기능을 모두 구현하였고 이를 MASM 32 어셈블 문법으로 변환, 링커를 호출하여 최종 실행 바이너리 파일 까지 생성한다.

lex의 기본구조는 위와 같다. 토큰 패싱과 더불어 타입체 체킹, 주석인지 여부를 구분한다. lex 구현은 단순해서 몇시간도 안걸렸다.(ANSI C lex 참고)
이제 lex에서 넘겨주는 token 정보를 바탕으로 yacc에서 이를 분석, 심볼 테이블을 만들어야 하는데, 고민해보다가 선배의 조언을 참고로 '함수'를 중심으로 심볼테이블을 구축하기로했다. 즉 각 함수마다 메모리를 할당하여 함수의 인자, 내부 변수, 값, 리턴 값등을 저장하는 것이다. 심볼테이블 구조는 아래와 같다.

 
위의 name에 보면 현재 make_triangle 과 make_lectangle, main 함수가 존재하고 각각의 인자가 테이블에 저장된 것을 알 수 있다. 이제 이를 바탕으로 yacc에서 SDT(syntax directed transition)기법을 이용하여, rule에 의해 reduce 될 때마다 추가 코드를 삽입하여 중간코드를 바로바로 생성하도록 하였다.

원래 중간코드란 각 머신에 디펜던트하게 생성해야하는 것이 원칙이나, 본 프로젝트에서는 실행 머신이 x86으로 고정되어 있기 떄문에 머신 의존성은 고려하지 않고, 어떻게 하면 어셈블리어로 쉽게 변환할지만 생각을 하였다. 하도 디스어셈블링해서 어셈블리어를 자주 들여다보니 나중에는 걍 코드만 보고 바로 어셈블리어로 변환할 수 있게되어;;; 거의 어셈블리어와 흡사하게 중간코드를 구현하였다.

 위 그림이 간단한 사칙연산인 a*b+d*e 를 중간코드로 변환한 그림인데, 사칙연산의 우선순위를 어떻게 처리하여 중간코드로 바꿀까 고심하다가,스택을 사용하니 간단하게 해결되었다. 무조건 identifier나 num이 패싱되어 올 경우, 이를 스택에 넣고 연산자 + - * /가 오면 pop을 하여 연산하고, 결과를 다시 push stack 하는 방법이다. 중간에 불필요한 push pop 같은 경우는 최적화 단계에서 모두 제거를 해주는 방법을 사용하였다.

전체 컴파일 과정을 발로그림 그림으로 도식화 해보면 다음과 같다.

함수호출, 멀티펑션콜, 재귀호출(사실 재귀는 함수호출을 제대로 구현한다면 그다지 어렵지 않다) if-else와 while-break 까지 구현하였다. 찾아보니 MASM6.0부터는 고급 디렉티브 .IF나 .WHILE을 제공해주기 때문에 매우 편하게[ㅋㅋ] 구현할 수 있었다.

실행파일까지 모두 생성이 되며, 내가 만든 이 SCC(small C compiler)로 컴파일이 가능한 코드는 아래와 같다.

int make_triangle(int size) {

int i,j;

printf("size %d  isRecursive %d\n",size);

i=size;

j=size;

if(size!=0) {

while(i>0) {

j=i;

while(j>0) {

printf("*");

j--;

}

i--;

printf("\n");

}

size--;

make_triangle(size);

}

else {  //recursive

printf("triangle end\n");

}

return size;

}

void make_lectangle(int size) {

int width=size;

int height=size;

int area;

int temp;

height=height-1;

temp=width;

if( width > height){  //가로 직사각형

printf("Let's draw 가로 직사각형\n");

while(height >0) {

width=temp;

while(width >0) {

printf("$");

width--;

}

printf("\n");

height--;

}

}

else { //세로 직 사각형

printf("Let's draw 세로 직사각형\n");

}

}

void Main() {

int size;

int result;

size=10;

printf("-----------------draw start------------------\n");

result=make_triangle(size);

printf("result is %d\n",result);

if(result != 0) {

size=5;

make_lectangle(size);

}

else {

printf("Drawing is still on going\n");

}

printf("------------------draw end-------------------\n");

//end test

}

간단한 재귀호출로 삼각형 열개와 사각형 하나를 그리는 예제이다.
가능한 한 예제로 구현가능한 것을 다 보여주려고 애썼다; 위 코드정도는 컴파일이 되며(ㅋㅋㅋ) 실행결과는 아래와 같다.

 

 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 얼마나 뿌듯했던지, 몇일 밤을 고생했다. 이것으로 학교에서의 모든 텀과 시험이 끝나고 졸업만이 남아있다. 참고로 이번 프로젝트는 NCC(NCC is Not C Compiler)를 제작한 선배의 조언을 많이 구했으며, 특별한 감사를 전하고 싶다.