RegEx engine module that builds NFA/DFA and uses it for matching

[Sicro]

RegEx engine module for PureBasic

• GitHub project page: Click
• Download: Click (see assets)

I've been working on a "regex engine" module for PureBasic for a while. The engine compiles a regular expression into an NFA (Nondeterministic finite automaton), optionally also into a very fast DFA (Deterministic finite automaton), and can run the NFA/DFA against a string.

When matching, the engine always chooses the longest match among several possible matches. No backtracking is required during this process, since all alternatives are checked simultaneously. So for a regular expression "0123x|0123y" and the string "0123y", after the failure at "x", the engine does not start again from the beginning at "0", but is behind "3" and the engine only has to read "y". In contrast to an NFA, a DFA does not try anything out, i.e. the DFA reads “y” directly.

It is also possible to pass multiple regular expressions to the engine and set unique ID numbers for them to be able to determine which regular expression matched in case of a match. This functionality makes it easy to create lexers. This is also the real motivation that led to this project. However, the engine is kept flexible in its usage and can easily be used for other purposes as well, which is why I don't consider it exclusively a lexer engine and therefore didn't name it that way.

You can find some code examples, the listing of the supported syntax for the regular expressions, further information and the module itself on GitHub.

Currently, the project is in beta phase, so I would be very grateful for feedback from you.

Features that are currently planned for upcoming versions: Click
These features will not be included in the current beta phase of version 1.0.0, but only in the next minor versions, e.g. 1.1.0, 1.2.0 etc.

Note that this project does not intend to provide a RegEx engine to replace more feature-rich engines like the PCRE natively integrated in PureBasic. So there will be no support for capturing groups, backreferences, word boundaries and anchors.

[Sicro]

1.0.0-beta.2 released

Download: Click

Improved

• Unicode case unfolding table rewritten, resulting in 44% smaller executables.
• Character classes now produce much more compact NFAs, resulting in faster NFA matching, faster DFA creation, and less memory consumption.
• The more compact NFAs also benefit the DFAs, as they are now much smaller as well.

Fixed

• Escaping opening square brackets within character classes was not possible.

[Kwai chang caine]

Hello SICRO

First thanks for sharing this nice code
Unfortunately, like surely numerous persons i don't understand one word of the REGEX
But the worst it's that interesting me when even

I profit from your splendid works to ask to you a question, if you allow me
Your work can he translate REGEX in something understandable by the first fool to come ? (like me for exampler )
And if not, know you a very very simple freeware, for babies, who can create a REGEX without learn this complex rules ?

Congratulations again for your work

[Sicro]

Your work can he translate REGEX in something understandable by the first fool to come ? (like me for exampler )

If you have trouble imagining how a RegEx works, you can use a RegEx visualizer or a tool that explains the RegEx.

And if not, know you a very very simple freeware, for babies, who can create a REGEX without learn this complex rules ?

You don't need a tool for that. If you experiment a bit with RegEx, you will quickly understand how it works. Start simple, like "a|b" and experiment further.

If you want to discuss further about RegEx in general, better create a new thread in this forum.

Congratulations again for your work

Thanks!

[Kwai chang caine]

Thanks a lot for your answer

[Sicro]

1.0.0-beta.2 has been re-released.

The SimpleCaseUnfolding table was a bit buggy. I didn't want to release a new beta version number for that.

Beta 3 is already in work and will probably be the last beta version.

[Sicro]

Finale 1.0.0 released

After some testing and improvements, I have now decided to release the final version 1.0.0

Download: Click

New

• Added ASCII mode, which restricts the predefined character classes to ASCII characters only (encoding is still UCS-2) and restricts case-insensitive mode to uppercase and lowercase letters only, instead of applying Unicode case-folding.
• Developer tools added.

Improved

• More error handling added.

Fixed

• Processing of RegExes like (a*)* or (a*)+ triggered an infinite loop.
• Parsing of RegEx modes was fixed.
• Memory leaks have been fixed.

[Sicro]

1.1.0-beta.1 released

Download: Click

New

• Single-byte mode: creates much smaller NFAs/DFAs by only supporting characters that do not need the second byte in the UCS-2 encoding (\x01 up to \xFF).
• Code example that visualizes the NFAs/DFAs as Graphviz diagrams.

Improved

• It is checked whether the parameter regExId in AddNfa() has a valid value.
• Matching with an NFA and creating a DFA is faster. The extent of the speed increase depends on how many alternative paths have to be followed during NFA processing (e.g. a large number of paths are followed by the very complex RegEx character class \w).

Fixed

• Outside of character classes, identical characters were unnecessarily added twice to the NFA when both case-insensitive mode and ASCII mode were enabled and the character has no upper and lower case.

[loulou2522]

Thanks to explain what is NFAs/DFAs
Happy Christmas

[Sicro]

You're welcome.

If you are interested in the NFA and DFA, I recommend that you experiment with the new code example that creates diagrams using the Graphviz tool. The diagrams are interesting to look at.

I wish you a Merry Christmas too.

[Sicro]

1.1.0-beta.2 released

Download: Click

Fixed

• Due to the implementation of single-byte mode, case-sensitive mode was not processed correctly with user-defined character classes (negated or not). This was also the case when single-byte mode was not activated.
• User-defined negated character classes were not processed correctly with single-byte mode activated.

[Sicro]

Final 1.1.0 released

Download: Click

In the next version, I will implement the feature of being able to create a minimal DFA from an existing DFA. Such a DFA contains only the number of states that are really required, which makes the DFA smaller and consumes less memory. However, the number of transitions that the DFA has to perform in a minimal form does not change, but maybe it is still faster because it fits better into the CPU cache, etc. It will be interesting.