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 |
#148 in Parser tooling
22 downloads per month
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
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
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 }")