무엇인가
작은 언어의 문법을 클래스 구조로 표현하고, 그 구조를 따라가며 해석한다. 문법 규칙 하나가 노드 하나가 되고, 전체 문장은 노드들의 트리(AST)가 된다.
“패턴”이라 부르지만 실제로는 작은 언어를 만드는 방법에 가깝다. 아키텍처 목록에 들어 있는 이유는, 시스템을 “규칙을 데이터로 두고 해석하는” 모양으로 짜는 선택 자체가 구조적 결정이기 때문이다.
구조
3 + 4 * 2를 트리로 만들면 이렇다. 곱셈이 아래에 있으니 먼저 계산된다 —
우선순위가 계산 로직이 아니라 트리 모양에 들어 있다.
graph TD ADD["+"] --> N3["3"] ADD --> MUL["*"] MUL --> N4["4"] MUL --> N2["2"]
C++로 보기
노드마다 eval() 하나씩. 재귀가 곧 해석이다.
#include <iostream>
#include <memory>
#include <stdexcept>
#include <string>
#include <unordered_map>
using Env = std::unordered_map<std::string, double>;
struct Expr {
virtual ~Expr() = default;
virtual double eval(const Env&) const = 0;
virtual std::string text() const = 0;
};
using ExprPtr = std::unique_ptr<Expr>;
// 종단 표현: 숫자
struct Number : Expr {
double v;
explicit Number(double v) : v(v) {}
double eval(const Env&) const override { return v; }
std::string text() const override { return std::to_string(v); }
};
// 종단 표현: 변수
struct Variable : Expr {
std::string name;
explicit Variable(std::string n) : name(std::move(n)) {}
double eval(const Env& env) const override {
auto it = env.find(name);
if (it == env.end()) throw std::runtime_error("undefined: " + name);
return it->second;
}
std::string text() const override { return name; }
};
// 비종단 표현: 이항 연산
struct Binary : Expr {
char op;
ExprPtr lhs, rhs;
Binary(char op, ExprPtr l, ExprPtr r) : op(op), lhs(std::move(l)), rhs(std::move(r)) {}
double eval(const Env& env) const override {
double a = lhs->eval(env);
double b = rhs->eval(env);
if (op == '+') return a + b;
if (op == '-') return a - b;
if (op == '*') return a * b;
if (op == '/') {
if (b == 0) throw std::runtime_error("divide by zero");
return a / b;
}
throw std::runtime_error("bad op");
}
std::string text() const override {
return "(" + lhs->text() + " " + op + " " + rhs->text() + ")";
}
};
ExprPtr num(double v) { return std::make_unique<Number>(v); }
ExprPtr var(std::string n) { return std::make_unique<Variable>(std::move(n)); }
ExprPtr bin(char op, ExprPtr l, ExprPtr r) {
return std::make_unique<Binary>(op, std::move(l), std::move(r));
}
int main() {
// 3 + 4 * 2 — 곱셈을 아래에 두어 우선순위를 표현한다
ExprPtr e1 = bin('+', num(3), bin('*', num(4), num(2)));
std::cout << e1->eval({}) << "\n";
// (x + y) / 2 — 같은 트리를 환경만 바꿔 여러 번 해석한다
ExprPtr e2 = bin('/', bin('+', var("x"), var("y")), num(2));
std::cout << "x=10,y=20 -> " << e2->eval({{"x", 10}, {"y", 20}}) << "\n";
std::cout << "x=1, y=2 -> " << e2->eval({{"x", 1}, {"y", 2}}) << "\n";
try {
bin('/', num(1), num(0))->eval({});
} catch (const std::exception& ex) {
std::cout << "오류: " << ex.what() << "\n";
}
}한 번 만든 트리를 환경만 바꿔 여러 번 해석한다는 점이 실용적인 값이다. 수식을 문자열로 매번 파싱하는 대신 트리로 두면 반복 평가가 싸진다.
여기에는 파서가 없다. 문자열을 트리로 바꾸는 일은 이 패턴의 범위 밖이고 보통 별도의 파서가 맡는다. 인터프리터 패턴이 정하는 것은 트리의 모양과 평가 방식이다.
언제 쓰나
- 사용자가 규칙이나 수식을 입력하고 그것을 반복 평가해야 할 때(필터 조건, 계산기, 규칙 엔진).
- 문법이 작고 잘 안 바뀔 때. 규칙 수만큼 클래스가 생기기 때문이다.
- 설정을 코드가 아니라 데이터로 두고 싶을 때.
대가
- 문법이 커지면 클래스 폭발. 그 지점부터는 파서 생성기나 별도 VM 쪽이 낫다.
- 노드마다 가상 호출이 일어나므로 빠르지 않다. 뜨거운 경로면 바이트코드 컴파일을 고려한다.
- 재귀 평가라 깊은 입력에서 스택이 터질 수 있다.
실제로 만나는 곳
정규표현식 엔진, SQL 옵티마이저의 표현식 트리, 스프레드시트 수식, 빌드 시스템의 조건식, 그리고 컴파일러 프런트엔드의 AST 자체.