Newer
Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
/*
* RegularEquationSolver.h
*
* Created on: 4. 3. 2014
* Author: tomas
*/
#ifndef REGULAREQUATIONSOLVER_H_
#define REGULAREQUATIONSOLVER_H_
#include <map>
#include <deque>
#include <queue>
#include <alphabet/Symbol.h>
#include <exception/AlibException.h>
#include <regexp/unbounded/UnboundedRegExpElement.h>
#include "common/macros.h"
// #include "RegExpOptimize.h" //TODO uncomment when implemented
namespace equations {
/**
* Base class for regular equations solvers.
*/
class RegularEquationSolver
{
public:
RegularEquationSolver( void );
virtual ~RegularEquationSolver( void );
/**
* Adds nonterminal symbol into system.
*
* @param symb given symbol
*/
void addSymbol( const alphabet::Symbol & symb );
/**
* Adds equation in form FROM = eq TO
*
* @param from symbol
* @param to symbol
* @param eq equation
*/
void addEquation( const alphabet::Symbol & from, const alphabet::Symbol & to, const regexp::UnboundedRegExpElement* eq );
/**
* Adds equation in form: FROM = eq
*
* @param from
* @param eq
*/
void addEquation( const alphabet::Symbol & from, const regexp::UnboundedRegExpElement* eq );
/**
* Solve expression system
*
* @param solveFor will solve equation system for given symbol
* @return regexp
*/
regexp::UnboundedRegExp solve( const alphabet::Symbol & solveFor );
protected:
/**
* actual equations elimination
* @return pointer to solutions RegExp tree root
*/
virtual regexp::UnboundedRegExpElement* eliminate( void ) = 0;
/**
* Runs BFS to determine depth of symbols in equation system and stores it in m_symbolsByDepth;
* @see m_symbolsByDepth
*/
void symbolsByDepth( const alphabet::Symbol & solveFor );
/**
* @see symbolsByDepth
*/
std::deque<alphabet::Symbol> m_symbolsByDepth;
/**
* Stores transitions from nonterminal to nonterminal, eg A = 2A + 2B + 1C
*/
std::map<alphabet::Symbol, std::map<alphabet::Symbol, regexp::UnboundedRegExpElement*>> m_eqTransition;
/**
* Stores equation not going to particular nonterminal, eg A = 01*
*/
std::map<alphabet::Symbol, regexp::UnboundedRegExpElement*> m_eqFinal;
/**
* Set of symbols
*/
std::set<alphabet::Symbol> m_symbols;
};
} /* namespace equations */
#endif /* REGULAREQUATIONSOLVER_H_ */