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
Code
use make_dfa;
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
Code
use make_dfa;
Output
[src/main.rs:30] &path = [
"Seen { }",
"Seen { b }",
"Seen { ba }",
"Seen { }",
"Seen { b }",
"Seen { ba }",
"Seen { bab }",
"Seen { bab }",
]