Expand description
§NFA Regex
A non finite automata regular expression engine library. NFA Regex concept: https://swtch.com/~rsc/regexp/regexp1.html
Implementation of NFA regex engine:
- Convert infix string regex pattern to postfix pattern also called reverse polish notation. https://en.wikipedia.org/wiki/Reverse_Polish_notation https://www.free-online-calculator-use.com/infix-to-postfix-converter.html
- Build the NFA regex engine from the postfix notation.
List of supported operators for NFA regex:
| Operator | Description |
|---|---|
| \ | Escape character |
| - | Range operator. E.g. [0-9a-z] |
| . | Any displayable character (also called metacharacter) |
| [] | Square bracket, Ors characters inside |
| () | Round bracket, groups characters (concats) |
| * | Zero or more character repeatition |
| + | One or more charatcer repeatition |
| ? | Zero or one character repeatition |
| {m,n} or {n} | Curly bracket for character repeatition with min and max limit count |
| ^ | Exclude characters used only inside [] at the begin. E.g. [^ab] - string must not have a and b. |
| ––––––– | ————————————————————————————————————————————————— |
Operator precedance and associativity, table taken from unix: (Not all operators are supported in below implementation.) +—+–––––––––––––––––––––––––––––+ | | ERE Precedence (from high to low) | +—+–––––––––––––––––––––––––––––+ | 1 | Collation-related bracket symbols | [==] [::] [..] | | 2 | Escaped characters | <special character> | | 3 | Bracket expression | [] | | 4 | Grouping | () | | 5 | Single-character-ERE duplication | * + ? {m,n} | | 6 | Concatenation | | | 7 | Anchoring | ^ $ | | 8 | Alternation | | | +—+———————————–+–––––––––––+
Structs§
- Regex
- NFA regex engine