google/redgrep
View on GitHub ↗ ★ 165 C++ archived
♥ Janusz Brzozowski
12 mentions on Hacker News by 7 people: 1 story, 11 comments · first 2015-10-21 · latest 2026-03-24
20082026
-
…I recall correctly, it doesn't handle some obstruse regexes the way conventional tools do however. https://github.com/google/redgrep
comment by davidgrenier · 2026-03-24 · in Finding all regex matches has always been O(n²) -
…via Brzozowski derivatives. See https://en.wikipedia.org/wiki/Brzozowski_derivative See also https://github.com/google/redgrep Regular languages have a bunch of closure properties. In practice, intersection and complement are really…
comment by eru · 2025-12-23 · in Chomsky and the Two Cultures of Statistical Learning (2011) -
…a lazy DFA, because full DFAs are too expensive to build in the "general purpose" context.) [1]: https://github.com/google/redgrep
comment by burntsushi · 2023-09-09 · in Debugging catastrophic backtracking for regular expressions in Python -
…NFA/DFA and lazy DFA. Though there is an implementation that relies only on Brzozowski derivatives: https://github.com/google/redgrep
comment by c0nstantine · 2023-03-07 · in Show HN: Regex Derivatives (Brzozowski Derivatives) -
▲ 2
Redgrep – grep based on regex derivatives, matches in linear timestory by pabs3 · 2021-04-27 · 0 comments
-
…might work. Nothing about Viterbi is fast, in my experience implementing it in the past. :-) > https://github.com/google/redgrep/blob/main/parser.yy mentions something about capture, but not sure if that has anything to do with capture…
comment by burntsushi · 2021-03-14 · in Speed of Rust vs. C -
…an inkling that something inspired by https://en.wikipedia.org/wiki/Viterbi_algorithm might work. https://github.com/google/redgrep/blob/main/parser.yy mentions something about capture, but not sure if that has anything to do with capture…
comment by eru · 2021-03-14 · in Speed of Rust vs. C -
…through ripgrep's website: does ripgrep support intersection and complement of expressions? Like eg https://github.com/google/redgrep does. Regular languages are closed under those operations after all.
comment by eru · 2021-03-14 · in Speed of Rust vs. C -
…[2] - https://github.com/google/re2/issues/156#issuecomment-354068... [3] - https://github.com/google/redgrep
comment by burntsushi · 2021-01-01 · in State machines are wonderful tools -
…There a bunch of non-production implementations floating around like https://github.com/google/redgrep https://github.com/MichaelPaddon/epsilon (This technique was revived by the 2009 paper cited) ----- Regarding the blog post,
comment by chubot · 2019-06-30 · in Regular Expression Matching Can Be Simple and Fast (2007) -
There's also redgrep ( https://github.com/google/redgrep ) that supports intersection and complements of regular expressions. I am toying the idea of writing a little game where player A thinks of a regular expression, and player B tries…
comment by eru · 2017-07-06 · in Regex Puzzle -
…Redgrep is a cool project by Paul Wankadia that uses LLVM to JIT regexp automata into machine code. https://github.com/google/redgrep . The two things that are tough about JITting for very large automata, though, are breaking the code up…
comment by jonstewart · 2015-10-21 · in Hyperscan, a high-performance multiple regex matching library