우리는 프로그래밍을 할 때 소스 코드source code를 실행시킵니다. 파이썬Python 코드를 컴퓨터에서 동작시키는 것이 대표적인 사례입니다. 하지만 사실 컴퓨터는 그런 코드를 직접 이해할 수 없고, 대신 명령어 세트instruction set만 알아듣습니다. 비트bit로 표현된 이 명령들은 머신 코드machine code라고도 부릅니다.

그래서 소스 코드와 기계어 사이를 이어주는 프로그램, 즉 컴파일러compiler나 인터프리터interpreter가 필요하게 됩니다.

source code to machine language — 그림 1. 소스 코드부터 머신 코드까지. 컴파일러가 소스 코드를 머신 코드로 만들면 컴퓨터가 이를 읽고 실행합니다, 인터프리터는 소스 코드를 읽고 실행합니다.

컴파일러는 소스 코드를 기계어로 바꾸는 프로그램을 말합니다. 특정한 명령어 세트를 목적지라고 생각하는 데서 소스source라는 표현이 의미를 가지게 됩니다. 한편 인터프리터는 소스 코드를 이해하는 프로그램을 기계어로 미리 만들어 놓은 것입니다.

컴파일러와 인터프리터는 방대한 주제이지만, 그럼에도 불구하고 간단한 인터프리터는 만들어 볼만합니다. 만든다고 해서 아예 처음부터 만들 필요는 없습니다. 인터프리터는 이미 만들어진 인터프리터로 만들 수 있기 때문입니다.

여기서는 함수를 변수처럼 값으로 취급하는 함수형 프로그래밍 언어functional programming language를 구현해보겠습니다. 이 내용을 통해, 소스 코드부터 실제 실행에 이르기까지의 구체적인 과정을 이해하게 될 것입니다. 변수는 어떻게 관리되는지, 함수는 어떻게 호출되는지 등을 직접 만들어보면서 알아볼 것이기 때문입니다.

언어 디자인 하기

간략한 설명을 위해, 여기서 만들 언어는 간단한 문법만 갖출 것입니다. 우리의 목표는 사칙 연산과 변수 대입, 그리고 함수 호출을 할 수 있는 정도이고, 완성된 모습은 다음과 같습니다.

g = 98/10
y = t -> y0 -> g*t*t/2 + y0
y(10)(5)

예시 코드는 자유 낙하 운동 시뮬레이션, 즉 물체를 위치 y0에서 놓았을 때 t초 후 위치 y를 구하는 간단한 프로그램입니다. 내용이 중요한 것은 아니니 전체적인 모습만 참고하세요. 언어를 완성했을 때 실제로 이 코드를 실행해볼 것입니다.

숫자 값은 98 처럼 정수integer를 쓸 것입니다. 즉 소수점을 가진 숫자는 구현을 생략합니다. g나 y처럼 알파벳은 변수variable나 함수function 이름이 될 것입니다. 사실 변수와 함수를 구분하지 않을 것이므로, 혼동의 여지없이 둘 다 변수라고 부를 것입니다. 함수를 이렇게 변수 취급 할 수 있는 것은 함수형 언어의 특징입니다.

또 다른 제약 사항으로, 함수는 단 하나의 매개변수parameter만 가질 것입니다. 하지만 그럼에도 커링currying과 클로저closure를 통해 함수가 여러 개의 매개변수를 가진 것처럼 만들 수 있습니다. 사실 하스켈Haskell과 같은 함수형 언어가 이런식으로 동작합니다.

예시 코드의 함수 y가 그런 경우입니다. 함수 호출 시 y(10)(5)와 같은 식으로 마치 두 개의 호출 인자call argument를 전달하는 것처럼 표현할 수 있습니다. 커링과 클로저는 추후 더 살펴볼 기회가 있을 것입니다.

프로그래밍 언어 구현 단계

프로그래밍 언어의 구현은 크게 세 단계로 나눌 수 있습니다.

language implementation steps — 그림 2. 프로그래밍 언어 구현 세 단계. 소스코드에서 평가 값에 이르기까지 토큰화와 파싱을 거칩니다.

먼저 소스 코드의 문자들을 의미 단위로 나눕니다. 그 단위를 흔히 토큰token으로 부르고, 토큰으로 나누는 작업을 토큰화tokenize라고 부릅니다. 예를 들어 ‘1+23’이라는 코드를 세 개의 토큰 ‘1/+/23’으로 나누는 작업입니다.

토큰을 만들면 소스 코드가 문법에 맞는지 확인할 수 있습니다. 이어서 그 문법을 상징하는 트리tree를 만들 수 있는데, 추상 문법 트리abstract syntax tree, 또는 AST라고도 부릅니다. 파싱parsing이라고 부를 이 작업은 토큰을 받아 문법 트리를 결과로 낼 것입니다. 예를 들어 ‘1/+/23’ 라는 세 토큰에서 일종의 ‘덧셈 노드’를 만들 수 있습니다.

이렇게 만든 트리는 다양한 방법으로 처리할 수 있습니다. 간단하게는 트리를 바로 어떤 값으로 평가evaluate할 수 있는데요. 여기서 만들 인터프리터가 그렇게 할 것입니다. 예를 들어, 방금 예시에서 만든 ‘덧셈 노드’를 평가해 24이라는 결과를 낼 수 있습니다.

한편 이 트리를 다른 언어로 바꿀 수도 있습니다. 컴파일러는 코드 생성code generation이라고 부르는 단계를 거쳐 다른 언어를 결과로 내놓습니다. C++ 같은 언어의 컴파일러는, 타겟 기계가 이해하는 코드, 즉 기계어를 생성합니다. 한편 자바Java 같은 언어는 가상의 기계가 타겟인데, 흔히 가상 머신virtual machine이라고 부르는 것입니다. 자바가 사용하는 JVM, 즉 Java virtual machine이 바로 그 구현체입니다.

인터프리터 디자인

정리하면 여기서 만들 인터프리터는 아래 수도코드와 같습니다.

인터프리터 (코드)

토큰 $\leftarrow$ 토큰화(코드)

문법 트리 $\leftarrow$ 파싱(토큰)

값 $\leftarrow$ 평가(문법 트리)

리턴 값

여기서는 토큰화를 본격적으로 만들어보겠습니다.

의미 단위로 나누기

토큰화란 무엇인지 설명하기 위해 다음과 같은 코드를 예로 들어봅시다.

g = 98/10

토큰화란 g, =, 98, /, 10과 같이 나누는 것을 말합니다. 여기서 주목할 것은 각각이 온전한 하나의 의미를 가진다는 사실입니다. (그래서 9와 8이 아니라 98로 나눴습니다.)

이런 작업엔 토크나이저tokenizer, 렉서lexer, 또는 스캐너scanner 등의 이름이 있지만, 여기서는 토크나이저라고 부르겠습니다.

소스 코드란 문자열에 불과하고, 토크나이저는 문자를 하나씩 읽게 됩니다. 그런데 그 과정에서 다음 문자를 미리 볼 수밖에 없습니다. 예를 들어, 98과 같은 숫자만 하더라도, 이 숫자가 언제 끝날지 알려면 8 다음에 무엇이 오는지 미리 알아야 합니다.

이런 문제는 토큰화 과정에서 반복적으로 나타납니다. 따라서 이를 처리하기 위한 부분을 먼저 간단히 만들어보겠습니다.

문자 읽기

문자를 하나씩 읽는 리더 클래스를 만들어봅시다. 예를 들어 파이썬으로 이렇게 구현할 수 있습니다.

class CharReader:
    def __init__(self, source: str):
        self.source = source
        self.pos = 0 # index to read next

이 클래스는 소스 코드를 받아 인스턴스를 만들 것입니다. 내부적으로는 다음에 읽을 문자 위치를 pos로 기억해둡니다.

문자를 읽는 것과, 다음 문자 위치로 이동하는 메소드는 따로 만들겠습니다. 각각 read(), advance() 메소드로 구현합니다. 이렇게 다음 문자를 미리 봐야 하는 문제를 해결할 것입니다.

    def read(self) -> str:
        # ...

    def advance(self) -> None:
        # ...

만약 다음 문자를 미리 보고 싶다면, read() 메소드만 호출하고 advance() 호출은 하지 않으면 됩니다.

먼저 현재 위치의 문자를 읽는 메소드를 만듭시다.

    def read(self) -> str:
        if self.pos == len(self.source):
            return "\0"

        return self.source[self.pos]

소스 코드 끝에 도달하면 널 문자(\0)를 주는 것으로 만들었습니다. 이렇게 하면 read() 메소드를 호출하기 전에 소스 코드를 다 읽었는지 따로 검사할 필요가 없어질 것입니다.

이제 다음 문자로 이동하는 메소드를 만들어 클래스를 완성합니다.

    def advance(self) -> None:
        if self.pos == len(self.source):
            return

        self.pos += 1

소스 코드 끝에 도달하면 아무 것도 하지 않습니다. 즉 read() 메소드가 널 문자를 주도록 만듭니다.

이 클래스는 다음과 같이 사용할 수 있습니다.

reader = CharReader("12")
reader.read() # == "1"
reader.advance()
reader.read() # == "2"
reader.advance()
reader.read() # == "\0"

토큰화하기

여기서 만들 토크나이저는 다음과 같은 토큰 타입을 이용할 것입니다.

class Token:
    def __init__(self, kind: str, value: str = ""):
        self.kind = kind
        self.value = value

예를 들면 다음처럼 덧셈 토큰이나 숫자 토큰을 만들 것입니다.

Token("+") # plus token
Token("number", "123") # number token

이제 토큰화를 맡는 토크나이저를 만들어봅시다. 이 클래스는 소스 코드로 인스턴스를 초기화합니다.

class Tokenizer:
    def __init__(self, source: str):
        self.reader = CharReader(source)

토큰을 하나 만드는 메소드를 구현해봅시다.

    def tokenize(self) -> Token:
        self.skipWhitespace()

        char = self.reader.read()
        self.reader.advance()

        if char in "()+*/=":
            return Token(char)

먼저 skipWhitespace() 메소드로 공백 문자는 건너 뜁니다. 그리고 문자를 읽자마자 바로 토큰을 결정할 수 있으면 그렇게 합니다.

공백 문자를 건너뛰는 보조 메소드는 다음과 같이 쉽게 만들 수 있습니다.

    def skipWhitespace(self) -> None:
        while self.reader.read() == " ":
            self.reader.advance()

만약 - 문자를 만나면, 다음 문자에 따라 토큰을 결정합니다. 경우에 따라 -> 토큰이나 - 토큰을 만들게 됩니다.

    def tokenize(self) -> Token:
        # ...

        if char == "-":
            nextChar = self.reader.read()
            if nextChar == ">":
                self.reader.advance()
                return Token("->")

            return Token("-")

만약 숫자를 만났다면 다음 문자도 숫자인지 보고 토큰을 결정해야 합니다. 얼마나 많은 문자를 읽어야 할지 모르기 때문에, 숫자가 아닐 동안 계속 읽습니다.

    def tokenize(self) -> Token:
        # ...

        if char.isdigit():
            chars = [char]
            while True:
                nextChar = self.reader.read()
                if nextChar.isdigit():
                    self.reader.advance()
                    chars.append(nextChar)
                    continue

                value = "".join(chars)
                return Token("number", value)

한편, 알파벳 문자를 만난다면 변수 이름일 것입니다. 식별자identifier라고도 부릅니다. 예를 들어, 소스 코드에서 foo를 읽었다면 식별자 토큰이 만들어질 것입니다. 뒤에 숫자가 붙은 foo123 같은 것도 그렇습니다.

여기서는 토큰화를 간단히 하기위해, 변수는 숫자로 시작할 수 없도록 할 것입니다. 왜냐면 숫자라고 생각해서 읽다가 식별자로 만들기가 번거롭기 때문입니다. 사실 많은 프로그래밍 언어가 이런 규칙을 가집니다. 이제는 왜 그런 규칙이 있는지 조금은 이해가 될 것입니다.

식별자 토큰은 숫자 토큰을 만드는 방법과 비슷하기 때문에, 직접 만들어보는 부분으로 남겨두겠습니다.

토크나이저 완성하기

이제 모든 토큰을 리턴하는 메소드를 다음과 같이 만들 수 있습니다. 앞으로 만들 파서는 이 메소드를 이용할 것입니다.

    def getTokens(self) -> List[Token]:
        tokens: List[Token] = []
        while self.reader.read() != "\0":
            tokens.append(self.tokenize())
        tokens.append(Token("END"))

        return tokens

여기서 END 라는 종료 토큰을 명시적으로 맨 뒤에 넣습니다. 이를 통해 파서는 소스 코드의 끝을 알 게 될 것입니다.

이 토크나이저는 다음과 같이 사용할 수 있습니다.

tokens = Tokenizer("12 + abc34").getTokens()

tokens[0].kind # == "number"
tokens[0].value # == "12"

tokens[1].kind # == "+"

tokens[2].kind # == "identifier"
tokens[2].value # == "abc34"

토크나이저는 소스 코드가 문법에 맞는지 아닌지 확인하지 않습니다. 즉 12 = 34 같은 코드도 아무 불만 없이 토큰화합니다. 왜냐면 문법 검사는 토크나이저의 역할이 아니기 때문입니다. 문법은 파싱 단계에서 확인할 것입니다.

마치며

인터프리터의 토크나이저 부분을 구현해보았습니다. 토크나이저가 생성한 토큰은 앞으로 만들 파서의 입력이 될 것입니다.

간단한 구현을 위해 스트링string과 불리언boolean 타입, 조건문과 반복문 등을 생략했습니다. 인터프리터를 완성하고나면, 돌아와서 빠진 부분을 구현해보는 것도 어렵지 않을 것입니다.

그 중에 반복문을 만드는 방법을 간단히 언급하고 넘어가보겠습니다. 예약어reserved keyword를 두는 방법이 있는데, for 라는 반복문을 만들고 싶다면 프로그래머가 for를 변수 이름 같은 것으로 쓰지 못하도록 만드는 것입니다. 토크나이저 수준에서 for를 만나면, 식별자 토큰 대신 예약어 토큰을 만들어냄으로써 구현할 수 있습니다.

한편, 반복문을 직접 지원하지 않고, 재귀recursion로 반복을 수행하도록 프로그래머에게 맡길 수도 있습니다. 하스켈을 비롯한 함수형 프로그래밍 언어가 이런 방법을 사용합니다. 대신 콜 스택call stack으로 인한 메모리 사용을 개선하기 위해, 꼬리 재귀 최적화tail recursion optimization와 같은 부분이 중요하게 됩니다.

여기까지 생략된 부분을 포함한 코드는 지스트Gist에서 볼 수 있습니다.

레퍼런스

Writing An Interpreter In Go (Thorsten Ball, 2020), 또는 밑바닥부터 만드는 인터프리터 in Go (2021): 테스트 코드와 함께 Go 언어로 인터프리터를 구현하는 방법이 소개되어 있습니다.
만들면서 배우는 컴파일러 첫걸음 (나카다 이쿠오, 2021): 간단한 컴파일러를 구현하며 비교적 이론적인 내용에 중점을 둔 책입니다.
The Elements of Computing Systems (Shimon Schocken, Noam Nisan, 2021), 또는 밑바닥부터 만드는 컴퓨팅 시스템 (2023): 후반부에서 자바와 같은 객체지향 프로그래밍 언어를 가상 머신을 통해 구현하는 방법을 다룹니다.