작은 인터프리터는 문장을 어떻게 실행할까? 토큰·파서·AST 원리

인터프리터는 사람이 쓴 텍스트를 읽고 바로 실행하는 프로그램이다. 핵심은 문자열을 곧바로 계산하는 데 있지 않다. 텍스트를 의미 있는 단위로 나누고, 문법 구조를 만들고, 그 구조를 규칙에 따라 평가하는 데 있다.

1 + 2 * 3을 실행한다는 것은 문자를 왼쪽부터 읽는 일이 아니다. 토큰을 만들고, 우선순위를 반영한 구문 트리(AST)를 만들고, 그 트리를 평가하는 일이다.

문자는 어떻게 토큰이 될까

입력은 문자들의 나열이다.

1 + 2 * 3

하지만 계산 규칙은 문자 하나가 아니라 숫자, 연산자, 괄호 같은 의미 단위에서 작동한다. 렉서(lexer) 또는 토크나이저(tokenizer)는 입력을 다음처럼 나눈다.

NUMBER(1)  PLUS  NUMBER(2)  STAR  NUMBER(3)  EOF

공백은 대부분 의미가 없으므로 건너뛴다. 반면 12는 1, 2라는 두 숫자가 아니라 하나의 숫자 토큰으로 읽어야 한다. 이 단계에서 잘못 나누면 이후의 문법과 평가가 모두 흔들린다.

토큰은 어떻게 실행할 구조가 될까

1 + 2 * 3은 보이는 순서대로 (1 + 2) * 3이 아니다. 곱셈이 덧셈보다 먼저 계산되므로 구조는 다음과 같다.

      (+)
     /   \
    1     (*)
         /   \
        2     3

이런 구조를 추상 구문 트리(AST, Abstract Syntax Tree)라고 한다. 트리는 화면에 보이는 괄호가 없어도 우선순위와 결합 방향을 명시한다. 파서(parser)는 토큰 순서를 읽어 문법에 맞는 트리를 만든다.

파서의 역할은 “입력이 맞다/틀리다”를 확인하는 데서 끝나지 않는다. 어떤 부분이 왼쪽 피연산자이고 어떤 부분이 오른쪽 피연산자인지, 연산의 우선순위가 무엇인지 프로그램이 실행할 구조로 바꾼다.

트리는 어떻게 값이 될까

평가기(evaluator)는 노드 종류별 규칙을 적용한다.

숫자 노드      → 숫자 값 반환
덧셈 노드      → 왼쪽을 평가하고 오른쪽을 평가한 뒤 더함
곱셈 노드      → 왼쪽을 평가하고 오른쪽을 평가한 뒤 곱함

위 트리는 먼저 2 * 3을 6으로 평가하고, 마지막에 1 + 6을 계산해 7이 된다. 트리의 형태가 계산 순서를 결정하므로, 평가기는 토큰의 표면 순서를 다시 해석할 필요가 없다.

변수는 어디에 저장될까

let price = 10처럼 이름에 값을 붙이려면 인터프리터는 환경(environment)이 필요하다. 환경은 이름 → 값을 저장하는 해시 테이블처럼 생각할 수 있다.

let price = 10
price + 2

환경
  price → 10

여기서 해시 테이블은 다시 등장한다. 데이터베이스에서는 키를 파일 위치로 연결했고, 인터프리터에서는 변수 이름을 현재 값으로 연결한다. 같은 자료구조도 시스템 안에서 맡는 역할은 달라진다.

이해 확인 질문과 답변

토크나이저가 문자를 바로 계산하지 않고 토큰으로 나누는 이유는 무엇일까?

문자는 의미 단위가 아니다. 12는 한 숫자이고, ==는 두 개의 =와 다른 연산자일 수 있다. 토큰으로 나누면 이후 단계가 숫자, 이름, 연산자라는 명확한 단위로 규칙을 적용할 수 있다.

AST가 있으면 무엇이 좋아질까?

AST는 연산 우선순위와 피연산자 관계를 구조로 고정한다. 따라서 평가기는 1 + 2 * 3을 볼 때 곱셈을 먼저 해야 한다는 문법 규칙을 다시 추측하지 않고, 트리의 자식 노드를 평가하는 규칙만 따르면 된다.

파서와 평가기의 책임은 어떻게 다를까?

파서는 토큰이 문법에 맞는지 확인하고, 실행할 구조를 만든다. 평가기는 그 구조에 의미를 부여해 실제 값을 만든다. 문법 오류와 실행 오류를 구분할 수 있는 것도 이 책임 분리 덕분이다.

변수 환경에 해시 테이블이 어울리는 이유는 무엇일까?

변수 이름을 알면 해당 이름의 현재 값을 빨리 찾아야 하기 때문이다. 충돌과 갱신을 관리하는 해시 테이블은 이름 → 값 연결을 구현하기에 자연스럽다. 단, 변수의 범위와 중첩 함수까지 다루려면 환경을 여러 겹으로 연결하는 추가 규칙이 필요하다.

AI에게 이렇게 요청할 수 있다

다음에 AI에게 구현을 요청한다면 이렇게 요청할 수 있다.

사칙연산과 변수 선언을 지원하는 작은 인터프리터를 설명해 줘. 텍스트가 토큰, AST, 값으로 바뀌는 과정을 보여 주고, 곱셈 우선순위와 변수 환경을 각각 하나의 예시로 설명해 줘.

이 정도로 요청할 수 있다면, 코드를 직접 작성하지 않더라도 인터프리터의 실행 규칙을 어느 정도 통제하고 있는 것이다.