#dfa #machine #finite #state #automaton

nifty

A library for generating Deterministic Finite State Automata (DFA)

24 releases

0.3.3 May 22, 2019
0.3.2 May 22, 2019
0.2.9 May 22, 2019
0.1.9 May 22, 2019

#82 in Parser tooling

Download history 1/week @ 2023-10-22 24/week @ 2023-10-29 27/week @ 2023-11-12 1/week @ 2023-11-19 50/week @ 2023-11-26 73/week @ 2023-12-03 24/week @ 2023-12-17 48/week @ 2023-12-24 25/week @ 2023-12-31 1/week @ 2024-01-07 21/week @ 2024-01-14 24/week @ 2024-01-21 48/week @ 2024-01-28 1/week @ 2024-02-04

94 downloads per month

MIT license

335KB
8K SLoC

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

Building a DFA

example

Code

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 {
            d(q0, 'a') = q1
            d(q0, 'b') = q3

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

            d(q2, 'a') = q1
            d(q2, 'b') = 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",
    },
    accept_states: {
        "q0",
        "q1",
    },
    dead_states: {
        "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

example

Code

use nifty::make_dfa;

fn main() {
    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 {
            d(q0, 'a') = q0
            d(q1, 'a') = q2
            d(q2, 'a') = q0

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

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

    for tuple in &path {
        println!("{:?}", tuple);
    }   
}

Output

('a', "Seen { }")
('b', "Seen { b }")
('a', "Seen { ba }")
('a', "Seen { }")
('b', "Seen { b }")
('a', "Seen { ba }")
('b', "Seen { bab }")
('a', "Seen { bab }")

No runtime deps