reg::expression::parser::tree Struct Reference

Represents the table entries as binary trees. More...

Public Member Functions
pair< unique_ptr< tree >, unique_ptr< tree > >	findNextPair (token symbol, size_t row, size_t diag, parser const *p)
	Finds the child trees that can be derived from a given entry. More...
	tree (size_t row, size_t diag, parser const *p)
	Initializes a tree with a given table entry as root. More...
exptr	operator() (bool optimized, bool aggressive)
	Gives the RE encoded in this tree. More...

Public Attributes
parser const *	p
	Points to the parser this tree belongs to. More...
token	symbol
	This tree's root symbol. More...
pair< unique_ptr< tree >, unique_ptr< tree > >	children
	Trees with the symbols of the entry's derived pair as root. More...

Detailed Description

Represents the table entries as binary trees.

Definition at line 461 of file expression.cpp.

Constructor & Destructor Documentation

tree()

reg::expression::parser::tree::tree ( size_t  row, size_t  diag, parser const *  p  )

inline

Initializes a tree with a given table entry as root.

Parameters

row	the row of the entry
diag	the diagonal of the entry
p	pointer to the calling parser

Definition at line 494 of file expression.cpp.

                                                   :
        p(p),
        symbol([&]()->token{
          for (unsigned char i(token::END); i > 0; i--) {
          if (p->table[row][diag][i-1]) {
            return static_cast<token>(i-1);
          }
          }
          return token::END;
        }()),
        children(findNextPair(symbol, row, diag, p)) {}

Member Function Documentation

findNextPair()

pair<unique_ptr<tree>,unique_ptr<tree> > reg::expression::parser::tree::findNextPair ( token  symbol, size_t  row, size_t  diag, parser const *  p  )

inline

Finds the child trees that can be derived from a given entry.

Parameters

symbol	the entry's symbol
row	the row of the entry
diag	the diagonal of the entry
p	points to this tree's owning parser

Returns

pair of trees, both of which can be derived from the entry (may both be

null 

if the entry is nullable)

Definition at line 476 of file expression.cpp.

                                                                                                                 {
      for (size_t i = 0; i < diag; i++) {
        size_t leftDiag = diag-i-1;
        size_t rightDiag = i;
        size_t rightRow = diag+row-rightDiag;
        if (canDerive(symbol, p->table[row][leftDiag], p->table[rightRow][rightDiag])) {
          return make_pair(make_unique<tree>(row, leftDiag, p), make_unique<tree>(rightRow, rightDiag, p));
        }
      }
      return make_pair(unique_ptr<tree>(), unique_ptr<tree>());
    }

operator()()

exptr reg::expression::parser::tree::operator() ( bool  optimized, bool  aggressive  )

inline

Gives the RE encoded in this tree.

Definition at line 507 of file expression.cpp.

                                                      {
      switch (symbol) {
        case token::A:
          return spawnAlternation((*children.first)(optimized, aggressive), (*children.second)(optimized, aggressive), optimized, aggressive);
        case token::B:
          return (*children.second)(optimized, aggressive);
        case token::C:
          return spawnConcatenation((*children.first)(optimized, aggressive), (*children.second)(optimized, aggressive), optimized, aggressive);
        case token::K:
          return spawnKleene((*children.first)(optimized, aggressive), optimized, aggressive);
        case token::E:
          return (*children.second)(optimized, aggressive);
        case token::F:
          return (*children.first)(optimized, aggressive);
        case token::Σ: {
          char32_t symbol = p->symbolMapping[p->symbolMappingIndex++];
          if (p->symbolMappingIndex >= p->symbolMapping.size()) { p->symbolMappingIndex = 0; }
          if (symbol == p->lits.EPSILON) { return spawnEmptyString(); }
          else if (symbol == p->lits.EMPTY) { return spawnEmptySet(); }
          else { return spawnSymbol(symbol); }
        }
        default:
        return exptr();
      }
    }

Member Data Documentation

children

pair<unique_ptr<tree>,unique_ptr<tree> > reg::expression::parser::tree::children

Trees with the symbols of the entry's derived pair as root.

Definition at line 464 of file expression.cpp.

p

parser const* reg::expression::parser::tree::p

Points to the parser this tree belongs to.

Definition at line 462 of file expression.cpp.

symbol

token reg::expression::parser::tree::symbol

This tree's root symbol.

Definition at line 463 of file expression.cpp.

---

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

• expression.cpp