Regular-Expresso Changeset

Changeset - e9496b21cf64

Parent rev.

Child rev.

[Not reviewed]

default

0 4 0

Laman - 10 months ago 2024-06-20 12:36:50

added the alternative operator

4 files changed with 172 insertions and 5 deletions:

regexp.py

src/main.rs

src/regexp/token.rs

tests/test_regexp.rs

0 comments (0 inline, 0 general)

regexp.py

➞

Show inline comments

 from abc import abstractmethod
 class ParsingError(Exception):
 	pass
 class Token:
 	is_skippable = False
 	@abstractmethod
 	def list_first(self):
 		pass
 	@abstractmethod
 	def list_last(self):
 		pass
 	@abstractmethod
 	def list_neighbours(self):
 		pass
 class Symbol(Token):
 	def __init__(self, position, value):
 		self.position = position
 		self.value = value
 	def list_first(self):
 		yield self.position
 	def list_last(self):
 		yield self.position
 	def list_neighbours(self):
 		yield from []
 	def __str__(self):
 		return self.value
 class Plus(Token):
 	def __init__(self, content: Token):
 		self.content = content
 	def list_first(self):
 		yield from self.content.list_first()
 	def list_last(self):
 		yield from self.content.list_last()
 	def list_neighbours(self):
 		yield from self.content.list_neighbours()
 		for x in self.list_last():
 			for y in self.list_first():
 				yield (x, y)
 	def __str__(self):
 		return str(self.content) + "+"
 class Asterisk(Plus):
 	is_skippable = True
 	def __str__(self):
 		return str(self.content) + "*"
 class Alternative(Token):
 	def __init__(self, content: list):
 		self.variants = []
 		subsequence = []
 		for token in content:
 			if isinstance(token, AlternativeSeparator):
 				if not subsequence:
 					raise ParsingError("Found an empty Alternative variant.")
 				self.variants.append(Chain(subsequence))
 				subsequence = []
 			else:
 				subsequence.append(token)
 		if not subsequence:
 				raise ParsingError("Found an empty Alternative variant.")
 		self.variants.append(Chain(subsequence))
 	def list_first(self):
 		for x in self.variants:
 			yield from x.list_first()
 	def list_last(self):
 		for x in self.variants:
 			yield from x.list_last()
 	def list_neighbours(self):
 		for x in self.variants:
 			yield from x.list_neighbours()
 	@property
 	def is_skippable(self):
 		return any(x.is_skippable for x in self.variants)
 class AlternativeSeparator:
 	pass
 class Chain(Token):
 	def __init__(self, content: list):
 		self.content = content
 	def list_first(self):
 		for token in self.content:
 			yield from token.list_first()
 			if not token.is_skippable:
 				break
 	def list_last(self):
 		for token in reversed(self.content):
 			yield from token.list_last()
 			if not token.is_skippable:
 				break
 	def list_neighbours(self):
 		previous = []
 		for token in self.content:
 			for t in previous:
 				for x in t.list_last():
 					for y in token.list_first():
 						yield (x, y)
 			yield from token.list_neighbours()
 			if token.is_skippable:
 				previous.append(token)
 			else:
 				previous = [token]
 	@property
 	def is_skippable(self):
 		return all(x.is_skippable for x in self.content)
 	def __str__(self):
 		return "(" + "".join(str(x) for x in self.content) + ")"
 def find_closing_parenthesis(pattern, k):
 	counter = 0
 	for (i, c) in enumerate(pattern[k:]):
 		if c == "(":
 			counter += 1
 		elif c == ")":
 			counter -= 1
 		if counter == 0:
 			return k+i
 	raise ParsingError(f'A closing parenthesis not found. Pattern: "{pattern}", position: {k}')
 def parse(pattern, offset=0):
 	res = []
 	is_alternative = False
 	i = 0
 	while i < len(pattern):
 		c = pattern[i]
 		if c == "(":
 			j = find_closing_parenthesis(pattern, i)
 			inner_content = parse(pattern[i+1:j], offset+i+1)
 			res.append(inner_content)
 			i = j+1
 		elif c == "*":
 			try:
 				token = res.pop()
 			except IndexError as e:
 				raise ParsingError(f'The asterisk operator is missing an argument. Pattern: "{pattern}", position {i}')
 			res.append(Asterisk(token))
 			i += 1
 		elif c == "+":
 			try:
 				token = res.pop()
 			except IndexError as e:
 				raise ParsingError(f'The plus operator is missing an argument. Pattern: "{pattern}", position {i}')
 			res.append(Plus(token))
 			i += 1
 		elif c == ")":
 			raise ParsingError(f'An opening parenthesis not found. Pattern: "{pattern}", position: {i}')
 		elif c == "|":
 			is_alternative = True
 			res.append(AlternativeSeparator())
 			i += 1
 		else:
 			res.append(Symbol(i+offset, c))
 			i += 1
 	return Chain(res)
 	if is_alternative:
 		return Alternative(res)
 	else:
 		return Chain(res)
 class Regexp:
 	def __init__(self, pattern):
 		(self.rules, self.end_states) = self._parse(pattern)
 	def _parse(self, s):
 		r = parse(s)
 		rules = dict()
 		for i in r.list_first():
 			c = s[i]
 			key = (-1, c)
 			if key not in rules:
 				rules[key] = set()
 			rules[key].add(i)
 		for (i, j) in r.list_neighbours():
 			c = s[j]
 			key = (i, c)
 			if key not in rules:
 				rules[key] = set()
 			rules[key].add(j)
 		end_states = set(r.list_last())
 		if r.is_skippable:
 			end_states.add(-1)
 		return rules, end_states
 	def match(self, s):
 		current = {-1}
 		for c in s:
 			new_state = set()
 			for st in current:
 				key = (st, c)
 				if key in self.rules:
 					new_state.update(self.rules[key])
 			current = new_state
 		return any(st in self.end_states for st in current)
 	def determinize(self):
 		rules = dict()
 		end_states = {(-1,)} if -1 in self.end_states else set()
 		stack = [(-1,)]
 		processed_states = set()
 		while stack:
 			multistate = stack.pop()
 			new_rules = dict()
 			for ((st, c), target) in filter(lambda item: item[0][0] in multistate, self.rules.items()):
 				if c not in new_rules:
 					new_rules[c] = set()
 				new_rules[c].update(target)
 			for (c, target_set) in new_rules.items():
 				new_target = tuple(sorted(target_set))
 				rules[(multistate, c)] = new_target
 				if any(st in self.end_states for st in new_target):
 					end_states.add(new_target)
 				if new_target not in processed_states:
 					stack.append(new_target)
 					processed_states.add(new_target)
 		return (rules, end_states)
 class RegexpDFA:
 	def __init__(self, pattern):
 		r = Regexp(pattern)
 		(self.rules, self.end_states) = r.determinize()
 	def match(self, s):
 		st = (-1,)
 		for c in s:
 			key = (st, c)
 			if key in self.rules:
 				st = self.rules[key]
 			else:
 				return False
 		return st in self.end_states
 if __name__ == "__main__":
 	tests = ["", "a", "ab", "aabb", "abab", "abcd", "abcbcdbcd"]
 	for pattern in ["*", "((a)", "a)"]:
 		print("#", pattern)
 		try:
 			r = RegexpDFA(pattern)
 		except ParsingError as e:
 			print("Failed to parse the regexp:")

src/main.rs

➞

Show inline comments

 use regexp::Regexp;
 fn main() {
 	let tests = ["", "a", "ab", "aabb", "abab", "abcd", "abcbcdbcd"];
-	for pattern in ["*", "((a)", "a)", "+a"] {
+	for pattern in ["a(b|c)", "a*b*", "a+b+", "(ab)*", "(ab)+", "a((bc)*d)*"] {
 		println!("# {pattern}");
 		let r = match Regexp::new(&pattern.to_string()) {
 			Ok(r1) => r1.determinize(),
 			Err(e) => {
 				println!("{e}");
 				continue;
+			}
 		};
 		for &t in tests.iter() {
 			println!("{t} {}", r.eval(t.to_string()));
+		}
 		println!();
+	}
+}

src/regexp/token.rs

➞

Show inline comments

 use std::fmt;
+use std::{borrow::Borrow, fmt};
 #[derive(Debug, Clone)]
 pub enum ParsingError {
 	Asterisk {s: String, pos: usize},
 	Plus {s: String, pos: usize},
 	OpeningParenthesis {s: String, pos: usize},
 	ClosingParenthesis {s: String, pos: usize}
 	ClosingParenthesis {s: String, pos: usize},
 	EmptyAlternativeVariant
+}
 impl fmt::Display for ParsingError {
 	fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 		match self {
 			ParsingError::Asterisk {s, pos} => {
 				write!(f, "The asterisk operator is missing an argument. Pattern \"{s}\", position {pos}")
 			},
 			ParsingError::Plus {s, pos} => {
 				write!(f, "The plus operator is missing an argument. Pattern \"{s}\", position {pos}")
 			},
 			ParsingError::OpeningParenthesis {s, pos} => {
 				write!(f, "An opening parenthesis not found. Pattern \"{s}\", position {pos}")
 			},
 			ParsingError::ClosingParenthesis {s, pos} => {
 				write!(f, "An closing parenthesis not found. Pattern \"{s}\", position {pos}")
 			},
 			ParsingError::EmptyAlternativeVariant => {
 				write!(f, "Found an empty Alternative variant.")
+			}
+		}
+	}
+}
 pub struct Symbol {
 	position: usize
+}
 pub struct Asterisk {
 	content: Box<Token>
+}
 pub struct Plus {
 	content: Box<Token>
+}
 pub struct Alternative {
 	content: Vec<Box<Token>>
+}
 pub struct Chain {
 	content: Vec<Box<Token>>
+}
 pub enum Token {
 	Symbol(Symbol),
 	Asterisk(Asterisk),
 	Plus(Plus),
 	Alternative(Alternative),
 	AlternativeSeparator,
 	Chain(Chain)
+}
 impl Symbol {
 	fn list_first(&self) -> Vec<usize> {
 		return vec![self.position];
+	}
 	fn list_last(&self) -> Vec<usize> {
 		return vec![self.position];
+	}
 	fn list_neighbours(&self) -> Vec<(usize, usize)> {
 		return vec![];
+	}
+}
 impl Asterisk {
 	fn list_first(&self) -> Vec<usize> {
 		return self.content.list_first();
+	}
 	fn list_last(&self) -> Vec<usize> {
 		return self.content.list_last();
+	}
 	fn list_neighbours(&self) -> Vec<(usize, usize)> {
 		let mut res = self.content.list_neighbours();
 		for x in self.list_last() {
 			for y in self.list_first() {
 				res.push((x, y));
+			}
+		}
 		return res;
+	}
+}
 impl Plus {
 	fn list_first(&self) -> Vec<usize> {
 		return self.content.list_first();
+	}
 	fn list_last(&self) -> Vec<usize> {
 		return self.content.list_last();
+	}
 	fn list_neighbours(&self) -> Vec<(usize, usize)> {
 		let mut res = self.content.list_neighbours();
 		for x in self.list_last() {
 			for y in self.list_first() {
 				res.push((x, y));
+			}
+		}
 		return res;
+	}
+}
 impl Alternative {
 	fn new(content: Vec<Box<Token>>) -> Result<Alternative, ParsingError> {
 		let mut variants: Vec<Vec<Box<Token>>> = vec![Vec::new()];
 		content.into_iter().for_each(|x| {
 			if matches!(x.borrow(), Token::AlternativeSeparator) {
 				variants.push(Vec::new());
 			} else {
 				variants.last_mut().unwrap().push(x);
+			}
 		});
 		if variants.iter().any(|x| x.is_empty()) {
 			return Err(ParsingError::EmptyAlternativeVariant);
+		}
 		return Ok(Alternative{
 			content: variants.into_iter().map(
 				|x| Box::new(Token::Chain(Chain{content: x}))
 			).collect()
 		});
+	}
 	fn is_skippable(&self) -> bool {
 			return self.content.iter().any(|x| x.is_skippable());
+	}
 	fn list_first(&self) -> Vec<usize> {
 		let mut res = Vec::new();
 		for token in self.content.iter() {
 			res.append(&mut token.list_first());
+		}
 		return res;
+	}
 	fn list_last(&self) -> Vec<usize> {
 		let mut res = Vec::new();
 		for token in self.content.iter() {
 			res.append(&mut token.list_last());
+		}
 		return res;
+	}
 	fn list_neighbours(&self) -> Vec<(usize, usize)> {
 		let mut res = Vec::new();
 		for token in self.content.iter() {
 			res.append(&mut token.list_neighbours());
+		}
 		return res;
+	}
+}
 impl Chain {
 	fn is_skippable(&self) -> bool {
 		return self.content.iter().all(|x| x.is_skippable());
+	}
 	fn list_first(&self) -> Vec<usize> {
 		let mut res = Vec::new();
 		for token in self.content.iter() {
 			res.append(&mut token.list_first());
 			if !token.is_skippable() {break;}
+		}
 		return res;
+	}
 	fn list_last(&self) -> Vec<usize> {
 		let mut res = Vec::new();
 		for token in self.content.iter().rev() {
 			res.append(&mut token.list_last());
 			if !token.is_skippable() {break;}
+		}
 		return res;
+	}
 	fn list_neighbours(&self) -> Vec<(usize, usize)> {
 		let mut res = Vec::new();
 		let mut previous: Vec<&Box<Token>> = Vec::new();
 		for token in self.content.iter() {
 			for t in previous.iter() {
 				for x in t.list_last() {
 					for y in token.list_first() {
 						res.push((x, y));
+					}
+				}
+			}
 			res.append(&mut token.list_neighbours());
 			if token.is_skippable() {
 				previous.push(token);
 			} else {
 				previous = vec![token];
+			}
+		}
 		return res;
+	}
+}
 impl Token {
 	pub fn is_skippable(&self) -> bool {
 		match self {
 			Token::Symbol(_) => false,
 			Token::Asterisk(_) => true,
 			Token::Plus(_) => false,
 			Token::Alternative(t) => t.is_skippable(),
 			Token::AlternativeSeparator => panic!(),
 			Token::Chain(t) => t.is_skippable()
+		}
+	}
 	pub fn list_first(&self) -> Vec<usize> {
 		match self {
 			Token::Symbol(t) => t.list_first(),
 			Token::Asterisk(t) => t.list_first(),
 			Token::Plus(t) => t.list_first(),
 			Token::Alternative(t) => t.list_first(),
 			Token::AlternativeSeparator => panic!(),
 			Token::Chain(t) => t.list_first()
+		}
+	}
 	pub fn list_last(&self) -> Vec<usize> {
 		match self {
 			Token::Symbol(t) => t.list_last(),
 			Token::Asterisk(t) => t.list_last(),
 			Token::Plus(t) => t.list_last(),
 			Token::Alternative(t) => t.list_last(),
 			Token::AlternativeSeparator => panic!(),
 			Token::Chain(t) => t.list_last()
+		}
+	}
 	pub fn list_neighbours(&self) -> Vec<(usize, usize)> {
 		match self {
 			Token::Symbol(t) => t.list_neighbours(),
 			Token::Asterisk(t) => t.list_neighbours(),
 			Token::Plus(t) => t.list_neighbours(),
 			Token::Alternative(t) => t.list_neighbours(),
 			Token::AlternativeSeparator => panic!(),
 			Token::Chain(t) => t.list_neighbours()
+		}
+	}
+}
 fn find_closing_parenthesis(s: &String) -> Option<usize> {
 	let chars: Vec<char> = s.chars().collect();
 	let mut counter = 0;
 	for (i, c) in chars.iter().enumerate() {
 		if *c == '(' {counter += 1;}
 		else if *c == ')' {counter -= 1;}
 		if counter == 0 {return Some(i);}
+	}
 	return None;
+}
 pub fn parse(pattern: &String, offset: usize) -> Result<Token, ParsingError> {
 	let chars: Vec<char> = pattern.chars().collect();
 	let mut res: Vec<Box<Token>> = Vec::new();
 	let mut is_alternative = false;
 	let mut i = 0;
 	while i < pattern.len() {
 		let c = chars[i];
 		match c {
 			'(' => {
 				let j = find_closing_parenthesis(&pattern[i..].to_string()).ok_or(ParsingError::ClosingParenthesis {s: pattern.clone(), pos: i})? + i;
 				let inner_content = parse(&pattern[i+1..j].to_string(), offset+i+1)?;
 				res.push(Box::new(inner_content));
 				i = j+1;
+			}
 			'*' => {
 				let token = res.pop().ok_or(ParsingError::Asterisk{s: pattern.clone(), pos: i})?;
 				res.push(Box::new(Token::Asterisk(Asterisk{content: token})));
 				i += 1;
+			}
 			'+' => {
 				let token = res.pop().ok_or(ParsingError::Plus{s: pattern.clone(), pos: i})?;
 				res.push(Box::new(Token::Plus(Plus{content: token})));
 				i += 1;
+			}
 			')' => {
 				return Err(ParsingError::OpeningParenthesis {s: pattern.clone(), pos: i});
+			}
 			'|' => {
 				is_alternative = true;
 				res.push(Box::new(Token::AlternativeSeparator));
 				i += 1;
+			}
 			_c => {
 				res.push(Box::new(Token::Symbol(Symbol{position: i+offset})));
 				i += 1;
+			}
+		}
+	}
 	return Ok(Token::Chain(Chain{content: res}));
 	if is_alternative {
 		return Ok(Token::Alternative(Alternative::new(res)?));
 	} else {
 		return Ok(Token::Chain(Chain{content: res}));
+	}
+}
 mod test {
 	use super::*;
 	#[test]
 	fn test_closing_parenthesis() {
 		let s = "()";
 		assert_eq!(find_closing_parenthesis(&s.to_string()), Some(1));
+	}
+}

tests/test_regexp.rs

➞

Show inline comments

 use regexp::Regexp;
 use regexp::ParsingError;
 #[test]
 fn test_eval_basic_nfa() {
 	let r = Regexp::new(&String::from("abc")).unwrap();
 	assert!(r.eval(String::from("abc")));
 	assert!(!r.eval(String::from("ab")));
 	assert!(!r.eval(String::from("abcd")));
+}
 #[test]
 fn test_eval_basic_dfa() {
 	let r = Regexp::new(&String::from("abc")).unwrap().determinize();
 	assert!(r.eval(String::from("abc")));
 	assert!(!r.eval(String::from("ab")));
 	assert!(!r.eval(String::from("abcd")));
+}
 #[test]
 fn test_eval_empty_nfa() {
 	assert!(Regexp::new(&String::from("a*")).unwrap().eval(String::from("")));
 	assert!(Regexp::new(&String::from("")).unwrap().eval(String::from("")));
 	assert!(!Regexp::new(&String::from("")).unwrap().eval(String::from("a")));
 	assert!(!Regexp::new(&String::from("a")).unwrap().eval(String::from("")));
+}
 #[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")));
+}
 #[test]
 fn test_eval_asterisk_nfa() {
 	let r = Regexp::new(&String::from("a*b*")).unwrap();
 	assert!(r.eval(String::from("a")));
 	assert!(r.eval(String::from("ab")));
 	assert!(r.eval(String::from("aabb")));
 	assert!(!r.eval(String::from("abab")));
+}
 #[test]
 fn test_eval_asterisk_dfa() {
 	let r = Regexp::new(&String::from("a*b*")).unwrap().determinize();
 	assert!(r.eval(String::from("a")));
 	assert!(r.eval(String::from("ab")));
 	assert!(r.eval(String::from("aabb")));
 	assert!(!r.eval(String::from("abab")));
+}
 #[test]
 fn test_eval_plus_nfa() {
 	let r = Regexp::new(&String::from("(ab)+")).unwrap();
 	assert!(!r.eval(String::from("a")));
 	assert!(r.eval(String::from("ab")));
 	assert!(r.eval(String::from("abab")));
 	assert!(!r.eval(String::from("aabb")));
+}
 #[test]
 fn test_eval_plus_dfa() {
 	let r = Regexp::new(&String::from("(ab)+")).unwrap().determinize();
 	assert!(!r.eval(String::from("a")));
 	assert!(r.eval(String::from("ab")));
 	assert!(r.eval(String::from("abab")));
 	assert!(!r.eval(String::from("aabb")));
+}
 #[test]
 fn test_eval_alternative_nfa() {
 	let r = Regexp::new(&String::from("a|b|c")).unwrap();
 	assert!(r.eval(String::from("a")));
 	assert!(r.eval(String::from("b")));
 	assert!(r.eval(String::from("c")));
 	assert!(!r.eval(String::from("")));
 	assert!(!r.eval(String::from("ab")));
+}
 #[test]
 fn test_eval_alternative_dfa() {
 	let r = Regexp::new(&String::from("a|b|c")).unwrap().determinize();
 	assert!(r.eval(String::from("a")));
 	assert!(r.eval(String::from("b")));
 	assert!(r.eval(String::from("c")));
 	assert!(!r.eval(String::from("")));
 	assert!(!r.eval(String::from("ab")));
+}
 #[test]
 fn test_invalid_asterisk() {
 	let x = Regexp::new(&String::from("*"));
 	assert!(matches!(x, Err(ParsingError::Asterisk{s: _, pos: 0})));
+}
 #[test]
 fn test_invalid_plus() {
 	let x = Regexp::new(&String::from("+"));
 	assert!(matches!(x, Err(ParsingError::Plus{s: _, pos: 0})));
+}
 #[test]
 fn test_invalid_closing_parenthesis() {
 	let x = Regexp::new(&String::from("(a"));
 	assert!(matches!(x, Err(ParsingError::ClosingParenthesis{s: _, pos: 0})));
+}
 #[test]
 fn test_invalid_opening_parenthesis() {
 	let x = Regexp::new(&String::from("a)"));
 	assert!(matches!(x, Err(ParsingError::OpeningParenthesis{s: _, pos: 1})));
+}
 #[test]
 fn test_invalid_empty_variant_start() {
 	let x = Regexp::new(&String::from("a(|b)"));
 	assert!(matches!(x, Err(ParsingError::EmptyAlternativeVariant)));
+}
 #[test]
 fn test_invalid_empty_variant_end() {
 	let x = Regexp::new(&String::from("a|"));
 	assert!(matches!(x, Err(ParsingError::EmptyAlternativeVariant)));
+}
 #[test]
 fn test_invalid_empty_variant_middle() {
 	let x = Regexp::new(&String::from("a||b"));
 	assert!(matches!(x, Err(ParsingError::EmptyAlternativeVariant)));
+}

0 comments (0 inline, 0 general)