Algorithms Library Toolkit
A toolkit for algorithms, especially for algorithms on formal languages
GlushkovFollow.h
Go to the documentation of this file.
1
6#pragma once
7
8#include <ext/iterator>
9
10#include <alib/set>
11
12#include <regexp/unbounded/UnboundedRegExp.h>
13
14#include <regexp/unbounded/UnboundedRegExpAlternation.h>
15#include <regexp/unbounded/UnboundedRegExpConcatenation.h>
16#include <regexp/unbounded/UnboundedRegExpElement.h>
17#include <regexp/unbounded/UnboundedRegExpEmpty.h>
18#include <regexp/unbounded/UnboundedRegExpEpsilon.h>
19#include <regexp/unbounded/UnboundedRegExpIteration.h>
20#include <regexp/unbounded/UnboundedRegExpSymbol.h>
21
22#include "GlushkovFirst.h"
23#include "GlushkovLast.h"
24#include "GlushkovPos.h"
25
26#include <regexp/properties/RegExpEpsilon.h>
27
28namespace regexp {
29
35class GlushkovFollow {
36public:
42 template < class SymbolType >
43 static ext::set < UnboundedRegExpSymbol < SymbolType > > follow ( const regexp::UnboundedRegExp < SymbolType > & re, const UnboundedRegExpSymbol < SymbolType > & symbol );
44
45 template < class SymbolType >
46 class Unbounded {
47 public:
48 static ext::set < regexp::UnboundedRegExpSymbol < SymbolType > > visit ( const regexp::UnboundedRegExpAlternation < SymbolType > & node, const regexp::UnboundedRegExpSymbol < SymbolType > & symbolptr );
49 static ext::set < regexp::UnboundedRegExpSymbol < SymbolType > > visit ( const regexp::UnboundedRegExpConcatenation < SymbolType > & node, const regexp::UnboundedRegExpSymbol < SymbolType > & symbolptr );
50 static ext::set < regexp::UnboundedRegExpSymbol < SymbolType > > visit ( const regexp::UnboundedRegExpIteration < SymbolType > & node, const regexp::UnboundedRegExpSymbol < SymbolType > & symbolptr );
51 static ext::set < regexp::UnboundedRegExpSymbol < SymbolType > > visit ( const regexp::UnboundedRegExpSymbol < SymbolType > & node, const regexp::UnboundedRegExpSymbol < SymbolType > & symbFollow );
52 static ext::set < regexp::UnboundedRegExpSymbol < SymbolType > > visit ( const regexp::UnboundedRegExpEmpty < SymbolType > & node, const regexp::UnboundedRegExpSymbol < SymbolType > & symbFollow );
53 static ext::set < regexp::UnboundedRegExpSymbol < SymbolType > > visit ( const regexp::UnboundedRegExpEpsilon < SymbolType > & node, const regexp::UnboundedRegExpSymbol < SymbolType > & symbFollow );
54 };
55
61 template < class SymbolType >
62 static ext::map < regexp::FormalRegExpSymbol < SymbolType >, ext::set < regexp::FormalRegExpSymbol < SymbolType > > > follow ( const regexp::FormalRegExp < SymbolType > & re );
63
64 template < class SymbolType >
65 class Formal {
66 public:
67 static void visit ( const regexp::FormalRegExpAlternation < SymbolType > & node, ext::set < regexp::FormalRegExpSymbol < SymbolType > > & currentFollow, ext::map < regexp::FormalRegExpSymbol < SymbolType >, ext::set < regexp::FormalRegExpSymbol < SymbolType > > > & res );
68 static void visit ( const regexp::FormalRegExpConcatenation < SymbolType > & node, ext::set < regexp::FormalRegExpSymbol < SymbolType > > & currentFollow, ext::map < regexp::FormalRegExpSymbol < SymbolType >, ext::set < regexp::FormalRegExpSymbol < SymbolType > > > & res );
69 static void visit ( const regexp::FormalRegExpIteration < SymbolType > & node, ext::set < regexp::FormalRegExpSymbol < SymbolType > > & currentFollow, ext::map < regexp::FormalRegExpSymbol < SymbolType >, ext::set < regexp::FormalRegExpSymbol < SymbolType > > > & res );
70 static void visit ( const regexp::FormalRegExpSymbol < SymbolType > & node, ext::set < regexp::FormalRegExpSymbol < SymbolType > > & currentFollow, ext::map < regexp::FormalRegExpSymbol < SymbolType >, ext::set < regexp::FormalRegExpSymbol < SymbolType > > > & res );
71 static void visit ( const regexp::FormalRegExpEmpty < SymbolType > & node, ext::set < regexp::FormalRegExpSymbol < SymbolType > > & currentFollow, ext::map < regexp::FormalRegExpSymbol < SymbolType >, ext::set < regexp::FormalRegExpSymbol < SymbolType > > > & res );
72 static void visit ( const regexp::FormalRegExpEpsilon < SymbolType > & node, ext::set < regexp::FormalRegExpSymbol < SymbolType > > & currentFollow, ext::map < regexp::FormalRegExpSymbol < SymbolType >, ext::set < regexp::FormalRegExpSymbol < SymbolType > > > & res );
73 };
74};
75
76template < class SymbolType >
77ext::set < UnboundedRegExpSymbol < SymbolType > > GlushkovFollow::follow ( const regexp::UnboundedRegExp < SymbolType > & re, const UnboundedRegExpSymbol < SymbolType > & symbol ) {
78 return re.getRegExp ( ).getStructure ( ).template accept < ext::set < regexp::UnboundedRegExpSymbol < SymbolType > >, GlushkovFollow::Unbounded < SymbolType > > ( symbol );
79}
80
81template < class SymbolType >
82ext::set < regexp::UnboundedRegExpSymbol < SymbolType > > GlushkovFollow::Unbounded < SymbolType >::visit ( const regexp::UnboundedRegExpAlternation < SymbolType > & node, const regexp::UnboundedRegExpSymbol < SymbolType > & symbolptr ) {
83 auto iter = std::find_if ( node.getElements ( ).begin ( ), node.getElements ( ).end ( ), [ & ] ( const UnboundedRegExpElement < SymbolType > & element ) {
84 return element.template accept < bool, GlushkovPos::Unbounded < SymbolType > > ( symbolptr );
85 } );
86
87 if ( iter == node.getElements ( ).end ( ) )
88 throw exception::CommonException ( "GlushkovFollow::Unbounded < SymbolType >::visit(Alt)" );
89
90 return iter->template accept < ext::set < regexp::UnboundedRegExpSymbol < SymbolType > >, GlushkovFollow::Unbounded < SymbolType > > ( symbolptr );
91}
92
93template < class SymbolType >
94ext::set < regexp::UnboundedRegExpSymbol < SymbolType > > GlushkovFollow::Unbounded < SymbolType >::visit ( const regexp::UnboundedRegExpConcatenation < SymbolType > & node, const regexp::UnboundedRegExpSymbol < SymbolType > & symbolptr ) {
95 ext::set < regexp::UnboundedRegExpSymbol < SymbolType > > ret;
96 ext::set < regexp::UnboundedRegExpSymbol < SymbolType > > tmp;
97 ext::set < regexp::UnboundedRegExpSymbol < SymbolType > > lastSet;
98
99 for ( auto e = node.getElements ( ).begin ( ); e != node.getElements ( ).end ( ); e++ ) {
100 if ( ! e->template accept < bool, GlushkovPos::Unbounded < SymbolType > > ( symbolptr ) )
101 continue;
102
103 tmp = e->template accept < ext::set < regexp::UnboundedRegExpSymbol < SymbolType > >, GlushkovFollow::Unbounded < SymbolType > > ( symbolptr );
104 ret.insert ( tmp.begin ( ), tmp.end ( ) );
105
106 lastSet = e->template accept < ext::set < regexp::UnboundedRegExpSymbol < SymbolType > >, GlushkovLast::Unbounded < SymbolType > > ( );
107
108 if ( lastSet.find ( symbolptr ) != lastSet.end ( ) )
109 for ( auto f = next ( e ); f != node.getElements ( ).end ( ); f++ ) {
110 tmp = f->template accept < ext::set < regexp::UnboundedRegExpSymbol < SymbolType > >, GlushkovFirst::Unbounded < SymbolType > > ( );
111 ret.insert ( tmp.begin ( ), tmp.end ( ) );
112
113 if ( ! regexp::properties::RegExpEpsilon::languageContainsEpsilon ( * f ) )
114 break;
115 }
116
117 }
118
119 return ret;
120}
121
122template < class SymbolType >
123ext::set < regexp::UnboundedRegExpSymbol < SymbolType > > GlushkovFollow::Unbounded < SymbolType >::visit ( const regexp::UnboundedRegExpIteration < SymbolType > & node, const regexp::UnboundedRegExpSymbol < SymbolType > & symbolptr ) {
124 ext::set < regexp::UnboundedRegExpSymbol < SymbolType > > ret = node.getElement ( ).template accept < ext::set < regexp::UnboundedRegExpSymbol < SymbolType > >, GlushkovFollow::Unbounded < SymbolType > > ( symbolptr );
125 ext::set < regexp::UnboundedRegExpSymbol < SymbolType > > lastSet = node.getElement ( ).template accept < ext::set < regexp::UnboundedRegExpSymbol < SymbolType > >, GlushkovLast::Unbounded < SymbolType > > ( );
126
127 if ( lastSet.find ( symbolptr ) != lastSet.end ( ) ) {
128 ext::set < regexp::UnboundedRegExpSymbol < SymbolType > > firstSet = node.getElement ( ).template accept < ext::set < regexp::UnboundedRegExpSymbol < SymbolType > >, GlushkovFirst::Unbounded < SymbolType > > ( );
129 ret.insert ( firstSet.begin ( ), firstSet.end ( ) );
130 }
131
132 return ret;
133}
134
135template < class SymbolType >
136ext::set < regexp::UnboundedRegExpSymbol < SymbolType > > GlushkovFollow::Unbounded < SymbolType >::visit ( const regexp::UnboundedRegExpSymbol < SymbolType > & /* node */, const regexp::UnboundedRegExpSymbol < SymbolType > & /* symbolptr */ ) {
137 return ext::set < regexp::UnboundedRegExpSymbol < SymbolType > > ( );
138}
139
140template < class SymbolType >
141ext::set < regexp::UnboundedRegExpSymbol < SymbolType > > GlushkovFollow::Unbounded < SymbolType >::visit ( const regexp::UnboundedRegExpEmpty < SymbolType > & /* node */, const regexp::UnboundedRegExpSymbol < SymbolType > & /* symbolptr */ ) {
142 return ext::set < regexp::UnboundedRegExpSymbol < SymbolType > > ( );
143}
144
145template < class SymbolType >
146ext::set < regexp::UnboundedRegExpSymbol < SymbolType > > GlushkovFollow::Unbounded < SymbolType >::visit ( const regexp::UnboundedRegExpEpsilon < SymbolType > & /* node */, const regexp::UnboundedRegExpSymbol < SymbolType > & /* symbolptr */ ) {
147 return ext::set < regexp::UnboundedRegExpSymbol < SymbolType > > ( );
148}
149
150template < class SymbolType >
151ext::map < regexp::FormalRegExpSymbol < SymbolType >, ext::set < regexp::FormalRegExpSymbol < SymbolType > > > GlushkovFollow::follow ( const regexp::FormalRegExp < SymbolType > & re ) {
152 ext::map < regexp::FormalRegExpSymbol < SymbolType >, ext::set < regexp::FormalRegExpSymbol < SymbolType > > > res;
153 ext::set < regexp::FormalRegExpSymbol < SymbolType > > currentFollow;
154 re.getRegExp ( ).getStructure ( ).template accept < void, GlushkovFollow::Formal < SymbolType > > ( currentFollow, res );
155 return res;
156}
157
158template < class SymbolType >
159void GlushkovFollow::Formal < SymbolType >::visit ( const regexp::FormalRegExpAlternation < SymbolType > & node, ext::set < regexp::FormalRegExpSymbol < SymbolType > > & currentFollow, ext::map < regexp::FormalRegExpSymbol < SymbolType >, ext::set < regexp::FormalRegExpSymbol < SymbolType > > > & res ) {
160 node.getLeftElement ( ).template accept < void, GlushkovFollow::Formal < SymbolType > > ( currentFollow, res );
161 node.getRightElement ( ).template accept < void, GlushkovFollow::Formal < SymbolType > > ( currentFollow, res );
162}
163
164template < class SymbolType >
165void GlushkovFollow::Formal < SymbolType >::visit ( const regexp::FormalRegExpConcatenation < SymbolType > & node, ext::set < regexp::FormalRegExpSymbol < SymbolType > > & currentFollow, ext::map < regexp::FormalRegExpSymbol < SymbolType >, ext::set < regexp::FormalRegExpSymbol < SymbolType > > > & res ) {
166 ext::set < regexp::FormalRegExpSymbol < SymbolType > > leftFollow = node.getRightElement ( ).template accept < ext::set < regexp::FormalRegExpSymbol < SymbolType > >, GlushkovFirst::Formal < SymbolType > > ( );
167 if ( regexp::properties::RegExpEpsilon::languageContainsEpsilon ( node.getRightElement ( ) ) )
168 leftFollow.insert ( currentFollow.begin ( ), currentFollow.end ( ) );
169 node.getLeftElement ( ).template accept < void, GlushkovFollow::Formal < SymbolType > > ( leftFollow, res );
170 node.getRightElement ( ).template accept < void, GlushkovFollow::Formal < SymbolType > > ( currentFollow, res );
171}
172
173template < class SymbolType >
174void GlushkovFollow::Formal < SymbolType >::visit ( const regexp::FormalRegExpIteration < SymbolType > & node, ext::set < regexp::FormalRegExpSymbol < SymbolType > > & currentFollow, ext::map < regexp::FormalRegExpSymbol < SymbolType >, ext::set < regexp::FormalRegExpSymbol < SymbolType > > > & res ) {
175 ext::set < regexp::FormalRegExpSymbol < SymbolType > > newFollow = node.getElement ( ).template accept < ext::set < regexp::FormalRegExpSymbol < SymbolType > >, GlushkovFirst::Formal < SymbolType > > ( );
176 newFollow.insert ( currentFollow.begin ( ), currentFollow.end ( ) );
177 node.getElement ( ).template accept < void, GlushkovFollow::Formal < SymbolType > > ( newFollow, res );
178}
179
180template < class SymbolType >
181void GlushkovFollow::Formal < SymbolType >::visit ( const regexp::FormalRegExpSymbol < SymbolType > & node, ext::set < regexp::FormalRegExpSymbol < SymbolType > > & currentFollow, ext::map < regexp::FormalRegExpSymbol < SymbolType >, ext::set < regexp::FormalRegExpSymbol < SymbolType > > > & res ) {
182 res.insert ( std::make_pair ( node, currentFollow ) );
183}
184
185template < class SymbolType >
186void GlushkovFollow::Formal < SymbolType >::visit ( const regexp::FormalRegExpEmpty < SymbolType > & /* node */, ext::set < regexp::FormalRegExpSymbol < SymbolType > > & /* currentFollow */, ext::map < regexp::FormalRegExpSymbol < SymbolType >, ext::set < regexp::FormalRegExpSymbol < SymbolType > > > & /* res */ ) {
187}
188
189template < class SymbolType >
190void GlushkovFollow::Formal < SymbolType >::visit ( const regexp::FormalRegExpEpsilon < SymbolType > & /* node */, ext::set < regexp::FormalRegExpSymbol < SymbolType > > & /* currentFollow */, ext::map < regexp::FormalRegExpSymbol < SymbolType >, ext::set < regexp::FormalRegExpSymbol < SymbolType > > > & /* res */ ) {
191}
192
193} /* namespace regexp */
194
exception::CommonException
Basic exception from which all other exceptions are derived.
Definition: CommonException.h:21
ext::map
Class extending the map class from the standard library. Original reason is to allow printing of the ...
Definition: map.hpp:48
ext::set
Definition: set.hpp:44
ext::set::begin
auto begin() &
Inherited behavior of begin for non-const instance.
Definition: set.hpp:99
ext::set::end
auto end() &
Inherited behavior of end for non-const instance.
Definition: set.hpp:129
regexp::FormalRegExpAlternation
Represents the alternation operator in the regular expression. The node must have exactly two childre...
Definition: FormalRegExpAlternation.h:44
regexp::FormalRegExpConcatenation
Represents the concatenation operator in the regular expression. The node must have exactly two child...
Definition: FormalRegExpConcatenation.h:44
regexp::FormalRegExpEmpty
Represents the empty expression in the regular expression. The node can't have any children.
Definition: FormalRegExpEmpty.h:41
regexp::FormalRegExpEpsilon
Represents the epsilon expression in the regular expression. The node can't have any children.
Definition: FormalRegExpEpsilon.h:41
regexp::FormalRegExpIteration
Represents the iteration operator in the regular expression. The node has exactly one child.
Definition: FormalRegExpIteration.h:44
regexp::FormalRegExpSymbol
Represents the symbol in the regular expression. The can't have any children.
Definition: FormalRegExpSymbol.h:42
regexp::FormalRegExp
Formal regular expression represents regular expression. It describes regular languages....
Definition: FormalRegExp.h:78
regexp::FormalRegExp::getRegExp
const FormalRegExpStructure< SymbolType > & getRegExp() const &
Definition: FormalRegExp.h:208
regexp::GlushkovFirst::Formal
Definition: GlushkovFirst.h:57
regexp::GlushkovFirst::Unbounded
Definition: GlushkovFirst.h:39
regexp::GlushkovFollow::Formal
Definition: GlushkovFollow.h:65
regexp::GlushkovFollow::Formal::visit
static void visit(const regexp::FormalRegExpAlternation< SymbolType > &node, ext::set< regexp::FormalRegExpSymbol< SymbolType > > &currentFollow, ext::map< regexp::FormalRegExpSymbol< SymbolType >, ext::set< regexp::FormalRegExpSymbol< SymbolType > > > &res)
Definition: GlushkovFollow.h:159
regexp::GlushkovFollow::Unbounded
Definition: GlushkovFollow.h:46
regexp::GlushkovFollow::Unbounded::visit
static ext::set< regexp::UnboundedRegExpSymbol< SymbolType > > visit(const regexp::UnboundedRegExpAlternation< SymbolType > &node, const regexp::UnboundedRegExpSymbol< SymbolType > &symbolptr)
Definition: GlushkovFollow.h:82
regexp::GlushkovFollow
Definition: GlushkovFollow.h:35
regexp::GlushkovFollow::follow
static ext::set< UnboundedRegExpSymbol< SymbolType > > follow(const regexp::UnboundedRegExp< SymbolType > &re, const UnboundedRegExpSymbol< SymbolType > &symbol)
Definition: GlushkovFollow.h:77
regexp::GlushkovLast::Unbounded
Definition: GlushkovLast.h:39
regexp::GlushkovPos::Unbounded
Definition: GlushkovPos.h:34
regexp::UnboundedRegExpAlternation
Represents the alternation operator in the regular expression. The node can have 0 to n children in l...
Definition: UnboundedRegExpAlternation.h:44
regexp::UnboundedRegExpConcatenation
Represents the concatenation operator in the regular expression. The node can have 0 to n children in...
Definition: UnboundedRegExpConcatenation.h:44
regexp::UnboundedRegExpElement
Definition: UnboundedRegExpElement.h:62
regexp::UnboundedRegExpEmpty
Represents the empty expression in the regular expression. The node can't have any children.
Definition: UnboundedRegExpEmpty.h:41
regexp::UnboundedRegExpEpsilon
Represents the epsilon expression in the regular expression. The node can't have any children.
Definition: UnboundedRegExpEpsilon.h:41
regexp::UnboundedRegExpIteration
Represents the iteration operator in the regular expression. The node has exactly one child.
Definition: UnboundedRegExpIteration.h:43
regexp::UnboundedRegExpSymbol
Represents the symbol in the regular expression. The can't have any children.
Definition: UnboundedRegExpSymbol.h:42
regexp::UnboundedRegExp
Unbounded regular expression represents regular expression. It describes regular languages....
Definition: UnboundedRegExp.h:80
regexp::UnboundedRegExp::getRegExp
const UnboundedRegExpStructure< SymbolType > & getRegExp() const &
Definition: UnboundedRegExp.h:210
regexp::properties::RegExpEpsilon::languageContainsEpsilon
static bool languageContainsEpsilon(const regexp::FormalRegExpElement< SymbolType > &regexp)
Definition: RegExpEpsilon.h:91
automaton::determinize::ret
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
automaton::simplify::res
return res
Definition: MinimizeByPartitioning.h:145
ext::make_pair
constexpr auto make_pair(T1 &&x, T2 &&y)
Definition: pair.hpp:79
node
Definition: Node.cpp:11
regexp
Definition: ToAutomaton.h:15
Generated on Mon Dec 27 2021 10:21:51 for Algorithms Library Toolkit by doxygen 1.9.2