Crate nfa_regex[−][src]

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:

  1. 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
  2. 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. 1 - string must not have a and b. | | | ORs characters or group. (Do not use inside []) |–––––––|—————————————————————————————————————————————————

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 | | | +—+———————————–+–––––––––––+

  1.  ↩

Structs

Regex

NFA regex engine