컴파일러 파이프라인

① 직접 돌려보는 미니 컴파일러

② 렉서: 글자를 토큰으로 자르기

렉서(어휘 분석기)는 소스 문자열을 왼쪽에서 오른쪽으로 한 글자씩 읽으며, 의미 있는 최소 단위인 토큰으로 묶는다. 공백은 버리고, 숫자는 이어 붙이고, + * ( 같은 기호는 각각 하나의 토큰이 된다.

function lex(src) {
  const tokens = [];
  let i = 0;
  while (i < src.length) {
    const c = src[i];
    if (c === ' ') { i++; continue; }              // 공백은 무시
    if (/[0-9]/.test(c)) {                          // 숫자: 연속된 자릿수를 모음
      let n = '';
      while (/[0-9.]/.test(src[i])) n += src[i++];
      tokens.push({ type: 'NUM', value: parseFloat(n) });
      continue;
    }
    if (/[a-zA-Z_]/.test(c)) {                      // 식별자(변수 이름)
      let s = '';
      while (/[a-zA-Z0-9_]/.test(src[i])) s += src[i++];
      tokens.push({ type: 'NAME', value: s });
      continue;
    }
    if ('+-*/()'.includes(c)) {                     // 연산자 · 괄호
      tokens.push({ type: 'OP', value: c }); i++;
      continue;
    }
    throw new Error('알 수 없는 문자: ' + c);
  }
  tokens.push({ type: 'EOF' });                     // 끝 표시
  return tokens;
}

③ 파서: 토큰을 트리로 — 문법과 우선순위

파서(구문 분석기)는 토큰 열이 문법 규칙에 맞는지 확인하면서 AST(Abstract Syntax Tree, 추상 구문 트리)를 만든다. 아래는 사칙연산 문법을 재귀 하강(recursive descent) 방식으로 표현한 것이다. 함수가 문법 규칙 하나에 대응한다.

expr   → term  (('+' | '-') term)*      // 덧셈·뺄셈: 가장 느슨하게 묶임
term   → factor (('*' | '/') factor)*   // 곱셈·나눗셈: 더 강하게 묶임
factor → NUMBER | NAME
       | '(' expr ')'                    // 괄호는 우선순위를 강제로 올림
       | '-' factor                      // 단항 마이너스

function parseExpr() {
  let node = parseTerm();
  while (peek() === '+' || peek() === '-') {
    const op = next();
    node = { type: 'BinOp', op, left: node, right: parseTerm() };
  }
  return node;
}
function parseTerm() {
  let node = parseFactor();
  while (peek() === '*' || peek() === '/') {
    const op = next();
    node = { type: 'BinOp', op, left: node, right: parseFactor() };
  }
  return node;
}

핵심은 덧셈을 곱셈보다 먼저 함수로 호출한다는 점이다. 그러면 곱셈이 트리의 더 아래쪽(=더 먼저 계산됨)에 놓여, 우리가 배운 연산 우선순위가 트리 구조 자체로 표현된다. 3 + 4 * 2 의 AST는 이렇게 된다:

      (+)
     /   \
   3     (*)
        /   \
       4     2      →  4*2 를 먼저, 그 다음 3+8 = 11

④ AST 평가: 나무를 훑어 계산하기

AST가 생기면 나머지는 쉽다. 각 노드를 재귀적으로 방문한다 — 잎(숫자·변수)은 값을 그대로 돌려주고, 연산 노드는 양쪽 자식을 먼저 계산한 뒤 연산을 적용한다. 이 방식이 바로 파이썬·루비·자바스크립트 초기 구현이 쓰던 트리 순회 인터프리터다.

function evalNode(node, env) {
  switch (node.type) {
    case 'Num':   return node.value;
    case 'Name':  return env[node.value];           // 변수 테이블에서 조회
    case 'BinOp': {
      const l = evalNode(node.left,  env);          // 왼쪽 서브트리 먼저
      const r = evalNode(node.right, env);          // 오른쪽 서브트리
      if (node.op === '+') return l + r;
      if (node.op === '-') return l - r;
      if (node.op === '*') return l * r;
      if (node.op === '/') {
        if (r === 0) throw new Error('0으로 나눌 수 없음');
        return l / r;
      }
    }
    case 'Neg':   return -evalNode(node.operand, env);
  }
}

⑤ 코드 생성: 트리 대신 바이트코드

실제 언어는 매번 트리를 훑으면 느리므로, AST를 한 번 스택 기반 가상머신(VM) 명령어로 번역해 둔다. 후위 순회하며 잎에서는 PUSH, 연산 노드에서는 ADD/SUB/MUL/DIV 를 뿜으면 된다. 위 데모의 마지막 상자가 3 + 4 * 2 를 아래처럼 바꾼다:

PUSH 3
PUSH 4
PUSH 2
MUL        ; 스택: [3, 8]
ADD        ; 스택: [11]

파이썬은 이 바이트코드를 .pyc 파일에 캐싱하고, 자바는 .class 로, 자바스크립트 V8·자바 JIT은 여기서 한 발 더 나아가 기계어로 실시간 컴파일(JIT) 한다.

⑥ 인터프리터 vs 컴파일러