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 through a DFABuilder, which ensures that the DFA has valid transitions for every symbol in the alphabet.

Examples

Using the DFABuilder

Code Represntation ```rust use nifty::dfa::DFABuilder;

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

let mut dfa = DFABuilder::default()
    .add_state(&q0)
    .add_state(&q1)
    .add_state(&q2)
    .add_state(&q3)
    .mark_dead_state(&q3)
    .mark_start_state(&q0)
    .mark_accept_state(&q0)
    .mark_accept_state(&q1)
    .add_transition(&q0, &'a', &q1)
    .add_transition(&q0, &'b', &q3)
    .add_transition(&q1, &'a', &q1)
    .add_transition(&q1, &'b', &q2)
    .add_transition(&q2, &'a', &q1)
    .add_transition(&q2, &'b', &q2)
    .recognizes("string is empty, or begins and ends with the letter { a }.")
    .build();

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: "string is empty, or begins and ends with the letter { 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 ``` use nifty::dfa::DFABuilder;

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

let mut dfa = DFABuilder::default() .addstate(&q0) .addstate(&q1) .addstate(&q2) .addstate(&q3) .markgoalstate(&q3) .markstartstate(&q0) .addtransition(&q0, &'a', &q0) .addtransition(&q1, &'a', &q2) .addtransition(&q2, &'a', &q0) .addtransition(&q0, &'b', &q1) .addtransition(&q1, &'b', &q1) .addtransition(&q2, &'b', &q3) .recognizes("input contains { bab }") .build();

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 }", ]