Module nfa

Gregex Logic

Contains the underlying logic of the Gregex crate. This crate is responsible for converting the Node tree to the NFA. The NFA is then used to match the input string.

The crate uses the Glushkov’s Construction Algorithm to convert the Node tree to the NFA. The advantage over the Thompson’s Construction Algorithm is that the NFA generated has states equal to number of terminals + 1. Although, the NFA generated by Thumpson’s can be converted to the Glushkov’s form, by removing the epsilon transitions.

The translation module contains the code to convert the Node tree to the NFA. The nfa module contains the code to match the input string with the NFA. Has the implementation of a non-deterministic finite automaton (NFA).

Structs

NFA

The NFA struct represents a non-deterministic finite automaton.