Algorithms Library Toolkit
A toolkit for algorithms, especially for algorithms on formal languages
All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Concepts
GlushkovFollowNaive.h
Go to the documentation of this file.
1
6#pragma once
7
8#include <alib/map>
9#include <alib/set>
10#include <alib/vector>
12
15
16#include "GlushkovFirst.h"
17#include "GlushkovPos.h"
18
19namespace rte {
20
22
23 // --------------------------------------------------------------------
24
25 template < class SymbolType >
27
28 template < class SymbolType >
30
31 // --------------------------------------------------------------------
32
33 template < class SymbolType >
35
36 template < class SymbolType >
37 static void preprocessSubMap ( const TAlphabet < SymbolType > & alphabetK, TSubstMap < SymbolType > & subMap );
38
39 template < class SymbolType >
41
42 template < class T >
43 static void cartesian_rec ( const ext::vector < ext::vector < T > > & input, ext::vector < ext::vector < T > > & ret, ext::vector < T > & current, size_t depth );
44
45public:
51 template < class SymbolType >
53
54 template < class SymbolType >
55 class Formal {
56 public:
63 };
64
65};
66
67template < class SymbolType >
70
71 /* Init substitution map, ie \forall a \in K: sub[a] = \emptyset */
72 for ( const common::ranked_symbol < SymbolType > & ssymb : rte.getSubstitutionAlphabet ( ) )
73 subMap.insert ( std::make_pair ( ssymb, TAlphabet < SymbolType > { } ) );
74
75 /* recursively compute follow */
76 return rte.getRTE ( ).getStructure ( ).template accept < ext::set < ext::vector < common::ranked_symbol < SymbolType > > >, GlushkovFollowNaive::Formal < SymbolType > > ( symbol, rte.getSubstitutionAlphabet ( ), subMap );
77}
78
79// -----------------------------------------------------------------------------
80
81template < class T >
82void GlushkovFollowNaive::cartesian_rec ( const ext::vector < ext::vector < T > > & input, ext::vector < ext::vector < T > > & ret, ext::vector < T > & current, size_t depth ) {
83 if ( depth == input.size ( ) )
84 ret.push_back ( current );
85 else
86 for ( size_t i = 0; i < input[depth].size ( ); i++ ) {
87 current[depth] = input[depth][i];
88 cartesian_rec ( input, ret, current, depth + 1 );
89 }
90}
91
92template < class SymbolType >
96
97 cartesian_rec ( input, ret, current, 0 );
98
99 return ret;
100}
101
107template < class SymbolType >
108void GlushkovFollowNaive::preprocessSubMap ( const TAlphabet < SymbolType > & alphabetK, TSubstMap < SymbolType > & subMap ) {
109 for ( bool change = true; change; change = false )
110 for ( std::pair < const common::ranked_symbol < SymbolType >, TAlphabet < SymbolType > > & kv : subMap ) {
111 TAlphabet < SymbolType > & substSet = kv.second;
112
113 for ( auto eIter = substSet.begin ( ); eIter != substSet.end ( ); ) {
114 if ( alphabetK.count ( * eIter ) == 0 ) {
115 ++eIter;
116 } else {
117 auto it = subMap.find ( * eIter );
118 size_t oldSize = substSet.size ( );
119 substSet.insert ( it->second.begin ( ), it->second.end ( ) );
120 change = ( oldSize != substSet.size ( ) ); // something was added
121 eIter = substSet.erase ( eIter );
122 }
123 }
124 }
125}
126
127template < class SymbolType >
128ext::set < ext::vector < common::ranked_symbol < SymbolType > > > GlushkovFollowNaive::replaceConstants ( const TAlphabet < SymbolType > & alphabetK, const ext::vector < ext::set < common::ranked_symbol < SymbolType > > > & follow, const TSubstMap < SymbolType > & subMap2 ) {
129 TSubstMap < SymbolType > subMap ( subMap2 );
130 preprocessSubMap ( alphabetK, subMap );
131
133
135 for ( const common::ranked_symbol < SymbolType > & e : s ) {
136 if ( alphabetK.count ( e ) > 0 )
137 input.push_back ( ext::vector < common::ranked_symbol < SymbolType > > ( subMap.at ( e ).begin ( ), subMap.at ( e ).end ( ) ) );
138 else
139 input.push_back ( ext::vector < common::ranked_symbol < SymbolType > > { e } );
140 }
141 }
142
143 /* now do the cartesian product on "input" */
145 return ext::set < ext::vector < common::ranked_symbol < SymbolType > > > ( followSet.begin ( ), followSet.end ( ) );
146}
147
148// -----------------------------------------------------------------------------
149
150template < class SymbolType >
154
155 tmp = node.getLeftElement ( ).template accept < ext::set < ext::vector < common::ranked_symbol < SymbolType > > >, GlushkovFollowNaive::Formal < SymbolType > > ( symbolF, alphabetK, subMap );
156 ret.insert ( tmp.begin ( ), tmp.end ( ) );
157
158 tmp = node.getRightElement ( ).template accept < ext::set < ext::vector < common::ranked_symbol < SymbolType > > >, GlushkovFollowNaive::Formal < SymbolType > > ( symbolF, alphabetK, subMap );
159 ret.insert ( tmp.begin ( ), tmp.end ( ) );
160
161 return ret;
162}
163
164template < class SymbolType >
166
167 TSubstMap < SymbolType > subMap2 ( subMap );
168 auto itMap = subMap2.find ( node.getSubstitutionSymbol ( ).getSymbol ( ) );
169
170 itMap->second.clear ( );
171
172 for ( const auto & s : node.getRightElement ( ).template accept < TAlphabet < SymbolType >, GlushkovFirst::Formal < SymbolType > > ( ) )
173 itMap->second.insert ( s );
174
175 /*
176 * E sub F
177 * 1. if symbolF in F subtree, then Follow(F, symbolF);
178 * 2. if symbolF in E subtree, then Follow(E, symbolF);
179 */
180
181 if ( node.getLeftElement ( ).template accept < bool, GlushkovPos::Formal < SymbolType > > ( symbolF ) )
182 return node.getLeftElement ( ).template accept < ext::set < ext::vector < common::ranked_symbol < SymbolType > > >, GlushkovFollowNaive::Formal < SymbolType > > ( symbolF, alphabetK, subMap2 );
183 else
184 return node.getRightElement ( ).template accept < ext::set < ext::vector < common::ranked_symbol < SymbolType > > >, GlushkovFollowNaive::Formal < SymbolType > > ( symbolF, alphabetK, subMap );
185}
186
187template < class SymbolType >
189
191
192 auto itMap = subMap.find ( node.getSubstitutionSymbol ( ).getSymbol ( ) );
194
195 for ( const auto & s : node.getElement ( ).template accept < TAlphabet < SymbolType >, GlushkovFirst::Formal < SymbolType > > ( ) )
196 subMap[node.getSubstitutionSymbol ( ).getSymbol ( )].insert ( s );
197
198 auto res = node.getElement ( ).template accept < ext::set < ext::vector < common::ranked_symbol < SymbolType > > >, GlushkovFollowNaive::Formal < SymbolType > > ( symbolF, alphabetK, subMap );
199 itMap->second = backup;
200 return res;
201}
202
203template < class SymbolType >
205
208
209 if ( symbolF == node.getSymbol ( ) ) {
211
212 for ( const rte::FormalRTEElement < SymbolType > & c : node.getElements ( ) )
213 children.push_back ( c.template accept < TAlphabet < SymbolType >, GlushkovFirst::Formal < SymbolType > > ( ) );
214
215 return replaceConstants ( alphabetK, children, subMap );
216 }
217
218 for ( const auto & c : node.getElements ( ) ) {
219 tmp = c.template accept < ext::set < ext::vector < common::ranked_symbol < SymbolType > > >, GlushkovFollowNaive::Formal < SymbolType > > ( symbolF, alphabetK, subMap );
220 ret.insert ( tmp.begin ( ), tmp.end ( ) );
221 }
222
223 return ret;
224}
225
226template < class SymbolType >
229}
230
231template < class SymbolType >
234}
235
236} /* namespace rte */
237
Definition: ranked_symbol.hpp:20
Class extending the map class from the standard library. Original reason is to allow printing of the ...
Definition: map.hpp:48
std::pair< iterator, bool > insert(const T &key, const R &value)
Insert variant with explicit key and value parameters.
Definition: map.hpp:118
Class extending the pair class from the standard library. Original reason is to allow printing of the...
Definition: pair.hpp:43
Definition: set.hpp:44
auto begin() &
Inherited behavior of begin for non-const instance.
Definition: set.hpp:99
auto end() &
Inherited behavior of end for non-const instance.
Definition: set.hpp:129
Class extending the vector class from the standard library. Original reason is to allow printing of t...
Definition: vector.hpp:45
auto begin() &
Inherited behavior of begin for non-const instance.
Definition: vector.hpp:125
auto end() &
Inherited behavior of end for non-const instance.
Definition: vector.hpp:155
Represents the alternation operator in the regular tree expression. The node must have exactly two ch...
Definition: FormalRTEAlternation.h:44
Definition: FormalRTEElement.h:54
Represents the empty expression in the regular tree expression. The node can't have any children.
Definition: FormalRTEEmpty.h:40
Represents the iteration operator in the regular tree expression. The node has exactly one child.
Definition: FormalRTEIteration.h:45
Represents the concatenation operator in the regular tree expression. The node must have exactly two ...
Definition: FormalRTESubstitution.h:44
Represents the terminal symbol in the regular tree expression. The number of children must be the sam...
Definition: FormalRTESymbolAlphabet.h:44
Represents the substitution symbol in the regular tree expression. The node can't have any children.
Definition: FormalRTESymbolSubst.h:43
Formal regular tree expression represents regular tree expression. It describes regular tree language...
Definition: FormalRTE.h:71
Definition: GlushkovFirst.h:25
Definition: GlushkovFollowNaive.h:55
static ext::set< ext::vector< common::ranked_symbol< SymbolType > > > visit(const rte::FormalRTEAlternation< SymbolType > &node, const common::ranked_symbol< SymbolType > &symbolF, const TAlphabet< SymbolType > &alphabetK, TSubstMap< SymbolType > &subMap)
Definition: GlushkovFollowNaive.h:151
Definition: GlushkovFollowNaive.h:21
static ext::set< ext::vector< common::ranked_symbol< SymbolType > > > follow(const rte::FormalRTE< SymbolType > &rte, const common::ranked_symbol< SymbolType > &symbol)
Definition: GlushkovFollowNaive.h:68
Definition: GlushkovPos.h:24
ext::set< ext::pair< StateType, StateType > > ret(const ext::set< ext::pair< StateType, StateType > > &S, const DeterministicPushdownStoreSymbolType &pdaSymbol, const InputSymbolType &input, const N &nondeterministic)
Definition: RHDPDACommon.h:57
int i
Definition: AllEpsilonClosure.h:118
typename T::SymbolType SymbolType
Definition: ReachableStates.h:176
return res
Definition: MinimizeByPartitioning.h:145
constexpr auto make_pair(T1 &&x, T2 &&y)
Definition: pair.hpp:79
Definition: Node.cpp:11
Definition: ToFTAGlushkov.h:22