코드는 어떻게 실행될까: 토큰, AST, 바이트코드

배포 전에 디버깅용 console.log를 모두 지우기로 했다. 에디터의 정규식 치환으로 console\.log\(.*\);?를 빈 문자열로 바꿨다. 그런데 결과가 이상하다. 사용 안내 문자열 'console.log()로 값을 찍어 보세요'의 가운데가 잘려 나갔고, 인자가 여러 줄에 걸친 console.log( 호출은 첫 줄만 지워져 문법 오류가 났다.

정규식은 코드를 글자의 줄로 본다. 문자열 안의 글자와 진짜 함수 호출을 구별하지 못하고, 괄호가 어디서 닫히는지도 모른다. ESLint나 ast-grep 같은 도구는 같은 일을 할 때 코드를 먼저 트리로 바꾼다. JavaScript 엔진과 Python 인터프리터(interpreter)도 코드를 실행하기 전에 똑같이 트리를 만든다. 이 장은 1 + 2 * 3 한 줄이 글자 → 토큰 → 트리 → 명령 목록으로 바뀌어 실행되기까지를 직접 짜 보며 따라간다.

토큰화: 글자를 낱말로

사람은 12 + 3 * 4를 보면 "12, 더하기, 3, 곱하기, 4"로 읽는다. 컴퓨터가 받는 것은 글자 10개(공백 포함)다. 첫 단계는 글자를 의미 있는 낱말로 자르는 일이고, 이 낱말을 토큰(token), 자르는 프로그램을 토크나이저(tokenizer) 또는 렉서(lexer)라고 한다. 숫자 글자가 이어지면 하나로 묶고, 공백은 버리고, 기호는 하나씩 자른다.

1const src = '12 + 3 * 4'2const tokens: string[] = []3let i = 04while (i < src.length) {5  const ch = src[i]6  if (ch === ' ') {7    i++8  } else if (ch >= '0' && ch <= '9') {9    let num = ''10    while (i < src.length && src[i] >= '0' && src[i] <= '9') {11      num += src[i]12      i++13    }14    tokens.push('NUM:' + num)15  } else {16    tokens.push('OP:' + ch)17    i++18  }19}20console.log(tokens.join(' '))

NUM:12 OP:+ NUM:3 OP:* NUM:4

파싱: 우선순위는 트리 모양이다

토큰 목록 1 + 2 * 3은 아직 평평한 줄이다. 곱하기를 먼저 한다는 규칙은 어디에도 적혀 있지 않다. 이 규칙을 담는 단계가 파싱(parsing)이고, 결과물이 추상 구문 트리(abstract syntax tree, AST)다. JavaScript에서도 곱하기가 더하기보다 우선순위(precedence)가 높아 3 + 10 * 2는 23이다(MDN: 연산자 우선순위).

손으로 짜기 쉬운 파서는 재귀 하향 파서(recursive descent parser)다. 문법(grammar) 규칙 하나를 함수 하나로 짠다.

우선순위가 높은 연산일수록 호출 사슬에서 더 아래에 있는 함수(expr → term → factor)가 맡는다(곱하기는 term 안에서 끝낸 뒤에야 expr로 돌아오기 때문에 더하기보다 먼저 계산된다).

1const tokens = ['1', '+', '2', '*', '3', 'EOF']2function expr(): number {3  let left = term()4  while (tokens[0] === '+' || tokens[0] === '-') {5    const op = tokens.shift()6    const right = term()7    left = op === '+' ? left + right : left - right8  }9  return left10}11function term(): number {12  let left = factor()13  while (tokens[0] === '*') {14    tokens.shift()15    const right = factor()16    left = left * right17  }18  return left19}20function factor(): number {21  const tok = tokens.shift()!22  if (tok === '(') {23    const inner = expr()24    tokens.shift()25    return inner26  }27  return Number(tok)28}29console.log(expr())

7

계산 대신 노드를 만들어 돌려주면 그대로 AST가 된다.

+  → 7
├─ 1
└─ *  → 6
   ├─ 2
   └─ 3

1 + 2 * 3의 트리는 맨 위가 +이고 *는 그 오른쪽 아래에 달린다. 계산은 아래쪽 노드부터 하므로 *가 먼저 끝난다. 우선순위는 트리의 높낮이로 바뀌었다. 10 - 4 - 3은 왼쪽 -가 아래에 달려 (10 - 4) - 3 = 3이 된다. 같은 우선순위끼리 왼쪽부터 묶는 규칙(왼쪽 결합, left-associative)은 expr의 반복이 지금까지의 결과를 왼쪽 자식으로 넣으며 만든다. 괄호는 트리의 모양만 바꾸고 트리 안에는 남지 않는다.

Python은 자기 코드의 AST를 표준 라이브러리 ast 모듈로 보여 준다(Python 문서: ast). 같은 수식을 넣으면 같은 모양이 나온다(Python 3.14에서 실행한 결과).

>>> import ast
>>> print(ast.dump(ast.parse('1 + 2 * 3', mode='eval'), indent=2))
Expression(
  body=BinOp(
    left=Constant(value=1),
    op=Add(),
    right=BinOp(
      left=Constant(value=2),
      op=Mult(),
      right=Constant(value=3))))

실행: 바이트코드와 JIT

AST를 실행하는 가장 단순한 방법은 트리를 내려가며 노드마다 바로 계산하는 것이다. 이것을 트리 순회 인터프리터(tree-walking interpreter)라고 한다. 짜기는 쉽지만, 노드마다 함수를 부르고 자식을 따라가는 일이 실행할 때마다 되풀이된다. 그래서 많은 엔진은 AST를 한 번 더 바꿔 평평한 명령 목록, 바이트코드(bytecode)를 만든다.

CPython의 바이트코드는 dis 모듈로 볼 수 있다. 문서에 따르면 CPython 인터프리터는 값을 스택에 쌓아 두고 명령이 그 스택에서 값을 꺼내 쓴다. BINARY_OP은 스택 맨 위 두 값을 꺼내 계산하고 결과를 다시 넣는다(Python 문서: dis). 명령의 순서는 노드마다 왼쪽 자식, 오른쪽 자식, 연산자 순으로 내려 적은 순서다. 그래서 아래에 달린 노드의 명령이 그 위 연산자의 명령보다 먼저 나온다.

>>> import dis
>>> def f(a, b, c):
...     return a + b * c
>>> dis.dis(f)
  1           RESUME                   0

  2           LOAD_FAST_BORROW_LOAD_FAST_BORROW 1 (a, b)
              LOAD_FAST_BORROW         2 (c)
              BINARY_OP                5 (*)
              BINARY_OP                0 (+)
              RETURN_VALUE

V8(Chrome과 Node.js의 JavaScript 엔진)도 함수를 먼저 바이트코드로 바꿔 인터프리터 Ignition으로 실행한다. Ignition은 CPython의 스택 대신 레지스터(register, CPU 안의 작은 저장 칸)에 값을 두는 레지스터 기계(register machine) 방식이다(V8 블로그: Ignition). 바이트코드를 해석하며 실행하는 것은 기계어(machine code)보다 느리다. 그래서 V8은 자주 도는 함수를 기계어로 바꾸는 컴파일러(compiler)를 단계별로 둔다. 실행 중에 기계어로 컴파일하는 이 방식을 JIT(just-in-time) 컴파일이라고 한다(V8 블로그: Maglev).

Maglev와 TurboFan은 "이 변수는 늘 숫자였다", "이 객체는 늘 같은 모양이었다" 같은 피드백을 믿고 기계어를 만든다. 가정이 깨지면 그 기계어를 버리고 바이트코드 실행으로 되돌아간다. 이것을 최적화 해제(deoptimization)라고 한다.

객체 모양은 V8이 히든 클래스(hidden class)로 기록한다. 같은 속성을 같은 순서로 가진 객체는 같은 히든 클래스를 쓰고, 속성을 하나 더할 때마다 다른 히든 클래스로 옮겨 간다(V8 블로그: Fast properties). { x, y }로 만든 객체와 { y, x }로 만든 객체는 속성이 같아도 모양이 다르다. 같은 종류의 객체를 한 곳(생성 함수, 클래스 생성자)에서 같은 순서로 만들면 엔진이 모은 피드백이 계속 들어맞는다.

글자로 고치기와 트리로 고치기

처음 장면으로 돌아가자. ESLint 규칙은 소스를 직접 훑지 않는다. ESLint가 코드를 AST로 바꾼 뒤 트리를 내려가고 올라오며 노드를 방문하고, 규칙은 "CallExpression 노드를 만나면 불러 달라"처럼 노드 종류에 함수를 걸어 둔다(ESLint 문서: Custom Rules). ast-grep도 AST를 기준으로 코드를 찾고 고치는 도구다(ast-grep). console.log(...) 호출 노드를 찾으면 문자열 토큰 안의 글자는 처음부터 후보가 아니고, 인자가 몇 줄에 걸쳐 있든 노드 하나로 지워진다. 번들러가 import 문을 찾아 의존성을 잇는 일도 코드를 파싱한 결과 위에서 한다.

직접 짠 코드에서도 같은 차이가 난다. 사용자가 입력한 수식을 계산하는 기능을 AI에게 맡기면 글자를 쪼개는 코드가 나오기 쉽다.

정리하면, 공백으로 쪼개 왼쪽부터 계산하는 코드는 1+2처럼 붙여 쓴 입력을 못 읽고 1 + 2 * 3을 9로 만든다. 빠르다며 eval에 넘기면 수식 대신 들어온 아무 코드나 그 페이지의 권한으로 실행된다. 이 장의 토크나이저와 재귀 하향 파서처럼 허용한 토큰만 받아 트리로 만들어야 한다.

글자 수준의 치환이 늘 나쁜 것은 아니다. 파일 이름 한 줄, 설정 값 하나를 바꾸는 데 파서를 꺼낼 필요는 없다. 바꿀 대상이 코드의 구조(호출, 선언, 괄호의 짝)라면 트리로 다루는 도구를 고른다.

['+', 1, ['*', 2, 3]]
→ PUSH 1, PUSH 2, PUSH 3, MUL, ADD
→ 7