이론없이 컴파일러 만들기 꿈파일러 1

어릴 적 이야기 및 제작동기

어릴 적 이야기. 나는 학교에서 한 반에 있을 법한 컴퓨터를 매우 좋아하는 아이였다. 뭐 누구나 그렇겠지만 좋아하면 더 하고 싶고, 더 공부하고 싶고 그런다. 흘러 흘러 프로그래밍을 배우게 되었고 중3 겨울방학 Win32 API 에 빠져있던 무렵, 나에게 프로그래밍을 알려주는 멘토와 같은 형에게 물어봤다.

Q. 컴파일러 만드는거 어려워?

A. 어렵지 않을까?

그 때 당시는 프로그래밍에 대해서는 걸음마를 하고 있던터라 감히 컴파일러를 만들고 싶은 생각은 무참히 꺾였다. 실제로 알아 보니까 컴파일러를 만드는 과정은 정규 컴퓨터공학과정에서도 4학년에 다룰 정도로 난이도가 있었다. 사실은 수 년전에 컴파일러 비슷한 것을 만들긴 했다. 하지만 그 퀄리티가 너무 떨어지고 너무 급하게 진행했고 툴(lex, yacc)의 도움을 너무 심하게 받았기 때문에 아는 것이 제대로 없는 상태로 지나갔다.

직장생활을 계속 하던 중 머릿속에는 계속 컴파일러 만드는 과정을 한바퀴는 돌려봐야 하지 않을까? 라는 생각이 자꾸 들었다. 그 와중 회사동료가 1인 집짓기를 3년에 걸쳐서 하는 과정을 담은 링크를 보내줬다. 그 과정을 보면서 3년에 걸쳐서 집도 짓는데 키보드만 두들기면 되는 컴파일러 만들기를 못할 이유가 있을까? 생각이 들었고, 곧장 그 작업을 하기 시작했다.

이 때 참고한 두 서적은 컴파일러 책과 가상머신에 대한 책이다.

하지만 내 글에서 __이론적인 이야기는 최대한 배제__하고 진행할 것이다. 어릴 적 간직하고 있는 꿈을 실현한다는 의미로 컴파일러의 이름을 꿈파일러로~~

방법에 대한 개요

일반적인 컴파일러는 토큰화(Lexical Analysis 라고도 부른다) - 구문분석 - 의미분석 - 중간코드생성 - 최적화 - 코드생성 과정을 거친다. 내 글에서는 의미분석과 최적화 코드생성은 개나 줘라 마인드로 과감하게 버린다. 컴파일러에 밀접한 것들만 다루기에도 벅차며, 코드생성에서 아키텍쳐에 대해 종속적인 요소가 있게 되면 컴파일러를 만드는 과정보다 아키텍쳐공부가 더 크다.

구현 방식은 가장 구현하기 편한 방식으로 진행한다. 토큰화만 flex 를 쓰고 나머지 구문분석, 중간코드 생성 및 가상머신 설계까지 다 손수 코딩을 하며 진행한다. 구문분석은 Top-Down 재귀방식으로 구현하겠다. 토큰화 과정을 flex 를 쓴 이유에 대해서 말하자면, 토큰화 과정은 순수하게 노가다과정이며 툴의 도움을 받아도 전체 과정을 이해하기 부족하지 않다. 그리고 타입은 없는 것으로 한다. 정적 타입도 좋지만 해보면 알겠지만 동적 타입이 더 만들기 쉽다.

전체 흐름

토큰화 - 구분분석 - 가상머신이 실행할 수 있는 형태로 코드 생성 - 가상머신 동작

가상머신은 스택기반의 가상머신을 이용한다. 여기서 지역변수를 어떻게 다루는지 이해를 하면서 봐야한다.

토큰화

토큰화는 입력받은 문자열을 기본적인 카테고리로 분류하는 작업을 말한다. 보통 예약 키워드, 자료형, 식별자, 숫자, 사용되는 기호(+, -, *, /, %, !=, == 등등)로 분류한다. 이 과정에는 식별자가 함수이름인지 변수이름인지 모르는 단계다. 예를 들면

abc = 33;
abcd(11, 22, 33);
if a == 33 {
    
}

라는 코드가 있고 토큰화과정을 거친다면 순서대로 배열에 다음과 같이 담길 수 있다.

[id, ‘=’, number, ‘;’, id, ‘(‘, number, ‘,’, number, ‘,’, number, ‘)’, ‘;’, if, id, ‘==’, number, ‘{‘, ‘}’]

말 그대로 1차적인 분류다. 이 분류를 이용해 구문분석이 이뤄진다.

지면이 길어져 이만하고 다음장으로 넘긴다.