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
|
use std::collections::HashMap;
enum RegexParseError {
}
/// guaranteed to have at least 2 states
/// state 0 is always the start state
/// state 1 is always the accept state
struct Nfa {
num_states: usize,
transitions: HashMap<(usize, char), Vec<usize>>
}
/// Nfa builder using Thompson's construction
/// Invariant: state 0 is always the start state
/// Invariant: state 1 is always the end state
/// Invariant: start state has no incoming edges
/// Invariant: end state has no outgoing edges
impl Nfa {
fn from_regex(pattern: &str) -> Result<Self, RegexParseError> {
todo!();
}
fn empty() -> Self {
Self {
num_states: 2,
transitions: HashMap::from_iter([ ((0, '\0'), vec![1]) ])
}
}
fn from_literals(cs: impl IntoIterator<Item=char>) -> Self {
Self {
num_states: 2,
transitions: HashMap::from_iter(
cs.into_iter().map(|c| ((0, c), vec![1]))
)
}
}
fn from_union(lhs: Self, rhs: Self) -> Self {
let offset_lhs = 2;
let offset_rhs = 2 + lhs.num_states;
let new_transitions = [
((0, '\0'), vec![offset_lhs, offset_rhs]),
((offset_lhs + 1, '\0'), vec![1]),
((offset_rhs + 1, '\0'), vec![1])
].into_iter();
let lhs_transitions = lhs.transitions.into_iter()
.map(|((q_old, c), qs_new)| {
let new_input = (q_old + offset_lhs, c);
let new_output = qs_new.into_iter().map(|q| q + offset_lhs).collect();
(new_input, new_output)
});
let rhs_transitions = rhs.transitions.into_iter()
.map(|((q_old, c), qs_new)| {
let new_input = (q_old + offset_rhs, c);
let new_output = qs_new.into_iter().map(|q| q + offset_rhs).collect();
(new_input, new_output)
});
Self {
num_states: lhs.num_states + rhs.num_states + 2,
transitions: HashMap::from_iter(
new_transitions.chain(lhs_transitions).chain(rhs_transitions)
)
}
}
fn from_concat(lhs: Self, rhs: Self) -> Self {
let offset_lhs = 2;
let offset_rhs = 2 + lhs.num_states;
let new_transitions = [
((0, '\0'), vec![offset_lhs]),
((offset_lhs + 1, '\0'), vec![offset_rhs]),
((offset_rhs + 1, '\0'), vec![1]),
].into_iter();
let lhs_transitions = lhs.transitions.into_iter()
.map(|((q_old, c), qs_new)| {
let new_input = (q_old + offset_lhs, c);
let new_output = qs_new.into_iter().map(|q| q + offset_lhs).collect();
(new_input, new_output)
});
let rhs_transitions = rhs.transitions.into_iter()
.map(|((q_old, c), qs_new)| {
let new_input = (q_old + offset_rhs, c);
let new_output = qs_new.into_iter().map(|q| q + offset_rhs).collect();
(new_input, new_output)
});
Self {
num_states: lhs.num_states + rhs.num_states + 2,
transitions: HashMap::from_iter(
new_transitions.chain(lhs_transitions).chain(rhs_transitions)
)
}
}
fn from_star(inner: Self) -> Self {
const INNER_OFFSET: usize = 2;
let new_transitions = [
((0, '\0'), vec![1, INNER_OFFSET]),
((INNER_OFFSET + 1, '\0'), vec![INNER_OFFSET, 1]),
].into_iter();
let inner_transitions = inner.transitions.into_iter()
.map(|((q_old, c), qs_new)| {
let new_input = (q_old + INNER_OFFSET, c);
let new_output = qs_new.into_iter().map(|q| q + INNER_OFFSET).collect();
(new_input, new_output)
});
Self {
num_states: inner.num_states + 2,
transitions: HashMap::from_iter(
new_transitions.chain(inner_transitions)
)
}
}
fn from_plus(inner: Self) -> Self {
const INNER_OFFSET: usize = 2;
let new_transitions = [
((0, '\0'), vec![INNER_OFFSET]),
((INNER_OFFSET + 1, '\0'), vec![INNER_OFFSET, 1]),
].into_iter();
let inner_transitions = inner.transitions.into_iter()
.map(|((q_old, c), qs_new)| {
let new_input = (q_old + INNER_OFFSET, c);
let new_output = qs_new.into_iter().map(|q| q + INNER_OFFSET).collect();
(new_input, new_output)
});
Self {
num_states: inner.num_states + 2,
transitions: HashMap::from_iter(
new_transitions.chain(inner_transitions)
)
}
}
}
|
