Changeset - 0163ce5ddc96
Parent rev.
Child rev.
[Not reviewed]
default
0 4 0
Laman - 11 months ago 2024-06-22 22:02:30

added the automaton reduction
4 files changed with 119 insertions and 14 deletions:
regexp.py
54
4
src/main.rs
2
2
src/regexp.rs
55
tests/test_regexp.rs
8
8
0 comments (0 inline, 0 general)
regexp.py
➞
Show inline comments
 
@@ -271,9 +271,16 @@ class Regexp:
 

			




	
	
	
		
 

			




	
	
	
		
 
class RegexpDFA:

			




	
	
	
		
 
	def __init__(self, pattern):

			




	
	
	
		
 
	def __init__(self, rules, end_states):

			




	
	
	
		
 
		self.rules = rules

			




	
	
	
		
 
		self.end_states = end_states

			




	
	
	
		
 

			




	
	
	
		
 
	@classmethod

			




	
	
	
		
 
	def create(cls, pattern):

			




	
	
	
		
 
		r = Regexp(pattern)

			




	
	
	
		
 
		(self.rules, self.end_states) = r.determinize()

			




	
	
	
		
 
		(rules, end_states) = r.determinize()

			




	
	
	
		
 

			




	
	
	
		
 
		return cls(rules, end_states)

			




	
	
	
		
 

			




	
	
	
		
 
	def match(self, s):

			




	
	
	
		
 
		st = (-1,)

			




	
	
		
 
@@ -287,13 +294,56 @@ class RegexpDFA:

			




	
	
	
		
 

			




	
	
	
		
 
		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)

			




	
	
	
		
 

			




	
	
	
		
 
	def _find_equivalent_states(self):

			




	
	
	
		
 
		state_set = [(-2,), (-1,)] + sorted(set(self.rules.values()))

			




	
	
	
		
 
		alphabet = {c for (st, c) in self.rules.keys()}

			




	
	
	
		
 
		equivalents = {(s1, s2) for (i, s1) in enumerate(state_set) for s2 in state_set[i+1:]}

			




	
	
	
		
 

			




	
	
	
		
 
		for (s1, s2) in equivalents.copy():

			




	
	
	
		
 
			if (s1 in self.end_states and s2 not in self.end_states) or (s1 not in self.end_states and s2 in self.end_states):

			




	
	
	
		
 
				equivalents.remove((s1, s2))

			




	
	
	
		
 
		

			




	
	
	
		
 
		ctrl = True

			




	
	
	
		
 
		while ctrl:

			




	
	
	
		
 
			ctrl = False

			




	
	
	
		
 
			for (s1, s2) in equivalents.copy():

			




	
	
	
		
 
				for c in alphabet:

			




	
	
	
		
 
					t1 = self.rules.get((s1, c), (-2,))

			




	
	
	
		
 
					t2 = self.rules.get((s2, c), (-2,))

			




	
	
	
		
 
					key = (min(t1, t2), max(t1, t2))

			




	
	
	
		
 
					if t1 != t2 and key not in equivalents:

			




	
	
	
		
 
						equivalents.remove((s1, s2))

			




	
	
	
		
 
						ctrl = True

			




	
	
	
		
 
						break

			




	
	
	
		
 
		

			




	
	
	
		
 
		return equivalents

			




	
	
	
		
 
	

			




	
	
	
		
 
	def _collapse_states(self, equivalents):

			




	
	
	
		
 
		rules = self.rules.items()

			




	
	
	
		
 
		end_states = self.end_states.copy()

			




	
	
	
		
 

			




	
	
	
		
 
		for (s1, s2) in sorted(equivalents):

			




	
	
	
		
 
			rules = map(

			




	
	
	
		
 
				lambda item: (item[0], s1 if item[1] == s2 else item[1]),

			




	
	
	
		
 
				filter(lambda item: item[0][0] != s2, rules)

			




	
	
	
		
 
			)

			




	
	
	
		
 
			end_states.discard(s2)

			




	
	
	
		
 
		

			




	
	
	
		
 
		return (dict(rules), end_states)

			




	
	
	
		
 

			




	
	
	
		
 

			




	
	
	
		
 
if __name__ == "__main__":

			




	
	
	
		
 
	tests = ["", "a", "ab", "aabb", "abab", "abcd", "abcbcdbcd"]

			




	
	
	
		
 
	for pattern in ["*", "((a)", "a)"]:

			




	
	
	
		
 
	for pattern in ["a(b|c)", "a*b*", "(ab)*", "a((bc)*d)*"]:

			




	
	
	
		
 
		print("#", pattern)

			




	
	
	
		
 
		try:

			




	
	
	
		
 
			r = RegexpDFA(pattern)

			




	
	
	
		
 
			r = RegexpDFA.create(pattern).reduce()

			




	
	
	
		
 
		except ParsingError as e:

			




	
	
	
		
 
			print("Failed to parse the regexp:")

			




	
	
	
		
 
			print(e)

			




        

    


    
    

    

        

                

                    src/main.rs
                

                

                  
                      
                        

                      ➞

                      
                        
                  

                  
                      
                  
                      
                  
                      
                  
                      
                  
                  
                

                

                    Show inline comments
                    
                

        

        

            



	
	
		
 
@@ -2,10 +2,10 @@ use regexp::Regexp;

			




	
	
	
		
 

			




	
	
	
		
 
fn main() {

			




	
	
	
		
 
	let tests = ["", "a", "ab", "aabb", "abab", "abcd", "abcbcdbcd"];

			




	
	
	
		
 
	for pattern in ["a(b|c)", "a*b*", "a+b+", "(ab)*", "(ab)+", "a((bc)*d)*"] {

			




	
	
	
		
 
	for pattern in ["a(b|c)", "a*b*", "(ab)*", "a((bc)*d)*"] {

			




	
	
	
		
 
		println!("# {pattern}");

			




	
	
	
		
 
		let r = match Regexp::new(&pattern.to_string()) {

			




	
	
	
		
 
			Ok(r1) => r1.determinize(),

			




	
	
	
		
 
			Ok(r1) => r1.determinize().reduce(),

			




	
	
	
		
 
			Err(e) => {

			




	
	
	
		
 
				println!("{e}");

			




	
	
	
		
 
				continue;

			




        

    


    
    

    

        

                

                    src/regexp.rs
                

                

                  
                      
                        

                      ➞

                      
                        
                  

                  
                      
                  
                      
                  
                      
                  
                      
                  
                  
                

                

                    Show inline comments
                    
                

        

        

            



	
	
		
 
@@ -5,6 +5,7 @@ pub use token::ParsingError;

			




	
	
	
		
 
use token::parse;

			




	
	
	
		
 

			




	
	
	
		
 
const START: usize = usize::MAX;

			




	
	
	
		
 
const FAIL: usize = START-1;

			




	
	
	
		
 

			




	
	
	
		
 
fn encode_set(set: &HashSet<usize>) -> u64 {

			




	
	
	
		
 
	let mut res = 0;

			




	
	
		
 
@@ -144,4 +145,58 @@ impl RegexpDFA {

			




	
	
	
		
 

			




	
	
	
		
 
		return self.end_states.contains(&state);

			




	
	
	
		
 
	}

			




	
	
	
		
 

			




	
	
	
		
 
	pub fn reduce(&self) -> RegexpDFA {

			




	
	
	
		
 
		let equivalents = self.find_equivalent_states();

			




	
	
	
		
 
		return self.collapse_states(equivalents);

			




	
	
	
		
 
	}

			




	
	
	
		
 

			




	
	
	
		
 
	fn find_equivalent_states(&self) -> Vec<(u64, u64)> {

			




	
	
	
		
 
		let state_set: HashSet<u64> = HashSet::from_iter(self.rules.values().copied());

			




	
	
	
		
 
		let mut state_vec: Vec<u64> = Vec::from_iter(state_set.into_iter());

			




	
	
	
		
 
		state_vec.push(START as u64);

			




	
	
	
		
 
		state_vec.push(FAIL as u64);

			




	
	
	
		
 
		state_vec.sort();

			




	
	
	
		
 
		state_vec.reverse();

			




	
	
	
		
 
		let alphabet: HashSet<char> = self.rules.keys().map(|(_st, c)| c).copied().collect();

			




	
	
	
		
 

			




	
	
	
		
 
		let mut equivalents = HashSet::new();

			




	
	
	
		
 
		state_vec.iter().enumerate().for_each(|(i, s1)| {

			




	
	
	
		
 
			equivalents.extend(

			




	
	
	
		
 
				state_vec[i+1..].iter()

			




	
	
	
		
 
				.filter(|s2| !(self.end_states.contains(s1)^self.end_states.contains(s2)))

			




	
	
	
		
 
				.map(|s2| (*s1, *s2))

			




	
	
	
		
 
			);

			




	
	
	
		
 
		});

			




	
	
	
		
 

			




	
	
	
		
 
		let mut n = usize::MAX;

			




	
	
	
		
 
		while equivalents.len() < n {

			




	
	
	
		
 
			n = equivalents.len();

			




	
	
	
		
 
			equivalents = equivalents.iter().filter(|(s1, s2)| {

			




	
	
	
		
 
				!alphabet.iter().any(|c| {

			




	
	
	
		
 
					let t1 = self.rules.get(&(*s1, *c)).unwrap_or(&(FAIL as u64));

			




	
	
	
		
 
					let t2 = self.rules.get(&(*s2, *c)).unwrap_or(&(FAIL as u64));

			




	
	
	
		
 
					let key = (*t1.min(t2), *t1.max(t2));

			




	
	
	
		
 
					return t1 != t2 && !equivalents.contains(&key);

			




	
	
	
		
 
				})

			




	
	
	
		
 
			}).copied().collect();

			




	
	
	
		
 
		}

			




	
	
	
		
 

			




	
	
	
		
 
		return Vec::from_iter(equivalents.into_iter());

			




	
	
	
		
 
	}

			




	
	
	
		
 

			




	
	
	
		
 
	fn collapse_states(&self, mut equivalents: Vec<(u64, u64)>) -> RegexpDFA {

			




	
	
	
		
 
		let mut rules = self.rules.clone();

			




	
	
	
		
 
		let mut end_states = self.end_states.clone();

			




	
	
	
		
 
		equivalents.sort();

			




	
	
	
		
 

			




	
	
	
		
 
		for (s1, s2) in equivalents.into_iter() {

			




	
	
	
		
 
			rules = rules.into_iter()

			




	
	
	
		
 
				.filter(|((st, _c), _t)| *st != s2)

			




	
	
	
		
 
				.map(|(key, t)| (key, if t==s2 {s1} else {t})).collect();

			




	
	
	
		
 
			end_states.remove(&s2);

			




	
	
	
		
 
		}

			




	
	
	
		
 

			




	
	
	
		
 
		return RegexpDFA{rules, end_states};

			




	
	
	
		
 
	}

			




	
	
	
		
 
}

			




        

    


    
    

    

        

                

                    tests/test_regexp.rs
                

                

                  
                      
                        

                      ➞

                      
                        
                  

                  
                      
                  
                      
                  
                      
                  
                      
                  
                  
                

                

                    Show inline comments
                    
                

        

        

            



	
	
		
 
@@ -11,7 +11,7 @@ fn test_eval_basic_nfa() {

			




	
	
	
		
 

			




	
	
	
		
 
#[test]

			




	
	
	
		
 
fn test_eval_basic_dfa() {

			




	
	
	
		
 
	let r = Regexp::new(&String::from("abc")).unwrap().determinize();

			




	
	
	
		
 
	let r = Regexp::new(&String::from("abc")).unwrap().determinize().reduce();

			




	
	
	
		
 
	assert!(r.eval(String::from("abc")));

			




	
	
	
		
 
	assert!(!r.eval(String::from("ab")));

			




	
	
	
		
 
	assert!(!r.eval(String::from("abcd")));

			




	
	
		
 
@@ -27,9 +27,9 @@ fn test_eval_empty_nfa() {

			




	
	
	
		
 

			




	
	
	
		
 
#[test]

			




	
	
	
		
 
fn test_eval_empty_dfa() {

			




	
	
	
		
 
	assert!(Regexp::new(&String::from("a*")).unwrap().determinize().eval(String::from("")));

			




	
	
	
		
 
	assert!(Regexp::new(&String::from("")).unwrap().determinize().eval(String::from("")));

			




	
	
	
		
 
	assert!(!Regexp::new(&String::from("")).unwrap().determinize().eval(String::from("a")));

			




	
	
	
		
 
	assert!(Regexp::new(&String::from("a*")).unwrap().determinize().reduce().eval(String::from("")));

			




	
	
	
		
 
	assert!(Regexp::new(&String::from("")).unwrap().determinize().reduce().eval(String::from("")));

			




	
	
	
		
 
	assert!(!Regexp::new(&String::from("")).unwrap().determinize().reduce().eval(String::from("a")));

			




	
	
	
		
 
}

			




	
	
	
		
 

			




	
	
	
		
 
#[test]

			




	
	
		
 
@@ -43,7 +43,7 @@ fn test_eval_asterisk_nfa() {

			




	
	
	
		
 

			




	
	
	
		
 
#[test]

			




	
	
	
		
 
fn test_eval_asterisk_dfa() {

			




	
	
	
		
 
	let r = Regexp::new(&String::from("a*b*")).unwrap().determinize();

			




	
	
	
		
 
	let r = Regexp::new(&String::from("a*b*")).unwrap().determinize().reduce();

			




	
	
	
		
 
	assert!(r.eval(String::from("a")));

			




	
	
	
		
 
	assert!(r.eval(String::from("ab")));

			




	
	
	
		
 
	assert!(r.eval(String::from("aabb")));

			




	
	
		
 
@@ -62,7 +62,7 @@ fn test_eval_alternative_nfa() {

			




	
	
	
		
 

			




	
	
	
		
 
#[test]

			




	
	
	
		
 
fn test_eval_alternative_dfa() {

			




	
	
	
		
 
	let r = Regexp::new(&String::from("a|b|c")).unwrap().determinize();

			




	
	
	
		
 
	let r = Regexp::new(&String::from("a|b|c")).unwrap().determinize().reduce();

			




	
	
	
		
 
	assert!(r.eval(String::from("a")));

			




	
	
	
		
 
	assert!(r.eval(String::from("b")));

			




	
	
	
		
 
	assert!(r.eval(String::from("c")));

			




	
	
		
 
@@ -85,12 +85,12 @@ fn test_eval_lambda_nfa() {

			




	
	
	
		
 

			




	
	
	
		
 
#[test]

			




	
	
	
		
 
fn test_eval_lambda_dfa() {

			




	
	
	
		
 
	let r = Regexp::new(&String::from("a_")).unwrap().determinize();

			




	
	
	
		
 
	let r = Regexp::new(&String::from("a_")).unwrap().determinize().reduce();

			




	
	
	
		
 
	assert!(r.eval(String::from("a")));

			




	
	
	
		
 
	assert!(!r.eval(String::from("")));

			




	
	
	
		
 
	assert!(!r.eval(String::from("ab")));

			




	
	
	
		
 

			




	
	
	
		
 
	let r = Regexp::new(&String::from("a|_")).unwrap().determinize();

			




	
	
	
		
 
	let r = Regexp::new(&String::from("a|_")).unwrap().determinize().reduce();

			




	
	
	
		
 
	assert!(r.eval(String::from("a")));

			




	
	
	
		
 
	assert!(r.eval(String::from("")));

			




	
	
	
		
 
	assert!(!r.eval(String::from("b")));

			




        

    



    


    



    



      

      





    
    0 comments (0 inline, 0 general)
    





    


  

  







  


    




    








    
        Server instance: Sirius-538
    
    
        This site is powered by
            Kallithea 0.7.0,
        which is
        © 2010–2023 by various authors & licensed under GPLv3.
            – Support