reg::expression::parser Struct Reference

Parses regular expressions. More...

Classes
struct	tree
	Represents the table entries as binary trees. More...

Public Types
enum	token : unsigned char {   A, B, C, K,   E, F, Σ, P,   L, R, S, END }
	Tokens the grammar deals with. More...
typedef bitset< token::END >	tokens
	Tokens don't usually come alone. More...

Public Member Functions
	parser (u32string const &re, literals const &lits)
	Initializes with a string to parse and literals to parse for. More...
exptr	operator() (bool optimized, bool aggressive)
	Gives the RE resulting from parsing. More...

Static Public Member Functions
static tokens	getUClosure (tokens const &m)
	Constructs the reflexive-transitive closure of the inverse unit relation for a given set of symbols. More...
static bool	canDerive (token symbol, tokens const &left, tokens const &right)
	Checks if a token could derive a pair of tokens from two other entries. More...
static void	compileTableEntry (size_t row, size_t diag, vector< vector< tokens >> &table)
	Fills a table entry. More...

Public Attributes
literals	lits
	Stores interpretations for characters encountered in the parsed string. More...
vector< char32_t >	symbolMapping
	Stores the actual symbols encountered in the RE while parsing. More...
size_t	symbolMappingIndex
	Index for when symbols have to be extracted from the mapping. More...
vector< vector< tokens > >	table
	The table of sets of symbols that derive a subsentence. More...
bool	badRegularExpression = false
	Signifies that the RE used to initialize this object was invalid. More...

Static Public Attributes
static array< token, token::END > const	inverseUnitGraph
	Maps symbols that may be derived in-place to their predecessing symbols. More...
static array< array< tokens, token::END >, token::END > const	inverseBinaryRules
	Maps pairs of symbols to the symbols that derive them. More...

Detailed Description

Parses regular expressions.

Recognizes REs generated by the following context-free grammar, where P stands for the alternative symbol (literal "+" or "|"), L for a left parenthesis (literal "("), R for a right parenthesis (literal ")") and S for the Kleene star (literal "*"). Σ is a placeholder for any symbol that makes up the regular language described by the RE:

GRE=(
       {A, B, C, K, E, F},
       {Σ, P, L, R, S}, A,
       {
         (A,C), (A,AB),
         (B,PC),
         (C,K), (C,CK),
         (K,E), (K,ES),
         (E,Σ), (E,LF),
         (F,AR)
       }
    )

This parser is based on the article To CNF or not to CNF? An Efficient Yet Presentable Version of the CYK Algorithm by Martin Lange and Hans Leiß, published in informatica didactica No. 8. Conventions will be based on this article.

Definition at line 319 of file expression.cpp.

Member Typedef Documentation

tokens

typedef bitset<token::END> reg::expression::parser::tokens

Tokens don't usually come alone.

Definition at line 337 of file expression.cpp.

Member Enumeration Documentation

token

enum reg::expression::parser::token : unsigned char

Tokens the grammar deals with.

Enumerator
A	Beginning of an alternation expression.
B	Second part of an alternation expression.
C	A concatenation expression.
K	Kleene expression.
E	Beginning of a new subexpression.
F	Second part of a new subexpression.
Σ	A symbol expression.
P	An alternation symbol.
L	A left parenthesis.
R	A right parenthesis.
S	A Kleene star symbol.
END	Number of elements in this enumeration, NOT AN ACTUAL TOKEN!

Definition at line 321 of file expression.cpp.

             : unsigned char {
      A, 
      B, 
      C, 
      K, 
      E, 
      F, 
      Σ, 
      P, 
      L, 
      R, 
      S, 
      END 
    };

Constructor & Destructor Documentation

parser()

reg::expression::parser::parser ( u32string const &  re, literals const &  lits  )

inline

Initializes with a string to parse and literals to parse for.

Definition at line 429 of file expression.cpp.

                                                    {
    if (re.empty()) {
      badRegularExpression = true;
      return;
    }
    symbolMappingIndex = 0;
    size_t numberOfTokens(re.length());
    symbolMapping.reserve(numberOfTokens);
    table.reserve(numberOfTokens);
    size_t row(0);
    for (char32_t symbol : re) {
      table.push_back(vector<tokens>(numberOfTokens-row, tokens()));
      if (symbol == lits.L) { table[row][0].set(token::L); }
      else if (symbol == lits.R) { table[row][0].set(token::R); }
      else if (symbol == lits.P) { table[row][0].set(token::P); }
      else if (symbol == lits.S) { table[row][0].set(token::S); }
      else {
        table[row][0].set(token::Σ);
        symbolMapping.push_back(symbol);
      }
      row++;
    }
    symbolMapping.shrink_to_fit();
    for (size_t diag(1); diag < numberOfTokens; diag++) {
      for (size_t row(0); row < numberOfTokens - diag; row++) {
        compileTableEntry(row, diag, table);
      }
    }
    if (!getUClosure(table[0][table[0].size()-1])[token::A]) {
      badRegularExpression = true;
    }
  }

Member Function Documentation

canDerive()

static bool reg::expression::parser::canDerive ( token  symbol, tokens const &  left, tokens const &  right  )

inlinestatic

Checks if a token could derive a pair of tokens from two other entries.

Parameters

symbol	the original token
left	the set of tokens allowed for the first half of the result pair
right	the set of tokens allowed for the second half of the result pair

Returns

true if the original token may lead to any such pair, false else

Definition at line 373 of file expression.cpp.

                                                                               {
    tokens leftClosure(getUClosure(left));
    tokens rightClosure(getUClosure(right));
    for (unsigned char li(0); li < token::END; li++) {
    if (leftClosure[li]) {
      for (unsigned char ri(0); ri < token::END; ri++) {
      if (rightClosure[ri]) {
        for (unsigned char ci(0); ci < token::END; ci++) {
        if (inverseBinaryRules[li][ri][ci]) {
          for (unsigned char successor(ci); successor != token::END; successor = inverseUnitGraph[successor]) {
            if (symbol == successor) {
              return true;
            }
          }
        }
        }
      }
      }
    }
    }
    return false;
  }

compileTableEntry()

static void reg::expression::parser::compileTableEntry ( size_t  row, size_t  diag, vector< vector< tokens >> &  table  )

inlinestatic

Fills a table entry.

The entry will be filled with the set of symbols deriving the subsentence beginning at the diagonal entry in the same row and ending at the diagonal entry in the same column.

Parameters

row	the row of the entry to fill
diag	the diagonal of the entry to fill
table	the table to operate on

Definition at line 406 of file expression.cpp.

                                                                                        {
    for (size_t i(0); i < diag; i++) {
      tokens first(getUClosure(table[row][i]));
      for (unsigned char fi(0); fi < first.size(); fi++) {
      if (first[fi]) {
        tokens second(getUClosure(table[row+1+i][diag-i-1]));
        for (unsigned char si(0); si < second.size(); si++) {
        if (second[si]) {
          table[row][diag] |= inverseBinaryRules[fi][si];
        }
        } // Going through the tokens in second.
      }
      } // Going through the tokens in first.
    }
  }

getUClosure()

static tokens reg::expression::parser::getUClosure ( tokens const &  m )

inlinestatic

Constructs the reflexive-transitive closure of the inverse unit relation for a given set of symbols.

See Lemma 5 in the article.

Parameters

m	the set of symbols that may be derived in-place

Returns

the set of symbols that may be predecessors to any of the symbols in m

Definition at line 354 of file expression.cpp.

                                             {
    tokens closure;
    for (unsigned char c(0); c < token::END; c++) {
    if (m[c]) {
      for (token s(static_cast<token>(c)); s != token::END; s = inverseUnitGraph[s]) {
        closure.set(s);
      }
    }
    } // Going through the tokens in m.
    return closure;
  }

operator()()

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

inline

Gives the RE resulting from parsing.

Returns

exptr to the RE represented by the initialization string

Definition at line 540 of file expression.cpp.

                                                    {
    if (badRegularExpression) {
      #ifdef __EXCEPTIONS
      throw std::bad_function_call();
      #else
      return exptr();
      #endif
    }
    return tree(0, table.size()-1, this)(optimized, aggressive);
  }

Member Data Documentation

badRegularExpression

bool reg::expression::parser::badRegularExpression = false

Signifies that the RE used to initialize this object was invalid.

Definition at line 426 of file expression.cpp.

inverseBinaryRules

auto const reg::expression::parser::inverseBinaryRules

static

Initial value:

=
    []()->array<array<expression::parser::tokens,expression::parser::token::END>,expression::parser::token::END>{
  array<tokens,token::END> noPredecessor;
  noPredecessor.fill(tokens());
  array<array<tokens,token::END>,token::END> rules;
  rules.fill(noPredecessor);
  rules[token::A][token::B].set(token::A);
  rules[token::P][token::C].set(token::B);
  rules[token::C][token::K].set(token::C);
  rules[token::E][token::S].set(token::K);
  rules[token::L][token::F].set(token::E);
  rules[token::A][token::R].set(token::F);
  return rules;
}()

Maps pairs of symbols to the symbols that derive them.

Definition at line 343 of file expression.cpp.

inverseUnitGraph

auto const reg::expression::parser::inverseUnitGraph

static

Initial value:

=
    []()->array<expression::parser::token,expression::parser::token::END>{
  array<token,token::END> graph;
  graph.fill(token::END);
  graph[token::Σ] = token::E;
  graph[token::E] = token::K;
  graph[token::K] = token::C;
  graph[token::C] = token::A;
  return graph;
}()

Maps symbols that may be derived in-place to their predecessing symbols.

See Definition 2 and Lemma 4 in the article.

Definition at line 339 of file expression.cpp.

lits

literals reg::expression::parser::lits

Stores interpretations for characters encountered in the parsed string.

Definition at line 422 of file expression.cpp.

symbolMapping

vector<char32_t> reg::expression::parser::symbolMapping

Stores the actual symbols encountered in the RE while parsing.

Definition at line 423 of file expression.cpp.

symbolMappingIndex

size_t reg::expression::parser::symbolMappingIndex

mutable

Index for when symbols have to be extracted from the mapping.

Definition at line 424 of file expression.cpp.

table

vector<vector<tokens> > reg::expression::parser::table

The table of sets of symbols that derive a subsentence.

Definition at line 425 of file expression.cpp.

---

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

• expression.cpp