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
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