우리는 프로그래밍을 할 때 소스 코드source code를 실행시킵니다. 예를 들면 파이썬Python 코드를 컴퓨터에서 동작시킬 수 있는데요. 하지만 컴퓨터는 그런 코드를 이해할 수 없고, 명령어 세트instruction set라는 것을 통해서만 명령을 내릴 수 있습니다. 비트bit로 표현된 이런 것을 머신 코드machine code라고도 부릅니다.

그래서 소스 코드와 기계어 사이를 이어주는 프로그램이 필요한데요. 그 역할을 맡는 것을 크게 두 종류, 컴파일러compiler와 인터프리터interpreter로 나눌 수 있습니다.

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

컴파일러와 인터프리터는 방대한 주제이지만, 그럼에도 불구하고 간단한 인터프리터는 만들어 볼만한데요. 여기서는 함수를 변수처럼 값으로 취급하는 함수형 프로그래밍 언어functional programming language를 구현해보겠습니다. 이를 통해 소스 코드로부터 실제 실행에 이르기까지 구체적으로 어떤 일이 일어나는지 살펴볼 수 있습니다.

만들 언어의 모습

여기서 만들 언어는 간단한 문법만 갖출 것입니다. 목표는 사칙 연산과 변수 대입, 그리고 함수 호출을 할 수 있는 정도인데요. 아래 코드와 같은 모습입니다.

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

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

숫자 값은 98 처럼 정수integer를 쓸 것입니다. 즉 소수점을 가진 숫자는 구현을 생략하고요. g나 y처럼 알파벳은 변수variable나 함수function 이름이 될 것입니다. 사실 변수와 함수를 구분하지 않을 것이므로, 둘 다 변수라고 부르는 일이 많을 것입니다.

이 언어에서는 함수가 단 하나의 매개변수parameter만 갖도록 강제할 것입니다. 그럼에도 커링currying과 클로저closure를 통해 함수가 여러 개의 매개변수를 가진 것처럼 만들 수 있습니다.

예시 코드의 함수 y가 그런 경우인데요. 함수 호출 시 y(10)(5)와 같은 식으로 두 개의 호출 인자call argument를 전달합니다. 이런 식으로 마치 두 개의 매개변수를 받는 것처럼 다룰 수 있습니다. 이 부분은 직접적인 관련이 있는 나중에 다시 살펴볼 기회가 있을 것이므로 이 정도로 언급만 하고 넘어가겠습니다.

프로그래밍 언어 구현 단계

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

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

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

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

한편 이 트리를 다른 언어로 바꿀 수도 있습니다. 컴파일러가 코드 생성code generation이라고 부르는 이 단계를 거치는데요. C++ 같은 언어의 컴파일러는, 타겟 기계가 이해하는 코드, 즉 기계어를 생성합니다. 한편 자바Java 같은 언어는 가상의 기계를 대상으로 두고 그런 작업을 하는데요. 보통 그런 기계는 가상 머신virtual machine이라고 불립니다. 자바가 사용하는 JVMJava virtual machine은 그 구현체 중 하나입니다.

인터프리터 디자인

정리하면 여기서 만들 인터프리터는 아래 수도코드의 구현입니다.

이 글에서는 토큰화 부분을 본격적으로 만들어보겠습니다.

의미 단위로 나누기

예를 들어 다음과 같은 코드가 있다고 해봅시다.

g = 98/10

이 코드는 토큰화를 통해 g, =, 98과 같이 나눌 수 있는데요. 그런 작업을 하는 프로그램에는 토크나이저tokenizer, 렉서lexer, 또는 스캐너scanner 라는 다양한 이름이 있지만, 여기서는 토크나이저라고 부르겠습니다.

토크나이저를 구현할 때 만나게 되는 대표적인 문제로, 다음 문자를 미리 봐야하는 것이 있습니다. 예를 들어 여기서 만들 언어에는 - 토큰과 -> 토큰이 있는데요. 그래서 - 문자를 읽었을 때, 다음이 > 문자인지 읽어야 둘 중 하나로 토큰을 결정할 수 있습니다.

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

문자 읽기

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

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

인스턴스를 만들 때 받은 소스 코드와, 다음에 읽을 문자 위치를 내부적으로 기억해둡니다.

이 클래스는 현재 위치의 문자를 읽는 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 같은 코드도 아무 불만 없이 토큰화할 텐데요. 문법은 파싱 단계에서 확인할 것입니다.

마치며

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

간단한 구현을 위해 생략한 부분이 많습니다. 스트링과 불리언boolean 타입의 값, 조건문과 반복문 등이 이에 해당합니다. 여기서 이런 것을 만들지는 않을 것이지만, 여러 방법은 언급하는 정도로 짚어볼 만한데요.

예를 들어 반복문 구현을 위한 한 가지 방법으로, 예약어reserved keyword를 둘 수 있습니다. 즉 언어의 반복문 문법에서 for 라는 식별자를 쓰고 싶다면, 프로그래머가 for를 변수 이름과 같은 곳에 쓰지 못하도록 만드는 것입니다. 이는 토크나이저 수준에서 for를 만나면, 식별자 토큰 대신 예약어 토큰을 만들어냄으로써 구현할 수 있습니다. 아니면 반복문을 직접적으로 지원하지 않고, 재귀recursion로 반복을 수행하도록 프로그래머에게 맡길 수도 있습니다. 하스켈Haskell을 비롯한 함수형 프로그래밍 언어가 이런 방법을 사용하는데요. 대신 콜 스택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): 후반부에서 자바와 같은 객체지향 프로그래밍 언어를 가상 머신을 통해 구현하는 방법을 다룹니다.