Yacc grammar 파일을 열어 보면서 언어를 만드는 데 왜 두 번째 언어를 배워야 하는지 의문을 품어본 적이 있다면, 당신만 그런 것이 아니다. parser generator은 강력하지만, bounded context 안에서 자연스럽게 등장하는 작은 DSL에는 거의 항상 과하다.
파서를 애플리케이션의 나머지 부분과 같은 언어로 작성할 수 있다. 빌드 단계 없이, grammar 파일 없이, 디버깅할 수 없는 생성 코드 없이.
parser generator이 해결하는 문제는 아마 당신에게 없는 문제다
ANTLR, Bison, PEG.js 같은 parser generator은 grammar를 도메인 특화 메타언어로 표현하도록 강제한다. .g4나 .y 파일을 작성하고, 도구를 실행하고, 생성된 소스를 가져와서 임포트한 뒤, 뭔가 고장 났을 때 오류 메시지가 말이 되기를 기도한다.
완전한 프로그래밍 언어의 경우 이 트레이드오프는 가치가 있다. 생성된 LR 파서는 빠르고, grammar와 구현의 분리는 깔끔하다.
하지만 우리 대부분은 프로그래밍 언어를 만들지 않는다. 쿼리 필터, 설정 형식, 규칙 엔진, 혹은 단일 bounded context 안에 존재하는 아주 작은 표현 언어를 만든다. parser generator의 오버헤드, 분리된 빌드 단계, 배워야 할 두 번째 구문은 순전한 마찰이다.
파서 콤비네이터는 파싱을 평범한 코드로 만든다
파서 콤비네이터는 파서를 반환하는 함수이며, 파서는 입력을 소비하고 분석된 값이나 오류를 반환하는 함수다. higher-order function을 사용해 작은 파서를 더 큰 파서로 구성한다.
문자열 "hello"의 파서는 함수다. "hello" OR "world"의 파서는 첫 번째를 시도하고, 실패하면 두 번째를 시도하는 함수다. "hello" THEN "world"의 파서는 순차적으로 실행하고 결과를 결합한다.
이는 grammar가 그냥 코드라는 뜻이다. grammar 시각화 도구가 아닌 브레이크포인트로 디버깅한다.
40줄 TypeScript로 동작하는 산술 파서
다음은 아주 작은 표현 언어를 위한 완전한 파서다. 정수와 괄호로 묶인 덧셈을 처리한다. 의존성 없이, 생성된 파일 없이.
type Result<T> =
| { ok: true; value: T; pos: number }
| { ok: false; error: string; pos: number };
type Parser<T> = (input: string, pos: number) => Result<T>;
// Primitives: match a literal string or a regex
const str = (expected: string): Parser<string> => (input, pos) => {
const end = pos + expected.length;
return input.slice(pos, end) === expected
? { ok: true, value: expected, pos: end }
: { ok: false, error: `expected "${expected}"`, pos };
};
const regex = (re: RegExp): Parser<string> => (input, pos) => {
const m = input.slice(pos).match(new RegExp(`^(?:${re.source})`));
return m
? { ok: true, value: m[0], pos: pos + m[0].length }
: { ok: false, error: `expected /${re.source}/`, pos };
};
// Combinators: sequence, choice, map, lazy
const map = <A, B>(p: Parser<A>, f: (a: A) => B): Parser<B> => (input, pos) => {
const r = p(input, pos);
return r.ok ? { ...r, value: f(r.value) } : r;
};
const seq = <T extends Parser<unknown>[]>(...ps: T): Parser<any[]> => (input, pos) => {
const values: unknown[] = [];
let curr = pos;
for (const p of ps) {
const r = p(input, curr);
if (!r.ok) return r;
values.push(r.value);
curr = r.pos;
}
return { ok: true, value: values, pos: curr };
};
const or = <A, B>(a: Parser<A>, b: Parser<B>): Parser<A | B> => (input, pos) => {
const r = a(input, pos);
return r.ok ? r : b(input, pos);
};
const lazy = <T>(fn: () => Parser<T>): Parser<T> => (input, pos) => fn()(input, pos);
// Grammar: expr := number | "(" expr "+" expr ")"
const ws = regex(/\s*/);
const number = map(regex(/\d+/), n => parseInt(n, 10));
let expr: Parser<{ val: number }>;
expr = or(
map(
seq(str("("), ws, lazy(() => expr), ws, str("+"), ws, lazy(() => expr), str(")")),
([, , left, , , , right]) => ({ val: left.val + right.val })
),
map(number, val => ({ val }))
);
// Run it
const result = expr("(1 + (2 + 3))", 0);
console.log(result.ok ? result.value : result.error);
// Output: { val: 6 }실제로 무슨 일이 일어나는지 분해해 보자. str, regex, number는 기본 파서다. seq는 순서대로 파서를 실행한다. or은 대안을 시도한다. map은 결과를 변환한다. lazy만이 미묘한 부분이다. 재귀 grammar가 정의 시점에 폭발하지 않도록 평가를 지연시킨다.
타입 시스템이 각 파서가 생산하는 것을 추적한다. 파싱에 실패하면 정확한 위치와 예상 토큰을 얻는다. 이는 이미 대부분의 생성 파서가 기본적으로 제공하는 것보다 나은 오류 보고다.
왜 이것이 bounded context에 특히 잘 맞는가
도메인 주도 설계에서 bounded context는 의도적으로 작다. 그 안에 존재하는 DSL도 작아야 한다. 그 context가 신경 쓰는 구조만 필요하고, 그 외에는 아무것도 필요 없다.
파서 콤비네이터는 아래로 아름답게 스케일된다. 범용 쿼리 언어가 아닌, 도메인이 필요로 하는 유일한 쿼리 필터의 파서를 작성한다. 새로운 구조는 함수를 추가하는 것으로, 수천 줄의 C를 재생성하는 것이 아니다.
파서는 bounded context의 나머지와 동일한 저장소, 동일한 언어, 동일한 멘탈 모델 안에 존재한다. 도메인 모델이 바뀌면 파서도 함께 바뀐다. 다른 디렉토리에서 동기화가 어긋나는 grammar 파일은 존재하지 않는다.
콤비네이터가 부족한 점
공짜는 아니다. 콤비네이터가 내부적으로 구축하는 재귀 하강 파서는 좌재귀 규칙에 어려움을 겪는다. expr := expr + number | number라고 작성하면 파서는 영원히 자신을 호출한다.
이것은 좌재귀 규칙을 루프로 재작성하거나, 좌재귀를 대신 처리해 주는 라이브러리를 사용함으로써 해결한다. 작은 DSL에서는 실무상 문제가 되는 경우가 드물다.
또 다른 주의사항은 성능이다. 수동으로 튜닝된 재귀 하강 파서나 생성된 LR 파서는 순수 처리량에서 콤비네이터를 이긴다. 시작 시 한 번 읽히는 설정 파일이나, 요청당 한 번 평가되는 규칙의 경우 차이는 마이크로초 단위다. 중요하다고 가정하기 전에 측정하라.
자신만의 파서 구축을 시작하는 방법
가능한 한 가장 작은 grammar부터 시작하라. 하나의 구조를 파싱하고 테스트한 다음, 구성하라.
TypeScript를 작성한다면, parsimmon, arcsecond, chevrotain 같은 라이브러리가 위의 스크래치 구현보다 더 나은 오류 메시지와 좌재귀 처리를 갖춘 프로덕션 수준의 콤비네이터를 제공한다. Rust에는 nom, Haskell에는 Parsec, Python에는 parsy가 있다.
패턴은 어디서나 같다: primitives, sequence, choice, repetition, transformation. 한 번 배우면 어떤 언어에서도 적용할 수 있다.
FAQ
파서 콤비네이터란 무엇인가?
파서 콤비네이터는 하나 이상의 파서를 받아 새로운 파서를 반환하는 higher-order function이다. 단순한 파서를 조합하여 복잡한 파서를 구축할 수 있게 하며, 별도의 grammar 언어가 아닌 평범한 코드를 사용한다.
언제 parser generator을 계속 사용해야 하는가?
완전한 프로그래밍 언어를 파싱할 때, 최대 파싱 처리량이 필요할 때, 혹은 팀이 특정 생성기 생태계에 깊은 전문 지식을 보유하고 있을 때 생성기를 사용하라. 작은 DSL에는 보통 오버헤드가 그만한 가치가 없다.
파서 콤비네이터는 느린가?
수작업이나 생성된 LR 파서보다 느리지만, 대부분의 DSL 사용 사례에서는 그 격차는 무의미하다. 일반적인 콤비네이터 파서는 밀리초당 수천 개의 토큰을 처리한다. 설정 파일, 쿼리 문자열, 규칙 엔진에 충분히 빠르다.
TypeScript 이외의 언어에서도 파서 콤비네이터를 사용할 수 있는가?
물론이다. 이 패턴은 언어에 독립적이다. Rust의 nom, Haskell의 Parsec, Python의 parsy, Haskell의 attoparsec는 모두 성숙하고 널리 사용되는 라이브러리다.
다음에 bounded context 안에 작은 언어가 필요해지면, 정말로 grammar 파일과 코드 생성 단계가 필요한지 자문해 보라. 대부분의 DSL에 대해 답은 아니다. 콤비네이터 코드 100줄이면 디버거에서 한 단계씩 추적할 수 있고, 아무것도 재생성하지 않고 확장할 수 있으며, 6개월 후에도 실제로 이해할 수 있는 파서를 얻을 수 있다.