Changeset - 2810f86816cd
Parent rev.
Child rev.
[Not reviewed]
default
0 2 0
Laman - 10 months ago 2024-06-29 00:16:42

added an explicit fail state, removed its special handling from the code
2 files changed with 25 insertions and 11 deletions:
regexp.py
9
4
src/regexp.rs
16
7
0 comments (0 inline, 0 general)
regexp.py
➞
Show inline comments
 
@@ -272,12 +272,16 @@ class Regexp:
 
					index[target_tup] = new_target
 
					compact_rules.extend([-1] * n)
 
					stack.append(target_tup)
 
				compact_rules[index[multistate]*n + alphabet_index[c]] = index[target_tup]
 
				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):

			




	
	
		
 
@@ -292,15 +296,16 @@ class RegexpDFA:

			




	
	
	
		
 

			




	
	
	
		
 
		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 < 0:

			




	
	
	
		
 
			if c not in self.alphabet_index or st == fail:

			




	
	
	
		
 
				return False

			




	
	
	
		
 
			key = (st*n + self.alphabet_index[c])

			




	
	
	
		
 
			st = self.rules[key]

			




	
	
	
		
 

			




	
	
	
		
 
		return st in self.end_states

			




	
	
	
		
 

			




	
	
		
 
@@ -309,23 +314,23 @@ class RegexpDFA:

			




	
	
	
		
 
		(rules, end_states) = self._collapse_states(equivalents)

			




	
	
	
		
 

			




	
	
	
		
 
		return RegexpDFA(rules, end_states, self.alphabet_index)

			




	
	
	
		
 

			




	
	
	
		
 
	def normalize(self):

			




	
	
	
		
 
		n = len(self.alphabet_index)

			




	
	
	
		
 
		index = {-1: -1, 0: 0}

			




	
	
	
		
 
		index = {0: 0}

			




	
	
	
		
 
		queue = deque([0])

			




	
	
	
		
 

			




	
	
	
		
 
		rules = []

			




	
	
	
		
 

			




	
	
	
		
 
		while queue:

			




	
	
	
		
 
			si = queue.popleft()

			




	
	
	
		
 
			row = self.rules[si*n:(si+1)*n]

			




	
	
	
		
 
			for sj in row:

			




	
	
	
		
 
				if sj not in index:

			




	
	
	
		
 
					index[sj] = len(index)-1

			




	
	
	
		
 
					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}

			




	
	
	
		
 

			




	
	
	
		
 
		return RegexpDFA(rules, end_states, self.alphabet_index)

			




	
	
		
 
@@ -355,13 +360,13 @@ class RegexpDFA:

			




	
	
	
		
 
		rules = []

			




	
	
	
		
 

			




	
	
	
		
 
		eq_mapping = dict()

			




	
	
	
		
 
		for (s1, s2) in equivalents:

			




	
	
	
		
 
			eq_mapping[s2] = min(s1, eq_mapping.get(s2, math.inf))

			




	
	
	
		
 

			




	
	
	
		
 
		discard_mapping = {-1: -1}

			




	
	
	
		
 
		discard_mapping = dict()

			




	
	
	
		
 
		discard_count = 0

			




	
	
	
		
 

			




	
	
	
		
 
		for i in range(0, len(self.rules), n):

			




	
	
	
		
 
			si = i//n

			




	
	
	
		
 
			if si in eq_mapping:

			




	
	
	
		
 
				discard_count += 1

			




        

    


    
    

    

        

                

                    src/regexp.rs
                

                

                  
                      
                        

                      ➞

                      
                        
                  

                  
                      
                  
                      
                  
                      
                  
                      
                  
                  
                

                

                    Show inline comments
                    
                

        

        

            



	
	
		
 
@@ -3,13 +3,12 @@ use std::{collections::{HashMap, HashSet

			




	
	
	
		
 
mod token;

			




	
	
	
		
 
pub use token::ParsingError;

			




	
	
	
		
 
use token::parse;

			




	
	
	
		
 

			




	
	
	
		
 
const START_NFA: usize = usize::MAX;

			




	
	
	
		
 
const START_DFA: usize = 0;

			




	
	
	
		
 
const FAIL: usize = usize::MAX>>1;

			




	
	
	
		
 

			




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

			




	
	
	
		
 
	let mut v = Vec::from_iter(set.iter());

			




	
	
	
		
 
	v.sort();

			




	
	
	
		
 
	let res: Vec<String> = v.into_iter().map(|x| x.to_string()).collect();

			




	
	
	
		
 
	return res.join(",");

			




	
	
		
 
@@ -77,12 +76,13 @@ impl Regexp {

			




	
	
	
		
 
		}

			




	
	
	
		
 

			




	
	
	
		
 
		return multistate.iter().any(|x| self.end_states.contains(x));

			




	
	
	
		
 
	}

			




	
	
	
		
 

			




	
	
	
		
 
	pub fn determinize(&self) -> RegexpDFA {

			




	
	
	
		
 
		const FAIL: usize = usize::MAX;

			




	
	
	
		
 
		let alphabet_index: HashMap<char, usize> = self.alphabet.iter().enumerate().map(|(i, c)| (*c, i)).collect();

			




	
	
	
		
 
		let n = alphabet_index.len();

			




	
	
	
		
 
		let mut compact_rules = vec![FAIL; n];

			




	
	
	
		
 
		let mut end_states: HashSet<usize> = HashSet::new();

			




	
	
	
		
 
		if self.end_states.contains(&START_NFA) {end_states.insert(START_DFA);}

			




	
	
	
		
 

			




	
	
		
 
@@ -121,12 +121,16 @@ impl Regexp {

			




	
	
	
		
 
				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};

			




	
	
	
		
 
	}

			




	
	
	
		
 
}

			




	
	
	
		
 

			




	
	
	
		
 
pub struct RegexpDFA {

			




	
	
	
		
 
	rules: Vec<usize>,

			




	
	
		
 
@@ -134,21 +138,25 @@ pub struct RegexpDFA {

			




	
	
	
		
 
	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;

			




	
	
	
		
 
		}

			




	
	
	
		
 
		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 {

			




	
	
	
		
 
			if state == fail {

			




	
	
	
		
 
				return false;

			




	
	
	
		
 
			}

			




	
	
	
		
 
		}

			




	
	
	
		
 

			




	
	
	
		
 
		return self.end_states.contains(&state);

			




	
	
	
		
 
	}

			




	
	
		
 
@@ -164,30 +172,31 @@ impl RegexpDFA {

			




	
	
	
		
 
	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 mut index: Vec<usize> = vec![FAIL;m];

			




	
	
	
		
 
		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];

			




	
	
	
		
 
			for &sj in row {

			




	
	
	
		
 
				if sj != FAIL && index[sj] == FAIL {

			




	
	
	
		
 
				if sj != fail && index[sj] == fail {

			




	
	
	
		
 
					index[sj] = k;

			




	
	
	
		
 
					k += 1;

			




	
	
	
		
 
					queue.push_back(sj);

			




	
	
	
		
 
				}

			




	
	
	
		
 
			}

			




	
	
	
		
 
			rules.extend(row.iter().map(|&st| if st != FAIL {index[st]} else {FAIL}));

			




	
	
	
		
 
			rules.extend(row.iter().map(|&st| index[st]));

			




	
	
	
		
 
		}

			




	
	
	
		
 

			




	
	
	
		
 
		let end_states = self.end_states.iter().map(|st| index[*st]).collect();

			




	
	
	
		
 
		

			




	
	
	
		
 
		return RegexpDFA{rules, end_states, alphabet_index: self.alphabet_index.clone()};

			




	
	
	
		
 
	}

			




	
	
		
 
@@ -236,15 +245,15 @@ impl RegexpDFA {

			




	
	
	
		
 
		for si in 0..m {

			




	
	
	
		
 
			if eq_mapping[si] != si {

			




	
	
	
		
 
				discard_count += 1;

			




	
	
	
		
 
				continue;

			




	
	
	
		
 
			}

			




	
	
	
		
 
			discard_mapping[si] = si-discard_count;

			




	
	
	
		
 
			rules.extend(self.rules[si*n..(si+1)*n].iter().map(|&st| if st!=FAIL {eq_mapping[st]} else {FAIL}));

			




	
	
	
		
 
			rules.extend(self.rules[si*n..(si+1)*n].iter().map(|&st| eq_mapping[st]));

			




	
	
	
		
 
		}

			




	
	
	
		
 

			




	
	
	
		
 
		rules = rules.into_iter().map(|st| if st!=FAIL {discard_mapping[st]} else {FAIL}).collect();

			




	
	
	
		
 
		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()};

			




	
	
	
		
 
	}

			




	
	
	
		
 
}

			




        

    



    


    



    



      

      





    
    0 comments (0 inline, 0 general)
    





    


  

  







  


    




    








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