Regular-Expresso Changeset

Changeset - fd790596c353

Parent rev.

Child rev.

[Not reviewed]

default

0 2 0

Laman - 10 months ago 2024-06-30 16:15:19

implemented comparison of regexps with different alphabets

2 files changed with 65 insertions and 2 deletions:

regexp.py

src/regexp.rs

0 comments (0 inline, 0 general)

regexp.py

➞

Show inline comments

@@ @@ -197,24 +197,32 @@ def parse(pattern, offset=0): @@
 			res.append(Lambda())
 			i += 1
 		else:
 			res.append(Symbol(i+offset, c))
 			i += 1
 	if is_alternative:
 		return Alternative(res)
 	else:
 		return Chain(res)
 def print_dfa(dfa, label=""):
 	n = len(dfa.alphabet_index)
 	print(label)
 	for i in range(0, len(dfa.rules), n):
 		print(i//n, dfa.rules[i:i+n])
 	print(dfa.end_states)
 class Regexp:
 	def __init__(self, pattern):
 		r = parse(pattern)
 		rules = dict()
 		alphabet = set()
 		for i in r.list_first():
 			c = pattern[i]
 			alphabet.add(c)
 			key = (-1, c)
 			if key not in rules:
 				rules[key] = set()
@@ @@ -331,25 +339,27 @@ class RegexpDFA: @@
 					index[sj] = len(index)
 					queue.append(sj)
 			rules.extend(index[sj] for sj in row)
 		end_states = {index[si] for si in self.end_states if si in index}
 		return RegexpDFA(rules, end_states, self.alphabet_index)
 	def find_distinguishing_string(self, r):
 		if self.rules == r.rules and self.end_states == r.end_states:
 			return None
 		product = self._build_product_automaton(r)
 		r1 = self._expand_alphabet(r.alphabet_index)
 		r2 = r._expand_alphabet(self.alphabet_index)
 		product = r1._build_product_automaton(r2)
 		n = len(product.alphabet_index)
 		reverse_alphabet_index = {v: k for (k, v) in product.alphabet_index.items()}
 		queue = deque([(0, "")])
 		visited = {0}
 		while queue:
 			(state, acc) = queue.popleft()
 			if state in product.end_states:
 				return acc
 			for (i, target) in enumerate(product.rules[state*n:(state+1)*n]):
 				if target not in visited:
 					queue.append((target, acc+reverse_alphabet_index[i]))
@@ @@ -392,24 +402,46 @@ class RegexpDFA: @@
 			si = i//n
 			if si in eq_mapping:
 				discard_count += 1
 				continue
 			discard_mapping[si] = si - discard_count
 			rules.extend(map(lambda st: eq_mapping.get(st, st), self.rules[i:i+n]))
 		rules = [discard_mapping[st] for st in rules]
 		end_states = {discard_mapping[eq_mapping.get(st, st)] for st in self.end_states}
 		return (rules, end_states)
 	def _expand_alphabet(self, alphabet_index):
 		if alphabet_index == self.alphabet_index:
 			return self
 		n1 = len(self.alphabet_index)
 		m = len(self.rules) // n1
 		combined_alphabet = set(self.alphabet_index.keys()) | set(alphabet_index.keys())
 		combined_index = {c: i for (i, c) in enumerate(sorted(combined_alphabet))}
 		conversion_index = {v: combined_index[k] for (k, v) in self.alphabet_index.items()}
 		n2 = len(combined_alphabet)
 		rules = []
 		for i in range(0, len(self.rules), n1):
 			row = ([m]*n2)
 			for (j, st) in enumerate(self.rules[i:i+n1]):
 				row[conversion_index[j]] = st
 			rules.extend(row)
 		rules.extend([m]*n2)
 		return RegexpDFA(rules, self.end_states, combined_index).reduce().normalize()
 	def _build_product_automaton(self, r):
 		n = len(self.alphabet_index)
 		m = len(r.rules) // n
 		k = len(self.rules) // n
 		rules = []
 		end_states = set()
 		for s1 in range(k):
 			row1 = self.rules[s1*n:(s1+1)*n]
 			for s2 in range(m):
 				row2 = r.rules[s2*n:(s2+1)*n]

src/regexp.rs

➞

Show inline comments

@@ @@ -123,24 +123,25 @@ impl Regexp { @@
+				}
+			}
+		}
 		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};
+	}
+}
 #[derive(Clone)]
 pub struct RegexpDFA {
 	rules: Vec<usize>,
 	end_states: HashSet<usize>,
 	alphabet_index: HashMap<char, usize>
+}
 impl RegexpDFA {
 	pub fn eval(&self, s: String) -> bool {
 		let n = self.alphabet_index.len();
 		if n == 0 {
 			return s.len() == 0;
+		}
@@ @@ -197,25 +198,27 @@ impl RegexpDFA { @@
+		}
 		let end_states = self.end_states.iter().map(|st| index[*st]).collect();
 		return RegexpDFA{rules, end_states, alphabet_index: self.alphabet_index.clone()};
+	}
 	pub fn find_distinguishing_string(&self, other: &RegexpDFA) -> Option<String> {
 		if self.rules == other.rules && self.end_states == other.end_states {
 			return None;
+		}
 		let product = self.build_product_automaton(other);
 		let r1 = self.expand_alphabet(&other.alphabet_index);
 		let r2 = other.expand_alphabet(&self.alphabet_index);
 		let product = r1.build_product_automaton(&r2);
 		let n = product.alphabet_index.len();
 		let reverse_alphabet_index: HashMap<usize, char> = HashMap::from_iter(product.alphabet_index.iter().map(|(&k, &v)| (v, k)));
 		let mut queue = VecDeque::from([(0, "".to_string())]);
 		let mut visited = HashSet::new();
 		while !queue.is_empty() {
 			let (state, acc) = queue.pop_front().unwrap();
 			if product.end_states.contains(&state) {
 				return Some(acc);
+			}
 			for (i, target) in product.rules[state*n..(state+1)*n].iter().enumerate() {
 				if !visited.contains(target) {
@@ @@ -275,24 +278,52 @@ impl RegexpDFA { @@
 				continue;
+			}
 			discard_mapping[si] = si-discard_count;
 			rules.extend(self.rules[si*n..(si+1)*n].iter().map(|&st| eq_mapping[st]));
+		}
 		rules = rules.into_iter().map(|st| discard_mapping[st]).collect();
 		let end_states = self.end_states.iter().map(|st| discard_mapping[eq_mapping[*st]]).collect();
 		return RegexpDFA{rules, end_states, alphabet_index: self.alphabet_index.clone()};
+	}
 	fn expand_alphabet(&self, alphabet_index: &HashMap<char, usize>) -> RegexpDFA {
 		if *alphabet_index == self.alphabet_index {
 			return self.clone();
+		}
 		let n1 = self.alphabet_index.len();
 		let m = self.rules.len() / n1;
 		let combined_alphabet: HashSet<char> = HashSet::from_iter(self.alphabet_index.keys().chain(alphabet_index.keys()).copied());
 		let mut combined_vec = Vec::from_iter(combined_alphabet.into_iter());
 		combined_vec.sort();
 		let combined_index = HashMap::from_iter(combined_vec.iter().enumerate().map(|(i, c)| (*c, i)));
 		let conversion_index: HashMap<usize, usize> = HashMap::from_iter(self.alphabet_index.iter().map(|(k, v)| (*v, combined_index[k])));
 		let n2 = combined_vec.len();
 		let mut rules = vec![];
 		for i in 0..m {
 			let mut row = vec![m;n2];
 			for (j, st) in self.rules[i*n1..(i+1)*n1].iter().enumerate() {
 				row[conversion_index[&j]] = *st;
+			}
 			rules.append(&mut row);
+		}
 		rules.append(&mut vec![m;n2]);
 		return RegexpDFA{rules, end_states: self.end_states.clone(), alphabet_index: combined_index}.reduce().normalize();
+	}
 	fn build_product_automaton(&self, other: &RegexpDFA) -> RegexpDFA {
 		let n = self.alphabet_index.len();
 		let m = other.rules.len() / n;
 		let k = self.rules.len() / n;
 		let mut rules = vec![];
 		let mut end_states = HashSet::new();
 		for s1 in 0..k {
 			let row1 = &self.rules[s1*n..(s1+1)*n];
 			for s2 in 0..m {
 				let row2 = &other.rules[s2*n..(s2+1)*n];

0 comments (0 inline, 0 general)