nifty

A crate for generating Deterministic Finite State Automata in Rust.

Description

The goal of this crate is not to be an efficient parsing library. Use a regex for that.
Rather, this crate aims to preserve the integrity of stepping through a DFA state diagram.

It allows you to build a DFA with states of a generic type S that recognizes a language whose symbols are of a generic type T. You can traverse each transition symbol one by one, or you can consume an iterator of symbols, which the DFA will either Accept or Reject.

DFAs are created using a DFABuilder, or by using the make_dfa! macro. Both methods ensure that the DFA has valid transitions for every symbol in its alphabet.

Examples

Using the DFABuilder

Code Represntation ```rust use nifty::make_dfa;

fn main() { let q0 = "q0"; let q1 = "q1"; let q2 = "q2"; let q3 = "q3";

let mut dfa = make_dfa! {
    states { q0, q1, q2, q3 }
    accept { q0, q1 }
    start  { q0 }
    dead   { q3 }
    transitions {
        'a' => (q0, q1)
        'b' => (q0, q3)

        'a' => (q1, q1)
        'b' => (q1, q2)

        'a' => (q2, q1)
        'b' => (q2, q2)
    }
    recognizes { 
        "empty, or starts and ends with { a }"
    }
};

dbg!(&dfa);

dbg!(dfa.evaluate("".chars()));
dbg!(dfa.evaluate("a".chars()));
dbg!(dfa.evaluate("b".chars()));
dbg!(dfa.evaluate("aa".chars()));
dbg!(dfa.evaluate("ab".chars()));
dbg!(dfa.evaluate("abb".chars()));
dbg!(dfa.evaluate("aba".chars()));
dbg!(dfa.evaluate("abba".chars()));
dbg!(dfa.evaluate("babba".chars()));

} ```

Output ``` [src/lib.rs:82] &dfa = DFA { recognizes: "empty, or starts and ends with { a }", states: { "q0", "q1", "q2", "q3", }, acceptstates: { "q0", "q1", }, deadstates: { "q3", }, goal_states: {}, transitions: { 'a': { "q0": "q1", "q1": "q1", "q2": "q1", }, 'b': { "q0": "q3", "q1": "q2", "q2": "q2", }, }, start: Some( "q0", ), current: "q0", }

[src/main.rs:28] dfa.evaluate("".chars()) = Accept [src/main.rs:29] dfa.evaluate("a".chars()) = Accept [src/main.rs:30] dfa.evaluate("b".chars()) = Reject [src/main.rs:31] dfa.evaluate("aa".chars()) = Accept [src/main.rs:32] dfa.evaluate("ab".chars()) = Reject [src/main.rs:33] dfa.evaluate("abb".chars()) = Reject [src/main.rs:34] dfa.evaluate("aba".chars()) = Accept [src/main.rs:35] dfa.evaluate("abba".chars()) = Accept [src/main.rs:36] dfa.evaluate("babba".chars()) = Reject ```

Tracing a Path

Code ```rust use nifty::make_dfa;

let q0 = "Seen { }"; let q1 = "Seen { b }"; let q2 = "Seen { ba }"; let q3 = "Seen { bab }";

let mut dfa = make_dfa! { states { q0, q1, q2, q3 } start { q0 } goal { q3 } transitions { 'a' => (q0, q0) 'a' => (q1, q2) 'a' => (q2, q0)

    'b' => (q0, q1)
    'b' => (q1, q1)
    'b' => (q2, q3)
}
recognizes {
    "contains { bab }"
}

};

let path = "abaababa".chars() .map(|c| dfa.get_next(&c)) .collect::>();

dbg!(&path); ```

Output text [src/main.rs:30] &path = [ "Seen { }", "Seen { b }", "Seen { ba }", "Seen { }", "Seen { b }", "Seen { ba }", "Seen { bab }", "Seen { bab }", ]