FAdo.reex

Regular expressions manipulation

Regular expression classes and manipulation

class BuildRPNRegexp(context=None)

class BuildRPNSRE(context=None)

class BuildRegexp(context=None)

Semantics of the FAdo grammars’ regexps Priorities of operators: disj > conj > shuffle > concat > not > star >= option

class BuildSRE(context=None)

Parser for sre

class CAtom(val, sigma=None)

Simple Atom (symbol)

Variables:

• Sigma – alphabet set of strings

• val – the actual symbol

Constructor of a regular expression symbol.

Parameters:

val – the actual symbol

PD()

Closure of partial derivatives of the regular expression in relation to all words.

Returns:

set of regular expressions

Return type:

set

See also

Antimirov, 95

static alphabeticLength()

Number of occurrences of alphabet symbols in the regular expression.

Return type:

int

Attention

Doesn’t include the empty word.

derivative(sigma)

Derivative of the regular expression in relation to the given symbol.

Parameters:

sigma (str) – an arbitrary symbol.

Returns:

regular expression

Return type:

RegExp

Note

whether the symbols belong to the expression’s alphabet goes unchecked. The given symbol will be matched against the string representation of the regular expression’s symbol.

See also

10. 1. Brzozowski, Derivatives of Regular Expressions. J. ACM 11(4): 481-494 (1964)

static epsilonLength()

Number of occurrences of the empty word in the regular expression.

Return type:

int

first(parent_first=None)

List of possible symbols matching the first symbol of a string in the language of the regular expression.

Parameters:

parent_first (list) –

Returns:

list of symbols

Return type:

list

first_l()

First set for locations

followLists(lists=None)

Map of each symbol’s follow list in the regular expression.

Parameters:

lists (dict) –

Returns:

map of symbols’ follow lists {symbol: list of symbols}

Return type:

dict

Attention

For first() and last() return lists, the follow list for certain symbols might have repetitions in the case of follow maps calculated from Star operators. The union of last(), first() and follow() sets are always disjoint when the regular expression is in Star normal form ( Brüggemann-Klein, 92), therefore FAdo implements them as lists. You should order exclusively, or take a set from a list in order to resolve repetitions.

followListsD(lists=None)

Map of each symbol’s follow list in the regular expression.

Parameters:

lists (dict) –

Returns:

map of symbols’ follow list {symbol: list of symbols}

Return type:

dict

Attention

For first() and last() return lists, the follow list for certain symbols might have repetitions in the case of follow maps calculated from star operators. The union of last(), first() and follow() sets are always disjoint

See also

Sabine Broda, António Machiavelo, Nelma Moreira, and Rogério Reis. On the average size of glushkov and partial derivative automata. International Journal of Foundations of Computer Science, 23(5):969-984, 2012.

followListsStar(lists=None)

Map of each symbol’s follow list in the regular expression under a star.

Parameters:

lists (dict) –

Returns:

map of symbols’ follow lists {symbol: list of symbols}

Return type:

dict

See also

Sabine Broda, António Machiavelo, Nelma Moreira, and Rogério Reis. On the average size of glushkov and partial derivative automata. International Journal of Foundations of Computer Science, 23(5):969-984, 2012.

follow_l()

Follow set for locations

last(parent_last=None)

List of possible symbols matching the last symbol of a string in the language of the regular expression.

Parameters:

parent_last (list) –

Returns:

list of symbols

Return type:

list

last_l()

Last set for locations

linearForm()

Linear form of the regular expression , as a mapping from heads to sets of tails, so that each pair (head, tail) is a monomial in the set of linear forms.

Returns:

dict: dictionary mapping heads to sets of tails

See also

Antimirov, 95

linearFormC()

Returns:

linear form

Return type:

dict

linearP()

Whether the regular expression is linear; i.e., the occurrence of a symbol in the expression is unique.

Return type:

bool

mark()

Return type:

MAtom

static measure(from_parent=None)

A list with four measures for regular expressions.

Parameters:

from_parent –

Returns:

the measures

Return type:

[int,int,int,int]

[alphabeticLength, treeLength, epsilonLength, starHeight]

1. alphabeticLength: number of occurences of symbols of the alphabet;

2. treeLength: number of functors in the regular expression, including constants.

3. epsilonLength: number of occurrences of the empty word.

4. starHeight: highest level of nested Kleene stars, starting at one for one star occurrence.

5. disjLength: number of occurrences of the disj operator

6. concatLength: number of occurrences of the concat operator

7. starLength: number of occurrences of the star operator

8. conjLength: number of occurrences of the conj operator

9. starLength: number of occurrences of the shuffle operator

Attention

Methods for each of the measures are implemented independently. This is the most effective for obtaining more than one measure.

nfaThompson()

Epsilon-NFA constructed with Thompson’s method that accepts the regular expression’s language.

Returns:

NFA Thompson

Return type:

NFA

See also

11. Thompson. Regular Expression Search Algorithm. CACM 11(6), 419-422 (1968)

partialDerivatives(sigma)

Set of partial derivatives of the regular expression in relation to given symbol.

Parameters:

sigma (str) – symbol in relation to which the derivative will be calculated.

Returns:

set of regular expressions

Return type:

set

See also

Antimirov, 95

partialDerivativesC(sigma)

Parameters:

sigma (str) – symbol

Returns:

set of partial derivatives

Return type:

set

reduced(has_epsilon=False)

Equivalent regular expression with the following cases simplified:

1. Epsilon.RE = RE.Epsilon = RE

2. EmptySet.RE = RE.EmptySet = EmptySet

3. EmptySet + RE = RE + EmptySet = RE

4. Epsilon + RE = RE + Epsilon = RE, where Epsilon is in L(RE)

5. RE** = RE*

6. EmptySet* = Epsilon* = Epsilon

7.Epsilon:RE = RE:Epsilon= RE

Parameters:

• has_epsilon (bool) – used internally to indicate that the language of which this term is a subterm has the empty

• word. –

Returns:

regular expression

Return type:

RegExp

Attention

Returned structure isn’t strictly a duplicate. Use __copy__() for that purpose.

reversal()

Reversal of RegExp

Return type:

Regexp

rpn()

RPN representation

Returns:

printable RPN representation

Return type:

str

setOfSymbols()

Set of symbols that occur in a regular expression..

Returns:

set of symbols

Return type:

set

snf(hollowdot=False)

Star Normal Form (SNF) of the regular expression.

Parameters:

hollowdot (bool) – if True computes hollow dot function else black dot

Returns:

regular expression in star normal form

Return type:

RegExp

static starHeight()

Maximum level of nested regular expressions with a star operation applied.

For instance, starHeight(((a*b)*+b*)*) is 3.

Return type:

int

stringLength()

Length of the string representation of the regular expression.

Returns:

string length

Return type:

int

support(side=True)

Support of a regular expression.

Parameters:

side (bool) – if True concatenation of a set on the left if False on the right (prefix support)

Returns:

set of regular expressions

Return type:

set

See also

Champarnaud, J.M., Ziadi, D.: From Mirkin’s prebases to Antimirov’s word partial derivative. Fundam. Inform. 45(3), 195-205 (2001)

See also

Maia et al, Prefix and Right-partial derivative automata, 11th CIE 2015, 258-267 LNCS 9136, 2015

supportlast(side=True)

Subset of support such that elements have ewp

Parameters:

side (bool) – if True left-derivatives else right-derivatives

Returns:

set of partial derivatives

Return type:

set

static syntacticLength()

Number of nodes of the regular expression’s syntactical tree (sets).

Return type:

int

tailForm()

Returns:

tail form

Return type:

dict

static treeLength()

Number of nodes of the regular expression’s syntactical tree.

Return type:

int

unmarked()

The unmarked form of the regular expression. Each leaf in its syntactical tree becomes a RegExp(), the CEpsilon() or the CEmptySet().

Returns:

(general) regular expression

Return type:

RegExp

class CConcat(arg1, arg2, sigma=None)

Class for catenation operation on regular expressions.

ewp()

Whether the empty word property holds for this regular expression’s language.

Return type:

bool

first(parent_first=None)

First set

Returns:

first position set

Return type:

set

first_l()

First sets for locations

followLists(lists=None)

Follow set

Returns:

for each key position a set of follow positions

Return type:

dict

followListsD(lists=None)

Follow set

Returns:

for each key position a set of follow positions

Return type:

dict

follow_l()

Follow sets for locations

last(parent_last=None)

Last set

Returns:

last position set

Return type:

set

last_l()

Last sets for locations

linearForm()

Returns:

linear form

Return type:

dict

mark()

Make all atoms maked (tag False)

Return type:

RegExp

reversal()

Reversal of RegExp

Return type:

reex.RegExp

rpn()

Return type:

str

snf(_hollowdot=False)

Star Normal Form

support(side=True)

Set of partial derivatives

tailForm()

Returns:

tail form

Return type:

dict

unmark()

Conversion back to unmarked atoms :rtype: CConcat

class CConj(arg1, arg2, sigma=None)

Intersection operation of regexps

ewp()

Whether the empty word property holds for this regular expression’s language.

Return type:

bool

first_l()

First sets for locations

follow_l()

Follow sets for locations

last_l()

Last sets for locations

linearForm()

Returns:

linear form

Return type:

dict

mark()

Make all atoms maked (tag False)

Return type:

RegExp

rpn()

RPN representation

Returns:

printable RPN representation

Return type:

str

snf()

Star Normal Form

tailForm()

Returns:

tail form

Return type:

dict

class CDisj(arg1, arg2, sigma=None)

Class for disjunction/union operation on regular expressions.

ewp()

Whether the empty word property holds for this regular expression’s language.

Return type:

bool

first(parent_first=None)

First set

Returns:

first position set

Return type:

set

first_l()

First sets for locations

followLists(lists=None)

Follow set

Returns:

for each key position a set of follow positions

Return type:

dict

followListsD(lists=None)

Follow set

Returns:

for each key position a set of follow positions

Return type:

dict

follow_l()

Follow sets for locations

last(parent_last=None)

Last set

Returns:

last position set

Return type:

set

last_l()

Last sets for locations

linearForm()

Returns:

linear form

Return type:

dict

mark()

Convertion to marked atoms :rtype: CDisj

nfaThompson()

Returns an NFA (Thompson) that accepts the RE.

Return type:

NFA

reversal()

Reversal of RegExp

Return type:

reex.RegExp

rpn()

RPN representation

Returns:

printable RPN representation

Return type:

str

snf(hollowdot=False)

Star Normal Form

support(side=True)

Set of partial derivatives

tailForm()

Returns:

tail form

Return type:

dict

unmark()

Conversion back to unmarked atoms :rtype: CDisj

class CEmptySet(sigma=None)

Class that represents the empty set.

Constructor of a regular expression symbol.

Parameters:

val – the actual symbol

static emptysetP()

Returns:

static epsilonLength()

Returns:

static epsilonP()

Returns:

ewp()

Returns:

static measure(from_parent=None)

Parameters:

from_parent –

Returns:

nfaPD(pdmethod='nfaPDNaive')

Computes the partial derivative automaton

partialDerivatives(_)

Partial derivatives

partialDerivativesC(_)

Returns:

rpn()

Returns:

snf(_hollowdot=False)

Star Normal Form

class CEpsilon(sigma=None)

Class that represents the empty word.

Constructor of a regular expression symbol.

Parameters:

val – the actual symbol

static epsilonLength()

Number of occurrences of the empty word in the regular expression.

Returns:

number of epsilons

Return type:

int

static epsilonP()

Return type:

bool

ewp()

Return type:

bool

static measure(from_parent=None)

Parameters:

from_parent –

Returns:

measures

nfaThompson()

Return type:

NFA

partialDerivatives(_)

Returns:

partialDerivativesC(_)

Returns:

rpn()

Returns:

str

snf(_hollowdot=False)

Parameters:

_hollowdot –

Returns:

class COption(arg, sigma=None)

Class for option operation (reg + @epsilon) on regular expressions.

epsilonLength()

Number of occurrences of the empty word in the regular expression.

Returns:

number of epsilons

Return type:

int

ewp()

Whether the empty word property holds for this regular expression’s language.

Return type:

bool

first(parent_first=None)

First set

Returns:

first position set

Return type:

set

first_l()

First sets for locations

followLists(lists=None)

Follow set

Returns:

for each key position a set of follow positions

Return type:

dict

followListsD(lists=None)

Follow set

Returns:

for each key position a set of follow positions

Return type:

dict

followListsStar(lists=None)

to be fixed

follow_l()

Follow sets for locations

last(parent_first=None)

Last set

Returns:

last position set

Return type:

set

last_l()

Last sets for locations

linearForm()

Returns:

linear form

Return type:

dict

nfaThompson()

Returns a NFA that accepts the RE.

Return type:

NFA

rpn()

RPN representation

Returns:

printable RPN representation

Return type:

str

setOfSymbols()

Returns:

set of symbols

Return type:

set

snf(_hollowdot=False)

Star Normal Form

starHeight()

Maximum level of nested regular expressions with a star operation applied.

For instance, starHeight(((a*b)*+b*)*) is 3.

Returns:

number of nested star

Return type:

int

support(side=True)

Set of partial derivatives

tailForm()

Returns:

tail form

Return type:

dict

class CShuffle(arg1, arg2, sigma=None)

Shuffle operation of regexps

ewp()

Whether the empty word property holds for this regular expression’s language.

Return type:

bool

first(parent_list=None)

Parameters:

parent_list –

Returns:

first_l()

First sets for locations

followListsD(lists=None)

in progress

follow_l()

Follow sets for locations

last_l()

Last sets for locations

linearForm()

Returns:

linear form

Return type:

dict

mark()

Make all atoms maked (tag False)

Return type:

RegExp

rpn()

RPN representation

Returns:

printable RPN representation

Return type:

str

snf()

Star Normal Form

tailForm()

Returns:

tail form

Return type:

dict

class CShuffleU(arg, sigma=None)

Unary Shuffle operation of regexps

epsilonLength()

Number of occurrences of the empty word in the regular expression.

Returns:

number of epsilons

Return type:

int

ewp()

Whether the empty word property holds for this regular expression’s language.

Return type:

bool

first(parent_list=None)

Parameters:

parent_list –

Returns:

followListsD(lists=None)

in progress

last(parent_last=None)

Last set

Returns:

last position set

Return type:

set

linearForm()

Returns:

linear form

Return type:

dict

mark()

Make all atoms maked (tag False)

Return type:

RegExp

rpn()

RPN representation

Returns:

printable RPN representation

Return type:

str

snf()

Star Normal Form

starHeight()

Maximum level of nested regular expressions with a star operation applied.

For instance, starHeight(((a*b)*+b*)*) is 3.

Returns:

number of nested star

Return type:

int

tailForm()

Returns:

tail form

Return type:

dict

unmark()

Conversion back to RegExp

Return type:

reex.__class__

class CSigmaP(sigma=None)

Special regular expressions modulo associativity, commutativity, idempotence of disjunction and intersection;

associativity of concatenation; identities sigma^* and sigma^+.

CSigmaP: Class that represents the complement of the EmptySet word (sigma^+)

Constructor of a regular expression symbol.

Parameters:

val – the actual symbol

derivative(sigma)

Parameters:

sigma –

Returns:

ewp()

Returns:

linearForm()

Returns:

linearFormC()

Returns:

nfaPD(pdmethod='nfaPDNaive')

Computes the partial derivative automaton

partialDerivatives(sigma)

Parameters:

sigma –

Returns:

partialDerivativesC(_)

Parameters:

_ –

Returns:

rpn()

RPN representation

Returns:

printable RPN representation

Return type:

str

support(side=True)

Returns:

class CSigmaS(sigma=None)

Special regular expressions modulo associativity, commutativity, idempotence of disjunction and intersection;

associativity of concatenation; identities sigma^* and sigma^+.

CSigmaS: Class that represents the complement of the EmptySet set (sigma^*)

Constructor of a regular expression symbol.

Parameters:

val – the actual symbol

derivative(sigma)

Parameters:

sigma –

Returns:

ewp()

Returns:

linearForm()

Returns:

linearFormC()

Returns:

nfaPD(pdmethod='nfaPDNaive')

Computes the partial derivative automaton

partialDerivatives(sigma)

Parameters:

sigma –

Returns:

partialDerivativesC(sigma)

Parameters:

sigma –

Returns:

rpn()

RPN representation

Returns:

printable RPN representation

Return type:

str

support(side=True)

Returns:

class CStar(arg, sigma=None)

Class for iteration operation (aka Kleene star, or Kleene closure) on regular expressions.

epsilonLength()

Number of occurrences of the empty word in the regular expression.

Returns:

number of epsilons

Return type:

int

ewp()

Whether the empty word property holds for this regular expression’s language.

Return type:

bool

first(parent_first=None)

First set

Returns:

first position set

Return type:

set

first_l()

First sets for locations

followLists(lists=None)

Follow set

Returns:

for each key position a set of follow positions

Return type:

dict

followListsD(lists=None)

Follow set

Returns:

for each key position a set of follow positions

Return type:

dict

follow_l()

Follow sets for locations

last(parent_first=None)

Last set

Returns:

last position set

Return type:

set

last_l()

Last sets for locations

linearForm()

Returns:

linear form

Return type:

dict

nfaThompson()

Returns a NFA that accepts the RE.

Return type:

NFA

rpn()

RPN representation

Returns:

printable RPN representation

Return type:

str

snf(_hollowdot=False)

Star Normal Form

starHeight()

Maximum level of nested regular expressions with a star operation applied.

For instance, starHeight(((a*b)*+b*)*) is 3.

Returns:

number of nested star

Return type:

int

support(side=True)

Set of partial derivatives

tailForm()

Returns:

tail form

Return type:

dict

class Compl(arg, sigma=None)

Class for not operation on regular expressions.

epsilonLength()

Number of occurrences of the empty word in the regular expression.

Returns:

number of epsilons

Return type:

int

ewp()

Whether the empty word property holds for this regular expression’s language.

Return type:

bool

first(_)

First set

Returns:

first position set

Return type:

set

followLists()

Follow set

Returns:

for each key position a set of follow positions

Return type:

dict

followListsD()

Follow set

Returns:

for each key position a set of follow positions

Return type:

dict

last()

Last set

Returns:

last position set

Return type:

set

linearForm()

Returns:

linear form

Return type:

dict

mark()

Make all atoms maked (tag False)

Return type:

RegExp

rpn()

RPN representation

Returns:

printable RPN representation

Return type:

str

snf()

Star Normal Form

starHeight()

Maximum level of nested regular expressions with a star operation applied.

For instance, starHeight(((a*b)*+b*)*) is 3.

Returns:

number of nested star

Return type:

int

support(side=True)

Set of partial derivatives

tailForm()

Returns:

tail form

Return type:

dict

treeLength()

Number of nodes of the regular expression’s syntactical tree.

Returns:

tree lenght

Return type:

int

unmark()

Conversion back to RegExp

Return type:

reex.__class__

class Connective(arg1, arg2, sigma=None)

Base class for (binary) operations: concatenation, disjunction, etc

alphabeticLength()

Number of occurrences of alphabet symbols in the regular expression. :returns: alphapetic length :rtype: int

Attention

Doesn’t include the empty word.

epsilonLength()

Number of occurrences of the empty word in the regular expression.

Returns:

number of epsilons

Return type:

int

first(parent_first=None)

First set

Returns:

first position set

Return type:

set

followLists(lists=None)

Follow set

Returns:

for each key position a set of follow positions

Return type:

dict

followListsD(lists=None)

Follow set

Returns:

for each key position a set of follow positions

Return type:

dict

last(parent_last=None)

Last set

Returns:

last position set

Return type:

set

abstract linearForm()

Returns:

linear form

Return type:

dict

abstract mark()

Make all atoms maked (tag False)

Return type:

RegExp

abstract rpn()

RPN representation

Returns:

printable RPN representation

Return type:

str

setOfSymbols()

Returns:

set of symbols

Return type:

set

abstract snf()

Star Normal Form

starHeight()

Maximum level of nested regular expressions with a star operation applied.

For instance, starHeight(((a*b)*+b*)*) is 3.

Returns:

number of nested star

Return type:

int

treeLength()

Number of nodes of the regular expression’s syntactical tree.

Returns:

tree lenght

Return type:

int

class DAG(reg)

Class to support dags representing regexps

…seealso: P. Flajolet, P. Sipala, J.-M. Steyaert, Analytic variations on the common subexpression problem,

in: Automata, Languages and Programmin, LNCS, vol. 443, Springer, New York, 1990, pp. 220–234.

Args: reg (RegExp): regular expression

NFA()

Returns:

the partial derivative automaton

Return type:

NFA

catLF(idl, idr, delay=False)

Linear form for concatenation :param idl: node :type idl: int :param idr: node :type idr: int :param delay: if true partial derivatives are delayed :type delay: bool

Returns:

partial derivatives

Return type:

dict

..note:: both arguments are assumed to be already present in the DAG

getAtomIdx(val)

Node atom :param val: letter :type val: str

Returns:

node id

Return type:

int

getIdx(reg)

Builds dag nodes :param reg: regular expression :type reg: regexp

Returns:

node id

Return type:

int

interLF(diff1, diff2)

Intersection of partial derivatives

Parameters:

• diff1 (dict) – partial diff of the first argument

• diff2 (dict) – partial diff of the second argument

Return type:

dict

static plusLF(diff1, diff2)

Union of partial derivatives

Parameters:

• diff1 (dict) – partial diff of the first argument

• diff2 (dict) – partial diff of the second argument

Return type:

dict

shuffleLF(id1, id2)

Shuffle of partial derivatives :param id1: node :type id1: int :param id2: node :type id2: int

Returns:

partial derivatives

Return type:

dict

class DAG_I(reg)

Class to support dags representing regexps that inherit from DAG Partial derivatives are buid incrementally

Args: reg (RegExp): regular expression

cat_one(idl, idr, c)

Partial derivative by one symbol for concatenation :param idl: node :type idl: int :param idr: node :type idr: int :param c: symbol :type c: char

Returns:

partial derivatives

Return type:

set

evalWordP(w)

Parameters:

w (str) – a word

Returns:

True if w in L(reg)

Return type:

bool

one_derivative(id, c)

Parameters:

• c (str) – a symbol

• id (int) – a node (representing a regexp)

shuffle_one(id1, id2, c)

Shuffle of partial derivatives :param id1: node :type id1: int :param id2: node :type id2: int :param c: symbol :type c: char

Returns:

of partial derivatives

Return type:

set

class MAtom(val, mark, sigma=None)

Base class for pointed (marked) regular expressions

Used directly to represent atoms (characters). This class is used to obtain Yamada or Asperti automata. There is no evident use for it, outside this module.

Parameters:

• val – symbol

• sigma – alphabet

unmark()

Conversion back to RegExp

Return type:

reex.RegExp

class Position(val, sigma=None)

Class for marked regular expression symbols.

Constructor of a regular expression symbol.

Parameters:

val – the actual symbol

setOfSymbols()

Set of symbols that occur in a regular expression..

Returns:

set of symbols

Return type:

set

unmarked()

The unmarked form of the regular expression. Each leaf in its syntactical tree becomes a RegExp(), the CEpsilon() or the CEmptySet().

Returns:

(general) regular expression

Return type:

RegExp

class Power(arg, n=1, sigma=None)

Class for Power operation on regular expressions.

alphabeticLength()

Number of occurrences of alphabet symbols in the regular expression. :returns: alphapetic length :rtype: int

Attention

Doesn’t include the empty word.

epsilonLength()

Number of occurrences of the empty word in the regular expression.

Returns:

number of epsilons

Return type:

int

first()

First set

Returns:

first position set

Return type:

set

followLists()

Follow set

Returns:

for each key position a set of follow positions

Return type:

dict

followListsD()

Follow set

Returns:

for each key position a set of follow positions

Return type:

dict

last()

Last set

Returns:

last position set

Return type:

set

linearForm()

Returns:

linear form

Return type:

dict

mark()

Make all atoms maked (tag False)

Return type:

RegExp

reversal()

Reversal of RegExp

Return type:

reex.RegExp

rpn()

RPN representation

Returns:

printable RPN representation

Return type:

str

setOfSymbols()

Returns:

set of symbols

Return type:

set

snf()

Star Normal Form

starHeight()

Maximum level of nested regular expressions with a star operation applied.

For instance, starHeight(((a*b)*+b*)*) is 3.

Returns:

number of nested star

Return type:

int

support(side=True)

Set of partial derivatives

tailForm()

Returns:

tail form

Return type:

dict

treeLength()

Number of nodes of the regular expression’s syntactical tree.

Returns:

tree lenght

Return type:

int

class RegExp(sigma=None)

Base class for regular expressions.

Variables:

Sigma – alphabet set of strings

abstract static alphabeticLength()

Number of occurrences of alphabet symbols in the regular expression. :returns: alphapetic length :rtype: int

Attention

Doesn’t include the empty word.

compare(r, cmp_method='compareMinimalDFA', nfa_method='nfaPD')

Compare with another regular expression for equivalence.

Parameters:

• r (RegExp) –

• cmp_method (str) –

• nfa_method (str) – NFA construction

Returns:

True if the expressions are equivalent

Return type:

bool

compareMinimalDFA(r, nfa_method='nfaPosition')

Compare with another regular expression for equivalence through minimal DFAs.

Parameters:

• r (RegExp) –

• nfa_method (str) – NTFA construction

Returns:

True if equivalent

Return type:

bool

dfaAuPoint()

DFA “au-point” acconding to Nipkow

Returns:

“au-point” DFA

Return type:

DFA

See also

Andrea Asperti, Claudio Sacerdoti Coen and Enrico Tassi, Regular Expressions, au point. arXiv 2010

See also

Tobias Nipkow and Dmitriy Traytel, Unified Decision Procedures for Regular Expression Equivalence

dfaBrzozowski(memo=None)

Word derivatives automaton of the regular expression

Parameters:

memo – if True memorizes the states already computed

Returns:

word derivatives automaton

Return type:

DFA

See also

10. 1. Brzozowski, Derivatives of Regular Expressions. J. ACM 11(4): 481-494 (1964)

dfaNaiveFollow()

DFA that accepts the regular expression’s language, and is obtained from the follow automaton.

Returns:

DFA follow

Return type:

NFA

Note

Included for testing purposes.

See also

Ilie & Yu (Follow Automata, 2003)

dfaYMG()

DFA Yamada-McNaugthon-Gluskov acconding to Nipkow

Returns:

Y-M-G DFA

Return type:

DFA

See also

Tobias Nipkow and Dmitriy Traytel, Unified Decision Procedures for Regular Expression Equivalence

static emptysetP()

Whether the regular expression is the empty set.

Return type:

bool

abstract static epsilonLength()

Number of occurrences of the empty word in the regular expression.

Returns:

number of epsilons

Return type:

int

static epsilonP()

Whether the regular expression is the empty word.

Return type:

bool

equivP(other, strict=True)

Test RE equivalence with extended Hopcroft-Karp method

Parameters:

• other (RegExp) – RE

• strict (bool) – if True checks for same alphabets

Return type:

bool

equivalentP(other)

Tests equivalence

Parameters:

other (RegExp) – other regexp

Returns:

True if regexps are equivalent

Return type:

bool

evalWordP(word)

Verifies if a word is a member of the language represented by the regular expression.

Parameters:

word (str) – the word

Returns:

True if word belongs to the language

Return type:

bool

static ewp()

Whether the empty word property holds for this regular expression’s language.

Return type:

bool

abstract first()

First set

Returns:

first position set

Return type:

set

abstract followLists()

Follow set

Returns:

for each key position a set of follow positions

Return type:

dict

abstract followListsD()

Follow set

Returns:

for each key position a set of follow positions

Return type:

dict

abstract last()

Last set

Returns:

last position set

Return type:

set

abstract linearForm()

Returns:

linear form

Return type:

dict

abstract mark()

Make all atoms maked (tag False)

Return type:

RegExp

marked()

Regular expression in which every alphabetic symbol is marked with its Position.

The kind of regular expression returned is known, depending on the literary source, as marked, linear or restricted regular expression.

Returns:

linear regular expression

Return type:

RegExp

See also

r. McNaughton and H. Yamada, Regular Expressions and State Graphs for Automata, IEEE Transactions on Electronic Computers, V.9 pp:39-47, 1960

..attention: mark and unmark do not preserve the alphabet, neither set the new alphabet

nfaFollow()

NFA that accepts the regular expression’s language, whose structure, equiand construction.

Returns:

NFA follow

Return type:

NFA

See also

Ilie & Yu (Follow Automata, 03)

nfaFollowEpsilon(trim=True)

Epsilon-NFA constructed with Ilie and Yu’s method () that accepts the regular expression’s language.

Parameters:

trim (bool) – if True automaton is trimmed at the end

Returns:

possibly with epsilon transitions

Return type:

NFAe

Note

The regular expression must be reduced

See also

Ilie & Yu, Follow automta, Inf. Comp. ,v. 186 (1),140-162,2003

nfaGlushkov()

Position or Glushkov automaton of the regular expression. Recursive method.

Returns:

NFA position

Return type:

NFA

nfaLoc()

Location automaton of the regular expression.

Returns:

location nfa

Return type:

NFA

nfaNaiveFollow()

NFA that accepts the regular expression’s language, and is equal in structure to the follow automaton.

Returns:

NFA follow

Return type:

NFA

Note

Included for testing purposes.

See also

Ilie & Yu (Follow Automata, 2003)

nfaPD(pdmethod='nfaPDDAG')

Computes the partial derivative automaton

Parameters:

pdmethod (str) – an implementation of the PD automaton. Default value : nfaPDDAG

Returns:

a PD nfa

Return type:

NFA

Attention

for sre classes, CConj and CShuffle use nfaPDNaive directly

nfaPDDAG()

Partial derivative automaton using a DAG for the re and partial derivatives

Returns:

a PD nfa build using a DAG

Return type:

NFA

..seealso:: s.Konstantinidis, A. Machiavelo, N. Moreira, and r. Reis.

Partial derivative automaton by compressing regular expressions. DCFS 2021, volume 13037 of LNCS, pages 100–112. Springer, 2022

nfaPDNaive()

NFA that accepts the regular expression’s language,

and which is constructed from the expression’s partial derivatives.

Returns:

partial derivatives [or equation] automaton

Return type:

NFA

See also

V. M. Antimirov, Partial Derivatives of Regular Expressions and Finite Automaton Constructions .Theor. Comput. Sci.155(2): 291-319 (1996)

nfaPDO()

NFA that accepts the regular expression’s language, and which is constructed from the expression’s partial

derivatives.

Returns:

partial derivatives [or equation] automaton

Return type:

NFA

Note

optimized version

nfaPSNF()

Position or Glushkov automaton of the regular expression constructed from the expression’s star normal form.

Returns:

Position automaton

Return type:

NFA

nfaPosition(lstar=True)

Position automaton of the regular expression.

Parameters:

lstar (bool) – if not None followlists are computed as disjunct

Returns:

Position NFA

Return type:

NFA

nfaPre()

Prefix NFA of a regular expression

Returns:

prefix automaton

Return type:

NFA

See also

Maia et al, Prefix and Right-partial derivative automata, 11th CIE 2015, 258-267 LNCS 9136, 2015

notEmptyW()

Witness of non emptyness

Return type:

word or None

abstract rpn()

RPN representation

Returns:

printable RPN representation

Return type:

str

abstract static setOfSymbols()

Returns:

set of symbols

Return type:

set

setSigma(symbolset=None, strict=False)

Set the alphabet for a regular expression and all its nodes

Parameters:

• symbolset (set or list) – accepted symbols. If None, alphabet is unset.

• strict (bool) – if True checks if setOfSymbols is included in symbolSet

..attention: Normally this attribute is not defined in a RegExp()

abstract snf()

Star Normal Form

abstract static starHeight()

Maximum level of nested regular expressions with a star operation applied.

For instance, starHeight(((a*b)*+b*)*) is 3.

Returns:

number of nested star

Return type:

int

abstract support(side=True)

Set of partial derivatives

abstract tailForm()

Returns:

tail form

Return type:

dict

toDFA()

DFA that accepts the regular expression’s language

toNFA(nfa_method='nfaPD')

NFA that accepts the regular expression’s language. :param nfa_method:

abstract static treeLength()

Number of nodes of the regular expression’s syntactical tree.

Returns:

tree lenght

Return type:

int

unionSigma(other)

Returns the union of two alphabets

Return type:

set

wordDerivative(word)

Derivative of the regular expression in relation to the given word,

which is represented by a list of symbols.

Parameters:

word (list) – list of arbitrary symbols.

Returns:

regular expression

Return type:

RegExp

See also

10. 1. Brzozowski, Derivatives of Regular Expressions. J. ACM 11(4): 481-494 (1964)

class RegularExpression

Abstract base class for all regular expression objects

class SConcat(arg, sigma=None)

Class that represents the concatenation operation.

derivative(sigma)

Parameters:

sigma –

Returns:

ewp()

Returns:

head()

Returns:

head_rev()

Returns:

linearForm()

Returns:

linearFormC()

Returns:

partialDerivatives(sigma)

Parameters:

sigma –

Returns:

partialDerivativesC(sigma)

Parameters:

sigma –

Returns:

support(side=True)

Returns:

tail()

Returns:

tailForm()

Returns:

tail form

Return type:

dict

tail_rev()

Returns:

class SConj(arg, sigma=None)

Class that represents the conjunction operation.

derivative(sigma)

Parameters:

sigma –

Returns:

ewp()

Returns:

linearForm()

Returns:

partialDerivatives(sigma)

Parameters:

sigma –

Returns:

partialDerivativesC(sigma)

Parameters:

sigma –

Returns:

support(side=True)

Returns:

tailForm()

Returns:

tail form

Return type:

dict

class SConnective(arg, sigma=None)

Special regular expressions modulo associativity, commutativity, idempotence of disjunction and intersection;

associativity of concatenation; identities sigma^* and sigma^+. Connectives are:

SDisj: disjunction SConj: intersection SConcat: concatenation

For parsing use str2sre

alphabeticLength()

Returns:

epsilonLength()

Returns:

first()

First set

Returns:

first position set

Return type:

set

followLists()

Follow set

Returns:

for each key position a set of follow positions

Return type:

dict

followListsD()

Follow set

Returns:

for each key position a set of follow positions

Return type:

dict

last()

Last set

Returns:

last position set

Return type:

set

linearForm()

Returns:

linear form

Return type:

dict

mark()

Make all atoms maked (tag False)

Return type:

RegExp

nfaPD(pdmethod='nfaPDNaive')

Computes the partial derivative automaton

rpn()

RPN representation

Returns:

printable RPN representation

Return type:

str

setOfSymbols()

Returns:

snf()

Star Normal Form

starHeight()

Maximum level of nested regular expressions with a star operation applied.

For instance, starHeight(((a*b)*+b*)*) is 3.

Returns:

number of nested star

Return type:

int

abstract support(side=True)

Set of partial derivatives

syntacticLength()

Returns:

abstract tailForm()

Returns:

tail form

Return type:

dict

treeLength()

Returns:

class SDisj(arg, sigma=None)

Class that represents the disjunction operation for special regular expressions.

static cross(ri, s, lists)

Return type:

list

derivative(sigma)

Parameters:

sigma –

Returns:

ewp()

Returns:

first()

Returns:

followLists(lists=None)

Parameters:

lists –

Returns:

followListsStar(lists=None)

Parameters:

lists –

Returns:

last()

Returns:

linearForm()

Returns:

linearFormC()

Returns:

partialDerivatives(sigma)

Parameters:

sigma –

Returns:

partialDerivativesC(sigma)

Parameters:

sigma –

Returns:

support(side=True)

Returns:

tailForm()

Returns:

tail form

Return type:

dict

class SNot(arg, sigma=None)

Special regular expressions modulo associativity, commutativity, idempotence of disjunction and intersection;

associativity of concatenation; identities sigma^* and sigma^+. SNot: negation

alphabeticLength()

Returns:

derivative(sigma)

:param sigma :return:

epsilonLength()

Returns:

ewp()

Returns:

first()

First set

Returns:

first position set

Return type:

set

followLists()

Follow set

Returns:

for each key position a set of follow positions

Return type:

dict

followListsD()

Follow set

Returns:

for each key position a set of follow positions

Return type:

dict

last()

Last set

Returns:

last position set

Return type:

set

linearForm()

Returns:

linearFormC()

Returns:

mark()

Make all atoms maked (tag False)

Return type:

RegExp

nfaPD(pdmethod='nfaPDNaive')

Computes the partial derivative automaton

partialDerivatives(sigma)

Parameters:

sigma –

Returns:

partialDerivativesC(sigma)

Parameters:

sigma –

Returns:

rpn()

RPN representation

Returns:

printable RPN representation

Return type:

str

setOfSymbols()

Returns:

snf()

Star Normal Form

starHeight()

Maximum level of nested regular expressions with a star operation applied.

For instance, starHeight(((a*b)*+b*)*) is 3.

Returns:

number of nested star

Return type:

int

support(side=True)

Returns:

syntacticLength()

Returns:

tailForm()

Returns:

tail form

Return type:

dict

treeLength()

Returns:

class SStar(arg, sigma=None)

Special regular expressions modulo associativity, commutativity, idempotence of disjunction and intersection;

associativity of concatenation; identities sigma^* and sigma^+.

SStar: Class that represents Kleene star

derivative(sigma)

Parameters:

sigma –

Returns:

linearForm()

Returns:

nfaPD(pdmethod='nfaPDNaive')

Computes the partial derivative automaton

partialDerivatives(sigma)

Parameters:

sigma –

Returns:

partialDerivativesC(sigma)

Parameters:

sigma –

Returns:

support(side=True)

Returns:

class SpecialConstant(sigma=None)

Base class for Epsilon and EmptySet

Parameters:

sigma – alphabet

static alphabeticLength()

Returns:

derivative(sigma)

Parameters:

sigma –

Returns:

distDerivative(sigma)

Parameters:

sigma – an arbitrary symbol.

Return type:

regular expression

static epsilonLength()

Number of occurrences of the empty word in the regular expression.

Returns:

number of epsilons

Return type:

int

static first(parent_first=None)

Parameters:

parent_first –

Returns:

followLists(lists=None)

Parameters:

lists –

Returns:

followListsD(lists=None)

Parameters:

lists –

Returns:

static followListsStar(lists=None)

Parameters:

lists –

Returns:

last(parent_last=None)

Parameters:

parent_last –

Returns:

linearForm()

Returns:

mark()

Make all atoms maked (tag False)

Return type:

RegExp

partialDerivativesC(sigma)

Parameters:

sigma –

Returns:

reversal()

Reversal of RegExp

Return type:

reex.RegExp

abstract rpn()

RPN representation

Returns:

printable RPN representation

Return type:

str

static setOfSymbols()

Returns:

snf()

Star Normal Form

static starHeight()

Maximum level of nested regular expressions with a star operation applied.

For instance, starHeight(((a*b)*+b*)*) is 3.

Returns:

number of nested star

Return type:

int

support(side=True)

Returns:

supportlast(side=True)

Returns:

tailForm()

Returns:

static treeLength()

Number of nodes of the regular expression’s syntactical tree.

Returns:

tree lenght

Return type:

int

unmark()

Conversion back to unmarked atoms :rtype: SpecialConstant

unmarked()

The unmarked form of the regular expression. Each leaf in its syntactical tree becomes a RegExp(), the CEpsilon() or the CEmptySet().

Return type:

(general) regular expression

wordDerivative(word)

Parameters:

word –

Returns:

class Unary(arg, sigma=None)

Base class for unary operations: star, option, not, unary shuffle, etc

alphabeticLength()

Number of occurrences of alphabet symbols in the regular expression. :returns: alphapetic length :rtype: int

Attention

Doesn’t include the empty word.

abstract epsilonLength()

Number of occurrences of the empty word in the regular expression.

Returns:

number of epsilons

Return type:

int

abstract ewp()

Whether the empty word property holds for this regular expression’s language.

Return type:

bool

abstract first(parent_first=None)

First set

Returns:

first position set

Return type:

set

followLists(lists=None)

Follow set

Returns:

for each key position a set of follow positions

Return type:

dict

followListsD(lists=None)

Follow set

Returns:

for each key position a set of follow positions

Return type:

dict

abstract last(parent_last=None)

Last set

Returns:

last position set

Return type:

set

abstract linearForm()

Returns:

linear form

Return type:

dict

mark()

Make all atoms maked (tag False)

Return type:

RegExp

reversal()

Reversal of RegEx

Return type:

reex.RegExp

abstract rpn()

RPN representation

Returns:

printable RPN representation

Return type:

str

setOfSymbols()

Returns:

set of symbols

Return type:

set

snf()

Star Normal Form

abstract starHeight()

Maximum level of nested regular expressions with a star operation applied.

For instance, starHeight(((a*b)*+b*)*) is 3.

Returns:

number of nested star

Return type:

int

treeLength()

Number of nodes of the regular expression’s syntactical tree.

Returns:

tree lenght

Return type:

int

unmark()

Conversion back to RegExp

Return type:

reex.__class__

equivalentP(first, second)

Verifies if the two languages given by some representative (DFA, NFA or re) are equivalent

Parameters:

• first – language

• second – language

Return type:

bool

New in version 0.9.6.

powerset(iterable)

Powerset of a set. :param iterable: the set :type iterable: list

Returns:

the powerset

Return type:

itertools.chain

rpn2regexp(s, sigma=None, strict=False)

Reads a (simple) RegExp from a RPN representation

r ::=  .RR | +RR | *r | L | @
L ::=  [a-z] | [A-Z]

Parameters:

• s (str) – RPN representation

• strict (bool) – Boolean

• sigma (set) – alphabet

Return type:

reex.RegExp

Note

This method uses python stack… thus depth limitations apply

str2regexp(s, parser=Lark(open('/Users/rvr/Work/FAdo/FAdo/regexp_grammar.lark'), parser='lalr', lexer='contextual', ...), sigma=None, strict=False)

Reads a RegExp from string.

Parameters:

• s (string) – the string representation of the regular expression

• parser – a parser generator for regexps

• sigma (list or set of symbols) – alphabet of the regular expression

• strict (boolean) – if True tests if the symbols of the regular expression are included in sigma

Return type:

reex.RegExp

str2sre(s, parser=Lark(open('/Users/rvr/Work/FAdo/FAdo/regexp_grammar.lark'), parser='lalr', lexer='contextual', ...), sigma=None, strict=False)

Reads a sre from string. Arguments as str2regexp.

Return type:

reex.sre

to_s(r)

Returns a sre from FAdo regexp.

Parameters:

r (RegExp) – the FAdo representation regexp for a regular expression.

Return type:

RegExp