Gregex

Gregex is a regular expression solver which utilizes Non-deterministic Finite Automata (NFA) to simulate the input strings.

Usage

extern crate gregex;
use gregex::*;
fn main() {
    let tree = concatenate!(production!(terminal('a')), terminal('b'), terminal('c'));
    let regex = regex(&tree);
    assert!(regex.simulate("abc"));
    assert!(!regex.simulate("a"));
    assert!(regex.simulate("aaabc"));
}

Theory

The project uses Glushkov's construction algorithm for creating the NFA.

The pipeline can be summarised as below

lib.rs:

This crate provides a regular expression engine that uses a Nondeterministic finite automaton to simulate the regular expression. Here is a short example on how to use this crate

extern crate gregex;
use gregex::*;

fn main() {
    let tree = concatenate!(production!(terminal('a')), terminal('b'), terminal('c'));
    let regex = regex(&tree);
    assert!(regex.simulate("abc"));
    assert!(!regex.simulate("a"));
    assert!(regex.simulate("aaabc"));
}

The regex function uses the regular expression string to create a NFA that can be used to simulate the regular expression. The program uses the Glushkov's construction algorithm to create its NFA. The NFA is then later simulated to check if the input string matches the regular expression.

A brief overview of the pipeline: [