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
ToAutomatonGlushkov.h
Go to the documentation of this file.
1
6#pragma once
7
8#include <alib/pair>
9
12
13#include <automaton/FSM/NFA.h>
14
15#include <global/GlobalData.h>
16
17#include "../glushkov/GlushkovFirst.h"
18#include "../glushkov/GlushkovFollow.h"
19#include "../glushkov/GlushkovIndexate.h"
20#include "../glushkov/GlushkovLast.h"
21
24
26
27namespace regexp {
28
29namespace convert {
30
36public:
46 template < class SymbolType >
48
52 template < class SymbolType >
54
55};
56
57template < class SymbolType >
59 ext::pair < SymbolType, unsigned > q0 ( label::InitialStateLabel::instance < SymbolType > ( ), 0 );
61
62 // step 1
63 automaton.setInputAlphabet ( regexp.getAlphabet ( ) );
64
66
67 // steps 2, 3, 4
70
71 // \e in q0 check is in step 7
72
73 // step 5
74 for ( const ext::pair < SymbolType, unsigned > & symbol : indexedRegExp.getAlphabet ( ) )
75 automaton.addState ( symbol );
76
77 // step 6
79 automaton.addTransition ( q0, symbol.getSymbol ( ).first, symbol.getSymbol ( ) );
80
81 for ( const ext::pair < SymbolType, unsigned > & x : indexedRegExp.getAlphabet ( ) )
82 for ( const auto & f : regexp::GlushkovFollow::follow ( indexedRegExp, UnboundedRegExpSymbol < ext::pair < SymbolType, unsigned > > ( x ) ) ) {
84 const ext::pair < SymbolType, unsigned > & q = f.getSymbol ( );
85
86 automaton.addTransition ( p, q.first, q );
87 }
88
89 // step 7
90
92 automaton.addFinalState ( symbol.getSymbol ( ) );
93
95 automaton.addFinalState ( q0 );
96
98 common::Streams::log << "First:" << first << std::endl;
99 common::Streams::log << "Last: " << last << std::endl;
100
102 common::Streams::log << " q0 because #E in L(RE)" << std::endl;
103
104 for ( const ext::pair < SymbolType, unsigned > & x : indexedRegExp.getAlphabet ( ) )
105 common::Streams::log << "Follow(" << x << ") = " << regexp::GlushkovFollow::follow ( indexedRegExp, UnboundedRegExpSymbol < ext::pair < SymbolType, unsigned > > ( x ) ) << std::endl;
106 }
107
108 return automaton;
109}
110
111template < class SymbolType >
113 ext::pair < SymbolType, unsigned > q0 ( label::InitialStateLabel::instance < SymbolType > ( ), 0 );
115
116 // step 1
117 automaton.setInputAlphabet ( regexp.getAlphabet ( ) );
118
120
121 // steps 2, 3, 4
124
125 // \e in q0 check is in step 7
126
127 // step 5
128 for ( const ext::pair < SymbolType, unsigned > & symbol : indexedRegExp.getAlphabet ( ) )
129 automaton.addState ( symbol );
130
131 // step 6
132 for ( const regexp::FormalRegExpSymbol < ext::pair < SymbolType, unsigned > > & symbol : first )
133 automaton.addTransition ( q0, symbol.getSymbol ( ).first, symbol.getSymbol ( ) );
134
137 for ( const auto & f : entry.second ) {
138 const ext::pair < SymbolType, unsigned > & p = entry.first.getSymbol ( );
139 const ext::pair < SymbolType, unsigned > & q = f.getSymbol ( );
140
141 automaton.addTransition ( p, q.first, q );
142 }
143
144 // step 7
145
146 for ( const regexp::FormalRegExpSymbol < ext::pair < SymbolType, unsigned > > & symbol : last )
147 automaton.addFinalState ( symbol.getSymbol ( ) );
148
150 automaton.addFinalState ( q0 );
151
153 common::Streams::log << "First:" << first << std::endl;
154 common::Streams::log << "Last: " << last << std::endl;
155
157 common::Streams::log << " q0 because #E in L(RE)" << std::endl;
158
159 common::Streams::log << "Follow: " << regexp::GlushkovFollow::follow ( indexedRegExp ) << std::endl;
160 }
161
162 return automaton;
163}
164
165} /* namespace convert */
166
167} /* namespace regexp */
168
Nondeterministic finite automaton. Accepts regular languages.
Definition: NFA.h:66
static bool verbose
Verbose flag. Some algorithms print additional runtime information about internal datastructures or t...
Definition: GlobalData.h:24
static ext::reference_wrapper< ext::ostream > log
Standard loging stream. Mapped to descriptor 4.
Definition: GlobalData.h:78
Class extending the map class from the standard library. Original reason is to allow printing of the ...
Definition: map.hpp:48
Class extending the pair class from the standard library. Original reason is to allow printing of the...
Definition: pair.hpp:43
Definition: set.hpp:44
Represents the symbol in the regular expression. The can't have any children.
Definition: FormalRegExpSymbol.h:42
Formal regular expression represents regular expression. It describes regular languages....
Definition: FormalRegExp.h:78
const ext::set< SymbolType > & getAlphabet() const &
Definition: FormalRegExp.h:120
static ext::set< UnboundedRegExpSymbol< SymbolType > > first(const regexp::UnboundedRegExp< SymbolType > &re)
Definition: GlushkovFirst.h:69
static ext::set< UnboundedRegExpSymbol< SymbolType > > follow(const regexp::UnboundedRegExp< SymbolType > &re, const UnboundedRegExpSymbol< SymbolType > &symbol)
Definition: GlushkovFollow.h:77
static regexp::UnboundedRegExp< ext::pair< SymbolType, unsigned > > index(const regexp::UnboundedRegExp< SymbolType > &re)
static ext::set< UnboundedRegExpSymbol< SymbolType > > last(const regexp::UnboundedRegExp< SymbolType > &re)
Definition: GlushkovLast.h:69
Represents the symbol in the regular expression. The can't have any children.
Definition: UnboundedRegExpSymbol.h:42
Unbounded regular expression represents regular expression. It describes regular languages....
Definition: UnboundedRegExp.h:80
const ext::set< SymbolType > & getAlphabet() const &
Definition: UnboundedRegExp.h:122
Definition: ToAutomatonGlushkov.h:35
static automaton::NFA< SymbolType, ext::pair< SymbolType, unsigned > > convert(const regexp::UnboundedRegExp< SymbolType > &regexp)
Definition: ToAutomatonGlushkov.h:58
static bool languageContainsEpsilon(const regexp::FormalRegExpElement< SymbolType > &regexp)
Definition: RegExpEpsilon.h:91
q
Definition: SingleInitialStateEpsilonTransition.h:85
StateType q0
Definition: SingleInitialState.h:96
Definition: ToGrammar.h:31
Definition: converterCommon.hpp:8
Definition: ToAutomaton.h:15