Regular-Expresso Changeset

Changeset - 68c16b6d84f3

Parent rev.

Child rev.

[Not reviewed]

default

0 3 0

Laman - 10 months ago 2024-06-20 13:49:15

added the lambda transition

3 files changed with 51 insertions and 0 deletions:

regexp.py

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 Lambda(Token):
 	is_skippable = True
 	def list_first(self):
 		yield from []
 	def list_last(self):
 		yield from []
 	def list_neighbours(self):
 		yield from []
 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()
@@ @@ -167,48 +180,51 @@ def parse(pattern, offset=0): @@
 			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
 		elif c == "_":
 			res.append(Lambda())
 			i += 1
 		else:
 			res.append(Symbol(i+offset, c))
 			i += 1
 	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)

src/regexp/token.rs

➞

Show inline comments

@@ @@ -31,48 +31,49 @@ impl fmt::Display for ParsingError { @@
+	}
+}
 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 {
 	Lambda,
 	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> {
@@ @@ -204,81 +205,85 @@ impl Chain { @@
 		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::Lambda => true,
 			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::Lambda => vec![],
 			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::Lambda => vec![],
 			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::Lambda => vec![],
 			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> {
@@ @@ -292,47 +297,51 @@ pub fn parse(pattern: &String, offset: u @@
 			'(' => {
 				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;
+			}
 			'_' => {
 				res.push(Box::new(Token::Lambda));
 				i += 1;
+			}
 			_c => {
 				res.push(Box::new(Token::Symbol(Symbol{position: i+offset})));
 				i += 1;
+			}
+		}
+	}
 	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

@@ @@ -68,48 +68,74 @@ fn test_eval_plus_dfa() { @@
 	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_eval_lambda_nfa() {
 	let r = Regexp::new(&String::from("a_")).unwrap();
 	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();
 	assert!(r.eval(String::from("a")));
 	assert!(r.eval(String::from("")));
 	assert!(!r.eval(String::from("b")));
+}
 #[test]
 fn test_eval_lambda_dfa() {
 	let r = Regexp::new(&String::from("a_")).unwrap().determinize();
 	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();
 	assert!(r.eval(String::from("a")));
 	assert!(r.eval(String::from("")));
 	assert!(!r.eval(String::from("b")));
+}
 #[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]

0 comments (0 inline, 0 general)