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
15#include <core/stringApi.hpp>
16
18
19namespace core {
20
21template<class SymbolType >
22struct stringApi < regexp::UnboundedRegExpStructure < SymbolType > > {
24 static bool first ( ext::istream & input );
25 static void compose ( ext::ostream & output, const regexp::UnboundedRegExpStructure < SymbolType > & regexp );
26private:
30
34
37
38 enum class Priority {
39 ALTERNATION,
40 CONCATENATION,
41 FACTOR
42 };
43
44 class Unbounded {
45 public:
52 };
53};
54
55template<class SymbolType >
57 return regexp::UnboundedRegExpStructure < SymbolType > ( alternation ( input ) );
58}
59
60template<class SymbolType >
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);
70 res.appendElement(std::move(left));
71 res.appendElement(concatenation(input));
72
73 return alternationContCont(input, std::move ( res ) );
74 } else {
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);
84 res.appendElement(concatenation(input));
85
86 return alternationContCont(input, std::move ( res ) );
87 } else {
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);
104 res.appendElement(std::move(left));
105 res.appendElement(factor(input));
106
107 return concatenationContCont(input, std::move ( res ) );
108 } else {
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);
119 res.appendElement(factor(input));
120
121 return concatenationContCont(input, std::move ( res ) );
122 } else {
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);
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) {
138 } else if(token.type == regexp::RegExpFromStringLexer::TokenType::EMPTY) {
140 } else if(token.type == regexp::RegExpFromStringLexer::TokenType::ERROR) {
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);
153 regexp::UnboundedRegExpIteration < SymbolType > iter ( std::move ( elem ) );
154 return star(input, std::move ( iter ) );
155 } else {
158 }
159}
160
161template<class SymbolType >
163 return true;
164}
165
166template<class SymbolType >
168 Priority tmp = Priority::ALTERNATION;
170 regexp.getStructure ( ).template accept < void, stringApi < regexp::UnboundedRegExpStructure < SymbolType > >::Unbounded > ( out );
171}
172
173template < class SymbolType >
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 > > {
248 static bool first ( ext::istream & input );
249 static void compose ( ext::ostream & output, const regexp::UnboundedRegExp < SymbolType > & regexp );
250};
251
252template<class SymbolType >
255}
256
257template<class SymbolType >
260}
261
262template<class SymbolType >
265}
266
267} /* namespace core */
268
Basic exception from which all other exceptions are derived.
Definition: CommonException.h:21
static void putback(ext::istream &input, const Token &token)
Definition: lexer.hpp:61
Definition: dry-comparisons.hpp:131
Definition: istream.h:32
Definition: ostream.h:14
Class representing wrapper of dynamically allocated object behaving like rvalue reference.
Definition: ptr_value.hpp:40
Class extending the tuple class from the standard library. Original reason is to allow printing of th...
Definition: tuple.hpp:42
static Token next(ext::istream &input)
Definition: RegExpFromStringLexer.cpp:10
Represents the alternation operator in the regular expression. The node can have 0 to n children in l...
Definition: UnboundedRegExpAlternation.h:44
const ext::ptr_vector< UnboundedRegExpElement< SymbolType > > & getElements() const
Definition: UnboundedRegExpAlternation.h:185
Represents the concatenation operator in the regular expression. The node can have 0 to n children in...
Definition: UnboundedRegExpConcatenation.h:44
const ext::ptr_vector< UnboundedRegExpElement< SymbolType > > & getElements() const
Definition: UnboundedRegExpConcatenation.h:185
Definition: UnboundedRegExpElement.h:62
Represents the empty expression in the regular expression. The node can't have any children.
Definition: UnboundedRegExpEmpty.h:41
Represents the epsilon expression in the regular expression. The node can't have any children.
Definition: UnboundedRegExpEpsilon.h:41
Represents the iteration operator in the regular expression. The node has exactly one child.
Definition: UnboundedRegExpIteration.h:43
const UnboundedRegExpElement< SymbolType > & getElement() const
Definition: UnboundedRegExpIteration.h:196
Represents unbounded regular expression structure. Regular expression is stored as a tree of Unbounde...
Definition: UnboundedRegExpStructure.h:47
Represents the symbol in the regular expression. The can't have any children.
Definition: UnboundedRegExpSymbol.h:42
const SymbolType & getSymbol() const &
Definition: UnboundedRegExpSymbol.h:220
Unbounded regular expression represents regular expression. It describes regular languages....
Definition: UnboundedRegExp.h:80
return res
Definition: MinimizeByPartitioning.h:145
Definition: normalize.hpp:10
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
constexpr auto visit(Visitor &&vis, Variants &&... vars)
Definition: variant.hpp:42
Definition: ToAutomaton.h:15
Definition: stringApi.hpp:26