reg::gnfa::pImpl Struct Reference

Private implementation details of GNFAs. More...

Public Member Functions
	pImpl ()
	Constructs private implementation object for a GNFA accepting the empty language ∅. More...
	pImpl (unordered_map< string, unordered_map< string, expression::exptr >> &transitionMap, string const &initialState, forward_list< reference_wrapper< string const >> &acceptingStates)
	Constructs private implementation object with provided members. More...
expression::exptr const &	getTransition (string const &qLabel, string const &pLabel) const
	Safely fetches a transition RE between two states. More...
void	addTransition (string const &qLabel, string const &pLabel, expression::exptr re, bool optimized=true, bool aggressive=false)
	Safely adds a transition RE between two states. More...
string const &	generateState (char prefix='q', char suffix='\0')
	Generates a unique new state name with given prefix (and suffix). More...

Public Attributes
unordered_map< string, unordered_map< string, expression::exptr > >	transitions
	Holds the transition table viz state × state → regular expression. More...
string	initial
	Holds the name of the initial state. More...
string	accepting
	Holds the name of the accept state. More...

Detailed Description

Private implementation details of GNFAs.

Definition at line 26 of file gnfa.cpp.

Constructor & Destructor Documentation

pImpl() [1/2]

reg::gnfa::pImpl::pImpl ( )

inline

Constructs private implementation object for a GNFA accepting the empty language ∅.

Definition at line 35 of file gnfa.cpp.

          : initial("p0"), accepting("pF") {
    transitions[initial];
    transitions[accepting];
  }

pImpl() [2/2]

reg::gnfa::pImpl::pImpl ( unordered_map< string, unordered_map< string, expression::exptr >> &  transitionMap, string const &  initialState, forward_list< reference_wrapper< string const >> &  acceptingStates  )

inline

Constructs private implementation object with provided members.

Definition at line 41 of file gnfa.cpp.

                                                                      : transitions(move(transitionMap)) {
    initial = generateState('p',  '0');
    auto const& epsilon = expression::spawnEmptyString();
    transitions[initial][initialState] = epsilon;
    accepting = generateState('p', 'F');
    for (string const& a : acceptingStates) {
      transitions[a][accepting] = epsilon;
    }
  }

Member Function Documentation

addTransition()

void reg::gnfa::pImpl::addTransition ( string const &  qLabel, string const &  pLabel, expression::exptr  re, bool  optimized = true, bool  aggressive = false  )

inline

Safely adds a transition RE between two states.

The resulting transition will be labelled with the alternation of the provided RE and the former RE labelling the transition.

Parameters

qLabel	beginning of the transition
pLabel	end of the transition
re	the RE that should be added to the transition
optimized	pass-through to expression::spawnAlternation
aggressive	pass-through to expression::spawnAlternation

Definition at line 81 of file gnfa.cpp.

                                                                                                                                     {
    transitions[qLabel][pLabel] = expression::spawnAlternation(getTransition(qLabel, pLabel), re, optimized, aggressive);
  }

generateState()

string const& reg::gnfa::pImpl::generateState ( char  prefix = 'q', char  suffix = '\0'  )

inline

Generates a unique new state name with given prefix (and suffix).

State name generation has two modes:

1. If suffix == \0: The name begins with prefix and ends with an ever-increasing number.
2. Else: The name begins with prefix and ends with an ever-expanding repetition of suffix.

   Parameters

   prefix	printable char the new state's name should begin with
   suffix	printable char the new state's name should end with or \0 for a number

   Returns

   the first state name generated by the method above that is not present in the table of transitions

Definition at line 97 of file gnfa.cpp.

                                                                     {
    string state;
    if (suffix == '\0') {
      state = string(1, prefix).append(std::to_string(0));
      for (size_t q(1); transitions.count(state) != 0; q++) {
        state = string(1, prefix).append(std::to_string(q));
      }
    } else {
      for (state = string(1, prefix).append(1, suffix);
          transitions.count(state) != 0;
          state.append(1, suffix)
        ) {}
    }
    return transitions.insert(std::make_pair(state, unordered_map<string, expression::exptr>())).first->first;
  }

getTransition()

expression::exptr const& reg::gnfa::pImpl::getTransition ( string const &  qLabel, string const &  pLabel  ) const

inline

Safely fetches a transition RE between two states.

Parameters

qLabel	begin state of the transition
pLabel	end state of the transition

Returns

the RE corresponding to the transition between the states, ∅ if undefined

Definition at line 60 of file gnfa.cpp.

                                                                                         {
    auto const& from = transitions.at(qLabel);
    auto reIt = from.find(pLabel);
    if (reIt == from.end() || !reIt->second) {
      return expression::spawnEmptySet();
    }
    return reIt->second;
  }

Member Data Documentation

accepting

string reg::gnfa::pImpl::accepting

Holds the name of the accept state.

Definition at line 31 of file gnfa.cpp.

initial

string reg::gnfa::pImpl::initial

Holds the name of the initial state.

Definition at line 29 of file gnfa.cpp.

transitions

unordered_map<string,unordered_map<string,expression::exptr> > reg::gnfa::pImpl::transitions

Holds the transition table viz state × state → regular expression.

Definition at line 27 of file gnfa.cpp.

---

The documentation for this struct was generated from the following file:

• gnfa.cpp