Parses regular expressions. More...

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

Public Types
enum	token : unsigned char { token::A, token::B, token::C, token::K, token::E, token::F, token::Σ, token::P, token::L, token::R, token::S, token::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)
	Initializes with a string to parse. 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
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
	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 (“+” or “|”), L for a left parenthesis (“(”), R for a right parenthesis (“)”) and S for the Kleene star (“*”). Σ is a placeholder for any symbol that makes up the language described by the RE, the empty word (“ε” or “λ”) or the empty set (“∅”).

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 417 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 438 of file expression.cpp.

Member Enumeration Documentation

◆ token

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

strong

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 419 of file expression.cpp.

Constructor & Destructor Documentation

◆ parser()

reg::expression::parser::parser ( u32string const & re )

inline

Initializes with a string to parse.

Definition at line 542 of file expression.cpp.

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 479 of file expression.cpp.

◆ 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 514 of file expression.cpp.

◆ 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 456 of file expression.cpp.

◆ 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

Exceptions

std::bad_function_call if the regular expression string was malformed

Definition at line 675 of file expression.cpp.

Member Data Documentation

◆ badRegularExpression

bool reg::expression::parser::badRegularExpression

Initial value:

=

false

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

Definition at line 537 of file expression.cpp.

◆ inverseBinaryRules

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

static

Initial value:

=
    []() -> array<array<expression::parser::tokens, TOKEN(END)>, 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 444 of file expression.cpp.

◆ inverseUnitGraph

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

static

Initial value:

=
    []() -> array<expression::parser::token, 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 440 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 531 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 533 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 536 of file expression.cpp.

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

expression.cpp

Classes

Public Types

Public Member Functions

Static Public Member Functions

Public Attributes

Static Public Attributes

Detailed Description

Member Typedef Documentation

◆ tokens

Member Enumeration Documentation

◆ token

Constructor & Destructor Documentation

◆ parser()

Member Function Documentation

◆ canDerive()

◆ compileTableEntry()

◆ getUClosure()

◆ operator()()

Member Data Documentation

◆ badRegularExpression

◆ inverseBinaryRules

◆ inverseUnitGraph

◆ symbolMapping

◆ symbolMappingIndex

◆ table