주제: 컴파일러를 직접 만들어 보며 얻은 지식, 그리고 체험
이 보고서는 내가 개발한 UBL(Uxntal Bridge Language) 컴파일러의 내부
동작 원리와 변환 파이프라인을 분석한 것이다. UBL 컴파일러는 고수준
언어인 UBL로 작성된 코드를 Uxntal 어셈블리(*.tal)로 변환해
주는 역할을 한다.
*
Uxn은 가상의 CPU이고, Uxntal은 Uxn에서 실행시킬 수 있는 프로그래밍 언어이다.
컴파일러는 고수준의 언어를 저수준의 언어 또는 기계가 이해할 수 있는 언어로 변환해 주는 프로그램을 의미한다.
나는 개발자가 장래 희망이고 컴퓨터 공학에 관심이 많아, 컴파일러를 언젠가 만들어 보고 싶다고 생각했다. 그러던 와중, Uxntal이라는 기계어를 알게 되었고, Uxntal을 위한 고수준 언어가 없다는 것 또한 알게 되었다. 그래서 나는 Uxntal을 위한 컴파일러를 공부하고 직접 만들어보는 프로젝트를 기획하고 개발했다.
내가 만든 이 컴파일러는 크게 세 가지 핵심 단계를 거쳐 작동한다. 입력된 소스 코드는 ‘어휘 분석(Lexing)’, ‘구문 분석(Parsing)’, 그리고 ’코드 생성(Code Generation)’의 단계를 순차적으로 통과하며 최종 어셈블리 코드로 변환된다.
토크나이징(Tokenizing), 렉싱(Lexing) 이라고도 불리는 첫 번째 단계는 사람이 작성한 원시 소스 코드를 컴파일러가 이해할 수 있는 의미 있는 최소 단위인 ’토큰(Token)’으로 쪼개는 과정이다.
lexer.py를 통해 소스 코드를 처음부터 끝까지 문자 단위로
순회하며 다음과 같은 작업을 수행한다.
불필요한 정보 제거: 공백이나 줄바꿈 등은 건너뛰어 문법적 의미가 있는 텍스트만 추출한다.
토큰 분류: 읽어 들인 문자열을 키워드(예:
act, do, if), 구분 기호, 연산자,
숫자 리터럴, 식별자(함수나 변수 이름) 등으로 분류한다.
예외 처리: 원시 어셈블리 코드가 직접 삽입된
블록({@ ... @})을 통째로 하나의 토큰으로 묶어 처리하며,
인식할 수 없는 문자가 등장하면 파일명과 위치 정보를 포함한 오류를
발생시켜 쉽게 디버깅할 수 있도록 돕는다.
결과적으로 소스 코드는 일렬로 나열된 토큰 리스트로 변환되어 다음 단계로 전달된다.
파싱(Parsing)으로 불리는 두 번째 단계는 일렬로 늘어선 토큰 리스트를 문법 규칙에 따라 논리적인 계층 구조로 조립하는 과정이다. 이 과정을 통해 ’추상 구문 트리(AST, Abstract Syntax Tree)’가 만들어진다.
내가 parser.py에 구현한 파서는 ‘재귀 하강(Recursive
Descent)’ 방식을 사용하여 트리를 구성한다.
연산자 우선순위 처리: 논리 연산, 비교 연산, 사칙 연산 등의 우선순위를 함수 호출 체인으로 엄격하게 정의하여 올바른 계산 순서 트리가 구성되도록 하였다.
노드 생성: 함수 정의, 조건문, 반복문, 변수 대입 등 코드의 각 논리적 구조를 트리의 개별 노드로 생성한다. 각 노드는 자신이 어떤 크기의 데이터(8비트 또는 16비트)를 다루는지에 대한 정보도 함께 품는다.
문법 검증: 토큰의 순서가 문법에 맞지 않거나 예상
토큰이 틀리면, 즉시 위치 정보와 함께 구문
에러(SyntaxError)를 발생시킨다.
마지막 단계는 완성된 추상 구문 트리를 순회하면서 실제 목적 파일인 Uxntal 어셈블리 코드를 만들어내는 과정이다.
codegen.py에서 트리의 꼭대기부터 시작해 각 노드의 특성에
맞는 기계어 명령어를 문자열 형태로 덧붙여 나간다.
초기화 및 스코프 관리:
진입점(@on-reset)을 구성하고 메인
함수(act-main)를 호출하도록 기본 뼈대를 구성한다. 또한 현재
컴파일 중인 함수의 스코프를 추적하여 지역 변수들의 메모리 공간을
할당한다.
타입 검사 및 옵코드 매핑: 연산 시 양쪽
피연산자의 크기가 일치하는지 엄격하게 검사한다. 표현식의 결과 크기에
따라 다른 어셈블리 명령어(예: 8비트 더하기는 ADD, 16비트는
ADD2)가 자동으로 선택되어 출력된다.
제어 흐름 구성: if 문이나
while 문 같은 제어 로직은 어셈블리 수준의 분기 및 라벨 점프
코드로 번역된다. 반복문의 경우 시작 라벨과 끝 라벨을 자동으로 생성하여
논리적인 흐름이 끊기지 않게 묶어준다.
사실 나는 예전에, 발표하고 국어 보고서로 제출했던 Lambda Calculus(이하 람다 대수)를 직접 연산할 수 있도록 람다 대수용 파서를 구현한 경험이 있다. 하지만 람다 대수는 이항 연산자가 없는 표현 형식을 취하기 때문에, 이항 연산과 연산자 우선순위에 대해 생각하지 않아도 됐다. 하지만 이번에 만든 UBL에는 이항 연산자와 연산자 우선순위가 존재했다.
이항 연산자 우선순위를 파싱하는 방법은 생각보다 간단했다. 이항(binary) 연산자를 분석하는 만큼, 제귀 이진 탐색을 하듯이 분석하면 되는 것이었다.
우선순위가 가장 낮은 연산자를 우선으로, 우선순위가 순차적으로 높은 연산을 이진 탐색으로 분석하면 됐다.
a+b*c
라는 표현식이 있다면, +를 기준으로 a와
b*c로 나누고, b*c는 *를 기준으로
b와 c로 나누면 되는 것이다.
이번 컴파일러 제작을 기회로, 기존에 불필요했던 지식이 어떤 문제의 해답이었다는 걸 알고, 그 문제를 해결하는 법까지 알게 되었다.
사실 내 컴파일러에는 몇 가지 단계가 생략되어 있다. 그중 하나가 바로, AST Type Checking(추상 구문 트리 타입 확인)인데, 서로 다른 타입의 변수가 불가능한 연산을 수행하는지, 변수에 알맞은 타입의 변수 또는 값이 대입되는지 확인하는, 즉, 구문 분석에서 분석한 문법이 올바른 문법인지 확인하는 것이다.
나는 컴파일러에 대해 잘 모르는 채로, 컴파일러를 공부하기 위해 이
프로젝트를 시작했기에, 이 사실을 알았을 때는 이미 코드 생성의 구현
대부분을 마친 상태였다. 그래서 선택한 것은, 타입 확인을 코드 생성
단계에서 하는 것이었다.
이 문제를 해결하는 방법도 사실 앞의 이항 연산자 우선순위와 비슷한데,
제귀적으로 확인하는 것이다.
a+b*c
라는 표현식의 타입을 확인해야 한다면, 이항 연산자 우선순위로 분석된
우선순위가 (a+(b*c)) 일 것이다. 이때, a의
타입을 확인하고, (b*c)의 타입을 확인해야 하는데, 제귀적으로
(b*c) 의 타입을 확인한 결과를 사용하는 것이다.
(b*c) 의 타입은 역시 b의 타입과
c의 타입을 사용해 만들어진다.
위 과정에서 두 타입이 다르다면 에러가 나게 되는 것이다.
최신 언어들은 모두 변수를 거의 어디서든 선언할 수 있다. 이런 식으로 말이다.
변수 선언
계산
변수 선언
계산하지만 내 언어는 그렇지 않다. 변수를 사용하기 위해 변수 공간을 직접 지정해 줘야 했기 때문이다. 어떤 작업 도중에 공간이 부족해서 늘릴 수 없고, 작업을 하기 전에 필요한 공간을 미리 계산해서 작업 시작 전에 작업 공간을 요청해야 한다. 그러므로, 내 언어에서는 함수를 정의할 때, 함수에서 사용되는 변수들을 모두 선언한 뒤, 함수의 수식을 작성한다.
변수 선언
변수 선언
계산
계산사실, 이런 특징은 실제로 오래된 언어에서도 발견된다. 예를 들어 현재까지 쓰이는 오래된 언어인 C언어의 경우, 예전 버전인 C89에서는 함수의 맨 앞에 변수를 모두 선언해야 했다. 내 언어와 마찬가지로 말이다.
이런 특징들은 내가 처음에 예상하지 못한 채로 컴파일러를 만들기 시작했지만, 컴파일러를 만들면서 그 과정에서 자연스레 깨닫게 된 것이다. 이렇게 예전의 언어를 자연스레 따라가게 되는 것이, 프로그래밍의 역사를 내 몸으로 체험하는 것 같아 굉장히 신선한 경험이었다.
이번 UBL 컴파일러 프로젝트는 단순히 고수준 언어를 어셈블리로 변환하는 도구를 만드는 것을 넘어, 컴파일러의 전체 파이프라인과 내부 동작 원리를 깊이 있게 이해하는 계기가 되었다.
어휘 분석, 구문 분석, 코드 생성이라는 세 가지 컴파일러 핵심 단계를 직접 구현하는 과정에서 수많은 고민을 거쳤다. 람다 대수 파서 개발 경험을 바탕으로 이항 연산자 우선순위를 재귀적으로 파싱하는 구조를 정립하였고, 코드 생성 단계에 재귀적 타입 검사 로직을 녹여내어 타입 안정성을 확보했다. 또한 Uxntal의 메모리 특성에 맞춰 C89 스타일의 변수 선언 제약을 도입하게 된 과정은 언어 설계와 저수준 메모리 관리 간의 긴밀한 관계를 체득할 수 있게 해주었다. 이러한 저수준 메모리 관련 지식을 추후 보안 관련으로도 뻗어 여러 가지를 배우고 싶다.
프로젝트를 진행하며 배우고 정리한 컴파일러의 구조와 구현 과정에 대한 내용을 개인적으로 글로 작성하여 블로그에 배포하였다. 이를 통해 프로젝트에서 배운 내용을 다시 정리하고, 내가 이해한 내용을 다른 사람이 읽을 수 있는 형태로 기록할 수 있었다.
결과적으로 UBL 소스 코드가 이 컴파일 파이프라인을 거쳐 정교한 어셈블리 코드로 번역되고, 최종적으로 에뮬레이터 환경에서 정상 작동하는 전체 생태계를 완성할 수 있었다. 시행착오를 거치며 옛 프로그래머들이 고민했던 문제와 역사를 직접 체험할 수 있었다. 이번 경험을 기반으로 앞으로 더 복잡하고 정교한 시스템을 설계해보고 싶다.