Algorithms Library Toolkit
A toolkit for algorithms, especially for algorithms on formal languages
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