Algorithms Library Toolkit
A toolkit for algorithms, especially for algorithms on formal languages
GlushkovFirst.h
Go to the documentation of this file.
1
6#pragma once
7
8#include <alib/set>
9
10#include <regexp/unbounded/UnboundedRegExp.h>
11
12#include <regexp/unbounded/UnboundedRegExpAlternation.h>
13#include <regexp/unbounded/UnboundedRegExpConcatenation.h>
14#include <regexp/unbounded/UnboundedRegExpElement.h>
15#include <regexp/unbounded/UnboundedRegExpEmpty.h>
16#include <regexp/unbounded/UnboundedRegExpEpsilon.h>
17#include <regexp/unbounded/UnboundedRegExpIteration.h>
18#include <regexp/unbounded/UnboundedRegExpSymbol.h>
19
20#include <regexp/properties/RegExpEpsilon.h>
21
22namespace regexp {
23
29class GlushkovFirst {
30public:
35 template < class SymbolType >
36 static ext::set < UnboundedRegExpSymbol < SymbolType > > first ( const regexp::UnboundedRegExp < SymbolType > & re );
37
38 template < class SymbolType >
39 class Unbounded {
40 public:
41 static ext::set < regexp::UnboundedRegExpSymbol < SymbolType > > visit ( const regexp::UnboundedRegExpAlternation < SymbolType > & node );
42 static ext::set < regexp::UnboundedRegExpSymbol < SymbolType > > visit ( const regexp::UnboundedRegExpConcatenation < SymbolType > & node );
43 static ext::set < regexp::UnboundedRegExpSymbol < SymbolType > > visit ( const regexp::UnboundedRegExpIteration < SymbolType > & node );
44 static ext::set < regexp::UnboundedRegExpSymbol < SymbolType > > visit ( const regexp::UnboundedRegExpSymbol < SymbolType > & node );
45 static ext::set < regexp::UnboundedRegExpSymbol < SymbolType > > visit ( const regexp::UnboundedRegExpEmpty < SymbolType > & node );
46 static ext::set < regexp::UnboundedRegExpSymbol < SymbolType > > visit ( const regexp::UnboundedRegExpEpsilon < SymbolType > & node );
47 };
48
53 template < class SymbolType >
54 static ext::set < FormalRegExpSymbol < SymbolType > > first ( const regexp::FormalRegExp < SymbolType > & re );
55
56 template < class SymbolType >
57 class Formal {
58 public:
59 static ext::set < regexp::FormalRegExpSymbol < SymbolType > > visit ( const regexp::FormalRegExpAlternation < SymbolType > & node );
60 static ext::set < regexp::FormalRegExpSymbol < SymbolType > > visit ( const regexp::FormalRegExpConcatenation < SymbolType > & node );
61 static ext::set < regexp::FormalRegExpSymbol < SymbolType > > visit ( const regexp::FormalRegExpIteration < SymbolType > & node );
62 static ext::set < regexp::FormalRegExpSymbol < SymbolType > > visit ( const regexp::FormalRegExpSymbol < SymbolType > & node );
63 static ext::set < regexp::FormalRegExpSymbol < SymbolType > > visit ( const regexp::FormalRegExpEmpty < SymbolType > & node );
64 static ext::set < regexp::FormalRegExpSymbol < SymbolType > > visit ( const regexp::FormalRegExpEpsilon < SymbolType > & node );
65 };
66};
67
68template < class SymbolType >
69ext::set < UnboundedRegExpSymbol < SymbolType > > GlushkovFirst::first ( const regexp::UnboundedRegExp < SymbolType > & re ) {
70 return re.getRegExp ( ).getStructure ( ).template accept < ext::set < regexp::UnboundedRegExpSymbol < SymbolType > >, GlushkovFirst::Unbounded < SymbolType > > ( );
71}
72
73template < class SymbolType >
74ext::set < regexp::UnboundedRegExpSymbol < SymbolType > > GlushkovFirst::Unbounded < SymbolType >::visit ( const regexp::UnboundedRegExpAlternation < SymbolType > & node ) {
75 ext::set < regexp::UnboundedRegExpSymbol < SymbolType > > ret;
76 ext::set < regexp::UnboundedRegExpSymbol < SymbolType > > tmp;
77
78 for ( const UnboundedRegExpElement < SymbolType > & element : node.getElements ( ) ) {
79 tmp = element.template accept < ext::set < regexp::UnboundedRegExpSymbol < SymbolType > >, GlushkovFirst::Unbounded < SymbolType > > ( );
80 ret.insert ( tmp.begin ( ), tmp.end ( ) );
81 }
82
83 return ret;
84}
85
86template < class SymbolType >
87ext::set < regexp::UnboundedRegExpSymbol < SymbolType > > GlushkovFirst::Unbounded < SymbolType >::visit ( const regexp::UnboundedRegExpConcatenation < SymbolType > & node ) {
88 ext::set < regexp::UnboundedRegExpSymbol < SymbolType > > ret;
89 ext::set < regexp::UnboundedRegExpSymbol < SymbolType > > tmp;
90
91 for ( const UnboundedRegExpElement < SymbolType > & element : node.getElements ( ) ) {
92 tmp = element.template accept < ext::set < regexp::UnboundedRegExpSymbol < SymbolType > >, GlushkovFirst::Unbounded < SymbolType > > ( );
93 ret.insert ( tmp.begin ( ), tmp.end ( ) );
94
95 if ( ! regexp::properties::RegExpEpsilon::languageContainsEpsilon ( element ) ) // If regexp of this subtree can match epsilon, then we need to add next subtree
96 break;
97 }
98
99 return ret;
100}
101
102template < class SymbolType >
103ext::set < regexp::UnboundedRegExpSymbol < SymbolType > > GlushkovFirst::Unbounded < SymbolType >::visit ( const regexp::UnboundedRegExpIteration < SymbolType > & node ) {
104 return node.getElement ( ).template accept < ext::set < regexp::UnboundedRegExpSymbol < SymbolType > >, GlushkovFirst::Unbounded < SymbolType > > ( );
105}
106
107template < class SymbolType >
108ext::set < regexp::UnboundedRegExpSymbol < SymbolType > > GlushkovFirst::Unbounded < SymbolType >::visit ( const regexp::UnboundedRegExpSymbol < SymbolType > & node ) {
109 return ext::set < regexp::UnboundedRegExpSymbol < SymbolType > > { node };
110}
111
112template < class SymbolType >
113ext::set < regexp::UnboundedRegExpSymbol < SymbolType > > GlushkovFirst::Unbounded < SymbolType >::visit ( const regexp::UnboundedRegExpEpsilon < SymbolType > & /* node */ ) {
114 return ext::set < regexp::UnboundedRegExpSymbol < SymbolType > > ( );
115}
116
117template < class SymbolType >
118ext::set < regexp::UnboundedRegExpSymbol < SymbolType > > GlushkovFirst::Unbounded < SymbolType >::visit ( const regexp::UnboundedRegExpEmpty < SymbolType > & /* node */ ) {
119 return ext::set < regexp::UnboundedRegExpSymbol < SymbolType > > ( );
120}
121
122template < class SymbolType >
123ext::set < FormalRegExpSymbol < SymbolType > > GlushkovFirst::first ( const regexp::FormalRegExp < SymbolType > & re ) {
124 return re.getRegExp ( ).getStructure ( ).template accept < ext::set < regexp::FormalRegExpSymbol < SymbolType > >, GlushkovFirst::Formal < SymbolType > > ( );
125}
126
127template < class SymbolType >
128ext::set < regexp::FormalRegExpSymbol < SymbolType > > GlushkovFirst::Formal < SymbolType >::visit ( const regexp::FormalRegExpAlternation < SymbolType > & node ) {
129 ext::set < regexp::FormalRegExpSymbol < SymbolType > > left = node.getLeftElement ( ).template accept < ext::set < regexp::FormalRegExpSymbol < SymbolType > >, GlushkovFirst::Formal < SymbolType > > ( );
130 ext::set < regexp::FormalRegExpSymbol < SymbolType > > right = node.getRightElement ( ).template accept < ext::set < regexp::FormalRegExpSymbol < SymbolType > >, GlushkovFirst::Formal < SymbolType > > ( );
131 left.insert ( right.begin ( ), right.end ( ) );
132 return left;
133}
134
135template < class SymbolType >
136ext::set < regexp::FormalRegExpSymbol < SymbolType > > GlushkovFirst::Formal < SymbolType >::visit ( const regexp::FormalRegExpConcatenation < SymbolType > & node ) {
137 ext::set < regexp::FormalRegExpSymbol < SymbolType > > left = node.getLeftElement ( ).template accept < ext::set < regexp::FormalRegExpSymbol < SymbolType > >, GlushkovFirst::Formal < SymbolType > > ( );
138 if ( ! regexp::properties::RegExpEpsilon::languageContainsEpsilon ( node.getLeftElement ( ) ) ) // If regexp of this subtree can match epsilon, then we need to add next subtree
139 return left;
140 ext::set < regexp::FormalRegExpSymbol < SymbolType > > right = node.getRightElement ( ).template accept < ext::set < regexp::FormalRegExpSymbol < SymbolType > >, GlushkovFirst::Formal < SymbolType > > ( );
141 left.insert ( right.begin ( ), right.end ( ) );
142 return left;
143}
144
145template < class SymbolType >
146ext::set < regexp::FormalRegExpSymbol < SymbolType > > GlushkovFirst::Formal < SymbolType >::visit ( const regexp::FormalRegExpIteration < SymbolType > & node ) {
147 return node.getElement ( ).template accept < ext::set < regexp::FormalRegExpSymbol < SymbolType > >, GlushkovFirst::Formal < SymbolType > > ( );
148}
149
150template < class SymbolType >
151ext::set < regexp::FormalRegExpSymbol < SymbolType > > GlushkovFirst::Formal < SymbolType >::visit ( const regexp::FormalRegExpSymbol < SymbolType > & node ) {
152 return ext::set < regexp::FormalRegExpSymbol < SymbolType > > { node };
153}
154
155template < class SymbolType >
156ext::set < regexp::FormalRegExpSymbol < SymbolType > > GlushkovFirst::Formal < SymbolType >::visit ( const regexp::FormalRegExpEpsilon < SymbolType > & /* node */ ) {
157 return ext::set < regexp::FormalRegExpSymbol < SymbolType > > ( );
158}
159
160template < class SymbolType >
161ext::set < regexp::FormalRegExpSymbol < SymbolType > > GlushkovFirst::Formal < SymbolType >::visit ( const regexp::FormalRegExpEmpty < SymbolType > & /* node */ ) {
162 return ext::set < regexp::FormalRegExpSymbol < SymbolType > > ( );
163}
164
165} /* namespace regexp */
166
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::Formal::visit
static ext::set< regexp::FormalRegExpSymbol< SymbolType > > visit(const regexp::FormalRegExpAlternation< SymbolType > &node)
Definition: GlushkovFirst.h:128
regexp::GlushkovFirst::Unbounded
Definition: GlushkovFirst.h:39
regexp::GlushkovFirst::Unbounded::visit
static ext::set< regexp::UnboundedRegExpSymbol< SymbolType > > visit(const regexp::UnboundedRegExpAlternation< SymbolType > &node)
Definition: GlushkovFirst.h:74
regexp::GlushkovFirst
Definition: GlushkovFirst.h:29
regexp::GlushkovFirst::first
static ext::set< UnboundedRegExpSymbol< SymbolType > > first(const regexp::UnboundedRegExp< SymbolType > &re)
Definition: GlushkovFirst.h:69
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
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