reg::expression Class Reference

Represents formal regular expressions. More...

#include <expression.h>

Classes
struct	literals
struct	parser
	Parses regular expressions. More...

Public Types
enum	operation {   empty, symbol, kleene, concatenation,   alternation }
	The different purposes an RE may fulfill. More...
typedef std::shared_ptr< expression const >	exptr
	This is the type used to handle regular expressions. More...

Public Member Functions
size_t	size () const
	Reports the size of this RE's tree representation. More...
operation	getOperation () const
	Reports this RE's function. More...
	operator nfa const & () const
	Returns an NFA accepting the language that this RE describes. More...
bool	operator== (nfa const &other) const
	Checks whether this RE describes the same regular language as another object. More...
bool	operator!= (nfa const &other) const
	Checks whether this RE describes a different regular language than another object. More...
bool	operator== (expression const &r) const
bool	operator!= (expression const &r) const
char32_t	extractSymbol () const
	Reports this symbol expression's UTF-32-encoded symbol. More...
std::string	extractUtf8Symbol () const
	Reports this symbol expression's UTF-8-encoded symbol. More...
std::u32string	to_u32string () const
	Describes this RE in UTF-32-encoded human-readable form. More...
std::string	to_string () const
	Describes this RE in UTF-8-encoded human-readable form. More...
std::vector< exptr >::const_iterator	begin () const
	Returns an iterator pointing to this RE's first subexpression. More...
std::vector< exptr >::const_iterator	end () const
	Returns an iterator pointing behind this RE's last subexpression. More...

Static Public Member Functions
static void	reset ()
	Resets the symbols used for RE operators to their defaults. More...
static exptr const &	spawnEmptySet ()
	Gives an RE representing the empty set ∅. More...
static exptr const &	spawnEmptyString ()
	Gives an RE representing the empty string ε. More...
static exptr const &	spawnSymbol (char32_t symbol)
	Gives an RE representing the given UTF-32-encoded symbol. More...
static exptr const &	spawnSymbol (std::string const &utf8Symbol)
	Same as above for a UTF-8-encoded symbol. More...
static exptr	spawnKleene (exptr const &b, bool optimized=true, bool aggressive=false)
	Gives an RE representing the Kleene closure of a given RE. More...
static exptr	spawnConcatenation (exptr const &l, exptr const &r, bool optimized=true, bool aggressive=false)
	Gives an RE representing the concatenation of two given REs. More...
static exptr	spawnAlternation (exptr const &l, exptr const &r, bool optimized=true, bool aggressive=false)
	Gives an RE representing the alternation of two given REs. More...
static exptr	spawnFromString (std::u32string const &re, literals lits, bool optimized=false, bool aggressive=false)
static exptr	spawnFromString (std::string const &utf8Re, literals lits, bool optimized=false, bool aggressive=false)
static exptr	spawnFromString (std::u32string const &re, bool optimized=false, bool aggressive=false)
	Gives an RE encoded in a given string. More...
static exptr	spawnFromString (std::string const &utf8Re, bool optimized=false, bool aggressive=false)
	Same as above for a UTF-8-encoded string. More...

Static Public Attributes
static char32_t	L = U'('
	The symbol used to represent the Left parenthesis in a regular expression. More...
static char32_t	R = U')'
	The symbol used to represent the Right parenthesis in a regular expression. More...
static char32_t	K = U'*'
	The symbol used to represent the Kleene star in a regular expression. More...
static char32_t	A = U'+'
	The symbol used to represent the Alternation in a regular expression. More...
static char32_t	E = U'ε'
	The symbol used to represent the Empty string in a regular expression. More...
static char32_t	N = U'∅'
	The symbol used to represent the Null/empty set in a regular expression. More...

Detailed Description

Represents formal regular expressions.

One should never need to handle such an object directly, however, much less copy or move it and therefore copy and move constructors are deleted.

To work with regular expressions, one should use expression::exptr, which aliases a shared_ptr to an actual object and can be copied and moved to one's heart's content. To access member functions, one might dereference exptrs temporarily or, better yet, use the arrow -> operator.

See also

expression::exptr

Definition at line 28 of file expression.h.

Member Typedef Documentation

exptr

typedef std::shared_ptr<expression const> reg::expression::exptr

This is the type used to handle regular expressions.

Every method works on shared_ptrs to the actual regular expressions, to help with basic comparisons and to save memory.

For example, every symbol's (and the empty string's and the empty set's) regular expression is only instantiated once and then pointed to by as many exptrs as one likes.

Definition at line 40 of file expression.h.

Member Enumeration Documentation

operation

enum reg::expression::operation

strong

The different purposes an RE may fulfill.

See also

spawnEmptySet

spawnEmptyString

spawnSymbol

spawnKleene

spawnConcatenation

spawnAlternation

Definition at line 84 of file expression.h.

{ empty, symbol, kleene, concatenation, alternation };

Member Function Documentation

begin()

vector< expression::exptr >::const_iterator reg::expression::begin

(

)

const

Returns an iterator pointing to this RE's first subexpression.

Definition at line 315 of file expression.cpp.

                                                              {
  return subExpressions.cbegin();
}

end()

vector< expression::exptr >::const_iterator reg::expression::end

(

)

const

Returns an iterator pointing behind this RE's last subexpression.

Definition at line 320 of file expression.cpp.

                                                            {
  return subExpressions.cend();
}

extractSymbol()

char32_t reg::expression::extractSymbol

(

)

const

Reports this symbol expression's UTF-32-encoded symbol.

Returns

the char32_t encoded within this symbol expression, U'\0' for an empty string

Exceptions

std::logic_error

if this expression's purpose is not that of a symbol

Definition at line 249 of file expression.cpp.

                                         {
  auto it = std::find_if(
      expression::symbols.begin(),
      expression::symbols.end(),
      [&](pair<char32_t,exptr> const& entry)->bool{return entry.second.get() == this;}
  );
  if (it == expression::symbols.end()) {
    throw std::logic_error("This RE does not seem to be a valid symbol expression.");
  }
  return it->first;
}

extractUtf8Symbol()

string reg::expression::extractUtf8Symbol

(

)

const

Reports this symbol expression's UTF-8-encoded symbol.

Returns

the character encoded within this symbol expression, "" for an empty string

Exceptions

std::logic_error

if this expression's purpose is not that of a symbol

Definition at line 266 of file expression.cpp.

                                           {
  char32_t symbol(extractSymbol());
  if (symbol == U'\0') {
    return string();
  } else {
    return converter.to_bytes(extractSymbol());
  }
}

getOperation()

expression::operation reg::expression::getOperation

(

)

const

Reports this RE's function.

Note that the empty string's function is technically that of a symbol.

Returns

the expression::operation best describing this RE's purpose

Definition at line 205 of file expression.cpp.

                                                   {
  return op;
}

operator nfa const &()

reg::expression::operator nfa const &

(

)

const

Returns an NFA accepting the language that this RE describes.

operator!=() [1/2]

bool reg::expression::operator!=

(

nfa const &

other

)

const

Checks whether this RE describes a different regular language than another object.

Returns

false if this RE's language is exactly the same as the other object's, true else

Definition at line 230 of file expression.cpp.

                                                  {
  return !operator==(other);
}

operator!=() [2/2]

bool reg::expression::operator!=

(

expression const &

other

)

const

Deprecated:

Was generalized to compare to any class in reg.

Definition at line 240 of file expression.cpp.

                                                         {
  return *this != static_cast<nfa const&>(other);
}

operator==() [1/2]

bool reg::expression::operator==

(

nfa const &

other

)

const

Checks whether this RE describes the same regular language as another object.

Returns

true if this RE's language is exactly the same as the other object's, false else

Definition at line 222 of file expression.cpp.

                                                  {
  return other.operator==(*this);
}

operator==() [2/2]

bool reg::expression::operator==

(

expression const &

other

)

const

Deprecated:

Was generalized to compare to any class in reg.

Definition at line 235 of file expression.cpp.

                                                         {
  return *this == static_cast<nfa const&>(other);
}

reset()

void reg::expression::reset ( )

static

Resets the symbols used for RE operators to their defaults.

Definition at line 36 of file expression.cpp.

                       {
  L = U'(';
  R = U')';
  K = U'*';
  A = U'+';
  E = U'ε';
  N = U'∅';
}

size()

size_t reg::expression::size

(

)

const

Reports the size of this RE's tree representation.

In this context, an RE's size will be defined recursively as follows:

• ∅.size() = 1
• ε.size() = 1
• <symbol>.size() = 1
• (l+r).size() = 1 + l.size() + r.size()
• (lr).size() = 1 + l.size() + r.size()
• (b*).size() = 1 + b.size()

  Returns

  a measure of how many subexpressions this RE consists of

Definition at line 192 of file expression.cpp.

                              {
  size_t s(1);
  for (exptr const& re : *this) {
    s += re->size();
  }
  return s;
}

spawnAlternation()

expression::exptr reg::expression::spawnAlternation ( expression::exptr const &  l, expression::exptr const &  r, bool  optimized = true, bool  aggressive = false  )

static

Gives an RE representing the alternation of two given REs.

More formally, the RE's language will be L(l+r) = L(l) ∪ L(r).

Parameters

l	exptr to one of the REs
r	exptr to the other RE
optimized	whether simplifications on the syntax level should be applied
aggressive	whether the simplifications should check the semantic level

Returns

exptr to the RE representing the alternation of l and r

Definition at line 123 of file expression.cpp.

                                                                                                                                {
  if (optimized) {
    if (l == expression::spawnEmptySet()) {
      return r;
    }
    if (r == expression::spawnEmptySet()) {
      return l;
    }
    if (l == r) {
      return l;
    }
    if (aggressive) {
      if (*l == *expression::spawnEmptySet()) {
        return r;
      }
      if (*r == *expression::spawnEmptySet()) {
        return l;
      }
      if (*l == *r) {
        return l->size() > r->size() ? r : l;
      }
      dfa empty;
      if (empty == nfa::subtract(*l, *r).build()) {
        return r;
      }
      if (empty == nfa::subtract(*r, *l).build()) {
        return l;
      }
    }
  }
  return expression::exptr(new expression(l, r, operation::alternation));
}

spawnConcatenation()

expression::exptr reg::expression::spawnConcatenation ( expression::exptr const &  l, expression::exptr const &  r, bool  optimized = true, bool  aggressive = false  )

static

Gives an RE representing the concatenation of two given REs.

More formally, the RE's language will be L(lr) = L(l) • L(r).

Parameters

l	exptr to the first RE
r	exptr to the second RE
optimized	whether simplifications on the syntax level should be applied
aggressive	whether the simplifications should check the semantic level

Returns

exptr to the RE representing the concatenation of l and r

Definition at line 88 of file expression.cpp.

                                                                                                                                  {
  if (optimized) {
    if (l == expression::spawnEmptyString()) {
      return r;
    }
    if (r == expression::spawnEmptyString()) {
      return l;
    }
    if (r == expression::spawnEmptySet() || l == expression::spawnEmptySet()) {
      return expression::spawnEmptySet();
    }
    if (aggressive) {
      if (*l == *expression::spawnEmptyString()) {
        return r;
      }
      if (*r == *expression::spawnEmptyString()) {
        return l;
      }
      if (*r == *expression::spawnEmptySet() || *l == *expression::spawnEmptySet()) {
        return expression::spawnEmptySet();
      }
    }
  }
  return expression::exptr(new expression(l, r, operation::concatenation));
}

spawnEmptySet()

expression::exptr const & reg::expression::spawnEmptySet ( )

static

Gives an RE representing the empty set ∅.

More formally, the RE's language will be {}.

Returns

exptr to the RE representing the empty set ∅

Definition at line 50 of file expression.cpp.

                                                 {
  return expression::empty;
}

spawnEmptyString()

expression::exptr const & reg::expression::spawnEmptyString ( )

static

Gives an RE representing the empty string ε.

More formally, the RE's language will be {ε}.

Returns

exptr to the RE representing the empty string ε

Definition at line 59 of file expression.cpp.

                                                    {
  return expression::spawnSymbol(U'\0');
}

spawnFromString() [1/4]

expression::exptr reg::expression::spawnFromString ( std::u32string const &  re, literals  lits, bool  optimized = false, bool  aggressive = false  )

static

Deprecated:

Use the static members of expression for providing your own literals.

Definition at line 609 of file expression.cpp.

                                                                                                                  {
  char32_t l = L;
  char32_t r = R;
  char32_t k = K;
  char32_t a = A;
  char32_t e = E;
  char32_t n = N;
  L = lits.L;
  R = lits.R;
  K = lits.S;
  A = lits.P;
  E = lits.EPSILON;
  N = lits.EMPTY;
  parser stringParser(re);
  exptr result;
  try {
    result = stringParser(optimized, aggressive);
    L = l;
    R = r;
    K = k;
    A = a;
    E = e;
    N = n;
  } catch (std::bad_function_call ex) {
    L = l;
    R = r;
    K = k;
    A = a;
    E = e;
    N = n;
    throw std::invalid_argument("Malformed regular expression.");
  }
  return result;
}

spawnFromString() [2/4]

expression::exptr reg::expression::spawnFromString ( std::string const &  utf8Re, literals  lits, bool  optimized = false, bool  aggressive = false  )

static

Deprecated:

Use the static members of expression for providing your own literals.

Definition at line 645 of file expression.cpp.

                                                                                                                {
  return spawnFromString(converter.from_bytes(utf8Re), lits, optimized, aggressive);
}

spawnFromString() [3/4]

expression::exptr reg::expression::spawnFromString ( std::u32string const &  re, bool  optimized = false, bool  aggressive = false  )

static

Gives an RE encoded in a given string.

Parameters

re	the RE in text form
optimized	whether simplifications on the syntax level should be applied
aggressive	whether the simplifications should check the semantic level

Returns

exptr to the RE represented by the given string

Exceptions

std::invalid_argument

if the re string is malformed

Definition at line 657 of file expression.cpp.

                                                                                                   {
  parser stringParser(re);
  try {
    return stringParser(optimized, aggressive);
  } catch (std::bad_function_call e) {
    throw std::invalid_argument("Malformed regular expression.");
  }
}

spawnFromString() [4/4]

expression::exptr reg::expression::spawnFromString ( std::string const &  utf8Re, bool  optimized = false, bool  aggressive = false  )

static

Same as above for a UTF-8-encoded string.

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Definition at line 667 of file expression.cpp.

                                                                                                 {
  return spawnFromString(converter.from_bytes(utf8Re), optimized, aggressive);
}

spawnKleene()

expression::exptr reg::expression::spawnKleene ( expression::exptr const &  b, bool  optimized = true, bool  aggressive = false  )

static

Gives an RE representing the Kleene closure of a given RE.

More formally, the RE's language will be L(b*) = L(b)*.

Parameters

b	exptr to the RE
optimized	whether simplifications on the syntax level should be applied
aggressive	whether the simplifications should check the semantic level

Returns

exptr to the RE representing the Kleene closure of l

Definition at line 164 of file expression.cpp.

                                                                                                 {
  if (optimized) {
    if (b == expression::spawnEmptySet() || b == expression::spawnEmptyString()) {
      return expression::spawnEmptyString();
    }
    if (aggressive) {
      if (*b == *expression::spawnEmptySet() || *b == *expression::spawnEmptyString()) {
        return expression::spawnEmptyString();
      }
      if (*b == expression(b)) {
        return b;
      }
    }
  }
  return expression::exptr(new expression(b));
}

spawnSymbol() [1/2]

expression::exptr const & reg::expression::spawnSymbol ( char32_t  symbol )

static

Gives an RE representing the given UTF-32-encoded symbol.

More formally, the RE's language will be {<symbol>}.

Parameters

symbol

the symbol the RE should represent or "" for the empty string ε

Returns

exptr to the RE representing the symbol

Definition at line 69 of file expression.cpp.

                                                              {
  return expression::symbols.insert(make_pair(symbol, exptr(new expression(symbol)))).first->second;
}

spawnSymbol() [2/2]

expression::exptr const & reg::expression::spawnSymbol ( std::string const &  utf8Symbol )

static

Same as above for a UTF-8-encoded symbol.

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Definition at line 74 of file expression.cpp.

                                                                       {
  char32_t u32Symbol(converter.from_bytes(utf8Symbol)[0]);
  return expression::symbols.insert(make_pair(u32Symbol, exptr(new expression(u32Symbol)))).first->second;
}

to_string()

string reg::expression::to_string

(

)

const

Describes this RE in UTF-8-encoded human-readable form.

Definition at line 310 of file expression.cpp.

                                   {
  return converter.to_bytes(to_u32string());
}

to_u32string()

u32string reg::expression::to_u32string

(

)

const

Describes this RE in UTF-32-encoded human-readable form.

Definition at line 276 of file expression.cpp.

                                         {
  switch (op) {
    case operation::alternation : return subExpressions[0]->to_u32string() + A + subExpressions[1]->to_u32string();
    case operation::concatenation : {
      u32string concat;
      if (subExpressions[0]->op >= operation::alternation) {
        concat.append(L + subExpressions[0]->to_u32string() + R);
      } else {
        concat.append(subExpressions[0]->to_u32string());
      }
      if (subExpressions[1]->op >= operation::alternation) {
        concat.append(L + subExpressions[1]->to_u32string() + R);
      } else {
        concat.append(subExpressions[1]->to_u32string());
      }
      return concat;
    }
    case operation::kleene : {
      if (subExpressions[0]->op >= operation::concatenation) {
        return (L + subExpressions[0]->to_u32string() + R) + K;
      } else {
        return subExpressions[0]->to_u32string() + K;
      }
    }
    case operation::symbol : {
      char32_t symbol = extractSymbol();
      return u32string(1, symbol + (!symbol * E));
    }
    case operation::empty : return u32string(1, N);
    default : return u32string();
  }
}

Member Data Documentation

A

char32_t reg::expression::A = U'+'

static

The symbol used to represent the Alternation in a regular expression.

Definition at line 41 of file expression.h.

E

char32_t reg::expression::E = U'ε'

static

The symbol used to represent the Empty string in a regular expression.

Definition at line 41 of file expression.h.

K

char32_t reg::expression::K = U'*'

static

The symbol used to represent the Kleene star in a regular expression.

Definition at line 41 of file expression.h.

L

char32_t reg::expression::L = U'('

static

The symbol used to represent the Left parenthesis in a regular expression.

Definition at line 41 of file expression.h.

N

char32_t reg::expression::N = U'∅'

static

The symbol used to represent the Null/empty set in a regular expression.

Definition at line 41 of file expression.h.

R

char32_t reg::expression::R = U')'

static

The symbol used to represent the Right parenthesis in a regular expression.

Definition at line 41 of file expression.h.

---

The documentation for this class was generated from the following files:

• expression.h
• expression.cpp