1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
//! |
//! # 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.
//!
//! # Documentation
//!
//! [nifty::dfa](dfa/index.html)
//! [nifty::make_dfa!](macro.make_dfa!.html)
//!
//! # Examples
//!
//! ## Building a DFA
//!
//! <img src="https://raw.githubusercontent.com/ObliqueMotion/nifty/master/images/example.png">
//!
//! ### Code
//!
//! ```
//! use nifty::make_dfa;
//!
//! 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 }"
//! }
//! };
//!
//! dfa.evaluate("".chars()); // Accept
//! dfa.evaluate("a".chars()); // Accept
//! dfa.evaluate("b".chars()); // Reject
//! dfa.evaluate("aa".chars()); // Accept
//! dfa.evaluate("ab".chars()); // Reject
//! dfa.evaluate("abb".chars()); // Reject
//! dfa.evaluate("aba".chars()); // Accept
//! dfa.evaluate("abba".chars()); // Accept
//! dfa.evaluate("babba".chars()); // Reject
//!
//! ```
//!
//! ## Tracing a Path
//!
//! <img src="https://raw.githubusercontent.com/ObliqueMotion/nifty/master/images/example2.png">
//!
//! ### 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
//!
//! ```text
//! ('a', "Seen { }")
//! ('b', "Seen { b }")
//! ('a', "Seen { ba }")
//! ('a', "Seen { }")
//! ('b', "Seen { b }")
//! ('a', "Seen { ba }")
//! ('b', "Seen { bab }")
//! ('a', "Seen { bab }")
//! ```
/// Macro [make_dfa!](macro.make_dfa!.html) creates a [DFA](dfa/struct.DFA.html) using the [DFABuilder](dfa/struct.DFABuilder.html).
///
/// 1. `make_dfa!` **must** take `states{...}` first.
/// 2. `make_dfa!` **may** take any of `start{...}`, `accept{...}`, `dead{...}`, `goal{...}` in any order.
/// 3. `make_dfa!` **may** take any of `transitions{...}`, `recognizes{...}` in any order.
///
/// ### Example
///
/// <img src="https://raw.githubusercontent.com/ObliqueMotion/nifty/master/images/example2.png">
///
/// ### Code
///
/// ```
/// 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 {
/// 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 }"
/// }
/// };
/// ```