a query language in ~1000 lines: lexer, parser, evaluator

here’s a question that sounds trivial and isn’t: show me every 5xx response that also mentions a timeout.

in grep that’s a fragile little dance — grep -E 'status[=:] ?5[0-9]{2}' piped into another grep timeout, and now you’re matching 500 inside a request id, timeout inside a url, and you’ve quietly stopped trusting the output. what you wanted was this:

status >= 500 AND message contains "timeout"

and have the machine read >= as numeric greater-or-equal, AND as boolean conjunction, and "timeout" as a substring on one named field. that’s not grep. that’s a little language, and little languages need a lexer, a parser, and something to run them.

logmole ↗ is a small log-analysis cli i’ve been building in the open. last time i computed a rolling z-score without storing a single sample , and before that i ported the drain algorithm to collapse forty thousand log lines into a dozen templates. i closed the welford post promising the sequel would be the query dsl — a hand-rolled lexer and recursive-descent parser, and why i didn’t reach for a parser generator. here it is.

the whole thing — tokenizer, ast, parser, evaluator — is about a thousand lines of rust, tests included, and zero parser-generator dependencies. that last part is a decision, so let’s start there.

hand-roll or reach for a generator?

there’s a real fork the moment you parse anything, and people get religious about it. lalrpop, pest, nom, chumsky — rust has a good bench of parser tooling, and reaching for one is often right. not here, and the reason is grammar size. here’s the whole grammar:

logmole-core/src/query/ast.rs

expr       = or_expr
or_expr    = and_expr ("OR" and_expr)*
and_expr   = not_expr ("AND" not_expr)*
not_expr   = "NOT" atom | atom
atom       = comparison | "(" expr ")"
comparison = field_ref operator value
operator   = ">=" | "<=" | ">" | "<" | "==" | "!=" | "contains" | "matches"
value      = STRING | NUMBER | DURATION | BOOL | "null"

nine rules. no left recursion to massage away, no genuine ambiguity, eight operators and three connectives. this is the canonical worked example in every compilers text — bob nystrom builds essentially this grammar by hand in the parsing expressions ↗ chapter of crafting interpreters, and its whole point is that each grammar rule becomes a function and precedence falls out of how the functions call each other. no table, no codegen, no macro dsl to learn. the rules become a plain rust enum:

logmole-core/src/query/ast.rs

pub enum Expr {
    And(Box<Expr>, Box<Expr>),
    Or(Box<Expr>, Box<Expr>),
    Not(Box<Expr>),
    Comparison(Comparison),
}

my rule of thumb: hand-roll when the grammar fits on a napkin and you want the two things generators make awkward — precise, positioned errors, and a zero-dependency build. reach for a generator when the grammar is large, still moving, or actually ambiguous. this one’s a napkin. (i’ll come back to where that goes wrong. it does.)

the lexer: spanned tokens so errors can point

the tokenizer flattens the raw string into a Vec of tokens — one variant per thing the grammar can see:

logmole-core/src/query/lexer.rs

pub enum Token {
    Ident(String),
    StringLit(String),
    IntLit(i64),
    FloatLit(f64),
    /// A duration literal (e.g., `2s`, `500ms`, `1h30m`). Value in milliseconds.
    DurationLit(i64),
    BoolLit(bool),
    Null,
    And, Or, Not,
    Gte, Lte, Gt, Lt, Eq, Neq,
    Contains, Matches,
    // ...
}

the one thing i did not skimp on is position. every token carries the byte offset where it started:

logmole-core/src/query/lexer.rs

/// A token with its position in the source string.
#[derive(Debug, Clone)]
pub struct SpannedToken {
    pub token: Token,
    pub offset: usize,
}

that offset is the whole reason to hand-write the lexer instead of leaning on a regex tokenizer. when the parser chokes it can say at position 14 instead of somewhere in your query, good luck — the errors format straight off it. it also earns its keep in the two-character operators, where you peek one ahead: classic maximal munch, >= before >, and == before =.

logmole-core/src/query/lexer.rs

// == or =
'=' => {
    chars.next();
    if chars.peek().is_some_and(|&(_, c)| c == '=') {
        chars.next();
        tokens.push(SpannedToken { token: Token::Eq, offset: pos });
    } else {
        // Single = treated as ==
        tokens.push(SpannedToken { token: Token::Eq, offset: pos });
    }
}

look at the = case: both branches emit Token::Eq. a single = is silently accepted as if you’d typed ==. deliberate leniency, and exactly the kind of thing i’ll own up to later.

durations are the genuinely fiddly job. i want latency_ms > 2s to reach the evaluator already in milliseconds so it never thinks about units, and the loop walks suffix by suffix — the one real ambiguity being that m is minutes but ms is milliseconds:

logmole-core/src/query/lexer.rs

Some(&(_, 'm')) => {
    chars.next();
    // Check for 'ms'
    if chars.peek().is_some_and(|&(_, c)| c == 's') {
        chars.next();
        total_ms += (current_num) as i64;
    } else {
        total_ms += (current_num * 60_000.0) as i64; // minutes
    }
    current_num = 0.0;
}
// ... 'h', 's', 'd', and the next numeric chunk

1h30m accumulates 3_600_000 + 1_800_000 and lands as DurationLit(5_400_000), and the m/ms collision gets resolved by peeking one more character. units die at the lexer, which is where units should die.

the parser: precedence is the call graph

now the recursive-descent parser. i want a OR b AND c to mean a OR (b AND c) — AND binds tighter than OR, NOT tighter still, a parenthesized group tightest. a pratt parser ↗ expresses that with a table of binding powers. i express it with the shape of the code: one function per precedence level, each calling the next-tighter one. loosest first, OR, then the same loop one level down for AND, then NOT, then the atom:

logmole-core/src/query/parser.rs

/// `or_expr` = `and_expr` ("OR" `and_expr`)*
fn parse_or_expr(&mut self) -> Result<Expr, ParseError> {
    let mut left = self.parse_and_expr()?;
    while self.peek() == Some(&Token::Or) {
        self.advance();
        let right = self.parse_and_expr()?;
        left = Expr::Or(Box::new(left), Box::new(right));
    }
    Ok(left)
}

/// `not_expr` = "NOT" atom | atom
fn parse_not_expr(&mut self) -> Result<Expr, ParseError> {
    if self.peek() == Some(&Token::Not) {
        self.advance();
        let expr = self.parse_atom()?;
        Ok(Expr::Not(Box::new(expr)))
    } else {
        self.parse_atom()
    }
}

/// atom = comparison | "(" expr ")"
fn parse_atom(&mut self) -> Result<Expr, ParseError> {
    if self.peek() == Some(&Token::LParen) {
        self.advance();
        let expr = self.parse_expr()?;
        self.expect(&Token::RParen)?;
        Ok(expr)
    } else {
        self.parse_comparison()
    }
}

that’s the entire precedence machinery. OR < AND < NOT < atom, laid out as functions that call downward, and a parenthesized atom loops straight back to parse_expr so (a OR b) AND c reparents correctly. parse_or_expr never even sees an AND — it only glues together whatever parse_and_expr hands back. the precedence is the call graph, and at this size that’s easier to reason about than a table of binding powers.

the leaves are comparisons, and the value parser has the other bit of deliberate slack:

logmole-core/src/query/parser.rs

Some(Token::Ident(s)) => {
    // Allow unquoted string values (e.g., level == error)
    self.advance();
    Ok(LiteralValue::String(s))
}

level == error works with no quotes, because typing quotes around every value at a shell prompt is a tax nobody wants to pay. convenient. also a trap — later.

compiling to a closure

the parser produces an Expr tree, but the pipeline shouldn’t know what an ast is. so compile_query swallows the whole lexer-plus-parser stack and hands back one thing — a closure.

logmole-core/src/query/mod.rs

/// A compiled query filter that can be evaluated against log records.
pub type QueryFilter = Box<dyn Fn(&LogRecord<'_>) -> bool>;

pub fn compile_query(query: &str) -> Result<QueryFilter, LogmoleError> {
    let tokens = lexer::tokenize(query).map_err(|e| LogmoleError::QueryError(e.to_string()))?;
    let expr = parser::parse(&tokens).map_err(|e| LogmoleError::QueryError(e.to_string()))?;

    Ok(Box::new(move |record| eval::evaluate(&expr, record)))
}

lex once, parse once, move the Expr into a boxed closure, and every log line after that is just a Fn(&LogRecord) -> bool call. the caller filtering millions of records never sees a token or a tree — it sees a predicate. Box<dyn Fn> costs one virtual call per line, which against the cost of parsing a log line is free. that’s the seam between “the query language” and “the tool,” exactly one type wide.

the evaluator: tree-walking with opinions

evaluate is the textbook tree walk — four arms, three of them one line:

logmole-core/src/query/eval.rs

pub fn evaluate(expr: &Expr, record: &LogRecord<'_>) -> bool {
    match expr {
        Expr::And(left, right) => evaluate(left, record) && evaluate(right, record),
        Expr::Or(left, right) => evaluate(left, record) || evaluate(right, record),
        Expr::Not(inner) => !evaluate(inner, record),
        Expr::Comparison(cmp) => evaluate_comparison(cmp, record),
    }
}

&& and || give me short-circuit evaluation for free; i just recurse. all the actual judgment lives in the comparison, and this is where a log query language earns its keep, because logs are stringly-typed and users are not. somebody writes status >= 500 and the status field might be the integer 503 or the string "503" depending on the format. the query shouldn’t care. so ordered comparison tries numbers first and falls back to lexical string ordering:

logmole-core/src/query/eval.rs

fn compare_ordered(field: &ResolvedValue<'_>, literal: &LiteralValue) -> Option<std::cmp::Ordering> {
    // Try numeric comparison first
    if let (Some(a), Some(b)) = (resolved_as_f64(field), literal_as_f64(literal)) {
        return a.partial_cmp(&b);
    }
    // String comparison
    if let (Some(a), LiteralValue::String(b)) = (resolved_as_str(field), literal) {
        return Some(a.cmp(b.as_str()));
    }
    None
}

resolved_as_f64 is where coercion happens: an int field is an f64, a float is an f64, and a string field gets s.parse::<f64>().ok() — so "503" parses to 503.0 and compares numerically against 500. equality does the same cross-type dance, and a test pins it down: a record whose status is the string "503" still matches status >= 500. duration literals arrive as integer milliseconds from the lexer, so latency_ms > 2s just compares 5000 against 2000. coercing "503" to a number isn’t “correct” — it’s a choice, and for a triage tool eating heterogeneous logs it’s the useful one. i’d rather be useful than pure here.

the regex cache: LazyLock plus a poison-proof mutex

the matches operator runs a regex, and regex::Regex::new compiles a pattern into a state machine — not cheap. recompiling message matches "E\d{4}" fresh on every one of a million lines would be indefensible, so compiled regexes go in a process-wide cache that, because logmole evaluates across threads, has to be thread-safe:

logmole-core/src/query/eval.rs

/// Thread-safe cache for compiled regex patterns.
static REGEX_CACHE: std::sync::LazyLock<Mutex<HashMap<String, Option<Regex>>>> =
    std::sync::LazyLock::new(|| Mutex::new(HashMap::new()));

fn get_cached_regex(pattern: &str) -> Option<Regex> {
    let mut cache = REGEX_CACHE
        .lock()
        .unwrap_or_else(std::sync::PoisonError::into_inner);
    cache
        .entry(pattern.to_owned())
        .or_insert_with(|| Regex::new(pattern).ok())
        .clone()
}

three small things carry weight. std::sync::LazyLock ↗ — stable since 1.80 — gives me a static that initializes itself on first use, no once_cell dependency and no lazy_static! macro. the value is a Mutex<HashMap>, so lookups are serialized and safe. and the Option<Regex> means a pattern that fails to compile caches its failure as None — i don’t retry a broken regex a million times, i remember it’s broken. (Regex::is_match ↗ runs it downstream.)

the line i’m quietly proud of is .unwrap_or_else(std::sync::PoisonError::into_inner). a plain .lock().unwrap() panics if any thread ever panicked while holding this mutex — the lock is “poisoned.” but this cache holds compiled regexes, not invariants; a poisoned map is still a perfectly good map. PoisonError::into_inner ↗ hands me the guard anyway, so one unlucky panic elsewhere can’t turn my regex cache into a landmine that takes down every subsequent query — recover and keep filtering, instead of the whole cli falling over because something unrelated hiccuped.

the honest part: what i cut

the rule in this journal is that i don’t get to pretend. so:

• a single = is silently ==. i decided a typo’d equals shouldn’t be a syntax error. the flip side: a confused user gets no signal that = and == are supposedly different, because here they aren’t. forgiving parsers hide mistakes.
• unquoted string values are a foot-gun. level == error is lovely until someone writes level == 500 meaning the string and gets numeric coercion, or types a bare word that collides with a keyword. quotes exist for a reason and i made them optional.
• precedence-by-nesting is simple but rigid. adding a precedence level means surgery on the function chain, not a new row in a table. a pratt parser ↗ keeps precedence as data you extend; mine keeps it as control flow you rewrite. and NOT only binds an atom, so NOT a AND b is (NOT a) AND b — want NOT (a AND b), type the parens. that’s frozen into the shape of parse_not_expr.
• dotted field paths lex and parse but don’t evaluate. request.headers.host == "..." tokenizes fine and builds a real three-part FieldRef, then resolve_field returns None for anything non-simple because the record model is flat. a promise in the grammar the evaluator doesn’t keep yet; today it quietly matches nothing.
• string equality is case-insensitive, everywhere. right for level == error, surprising for a field where case is meaningful. i optimized for the common log case and made the uncommon one impossible.

none of these are bugs. they’re scope — every one a place where “make the shell-prompt experience nice” beat “be a rigorous language,” the right winner for a filter you type into a cli and the wrong one for anything a machine generates and feeds back in.

and the big one: hand-rolling was right here and would not survive success. at nine rules a hand-written recursive-descent parser is less code, more readable, and gives better errors than any generator i’d have pulled in. the moment this grammar grows real precedence levels, functions, or genuine ambiguity, the call-graph approach turns from elegant into a liability, and i’d port it to lalrpop or a proper pratt table without sentiment. knowing which size you’re at is the actual skill. i’m at napkin size, and i built a napkin.

lessons learned

• grammar size is the whole decision. “should i use a parser generator” has no context-free answer — it’s a function of how many rules you have and how fast they’re changing. a napkin grammar wants a hand-written parser; a language wants a generator. pick to the size you’re at.
• precedence can be code or data, and both are fine. one parse function per level makes precedence self-evident and unextensible; a pratt table makes it extensible and less obvious. choose the failure mode you can live with.
• positioned errors are a lexer decision, not a parser afterthought. a byte offset on every token cost one usize field and bought every message a place to point. “at position 14” is something you decide at tokenize time.
• recover where recovery is safe. PoisonError::into_inner on a cache turns an unrelated panic from “cli down” into “cli keeps going.” know which locks guard invariants and which just guard data.

next in the logmole series: memory-mapping a multi-gigabyte log and parsing records straight out of the mmap without copying a single line — zero-copy, lifetimes, and the borrow checker earning its keep.

the code is on github ↗ if you want to poke at it. it’s a work in progress, like everything here.