Regex Engine Internals as a Library

Re:Regex Engine Internals as a Library by IshKebab on Wednesday July 05, 2023 @04:57PM (#36606997)

Yeah I am slowly working on it. I think even custom alphabets wouldn't work for me. I'm trying to build something so this works:

        let is_even = |x: &i32| *x % 2 == 0;
        let is_odd = |x: &i32| *x % 2 == 0;
        let pattern = sequence(&[
            is_even,
            is_odd,
            repeat(or(is_even, is_odd), 2, 4),
        ]);
        let mut matcher = Matcher::compile(pattern);
        let elements = [4, 1, 23, 5, 6];
        for element in elements {
            matcher.step(element);
        }
        assert!(matcher.matches());

I'll get there one day.

Amazing work on the Regex crate by the way!

[ Parent | on HN ]

Re:Regex Engine Internals as a Library by ynik on Thursday July 06, 2023 @09:33AM (#36615514)

It's not that hard to build a backtracking matching engine, at least if performance is not important. I did that in the past for the C# syntax tree used in a decompiler. Basically the syntax tree has a bunch of additional (non-syntax) pattern nodes, that support flexible regex-style matching of a pattern-tree against a concrete syntax tree.

Example pattern: https://github.com/icsharpcode/ILSpy/blob/1100d64e4bbd878164...

Implementation: https://github.com/icsharpcode/ILSpy/tree/1100d64e4bbd878164...

[ Parent | on HN ]