Parsing Filter Expressions in NestJS with a Context-Free Grammar

Context

평탄한 쿼리 파라미터 방식(?status=active&age_gte=18)은 단순한 필터링에는 충분하지만, (status=active OR status=pending) AND age>=18 같은 중첩된 불린 로직을 표현할 수 없다. 불린 로직이 본질적으로 재귀 구조를 가지기 때문에 키-값 기반 파라미터로는 이러한 구조를 인코딩할 방법이 없다.

Technical Solution

• Context-Free Grammar(CFG)를 이용한 필터 언어 설계: expression → term ( ("+" | "-") term )* 같은 production 규칙으로 연산자 우선순위와 재귀적 중첩을 자동으로 처리
• Chevrotain 파서 생성 도구를 사용한 렉서·파서 구현: GreaterEqual(>=), LessEqual(<=), NotEqual(!=) 등 다중 문자 연산자를 정의할 때 토큰 순서를 통해 탐욕적 매칭 제어
• 재귀 하강 파싱(Recursive Descent)으로 각 non-terminal을 함수화: filter → or_expr → and_expr → atom 구조로 AND가 OR보다 강한 결합력을 가지도록 문법 우선순위 자동 반영
• 조건(condition) → 필드(field) + 연산자(operator) + 값들(values) 구조로 IN 쿼리를 쉼표 분리로 자연스럽게 처리: status=active,pending
• OpenAPI 스펙 기반 코드 생성으로 클라이언트에 타입 안전성 제공: @nestjs-filter-grammar/client-query-builder가 필터링 가능한 필드·지원 연산자·타입을 생성된 코드로 제시

Key Takeaway

Context-Free Grammar를 적용하면 임의의 수준으로 중첩 가능한 재귀 구조를 몇 줄의 생산 규칙으로 정의할 수 있으며, 파서 생성 도구를 통해 유효하지 않은 입력을 문법 단계에서 원천적으로 배제할 수 있다. 이는 ad-hoc 파싱 코드의 엣지 케이스 처리보다 구조적으로 더 견고한 설계를 보장한다.