Regular-Expresso Changeset

Changeset - 1790bcb433e3

Parent rev.

Child rev.

[Not reviewed]

default

0 2 0

Laman - 10 months ago 2024-06-30 17:02:12

fixes: never create an empty automaton, removed the erroneous early fail

2 files changed with 18 insertions and 20 deletions:

regexp.py

src/regexp.rs

0 comments (0 inline, 0 general)

regexp.py

➞

Show inline comments

@@ @@ -285,42 +285,41 @@ class Regexp: @@
 				if any(st in self.end_states for st in target_set):
 					end_states.add(index[target_tup])
 		fail = len(index)
 		compact_rules = [(st if st >= 0 else fail) for st in compact_rules]
 		compact_rules.extend([fail] * n)
 		return (compact_rules, end_states, alphabet_index)
 class RegexpDFA:
 	def __init__(self, rules, end_states, alphabet_index):
 		self.rules = rules
+		self.rules = rules or [1, 1]
 		self.end_states = end_states
 		self.alphabet_index = alphabet_index
+		self.alphabet_index = alphabet_index or {"": 0}
 	@classmethod
 	def create(cls, pattern):
 		r = Regexp(pattern)
 		(rules, end_states, alphabet_index) = r.determinize()
 		return cls(rules, end_states, alphabet_index)
 	def match(self, s):
 		st = 0
 		n = len(self.alphabet_index)
 		fail = len(self.rules) // n
 		for c in s:
-			if c not in self.alphabet_index or st == fail:
 			if c not in self.alphabet_index:
 				return False
 			key = (st*n + self.alphabet_index[c])
 			st = self.rules[key]
 		return st in self.end_states
 	def reduce(self):
 		equivalents = self._find_equivalent_states()
 		(rules, end_states) = self._collapse_states(equivalents)
 		return RegexpDFA(rules, end_states, self.alphabet_index)

src/regexp.rs

➞

Show inline comments

@@ @@ -88,25 +88,25 @@ impl Regexp { @@
 		// string hash -> single int DFA state
 		let mut index_new = HashMap::from([(START_NFA.to_string(), START_DFA)]);
 		// string hash -> HashSet NFA multistate
 		let mut index_multi = HashMap::from([(START_NFA.to_string(), HashSet::from([START_NFA]))]);
 		let mut stack = Vec::from([START_NFA.to_string()]);
 		while !stack.is_empty() {
 			let state_hash = stack.pop().unwrap();
 			let multistate = &index_multi[&state_hash];
 			let mut new_rules: HashMap<char, HashSet<usize>> = HashMap::new();
-			for key in self.rules.keys().filter(|key| multistate.contains(&key.0)) {
+			for key in self.rules.keys().filter(|(st, _c)| multistate.contains(st)) {
 				let (_st, c) = key;
 				if !new_rules.contains_key(c) {
 					new_rules.insert(*c, HashSet::new());
+				}
 				for target in &self.rules[key] {
 					new_rules.get_mut(c).unwrap().insert(*target);
+				}
+			}
 			for (c, target_set) in new_rules.into_iter() {
 				let target_hash = encode_set(&target_set);
 				let is_end = target_set.iter().any(|st| self.end_states.contains(st));
@@ @@ -118,72 +118,71 @@ impl Regexp { @@
 					stack.push(target_hash.clone());
+				}
 				compact_rules[index_new[&state_hash]*n + alphabet_index[&c]] = index_new[&target_hash];
 				if is_end {
 					end_states.insert(index_new[&target_hash]);
+				}
+			}
+		}
 		let fail = index_new.len();
 		compact_rules = compact_rules.into_iter().map(|st| if st != FAIL {st} else {fail}).collect();
 		compact_rules.extend(iter::repeat(fail).take(n));
 		return RegexpDFA{rules: compact_rules, end_states, alphabet_index};
 		return RegexpDFA::new(compact_rules, end_states, alphabet_index);
+	}
+}
 #[derive(Clone)]
 pub struct RegexpDFA {
 	rules: Vec<usize>,
 	end_states: HashSet<usize>,
 	alphabet_index: HashMap<char, usize>
+}
 impl RegexpDFA {
 	pub fn new(rules: Vec<usize>, end_states: HashSet<usize>, alphabet_index: HashMap<char, usize>) -> RegexpDFA {
 		if rules.len() > 0 {
 			return RegexpDFA{rules, end_states, alphabet_index};
 		} else {
 			return RegexpDFA{
 				rules: vec![1, 1],
 				end_states,
 				alphabet_index: HashMap::from([('\0', 0)])
 			};
+		}
+	}
 	pub fn eval(&self, s: String) -> bool {
 		let n = self.alphabet_index.len();
 		if n == 0 {
 			return s.len() == 0;
+		}
 		let fail = self.rules.len() / n;
 		let mut state = START_DFA;
 		for c in s.chars() {
 			if let Some(ci) = self.alphabet_index.get(&c) {
 				state = self.rules[state*n + ci];
 			} else {
 				return false;
+			}
 			if state == fail {
 				return false;
+			}
+		}
 		return self.end_states.contains(&state);
+	}
 	pub fn reduce(&self) -> RegexpDFA {
 		if self.alphabet_index.len() == 0 {
 			return RegexpDFA{rules: self.rules.clone(), end_states: self.end_states.clone(), alphabet_index: self.alphabet_index.clone()};
+		}
 		let equivalents = self.find_equivalent_states();
 		return self.collapse_states(equivalents);
+	}
 	pub fn normalize(&self) -> RegexpDFA {
 		let n = self.alphabet_index.len();
 		if n == 0 {
 			return RegexpDFA{rules: self.rules.clone(), end_states: self.end_states.clone(), alphabet_index: self.alphabet_index.clone()};
+		}
 		let m = self.rules.len()/n;
 		let fail = m;
 		let mut index: Vec<usize> = vec![fail;m];
 		index[0] = 0;
 		let mut queue = VecDeque::from([START_DFA]);
 		let mut rules = vec![];
 		let mut k = 1;
 		while !queue.is_empty() {
 			let si = queue.pop_front().unwrap();
 			let row = &self.rules[si*n..(si+1)*n];

0 comments (0 inline, 0 general)