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
CompactNFA.h
Go to the documentation of this file.
1
6/*
7 * This file is part of Algorithms library toolkit.
8 * Copyright (C) 2017 Jan Travnicek (jan.travnicek@fit.cvut.cz)
9
10 * Algorithms library toolkit is free software: you can redistribute it and/or modify
11 * it under the terms of the GNU General Public License as published by
12 * the Free Software Foundation, either version 3 of the License, or
13 * (at your option) any later version.
14
15 * Algorithms library toolkit is distributed in the hope that it will be useful,
16 * but WITHOUT ANY WARRANTY; without even the implied warranty of
17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 * GNU General Public License for more details.
19
20 * You should have received a copy of the GNU General Public License
21 * along with Algorithms library toolkit. If not, see <http://www.gnu.org/licenses/>.
22 */
23
24#pragma once
25
26#include <core/xmlApi.hpp>
28#include "../common/AutomatonFromXMLParser.h"
29#include "../common/AutomatonToXMLComposer.h"
30
31namespace core {
32
33template < class SymbolType, class StateType >
34struct xmlApi < automaton::CompactNFA < SymbolType, StateType > > {
42 static std::string xmlTagName() {
43 return "CompactNFA";
44 }
45
53 static bool first ( const ext::deque < sax::Token >::const_iterator & input ) {
55 }
56
65
73
81
88 static void composeTransitions ( ext::deque < sax::Token > & out, const automaton::CompactNFA < SymbolType, StateType > & automaton );
89};
90
91template < class SymbolType, class StateType >
94
95 ext::set < StateType > states = automaton::AutomatonFromXMLParser::parseStates < StateType > ( input );
96 ext::set < SymbolType > inputSymbols = automaton::AutomatonFromXMLParser::parseInputAlphabet < SymbolType > ( input );
97 StateType initialState = automaton::AutomatonFromXMLParser::parseInitialState < StateType > ( input );
98 ext::set < StateType > finalStates = automaton::AutomatonFromXMLParser::parseFinalStates < StateType > ( input );
99
100 automaton::CompactNFA < SymbolType, StateType > automaton ( std::move ( initialState ) );
101
102 automaton.setStates ( std::move ( states ) );
103 automaton.setInputAlphabet ( std::move ( inputSymbols ) );
104 automaton.setFinalStates ( std::move ( finalStates ) );
105
107
109 return automaton;
110}
111
112template < class SymbolType, class StateType >
115 StateType from = automaton::AutomatonFromXMLParser::parseTransitionFrom < StateType > ( input );
116 ext::vector < SymbolType > inputString = automaton::AutomatonFromXMLParser::parseTransitionInputSymbolMultiple < SymbolType > ( input );
117 StateType to = automaton::AutomatonFromXMLParser::parseTransitionTo < StateType > ( input );
119
120 automaton.addTransition ( std::move ( from ), std::move ( inputString ), std::move ( to ) );
121}
122
123template < class SymbolType, class StateType >
125 out.emplace_back ( xmlTagName ( ), sax::Token::TokenType::START_ELEMENT );
126
131 composeTransitions ( out, automaton );
132
133 out.emplace_back ( xmlTagName ( ), sax::Token::TokenType::END_ELEMENT );
134}
135
136template < class SymbolType, class StateType >
138 out.emplace_back ( "transitions", sax::Token::TokenType::START_ELEMENT );
139
140 for ( const auto & transition : automaton.getTransitions ( ) ) {
141 out.emplace_back ( "transition", sax::Token::TokenType::START_ELEMENT );
142
143 automaton::AutomatonToXMLComposer::composeTransitionFrom ( out, transition.first.first );
146
147 out.emplace_back ( "transition", sax::Token::TokenType::END_ELEMENT );
148 }
149
150 out.emplace_back ( "transitions", sax::Token::TokenType::END_ELEMENT );
151}
152
153} /* namespace core */
154
static void parseTransitions(ext::deque< sax::Token >::iterator &input, T &automaton)
Definition: AutomatonFromXMLParser.h:114
static void composeTransitionTo(ext::deque< sax::Token > &, const StateType &state)
Definition: AutomatonToXMLComposer.h:252
static void composeStates(ext::deque< sax::Token > &, const ext::set< StateType > &states)
Definition: AutomatonToXMLComposer.h:100
static void composeTransitionFrom(ext::deque< sax::Token > &, const StateType &state)
Definition: AutomatonToXMLComposer.h:259
static void composeInputAlphabet(ext::deque< sax::Token > &, const ext::set< SymbolType > &symbols)
Definition: AutomatonToXMLComposer.h:109
static void composeFinalStates(ext::deque< sax::Token > &, const ext::set< StateType > &states)
Definition: AutomatonToXMLComposer.h:170
static void composeTransitionInputSymbolMultiple(ext::deque< sax::Token > &, const ext::vector< SymbolType > &symbols)
Definition: AutomatonToXMLComposer.h:339
static void composeInitialState(ext::deque< sax::Token > &, const StateType &state)
Definition: AutomatonToXMLComposer.h:163
Compact nondeterministic finite automaton. Accepts regular languages. The automaton has a list of sym...
Definition: CompactNFA.h:78
Class extending the deque class from the standard library. Original reason is to allow printing of th...
Definition: deque.hpp:44
Definition: set.hpp:44
Class extending the vector class from the standard library. Original reason is to allow printing of t...
Definition: vector.hpp:45
static void popToken(ext::deque< Token >::iterator &input, Token::TokenType type, const std::string &data)
Definition: FromXMLParserHelper.cpp:39
static bool isToken(ext::deque< Token >::const_iterator input, Token::TokenType type, const std::string &data)
Definition: FromXMLParserHelper.cpp:29
typename T::StateType StateType
Definition: ToGrammarLeftRG.h:64
Definition: ToGrammar.h:31
Definition: normalize.hpp:10
static bool first(const ext::deque< sax::Token >::const_iterator &input)
Tests whether the token stream starts with this type.
Definition: CompactNFA.h:53
static std::string xmlTagName()
The XML tag name of class.
Definition: CompactNFA.h:42
Definition: xmlApi.hpp:27