로그 뷰어에 “레벨 3 이상이면서 커널에서 왔거나 메시지에 oom이 들어간 줄” 같은 조건을 넣고 싶다. 조건 조합마다 체크박스와 코드를 추가할 수는 없으니, 사용자가 level >= 3 and (src == kernel or msg ~ oom)처럼 작은 언어로 조건을 쓰게 하는 편이 낫다. 인터프리터(Interpreter)는 간단한 언어의 문법 규칙 하나하나를 클래스로 표현하고, 문장을 그 클래스들의 트리(추상 구문 트리)로 만든 뒤 트리를 따라 해석한다. 이 글에서는 로그 필터 언어를 만들어 해석하고, 문법 오류 보고, 트리를 클로저로 “컴파일”하는 최적화, C의 후위 표기 스택 인터프리터를 다룬다. GoF 23개 패턴 시리즈의 마지막 편이다.
이 시리즈의 다른 글
구조
| 참여자 | 역할 | 예제 |
|---|---|---|
| AbstractExpression | interpret(context) 선언 | Expr |
| TerminalExpression | 더 쪼개지지 않는 문법 기호 해석 | Compare (level >= 3) |
| NonterminalExpression | 다른 식을 조합하는 규칙, 자식을 재귀 해석 | And, Or, Not |
| Context | 해석에 필요한 전역 정보 | 로그 한 줄의 필드 맵 |
| Client | 문장으로 트리를 만들고(파서) 해석을 요청 | Parser, main() |
GoF 인터프리터 패턴은 트리를 해석하는 부분만 다루고, 문장을 트리로 바꾸는 파싱은 범위 밖으로 둔다. 예제에서는 문법을 그대로 옮긴 재귀 하강 파서를 함께 만들었다.
로그 필터 언어
// filter.hpp — 로그 필터 언어: 문법 규칙 하나 = 클래스 하나
// expr := term ('or' term)*
// term := factor ('and' factor)*
// factor := 'not' factor | '(' expr ')' | field op value
// op := '==' | '!=' | '>=' | '<=' | '~'
#pragma once
#include <map>
#include <memory>
#include <stdexcept>
#include <string>
using Context = std::map<std::string, std::string>; // 해석 문맥: 로그 한 줄의 필드
struct Expr { // AbstractExpression
virtual ~Expr() = default;
virtual bool interpret(const Context &c) const = 0;
virtual std::string str() const = 0;
};
using ExprP = std::unique_ptr<Expr>;
struct Compare : Expr { // TerminalExpression
std::string field, op, value;
Compare(std::string f, std::string o, std::string v) : field(std::move(f)), op(std::move(o)), value(std::move(v)) {}
bool interpret(const Context &c) const override
{
auto it = c.find(field);
if (it == c.end()) return false;
const std::string &x = it->second;
if (op == "==") return x == value;
if (op == "!=") return x != value;
if (op == "~") return x.find(value) != std::string::npos;
long a = std::stol(x), b = std::stol(value); // >=, <=는 숫자 비교
return op == ">=" ? a >= b : a <= b;
}
std::string str() const override { return field + op + value; }
};
struct And : Expr { // NonterminalExpression
ExprP l, r;
And(ExprP a, ExprP b) : l(std::move(a)), r(std::move(b)) {}
bool interpret(const Context &c) const override { return l->interpret(c) && r->interpret(c); }
std::string str() const override { return "(" + l->str() + " AND " + r->str() + ")"; }
};
struct Or : Expr {
ExprP l, r;
Or(ExprP a, ExprP b) : l(std::move(a)), r(std::move(b)) {}
bool interpret(const Context &c) const override { return l->interpret(c) || r->interpret(c); }
std::string str() const override { return "(" + l->str() + " OR " + r->str() + ")"; }
};
struct Not : Expr {
ExprP e;
explicit Not(ExprP x) : e(std::move(x)) {}
bool interpret(const Context &c) const override { return !e->interpret(c); }
std::string str() const override { return "NOT " + e->str(); }
};
class Parser { // 문장 → 추상 구문 트리
public:
explicit Parser(std::string s) : s_(std::move(s)) {}
ExprP parse()
{
auto e = expr();
skip();
if (pos_ != s_.size())
fail("unexpected '" + s_.substr(pos_, 1) + "'");
return e;
}
private:
ExprP expr() { auto e = term(); while (word("or")) e = std::make_unique<Or>(std::move(e), term()); return e; }
ExprP term() { auto e = factor(); while (word("and")) e = std::make_unique<And>(std::move(e), factor()); return e; }
ExprP factor()
{
if (word("not")) return std::make_unique<Not>(factor());
if (sym("(")) { auto e = expr(); if (!sym(")")) fail("expected ')'"); return e; }
std::string f = ident();
for (const char *op : {"==", "!=", ">=", "<=", "~"})
if (sym(op)) return std::make_unique<Compare>(f, op, ident());
fail("expected operator after '" + f + "'");
}
void skip() { while (pos_ < s_.size() && s_[pos_] == ' ') ++pos_; }
bool sym(const std::string &t) { skip(); if (s_.compare(pos_, t.size(), t) == 0) { pos_ += t.size(); return true; } return false; }
bool word(const std::string &w)
{
skip();
std::size_t e = pos_ + w.size();
if (s_.compare(pos_, w.size(), w) == 0 && (e == s_.size() || s_[e] == ' ' || s_[e] == '(')) { pos_ = e; return true; }
return false;
}
std::string ident()
{
skip();
std::size_t b = pos_;
while (pos_ < s_.size() && (isalnum((unsigned char)s_[pos_]) || s_[pos_] == '_')) ++pos_;
if (b == pos_) fail("expected name or value");
return s_.substr(b, pos_ - b);
}
[[noreturn]] void fail(const std::string &m)
{ throw std::runtime_error("at col " + std::to_string(pos_ + 1) + ": " + m + "\n " + s_ + "\n " + std::string(pos_, ' ') + "^"); }
std::string s_;
std::size_t pos_ = 0;
};// logfilter.cpp — 필터 문장을 해석해 로그를 거른다
#include <iostream>
#include <vector>
#include "filter.hpp"
int main()
{
std::vector<Context> logs = {
{{"level", "2"}, {"src", "net"}, {"msg", "link up"}},
{{"level", "4"}, {"src", "kernel"}, {"msg", "oom-killer invoked"}},
{{"level", "3"}, {"src", "disk"}, {"msg", "smart warning"}},
{{"level", "5"}, {"src", "app"}, {"msg", "oom in worker"}},
{{"level", "1"}, {"src", "kernel"}, {"msg", "boot ok"}},
};
for (std::string q : {"level >= 3 and (src == kernel or msg ~ oom)",
"not src == kernel and level <= 2",
"level >= 3 and (src == kernel",
"level => 3"}) {
std::cout << "query: " << q << '\n';
try {
ExprP e = Parser(q).parse();
std::cout << " tree : " << e->str() << '\n';
for (const auto &l : logs)
if (e->interpret(l))
std::cout << " match: [" << l.at("level") << "] " << l.at("src") << ": " << l.at("msg") << '\n';
} catch (const std::exception &ex) {
std::cout << " error " << ex.what() << '\n';
}
}
}$ g++ -std=c++20 -Wall -Wextra -O2 -o logfilter logfilter.cpp && ./logfilter
query: level >= 3 and (src == kernel or msg ~ oom)
tree : (level>=3 AND (src==kernel OR msg~oom))
match: [4] kernel: oom-killer invoked
match: [5] app: oom in worker
query: not src == kernel and level <= 2
tree : (NOT src==kernel AND level<=2)
match: [2] net: link up
query: level >= 3 and (src == kernel
error at col 30: expected ')'
level >= 3 and (src == kernel
^
query: level => 3
error at col 7: expected operator after 'level'
level => 3
^트리 출력을 보면 and가 or보다 먼저 묶였다. 문법 규칙의 층(expr → term → factor)이 그대로 연산자 우선순위가 된 것이다. 잘못된 문장은 해석 전에 파서가 위치와 함께 거부했다.
트리 해석 vs 클로저 컴파일
같은 트리를 매번 해석하면 노드마다 가상 호출과 연산자 문자열 비교, 숫자 변환이 반복된다. 트리를 한 번 람다 조합으로 바꿔 두면 연산자 선택과 상수 변환을 미리 끝낼 수 있다. 20만 줄을 5번 걸러 비교했다.
// compile.cpp — 트리를 매번 해석 vs 한 번 클로저로 "컴파일"한 뒤 실행
#include <chrono>
#include <functional>
#include <iostream>
#include <vector>
#include "filter.hpp"
using Pred = std::function<bool(const Context &)>;
Pred compile(const Expr &e) // 트리를 람다 조합으로 변환
{
if (auto *a = dynamic_cast<const And *>(&e)) { auto l = compile(*a->l), r = compile(*a->r); return [l, r](const Context &c) { return l(c) && r(c); }; }
if (auto *o = dynamic_cast<const Or *>(&e)) { auto l = compile(*o->l), r = compile(*o->r); return [l, r](const Context &c) { return l(c) || r(c); }; }
if (auto *n = dynamic_cast<const Not *>(&e)) { auto x = compile(*n->e); return [x](const Context &c) { return !x(c); }; }
auto *cmp = dynamic_cast<const Compare *>(&e);
std::string f = cmp->field, v = cmp->value;
if (cmp->op == "==") return [f, v](const Context &c) { auto it = c.find(f); return it != c.end() && it->second == v; };
if (cmp->op == "~") return [f, v](const Context &c) { auto it = c.find(f); return it != c.end() && it->second.find(v) != std::string::npos; };
long b = std::stol(v); // 숫자 변환을 컴파일 시점에 한 번만
bool ge = cmp->op == ">=";
return [f, b, ge](const Context &c) { auto it = c.find(f); if (it == c.end()) return false; long a = std::stol(it->second); return ge ? a >= b : a <= b; };
}
int main()
{
std::vector<Context> logs;
for (int i = 0; i < 200000; ++i)
logs.push_back({{"level", std::to_string(i % 6)}, {"src", i % 3 ? "app" : "kernel"}, {"msg", i % 7 ? "ok" : "oom"}});
ExprP tree = Parser("level >= 3 and (src == kernel or msg ~ oom)").parse();
Pred fast = compile(*tree);
auto time = [&](const char *name, auto &&pred) {
auto t0 = std::chrono::steady_clock::now();
int n = 0;
for (int rep = 0; rep < 5; ++rep)
for (const auto &l : logs) n += pred(l);
auto ms = std::chrono::duration<double, std::milli>(std::chrono::steady_clock::now() - t0).count();
std::cout << name << ms << " ms, matches=" << n / 5 << '\n';
};
time("interpret tree : ", [&](const Context &c) { return tree->interpret(c); });
time("compiled lambda: ", fast);
}$ g++ -std=c++20 -Wall -Wextra -O2 -o compile compile.cpp && ./compile
interpret tree : 37.9818 ms, matches=42857
compiled lambda: 29.0971 ms, matches=42857약 20% 빨라졌지만 극적이지는 않다. 줄마다 std::map에서 필드를 찾는 비용이 대부분이라, 성능이 중요하면 필드를 정수 인덱스로 미리 바꾸는 것처럼 문맥의 표현부터 손봐야 한다. 정규식 엔진이나 SQL 엔진이 해석기 대신 바이트코드나 기계어로 컴파일하는 것도 같은 이유다.
C 구현: 스택 기계
후위 표기(RPN)는 괄호와 우선순위가 없어 트리 없이 스택만으로 해석된다. 숫자는 쌓고, 연산자는 두 개를 꺼내 계산한 결과를 다시 쌓는다.
/* rpn.c — C 인터프리터: 후위 표기(RPN) 산술식을 스택 기계로 해석한다 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define STACK_MAX 64
/* 성공 0, 실패 -1. 오류 위치(토큰 번호)를 *err_at에 남긴다 */
static int rpn_eval(const char *src, double *out, int *err_at)
{
char buf[256], *save, *tok;
double st[STACK_MAX];
int sp = 0, n = 0;
snprintf(buf, sizeof(buf), "%s", src);
for (tok = strtok_r(buf, " ", &save); tok; tok = strtok_r(NULL, " ", &save), n++) {
char *end;
double v = strtod(tok, &end);
if (*end == '\0') { /* 숫자: 스택에 넣기 */
if (sp == STACK_MAX) goto error;
st[sp++] = v;
continue;
}
if (strlen(tok) != 1 || sp < 2) /* 연산자: 피연산자 2개 필요 */
goto error;
double b = st[--sp], a = st[--sp];
switch (tok[0]) {
case '+': st[sp++] = a + b; break;
case '-': st[sp++] = a - b; break;
case '*': st[sp++] = a * b; break;
case '/': if (b == 0) goto error; st[sp++] = a / b; break;
default: goto error;
}
}
if (sp != 1) goto error; /* 값이 정확히 하나 남아야 한다 */
*out = st[0];
return 0;
error:
*err_at = n;
return -1;
}
int main(void)
{
const char *progs[] = { "3 4 + 2 *", "5 1 2 + 4 * + 3 -", "2 3 4", "1 0 /", "7 +" };
for (size_t i = 0; i < sizeof(progs) / sizeof(progs[0]); i++) {
double v;
int at;
if (rpn_eval(progs[i], &v, &at) == 0)
printf("%-18s = %g\n", progs[i], v);
else
printf("%-18s : error at token %d\n", progs[i], at);
}
return 0;
}$ gcc -std=c11 -Wall -Wextra -O2 -D_POSIX_C_SOURCE=200809L -o rpn rpn.c && ./rpn
3 4 + 2 * = 14
5 1 2 + 4 * + 3 - = 14
2 3 4 : error at token 3
1 0 / : error at token 2
7 + : error at token 1피연산자가 남는 식, 0으로 나누기, 피연산자가 모자란 연산자를 모두 오류로 처리했다. JVM, Python, eBPF 같은 가상 머신도 규모만 다를 뿐 이렇게 스택이나 레지스터 위에서 명령을 해석하는 구조다.
컴포지트·방문자와의 관계
| 패턴 | 인터프리터에서의 역할 |
|---|---|
| 컴포지트 | 구문 트리 자체의 구조(And가 Expr 두 개를 가짐) |
| 방문자 | 해석 외의 연산(출력, 최적화, 타입 검사)을 노드 밖으로 뺄 때 |
| 플라이웨이트 | 같은 리터럴·식별자 노드를 공유할 때 |
| 반복자 | 트리를 순회할 때 |
주의사항
- 문법이 작을 때만: 규칙 하나가 클래스 하나라서 문법이 커지면 클래스가 폭발한다. 규모가 있는 언어는 파서 생성기(bison, ANTLR)나 기존 언어(Lua 등)를 내장하는 편이 낫다.
- 사용자 입력은 신뢰하지 않는다: 깊게 중첩된 괄호는 재귀 파서와 재귀 해석의 스택을 넘치게 할 수 있다. 중첩 깊이와 입력 길이를 제한한다.
- 예외 경로 점검: 예제의
Compare는 숫자가 아닌 값에>=를 쓰면std::stol이 예외를 던진다. 실제 도구라면 파싱 단계에서 필드 타입을 검사해 미리 거부한다. - 에러 메시지가 사용성이다: 위치 표시(
^)처럼 어디가 틀렸는지 보여 주지 않으면 작은 언어도 쓰기 어렵다. - 성능은 문맥 표현에서: 위 측정처럼 해석 방식보다 데이터 접근 비용이 더 클 때가 많다. 최적화 전에 어디서 시간이 드는지 측정한다.
마무리
인터프리터는 “문법을 코드 구조로 옮긴다”는 점에서 가장 직접적인 패턴이다. 문법 규칙 → 클래스, 문장 → 객체 트리, 의미 → interpret()가 일대일로 대응한다. 이것으로 생성 패턴 5개, 구조 패턴 7개, 행위 패턴 11개, GoF 23개 패턴을 C++과 C 예제로 모두 살펴봤다. 패턴은 외울 목록이 아니라, 변하는 부분과 변하지 않는 부분을 나누는 방법의 이름이라는 점이 시리즈 전체에 걸친 공통점이다.
참고
- Erich Gamma 외, 『Design Patterns: Elements of Reusable Object-Oriented Software』(GoF), Interpreter
- Robert Nystrom — Crafting Interpreters