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
UnboundedRegExp.h
Go to the documentation of this file.
1
6#pragma once
7
8#include <ext/memory>
9#include <ext/utility>
10#include <ext/compare>
11
12#include <regexp/unbounded/UnboundedRegExpElements.h>
13#include <regexp/unbounded/UnboundedRegExpStructure.h>
14#include <regexp/unbounded/UnboundedRegExp.h>
15#include <core/stringApi.hpp>
16
17#include <regexp/RegExpFromStringLexer.h>
18
19namespace core {
20
21template<class SymbolType >
22struct stringApi < regexp::UnboundedRegExpStructure < SymbolType > > {
23 static regexp::UnboundedRegExpStructure < SymbolType > parse ( ext::istream & input );
24 static bool first ( ext::istream & input );
25 static void compose ( ext::ostream & output, const regexp::UnboundedRegExpStructure < SymbolType > & regexp );
26private:
27 static ext::ptr_value < regexp::UnboundedRegExpElement < SymbolType > > alternation(ext::istream & input);
28 static ext::ptr_value < regexp::UnboundedRegExpElement < SymbolType > > alternationCont(ext::istream & input, ext::ptr_value < regexp::UnboundedRegExpElement < SymbolType > > left);
29 static ext::ptr_value < regexp::UnboundedRegExpElement < SymbolType > > alternationContCont(ext::istream & input, regexp::UnboundedRegExpAlternation < SymbolType > res);
30
31 static ext::ptr_value < regexp::UnboundedRegExpElement < SymbolType > > concatenation(ext::istream & input);
32 static ext::ptr_value < regexp::UnboundedRegExpElement < SymbolType > > concatenationCont(ext::istream & input, ext::ptr_value < regexp::UnboundedRegExpElement < SymbolType > > left);
33 static ext::ptr_value < regexp::UnboundedRegExpElement < SymbolType > > concatenationContCont(ext::istream & input, regexp::UnboundedRegExpConcatenation < SymbolType > res);
34
35 static ext::ptr_value < regexp::UnboundedRegExpElement < SymbolType > > factor(ext::istream & input);
36 static ext::ptr_value < regexp::UnboundedRegExpElement < SymbolType > > star(ext::istream & input, regexp::UnboundedRegExpElement < SymbolType > && elem);
37
38 enum class Priority {
39 ALTERNATION,
40 CONCATENATION,
41 FACTOR
42 };
43
44 class Unbounded {
45 public:
46 static void visit( const regexp::UnboundedRegExpAlternation < SymbolType > & alternation, ext::tuple < Priority &, ext::ostream & > & output);
47 static void visit( const regexp::UnboundedRegExpConcatenation < SymbolType > & concatenation, ext::tuple < Priority &, ext::ostream & > & output);
48 static void visit( const regexp::UnboundedRegExpIteration < SymbolType > & iteration, ext::tuple < Priority &, ext::ostream & > & output);
49 static void visit( const regexp::UnboundedRegExpSymbol < SymbolType > & symbol, ext::tuple < Priority &, ext::ostream & > & output);
50 static void visit( const regexp::UnboundedRegExpEpsilon < SymbolType > & epsilon, ext::tuple < Priority &, ext::ostream & > & output);
51 static void visit( const regexp::UnboundedRegExpEmpty < SymbolType > & empty, ext::tuple < Priority &, ext::ostream & > & output);
52 };
53};
54
55template<class SymbolType >
56regexp::UnboundedRegExpStructure < SymbolType > stringApi < regexp::UnboundedRegExpStructure < SymbolType > >::parse ( ext::istream & input ) {
57 return regexp::UnboundedRegExpStructure < SymbolType > ( alternation ( input ) );
58}
59
60template<class SymbolType >
61ext::ptr_value < regexp::UnboundedRegExpElement < SymbolType > > stringApi < regexp::UnboundedRegExpStructure < SymbolType > >::alternation(ext::istream & input) {
62 return alternationCont(input, concatenation(input));
63}
64
65template<class SymbolType >
66ext::ptr_value < regexp::UnboundedRegExpElement < SymbolType > > stringApi < regexp::UnboundedRegExpStructure < SymbolType > >::alternationCont(ext::istream & input, ext::ptr_value < regexp::UnboundedRegExpElement < SymbolType > > left) {
67 regexp::RegExpFromStringLexer::Token token = regexp::RegExpFromStringLexer::next(input);
68 if(token.type == regexp::RegExpFromStringLexer::TokenType::PLUS) {
69 regexp::UnboundedRegExpAlternation < SymbolType > res;
70 res.appendElement(std::move(left));
71 res.appendElement(concatenation(input));
72
73 return alternationContCont(input, std::move ( res ) );
74 } else {
75 regexp::RegExpFromStringLexer::putback(input, token);
76 return left;
77 }
78}
79
80template<class SymbolType >
81ext::ptr_value < regexp::UnboundedRegExpElement < SymbolType > > stringApi < regexp::UnboundedRegExpStructure < SymbolType > >::alternationContCont(ext::istream & input, regexp::UnboundedRegExpAlternation < SymbolType > res) {
82 regexp::RegExpFromStringLexer::Token token = regexp::RegExpFromStringLexer::next(input);
83 if(token.type == regexp::RegExpFromStringLexer::TokenType::PLUS) {
84 res.appendElement(concatenation(input));
85
86 return alternationContCont(input, std::move ( res ) );
87 } else {
88 regexp::RegExpFromStringLexer::putback(input, token);
89 return ext::ptr_value < regexp::UnboundedRegExpElement < SymbolType > > ( std::move ( res ) );
90 }
91}
92
93template<class SymbolType >
94ext::ptr_value < regexp::UnboundedRegExpElement < SymbolType > > stringApi < regexp::UnboundedRegExpStructure < SymbolType > >::concatenation(ext::istream & input) {
95 return concatenationCont(input, factor(input));
96}
97
98template<class SymbolType >
99ext::ptr_value < regexp::UnboundedRegExpElement < SymbolType > > stringApi < regexp::UnboundedRegExpStructure < SymbolType > >::concatenationCont(ext::istream & input, ext::ptr_value < regexp::UnboundedRegExpElement < SymbolType > > left) {
100 regexp::RegExpFromStringLexer::Token token = regexp::RegExpFromStringLexer::next(input);
101 if(token.type == ext::any_of ( regexp::RegExpFromStringLexer::TokenType::ERROR, regexp::RegExpFromStringLexer::TokenType::LPAR, regexp::RegExpFromStringLexer::TokenType::EPS, regexp::RegExpFromStringLexer::TokenType::EMPTY ) ) {
102 regexp::RegExpFromStringLexer::putback(input, token);
103 regexp::UnboundedRegExpConcatenation < SymbolType > res;
104 res.appendElement(std::move(left));
105 res.appendElement(factor(input));
106
107 return concatenationContCont(input, std::move ( res ) );
108 } else {
109 regexp::RegExpFromStringLexer::putback(input, token);
110 return left;
111 }
112}
113
114template<class SymbolType >
115ext::ptr_value < regexp::UnboundedRegExpElement < SymbolType > > stringApi < regexp::UnboundedRegExpStructure < SymbolType > >::concatenationContCont(ext::istream & input, regexp::UnboundedRegExpConcatenation < SymbolType > res) {
116 regexp::RegExpFromStringLexer::Token token = regexp::RegExpFromStringLexer::next(input);
117 if(token.type == regexp::RegExpFromStringLexer::TokenType::ERROR || token.type == regexp::RegExpFromStringLexer::TokenType::LPAR || token.type == regexp::RegExpFromStringLexer::TokenType::EPS || token.type == regexp::RegExpFromStringLexer::TokenType::EMPTY) {
118 regexp::RegExpFromStringLexer::putback(input, token);
119 res.appendElement(factor(input));
120
121 return concatenationContCont(input, std::move ( res ) );
122 } else {
123 regexp::RegExpFromStringLexer::putback(input, token);
124 return ext::ptr_value < regexp::UnboundedRegExpElement < SymbolType > > ( std::move ( res ) );
125 }
126}
127
128template<class SymbolType >
129ext::ptr_value < regexp::UnboundedRegExpElement < SymbolType > > stringApi < regexp::UnboundedRegExpStructure < SymbolType > >::factor(ext::istream & input) {
130 regexp::RegExpFromStringLexer::Token token = regexp::RegExpFromStringLexer::next(input);
131 if(token.type == regexp::RegExpFromStringLexer::TokenType::LPAR) {
132 ext::ptr_value < regexp::UnboundedRegExpElement < SymbolType > > base = alternation(input);
133 token = regexp::RegExpFromStringLexer::next(input);
134 if(token.type != regexp::RegExpFromStringLexer::TokenType::RPAR) throw exception::CommonException("Expected RPAR");
135 return star(input, std::move ( base ) );
136 } else if(token.type == regexp::RegExpFromStringLexer::TokenType::EPS) {
137 return star(input, ext::ptr_value < regexp::UnboundedRegExpElement < SymbolType > > ( regexp::UnboundedRegExpEpsilon < SymbolType > ( ) ) );
138 } else if(token.type == regexp::RegExpFromStringLexer::TokenType::EMPTY) {
139 return star(input, ext::ptr_value < regexp::UnboundedRegExpElement < SymbolType > > ( regexp::UnboundedRegExpEmpty < SymbolType > ( ) ) );
140 } else if(token.type == regexp::RegExpFromStringLexer::TokenType::ERROR) {
141 regexp::RegExpFromStringLexer::putback(input, token);
142 regexp::UnboundedRegExpSymbol < SymbolType > res(core::stringApi<SymbolType>::parse(input));
143 return star(input, std::move ( res ) );
144 } else {
145 throw exception::CommonException("Unrecognised token at factor rule");
146 }
147}
148
149template<class SymbolType >
150ext::ptr_value < regexp::UnboundedRegExpElement < SymbolType > > stringApi < regexp::UnboundedRegExpStructure < SymbolType > >::star(ext::istream & input, regexp::UnboundedRegExpElement < SymbolType > && elem) {
151 regexp::RegExpFromStringLexer::Token token = regexp::RegExpFromStringLexer::next(input);
152 if(token.type == regexp::RegExpFromStringLexer::TokenType::STAR) {
153 regexp::UnboundedRegExpIteration < SymbolType > iter ( std::move ( elem ) );
154 return star(input, std::move ( iter ) );
155 } else {
156 regexp::RegExpFromStringLexer::putback(input, token);
157 return ext::ptr_value < regexp::UnboundedRegExpElement < SymbolType > > ( std::move ( elem ) );
158 }
159}
160
161template<class SymbolType >
162bool stringApi < regexp::UnboundedRegExpStructure < SymbolType > >::first ( ext::istream & ) {
163 return true;
164}
165
166template<class SymbolType >
167void stringApi < regexp::UnboundedRegExpStructure < SymbolType > >::compose ( ext::ostream & output, const regexp::UnboundedRegExpStructure < SymbolType > & regexp ) {
168 Priority tmp = Priority::ALTERNATION;
169 ext::tuple < Priority &, ext::ostream & > out = ext::tie ( tmp, output );
170 regexp.getStructure ( ).template accept < void, stringApi < regexp::UnboundedRegExpStructure < SymbolType > >::Unbounded > ( out );
171}
172
173template < class SymbolType >
174void stringApi < regexp::UnboundedRegExpStructure < SymbolType > >::Unbounded::visit( const regexp::UnboundedRegExpAlternation < SymbolType > & alternation, ext::tuple < Priority &, ext::ostream & > & output ) {
175 if ( alternation.getElements ( ).empty ( )) {
176 std::get < 1 > ( output ) << "#0";
177 } else if ( alternation.getElements ( ).size ( ) == 1) {
178 alternation.getElements ( ) [ 0 ].template accept < void, core::stringApi < regexp::UnboundedRegExpStructure < SymbolType > >::Unbounded > ( output );
179 } else {
180 Priority outerPriorityMinimum = std::get < 0 > ( output );
181 if ( outerPriorityMinimum == ext::any_of ( Priority::CONCATENATION, Priority::FACTOR ) )
182 std::get < 1 > ( output ) << '(';
183 bool first = true;
184 for ( const auto & element : alternation.getElements ( ) ) {
185 if ( first ) {
186 first = false;
187 } else {
188 std::get < 1 > ( output ) << '+';
189 }
190 std::get < 0 > ( output ) = Priority::ALTERNATION;
191 element.template accept < void, core::stringApi < regexp::UnboundedRegExpStructure < SymbolType > >::Unbounded > ( output );
192 }
193 if ( outerPriorityMinimum == ext::any_of ( Priority::CONCATENATION, Priority::FACTOR ) )
194 std::get < 1 > ( output ) << ')';
195 }
196}
197
198template < class SymbolType >
199void stringApi < regexp::UnboundedRegExpStructure < SymbolType > >::Unbounded::visit( const regexp::UnboundedRegExpConcatenation < SymbolType > & concatenation, ext::tuple < Priority &, ext::ostream & > & output ) {
200 Priority outerPriorityMinimum = std::get < 0 > ( output );
201 if ( concatenation.getElements ( ).empty ( )) {
202 std::get < 1 > ( output ) << "#E";
203 } else if ( concatenation.getElements ( ).size ( ) == 1 ) {
204 concatenation.getElements ( ) [ 0 ].template accept < void, core::stringApi < regexp::UnboundedRegExpStructure < SymbolType > >::Unbounded > ( output );
205 } else {
206 if ( outerPriorityMinimum == Priority::FACTOR )
207 std::get < 1 > ( output ) << '(';
208 bool first = true;
209 for ( const auto & element : concatenation.getElements ( ) ) {
210 if ( first ) {
211 first = false;
212 } else {
213 std::get < 1 > ( output ) << ' ';
214 }
215 std::get < 0 > ( output ) = Priority::CONCATENATION;
216 element.template accept < void, core::stringApi < regexp::UnboundedRegExpStructure < SymbolType > >::Unbounded > ( output );
217 }
218 if ( outerPriorityMinimum == Priority::FACTOR )
219 std::get < 1 > ( output ) << ')';
220 }
221}
222
223template < class SymbolType >
224void stringApi < regexp::UnboundedRegExpStructure < SymbolType > >::Unbounded::visit( const regexp::UnboundedRegExpIteration < SymbolType > & iteration, ext::tuple < Priority &, ext::ostream & > & output ) {
225 std::get < 0 > ( output ) = Priority::FACTOR;
226 iteration.getElement ( ).template accept < void, core::stringApi < regexp::UnboundedRegExpStructure < SymbolType > >::Unbounded > ( output );
227 std::get < 1 > ( output ) << "*";
228}
229
230template < class SymbolType >
231void stringApi < regexp::UnboundedRegExpStructure < SymbolType > >::Unbounded::visit( const regexp::UnboundedRegExpSymbol < SymbolType > & symbol, ext::tuple < Priority &, ext::ostream & > & output ) {
232 core::stringApi < SymbolType >::compose ( std::get < 1 > ( output ), symbol.getSymbol ( ) );
233}
234
235template < class SymbolType >
236void stringApi < regexp::UnboundedRegExpStructure < SymbolType > >::Unbounded::visit( const regexp::UnboundedRegExpEpsilon < SymbolType > &, ext::tuple < Priority &, ext::ostream & > & output ) {
237 std::get < 1 > ( output ) << "#E";
238}
239
240template < class SymbolType >
241void stringApi < regexp::UnboundedRegExpStructure < SymbolType > >::Unbounded::visit( const regexp::UnboundedRegExpEmpty < SymbolType > &, ext::tuple < Priority &, ext::ostream & > & output ) {
242 std::get < 1 > ( output ) << "#0";
243}
244
245template<class SymbolType >
246struct stringApi < regexp::UnboundedRegExp < SymbolType > > {
247 static regexp::UnboundedRegExp < SymbolType > parse ( ext::istream & input );
248 static bool first ( ext::istream & input );
249 static void compose ( ext::ostream & output, const regexp::UnboundedRegExp < SymbolType > & regexp );
250};
251
252template<class SymbolType >
253regexp::UnboundedRegExp < SymbolType > stringApi < regexp::UnboundedRegExp < SymbolType > >::parse ( ext::istream & input ) {
254 return regexp::UnboundedRegExp < SymbolType > ( core::stringApi < regexp::UnboundedRegExpStructure < SymbolType > >::parse ( input ) );
255}
256
257template<class SymbolType >
258bool stringApi < regexp::UnboundedRegExp < SymbolType > >::first ( ext::istream & input ) {
259 return core::stringApi < regexp::UnboundedRegExpStructure < SymbolType > >::first ( input );
260}
261
262template<class SymbolType >
263void stringApi < regexp::UnboundedRegExp < SymbolType > >::compose ( ext::ostream & output, const regexp::UnboundedRegExp < SymbolType > & regexp ) {
264 core::stringApi < regexp::UnboundedRegExpStructure < SymbolType > >::compose ( output, regexp.getRegExp ( ) );
265}
266
267} /* namespace core */
268
exception::CommonException
Basic exception from which all other exceptions are derived.
Definition: CommonException.h:21
ext::Lexer< RegExpFromStringLexer >::putback
static void putback(ext::istream &input, const Token &token)
Definition: lexer.hpp:61
ext::any_of
Definition: dry-comparisons.hpp:131
ext::istream
Definition: istream.h:32
ext::ostream
Definition: ostream.h:14
ext::ptr_value
Class representing wrapper of dynamically allocated object behaving like rvalue reference.
Definition: ptr_value.hpp:40
ext::tuple
Class extending the tuple class from the standard library. Original reason is to allow printing of th...
Definition: tuple.hpp:42
regexp::RegExpFromStringLexer::next
static Token next(ext::istream &input)
Definition: RegExpFromStringLexer.cpp:10
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::UnboundedRegExpAlternation::getElements
const ext::ptr_vector< UnboundedRegExpElement< SymbolType > > & getElements() const
Definition: UnboundedRegExpAlternation.h:185
regexp::UnboundedRegExpConcatenation
Represents the concatenation operator in the regular expression. The node can have 0 to n children in...
Definition: UnboundedRegExpConcatenation.h:44
regexp::UnboundedRegExpConcatenation::getElements
const ext::ptr_vector< UnboundedRegExpElement< SymbolType > > & getElements() const
Definition: UnboundedRegExpConcatenation.h:185
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::UnboundedRegExpIteration::getElement
const UnboundedRegExpElement< SymbolType > & getElement() const
Definition: UnboundedRegExpIteration.h:196
regexp::UnboundedRegExpStructure
Represents unbounded regular expression structure. Regular expression is stored as a tree of Unbounde...
Definition: UnboundedRegExpStructure.h:47
regexp::UnboundedRegExpSymbol
Represents the symbol in the regular expression. The can't have any children.
Definition: UnboundedRegExpSymbol.h:42
regexp::UnboundedRegExpSymbol::getSymbol
const SymbolType & getSymbol() const &
Definition: UnboundedRegExpSymbol.h:220
regexp::UnboundedRegExp
Unbounded regular expression represents regular expression. It describes regular languages....
Definition: UnboundedRegExp.h:80
automaton::simplify::res
return res
Definition: MinimizeByPartitioning.h:145
core
Definition: normalize.hpp:10
ext::tie
constexpr tuple< Elements &... > tie(Elements &... args) noexcept
Helper of extended tuple of references construction. The tuple is constructed to reffer to values in ...
Definition: tuple.hpp:218
ext::visit
constexpr auto visit(Visitor &&vis, Variants &&... vars)
Definition: variant.hpp:42
regexp
Definition: ToAutomaton.h:15
core::stringApi
Definition: stringApi.hpp:26
Generated on Mon Dec 27 2021 10:21:55 for Algorithms Library Toolkit by doxygen 1.9.2