41–50 of 90 posts
- https://github.com/telekons/one-more-re-nightmare
- https://applied-langua.ge/posts/omrn-compiler.html
OMRN is a regex compiler that leverages Common Lisp's compiler to produce optimized assembly to match the given regex. It's incredibly fast. It does omit some features to achieve that, though.
Earlier quoted context omitted.
> I'm pretty sure that should say "the leftmost start paired with the leftmost end". I’m pretty sure it shouldn’t, that would give you the leftmost shortest match instead of leftmost longest.
As originally written, doesn't it go from the start of the first match to the end of the last match? I feel like I'm missing something.
(I tried to write some pseudocode here but got annoyed dealing with edge cases like zero-length matches at EOF, sorry.)
Earlier quoted context omitted.
As originally written, doesn't it go from the start of the first match to the end of the last match? I feel like I'm missing something.
It goes from start of the first match to the longest "alive" end, in practice it will go to a dead state and return after finding the match end. there's an implicit `.*` in front of the first pass but i felt it would've been a long tangent so i didn't want to get into it. so given input 'aabbcc' and pattern `b+`, first reverse pass (using `.*b+`) marks 'aa|b|bcc' the forward pass starts from the first match: 'aa->b|b…
So, once it gets going, a traditional engine can produce matches iteratively with no further allocation, but RE# requires allocation proportional to the total number of matches. And in return, it's very much faster and much easier to use (with intersection and complement).
Earlier quoted context omitted.
It uses far less tokens than C#, so watch this space...
Care to explain? Pattern matching, type inference, etc.?
https://martinalderson.com/posts/which-programming-languages...
If you claim it's the fastest, how does it compare to one-more-re-nightmare? - https://github.com/telekons/one-more-re-nightmare - https://applied-langua.ge/posts/omrn-compiler.html OMRN is a regex compiler that leverages Common Lisp's compiler to produce optimized assembly to match the given regex. It's incredibly fast. It does omit some features to achieve that, though.
OMRN: No lookaround, eager compilation, can output first match
RE#: No submatches, lazy compilation, must accumulate all matches
Both lookaround and submatch extraction are hard problems, but for practical purposes the lack of lazy compilation feels like it would be the most consequential, as it essentially disqualifies the engine from potentially adversarial REs (or I guess not with the state limit, but then it’s questionable if it actually counts as a full RE engine in such an application).
Earlier quoted context omitted.
It goes from start of the first match to the longest "alive" end, in practice it will go to a dead state and return after finding the match end. there's an implicit `.*` in front of the first pass but i felt it would've been a long tangent so i didn't want to get into it. so given input 'aabbcc' and pattern `b+`, first reverse pass (using `.*b+`) marks 'aa|b|bcc' the forward pass starts from the first match: 'aa->b|b…
Cheers. I was more confused by how you were doing multiple matches. So I read the paper, which describes the AllEnds algorithm. If I understand correctly, the reverse pass captures all of the match starts and these need to be remembered for the forward pass. Which is what you were showing above, but I didn't follow it. So, once it gets going, a traditional engine can produce matches iteratively with no further alloca…
It's also beneficial to merge some of the matching locations into ranges where possible, so when `a*` matches a long sequence of '|a|a|a|a|a|', it can be represented as a range of (0,5), we do this to keep the lookaround internal states smaller in the engine.
Cool stuff. Reminds me of the content you used to see on here all the time before AI took over
Not necessarily with bots, just posting a few links in a company Slack with the request for everyone to upvote it from their personal account could be enough.