diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/main.rs | 8 | ||||
| -rw-r--r-- | src/nfa.rs | 151 |
2 files changed, 159 insertions, 0 deletions
diff --git a/src/main.rs b/src/main.rs new file mode 100644 index 0000000..9218791 --- /dev/null +++ b/src/main.rs @@ -0,0 +1,8 @@ +mod nfa; + + +fn main() { + let mp_rule = "rule MP [A: formula, B: formula] { A } { A -> B } |- { B }"; + + println!("Hello, world!"); +} diff --git a/src/nfa.rs b/src/nfa.rs new file mode 100644 index 0000000..953e823 --- /dev/null +++ b/src/nfa.rs @@ -0,0 +1,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) + ) + } + } +} |