From d41013cef2705a41c849b0df446bb1ff9ce85511 Mon Sep 17 00:00:00 2001
From: Daniel Hader <dhader96@gmail.com>
Date: Sun, 6 Sep 2026 10:16:26 -0500
Subject: Nfa construction using Thompson's method

---
 src/main.rs |   8 ++++
 src/nfa.rs  | 151 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 159 insertions(+)
 create mode 100644 src/main.rs
 create mode 100644 src/nfa.rs

(limited to 'src')

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)
+            )
+        }
+    }
+}
-- 
cgit v1.2.3