Brzozowski
Languages and libraries
regex engine
SHOW HN2023
How HN took it
1 positive, 3 neutral or asking, 0 mixed, 3 critical, out of 7 comments about the project. Thread score -0.18.
Performance: 0 for, 3 againstIdea: 1 for, 0 against
The thread, comment by comment
Each row is a top-level comment and its replies, in HN's order. Select a cell to open that comment on HN.
positive neutral or mixed critical about another commenter or something else the maker
What HN said
What people liked
Concept is cool and the code is a good illustration
From 1 comment
This comment is not following HN guidelines, but: I saw this and I was immediately sure that I could make this blow up exponentially. But then I got too lazy to think about…
H8crilA on HN
Objections
Naive matching can blow up exponentially, e.g. (A*)* against long input
From 1 comment
From my own experiments[1], I suspect your engine might still be prone to exponential blowup: you only get proper linear matching if you reassociate and sort the choice…
mananaysiempre on HN
Linear matching needs reassociation, sorting and merging of terms
From 2 comments
From my own experiments[1], I suspect your engine might still be prone to exponential blowup: you only get proper linear matching if you reassociate and sort the choice…
mananaysiempre on HNI think I got your point. It is valid. To construct the DFA and have a finite number of derivatives we have to keep track of the following equivalences: r + r ~ r r + s ~ s + r…
c0nstantine on HN
Requests
Add DFA construction and term equivalence reduction
From 1 comment
I think I got your point. It is valid. To construct the DFA and have a finite number of derivatives we have to keep track of the following equivalences: r + r ~ r r + s ~ s + r…
c0nstantine on HN
Questions
How does derivative matching handle large Unicode character classes?
From 2 comments
As the sibling commenter said, indeed, the regex crate does not use derivatives. If you wouldn't mind, could you share what led you to that conclusion? I'd love to fix it! I am…
burntsushi on HNI don't think you should be worried about Unicode in particular. Although the derivation formula on paper is parameterized by a character, you don't have to compute the…
def-lkb on HN
Alternatives named
ocaml-re
From 1 comment
ocaml-re[1] uses a derivative-style construction to lazily build a DFA. The general idea is to use something similar to Owens et al's DFA construction, but doing it inline with…
Drup on HN
redgrep
From 1 comment
I don't think Rust regex engine relies on this technique. I guess the main point is when you construct the DFA directly you still have the possibility of the exponential…
c0nstantine on HN
Rust regex crate
From 1 comment
IIRC, that's what the Rust regex engine[1] currently uses [1] https://github.com/rust-lang/regex
SomeoneOnTheWeb on HN
Agda and Coq formalizations
From 2 comments
And here the formalized proof in less than 150 lines of code (in Agda) for Brzozowski Derivatives for regex matching (and additional regular languages theorems):…
evolveyourmind on HNThanks for sharing. I am not familiar with Agda. Will take a look. There is somewhat similar code in COQ: https://github.com/coq-community/regexp-Brzozowski
c0nstantine on HN