version = "1.0.0"

version = "1.0.0"

license = " GPL-3.0-or-later"

# Regular expresso

Written as an exercise in Rust and a refreshment of my university classes on finite automatons.

The supported syntax is restricted to the following operators:

* `*` - the Kleene star. The previous item can be present zero or more times.

* Concatenation - is implied between items following each other. `ab*` matches an `a` followed by any number of `b`s

* `+` or `|` - a union of several alternatives. Both symbols are equivalent.

* `_` - a lambda, an empty string

* `()` - parentheses, grouping several tokens together. For example `a|b*` matches a single `a` or any number of `b`s. `(a|b)*` matches any string of `a`s and `b`s

* Symbols not listed above are used as they are. There is no escaping, so matching for the operator literals is not possible.

## Usage

The python code supports Python 3.9 and higher. The rust code is written for Rust edition 2021.

```

# Match a string against a pattern (returns true or false)

python regexp.py match PATTERN STRING

# or

cargo run match PATTERN STRING

# Compare two regexps and return None of they are equivalent, or the shortest string that can distinguish them

# That is, it gets accepted by one, but not the other

python regexp.py compare PATTERN1 PATTERN2

# or

cargo run compare PATTERN1 PATTERN2

```

## Theory

1. The pattern gets parsed into a tree of its parts.

2. We check which symbols can stand at the beginning, which can follow each other and which can stand at the end of the string. These data are used to construct a non-deterministic finite automaton (NFA).

3. *Determinization:* We explore the possible paths through the NFA, recording the state sets visited. Each set is then converted to a single state of a deterministic finite automaton (DFA).

4. *Reduction (minimization):* We iteratively check which states of the DFA are equivalent - they can't be distinguished from each other by any string. Each equivalence class can be collapsed to a single state, compressing and simplifying the DFA.

5. *Normalization:* Finally we normalize the DFA by visiting its states in a breadth-first search (BFS) order, with edges ordered by the alphabet. Any unreachable states get removed here. (1)

6. Two regular expressions are equivalent if and only if their normalized DFAs are equal.

### Looking for a distinguishing string

1. We construct DFAs for both patterns as described just above.

2. We merge them into a product automaton, with states being a carthesian product of the original DFAs' states, and the transition function constructed accordingly. The state `(qa, qb)` is accepting if exactly one of `qa`, `qb` was accepting in the original automatons. (2)

3. We search through the product automaton's states in a BFS order, recording our path, until we find an accepting state. The path from the start to the accepting state defines a distinguishing word for the two input automata.

### Notes

(1) This is formally described as a part of reduction, but the implementation leaves it as a side effect of normalization.

Also note that the algorithm doesn't actually produce any unreachable states, so this is only relevant in (2).

(2) Construction of the product automaton can create plenty of states that can't be actually reached and their removal gets useful.

from typing import Iterator, Optional

	"""Abstract base class representing a single item of a regular expressions."""

	# is the Token mandatory, or can it be omitted

	def list_first(self) -> Iterator[int]:

		"""List all possible string positions the token can start with."""

	def list_last(self) -> Iterator[int]:

		"""List all possible string positions the token can end with."""

	def list_neighbours(self) -> Iterator[tuple[int, int]]:

		"""List positions of all possibly neighbouring subtokens."""

	"""An empty string, useful as an `Alternative`."""

	"""A regular letter or any other symbol without a special function."""

	def __init__(self, position: int, value: str):

	"""A unary operator specifying its content to occur zero or more times."""

	"""An operator with a variable number of arguments, specifying exchangeable alternatives."""

	def __init__(self, content: list[Token]):

		""":raises ParsingError: raised on an empty variant. That is an AlternativeSeparator surrounded by no other Tokens."""

	"""A special token to temporarily separate Alternative variants. Removed in the Alternative constructor."""

	"""An operator expressing a concatenation of its content Tokens."""

	def __init__(self, content: list[Token]):

def find_closing_parenthesis(pattern: str, pos: int) -> int:

	"""Given an opening parenthesis, find the closing one.

	:param pattern: the regexp pattern

	:param pos: the opening parenthesis position

	:return: a position of the matching closing parenthesis

	:raises AssertionError: on an incorrect call, if there is not an opening parenthesis at `pos`

	:raises ParsingError: on a malformed pattern with no matching parenthesis"""

	assert pattern[pos] == "("

	for (i, c) in enumerate(pattern[pos:]):

			return pos+i

	raise ParsingError(f'A closing parenthesis not found. Pattern: "{pattern}", position: {pos}')

def parse(pattern: str, offset: int=0) -> Token:

	"""Recursively parse the pattern into a Token tree.

	:param pattern: the regexp string

	:param offset: where the `pattern` starts in the original pattern, to record correct global token positions in the subcalls

	:return: a token sequence, wrapped in a Chain or an Alternative"""

def print_dfa(dfa: "RegexpDFA", label: str=""):

	"""Utility function for printing automatons in a readable format."""

	def __init__(self, pattern: str):

		"""Parse a pattern string into a sequence of Tokens and build a non-deterministic finite automaton from them."""

		# (state, symbol): {state1, ...}

		# record possible starting symbols

		# record all pairs of symbols that can immediately follow each other

		# record possible last symbols and mark them as accepting states

	def match(self, s: str) -> bool:

		"""Decide if a string matches the regexp.

		:param s: an input string"""

	def determinize(self) -> "RegexpDFA":

		"""Convert the non-deterministic finite automaton into a deterministic one."""

		# explore all possible state sets the NFA can visit

			# collect possible target states

			# map the state sets to integer labels and record them in a single dimensional rules list

		# create an additional fail state

		# and redirect all undefined transition rules to it

		return RegexpDFA(compact_rules, end_states, alphabet_index)

	def __init__(self, rules: list[int], end_states: set[int], alphabet_index: dict[str, int]):

		"""A deterministic finite automaton constructor.

		If the `rules` or the `alphabet_index` are empty, then instead of an empty automaton we create a trivial automaton failing on any input (accepting empty strings).

		:param rules: transition rules, where (i*n+j)th item defines the transition for i-th state on j-th alphabet symbol

		:param end_states: accepting states

		:param alphabet_index: mapping from alphabet symbols to rule columns"""

	@staticmethod

	def create(pattern: str) -> "RegexpDFA":

		"""Create a `Regexp` and determinize it."""

		return r.determinize()

	def match(self, s: str):

		"""Decide if a string matches the regexp.

		:param s: an input string"""

	def reduce(self) -> "RegexpDFA":

		"""Minimize the automaton by collapsing equivalent states."""

	def normalize(self) -> "RegexpDFA":

		"""Normalize the automaton by relabeling the states in a breadth first search walkthrough order and remove unreachable states."""

	def find_distinguishing_string(self, r: "RegexpDFA") -> Optional[str]:

		"""Find the shortest string that is accepted by self or `r`, but not both.

		:param r: the other automaton

		:return: the distinguishing string, or None if the automatons are equivalent"""

		r1 = self.reduce().normalize()

		r2 = r.reduce().normalize()

		if r1.rules == r2.rules and r1.end_states == r2.end_states:

		r1 = r1._expand_alphabet(r2.alphabet_index)

		r2 = r2._expand_alphabet(r1.alphabet_index)

		# state: symbol

		inverse_alphabet_index = {v: k for (k, v) in product.alphabet_index.items()}

					queue.append((target, acc+inverse_alphabet_index[i]))

	def _find_equivalent_states(self) -> list[set[int]]:

		"""Partition states into their equivalence classes with Hopcroft's algorithm.

		:return: sets of equivalent states. Unique states get single item sets."""

		# a transition rules inverse. target state + alphabet symbol -> source states

	def _collapse_states(self, partition: list[set[int]]) -> tuple[list[int], set[int]]:

		"""Collapse equivalent states from each class into a single one.

		:param partition: list of equivalence classes

		:return: rules list, accepting states"""

		# states mapping due to the equivalents collapse

		# states mapping to keep the rules list compact after the equivalents collapse

	def _expand_alphabet(self, alphabet_index: dict[str, int]) -> "RegexpDFA":

		"""Expand the automaton to accommodate union of `self.alphabet_index` and the provided `alphabet_index`.

		:param alphabet_index: a mapping from letters to rules columns

		:return: a RegexpDFA over the unified alphabet"""

		# a new alphabet_index

		# a new letter key: the old letter key

		# rewrite the rules into a new table, filling blanks with a new fail state

	def _build_product_automaton(self, r: "RegexpDFA") -> "RegexpDFA":

		"""Create a new automaton, with a carthesian product of the arguments' states and corresponding transition rules.

		:param r: the other finite automaton. It must have the same `alphabet_index` as `self`"""

		assert self.alphabet_index == r.alphabet_index

		# expand each self state into m new states, one for each of the r states

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