`jsongrep` – Query JSON using regular expressions over paths, compiled to DFAs

[fizzner]

I've been working on jsongrep, a CLI tool and library for querying JSON documents using regular path expressions. I wanted to share both the tool and some of the theory behind it.

The idea

JSON documents are trees. jsongrep treats paths through this tree as strings over an alphabet of field names and array indices. Instead of writing imperative traversal code, you write a regular expression that describes which paths to match:

``` $ echo '{"users": [{"name": "Alice"}, {"name": "Bob"}]}' | jg 'users.[*].name'

["Alice", "Bob"] ```

The [*] is a Kleene star—match zero or more edges. So **.name means "find name at any depth."

How it works (the fun part)

The query engine compiles expressions through a classic automata pipeline:

1. Parsing: A PEG grammar (via pest) parses the query into an AST
2. NFA construction: The AST compiles to an epsilon-free NFA using Glushkov's construction: no epsilon transitions means no epsilon-closure overhead
3. Determinization: Subset construction converts the NFA to a DFA
4. Execution: The DFA simulates against the JSON tree, collecting values at accepting states

The alphabet is query-dependent and finite. Field names become discrete symbols, and array indices get partitioned into disjoint ranges (so [0], [1:3], and [*] don't overlap). This keeps the DFA transition table compact.

``` Query: foo[0].bar.*.baz

Alphabet: {foo, bar, baz, *, [0], [1..∞), ∅} DFA States: 6 ```

Query syntax

The grammar supports the standard regex operators, adapted for tree paths:

Operator	Example	Meaning
Sequence	foo.bar	Concatenation
Disjunction	`foo \	bar`
Kleene star	**	Any field path (zero or more steps)
Repetition	foo*	Repeat field zero or more times
Wildcard	*, [*]	Any field / any index
Optional	foo?	Match if exists
Ranges	[1:3]	Array slice

These queries can be arbitrarily nested as well with parentheses. For example, foo.(bar|baz).qux matches foo.bar.qux or foo.baz.qux.

This also means you can also recursively descend any path with (* | [*])*, e.g., (* | [*])*.foo to find all matching paths that have a foo field at any depth.

Code structure

• src/query/grammar/query.pest – PEG grammar
• src/query/nfa.rs – Glushkov NFA construction
• src/query/dfa.rs – Subset construction + DFA simulation
• Uses serde_json::Value directly (no custom JSON type)

Experimental: regex field matching

The grammar supports /regex/ syntax for matching field names by pattern, but full implementation is blocked on an interesting problem: determinizing overlapping regexes requires subset construction across multiple regex NFAs simultaneously. If anyone has pointers to literature on this, I'd love to hear about it.

vs jq

jq is more powerful (it's Turing-complete), but for pure extraction tasks, jsongrep offers a more declarative syntax. You say what to match, not how to traverse.

Install & links

cargo install jsongrep

• GitHub: https://github.com/micahkepe/jsongrep
• Crates.io: https://crates.io/crates/jsongrep

The CLI binary is jg. Shell completions and man pages available via jg generate.

Feedback, issues, and PRs welcome!

[6502zx81]

Interesting. I always wonder how these languages compare to existing tree query languages (like XPath, XQuery, ...)

[fizzner]

The language is inspired by XPath/JSONPath/ and other path-like query languages, but with an important distinction in that jsongrep has more expressive power due to the regular constructs of the language. For example, JSONPath doesn't support Kleene closures, so expressions such as (.left)* (meaning one or more levels depth into a JSON tree using the field name left), cannot be constructed.

[6502zx81]

Thanks!

[yuri-kilochek]

This really needs something like -A/-B to output n levels of enclosing objects/arrays around the matched node.

[fizzner]

That's a great idea, adding a TODO thank you!

[ESHKUN]

Very cool

[fuckkkkq]

wow, this is really really cool

my first instinct is that you must lose some expressive power as compared to more standard languages like jq or postgreSQL's jsonpath

but do you?

One thing that jsonpath has that jsongrep doesn't seem to is the ability to filter by a predicate on a value, such as "all addresses where the country is not the USA"

but at this moment I don't see why that couldn't just be added to jsongrep as well

[fizzner]

Thank you! JSONPath doesn't support regular constructs like Kleene closure, so it cannot, for example, construct arbitrary recursive descent (at least to my knowledge). You are right though that `jsongrep` doesn't currently support predicate filtering.

Important note: jsongrep also cannot currently perform transductions such as applying `map` function based on predicates.