AutomatonFromXMLParser.cpp

/*
 * AutomatonFromXMLParser.cpp
 *
 *  Created on: Oct 12, 2013
 *      Author: Jan Travnicek
 */

#include "AutomatonFromXMLParser.h"

#include "../sax/ParserException.h"
#include "../alphabet/BlankSymbol.h"
#include "../label/Label.h"

#include "../Api.hpp"

namespace automaton {

Automaton AutomatonFromXMLParser::parseAutomaton(std::list<sax::Token> &input) const {
	return parseAutomaton(input, std::set<FEATURES>({FEATURES::AUTOMATON, FEATURES::EPSILON_NFA, FEATURES::NFA, FEATURES::DFA, FEATURES::COMPACT_NFA, FEATURES::EXTENDED_NFA, FEATURES::DPDA, FEATURES::SINGLE_POP_DPDA, FEATURES::INPUT_DRIVEN_NPDA, FEATURES::VISIBLY_PUSHDOWN_NPDA, FEATURES::REAL_TIME_HEIGHT_DETERMINISTIC_NPDA, FEATURES::NPDA, FEATURES::SINGLE_POP_NPDA, FEATURES::ONE_TAPE_DTM}));
}

Automaton AutomatonFromXMLParser::parseAutomaton(std::list<sax::Token>& input, const std::set<FEATURES>& features) const {
	if(isToken(input, sax::Token::TokenType::START_ELEMENT, "automaton")) {
		if(!features.count(FEATURES::AUTOMATON)) throw exception::AlibException();
		return Automaton(parseUnknownAutomaton(input));
	} else if(isToken(input, sax::Token::TokenType::START_ELEMENT, "EpsilonNFA")) {
		if(!features.count(FEATURES::EPSILON_NFA)) throw exception::AlibException();
		return Automaton(parseEpsilonNFA(input));
	} else if(isToken(input, sax::Token::TokenType::START_ELEMENT, "NFA")) {
		if(!features.count(FEATURES::NFA)) throw exception::AlibException();
		return Automaton(parseNFA(input));
	} else if(isToken(input, sax::Token::TokenType::START_ELEMENT, "DFA")) {
		if(!features.count(FEATURES::DFA)) throw exception::AlibException();
		return Automaton(parseDFA(input));
	} else if(isToken(input, sax::Token::TokenType::START_ELEMENT, "CompactNFA")) {
		if(!features.count(FEATURES::COMPACT_NFA)) throw exception::AlibException();
		return Automaton(parseCompactNFA(input));
	} else if(isToken(input, sax::Token::TokenType::START_ELEMENT, "ExtendedNFA")) {
		if(!features.count(FEATURES::EXTENDED_NFA)) throw exception::AlibException();
		return Automaton(parseExtendedNFA(input));
	} else if(isToken(input, sax::Token::TokenType::START_ELEMENT, "DPDA")) {
		if(!features.count(FEATURES::DPDA)) throw exception::AlibException();
		return Automaton(parseDPDA(input));
	} else if(isToken(input, sax::Token::TokenType::START_ELEMENT, "SinglePopDPDA")) {
		if(!features.count(FEATURES::SINGLE_POP_DPDA)) throw exception::AlibException();
		return Automaton(parseSinglePopDPDA(input));
	} else if(isToken(input, sax::Token::TokenType::START_ELEMENT, "InputDrivenNPDA")) {
		if(!features.count(FEATURES::INPUT_DRIVEN_NPDA)) throw exception::AlibException();
		return Automaton(parseInputDrivenNPDA(input));
	} else if(isToken(input, sax::Token::TokenType::START_ELEMENT, "VisiblyPushdownNPDA")) {
		if(!features.count(FEATURES::VISIBLY_PUSHDOWN_NPDA)) throw exception::AlibException();
		return Automaton(parseVisiblyPushdownNPDA(input));
	} else if(isToken(input, sax::Token::TokenType::START_ELEMENT, "RealTimeHeightDeterministicNPDA")) {
		if(!features.count(FEATURES::REAL_TIME_HEIGHT_DETERMINISTIC_NPDA)) throw exception::AlibException();
		return Automaton(parseRealTimeHeightDeterministicNPDA(input));
	} else if(isToken(input, sax::Token::TokenType::START_ELEMENT, "NPDA")) {
		if(!features.count(FEATURES::NPDA)) throw exception::AlibException();
		return Automaton(parseNPDA(input));
	} else if(isToken(input, sax::Token::TokenType::START_ELEMENT, "SinglePopNPDA")) {
		if(!features.count(FEATURES::SINGLE_POP_NPDA)) throw exception::AlibException();
		return Automaton(parseSinglePopNPDA(input));
	} else if(isToken(input, sax::Token::TokenType::START_ELEMENT, "OneTapeDTM")) {
		if(!features.count(FEATURES::ONE_TAPE_DTM)) throw exception::AlibException();
		return Automaton(parseOneTapeDTM(input));
	} else
		throw sax::ParserException(sax::Token("Automaton / EpsilonNFA / NFA / DFA / CompactNFA / ExtendedNFA / DPDA / SinglePopDPDA / InputDrivenNPDA / VisiblyPushdownNPDA / RealTimeHeightDeterministicNPDA / NPDA / SinglePopNPDA / OneTapeDTM", sax::Token::TokenType::START_ELEMENT), input.front());
}

bool AutomatonFromXMLParser::first(std::list<sax::Token>& input) const {
	if(isToken(input, sax::Token::TokenType::START_ELEMENT, "automaton") || isToken(input, sax::Token::TokenType::START_ELEMENT, "EpsilonNFA") || isToken(input, sax::Token::TokenType::START_ELEMENT, "NFA") || isToken(input, sax::Token::TokenType::START_ELEMENT, "DFA") || isToken(input, sax::Token::TokenType::START_ELEMENT, "CompactNFA") || isToken(input, sax::Token::TokenType::START_ELEMENT, "ExtendedNFA") || isToken(input, sax::Token::TokenType::START_ELEMENT, "DPDA") || isToken(input, sax::Token::TokenType::START_ELEMENT, "SinglePopDPDA")  || isToken(input, sax::Token::TokenType::START_ELEMENT, "InputDrivenNPDA") || isToken(input, sax::Token::TokenType::START_ELEMENT, "VisiblyPushdownNPDA") || isToken(input, sax::Token::TokenType::START_ELEMENT, "RealTimeHeightDeterministicNPDA") || isToken(input, sax::Token::TokenType::START_ELEMENT, "NPDA") || isToken(input, sax::Token::TokenType::START_ELEMENT, "SinglePopNPDA") || isToken(input, sax::Token::TokenType::START_ELEMENT, "OneTapeDTM")) {
		return true;
	} else {
		return false;
	}
}

template<>
void AutomatonFromXMLParser::parseTransitions(std::list<sax::Token> &input, RealTimeHeightDeterministicNPDA& automaton) const {
	popToken(input, sax::Token::TokenType::START_ELEMENT, "transitions");
	while (isTokenType(input, sax::Token::TokenType::START_ELEMENT)) {
		parseTransition(input, automaton);
	}
	popToken(input, sax::Token::TokenType::END_ELEMENT, "transitions");
}

template<>
void AutomatonFromXMLParser::parseTransitions(std::list<sax::Token> &input, VisiblyPushdownNPDA& automaton) const {
	popToken(input, sax::Token::TokenType::START_ELEMENT, "transitions");
	while (isTokenType(input, sax::Token::TokenType::START_ELEMENT)) {
		parseTransition(input, automaton);
	}
	popToken(input, sax::Token::TokenType::END_ELEMENT, "transitions");
}

template<class T>
void AutomatonFromXMLParser::parseTransitions(std::list<sax::Token> &input, T& automaton) const {
	popToken(input, sax::Token::TokenType::START_ELEMENT, "transitions");
	while (isTokenType(input, sax::Token::TokenType::START_ELEMENT)) {
		popToken(input, sax::Token::TokenType::START_ELEMENT, "transition");
		parseTransition(input, automaton);
		popToken(input, sax::Token::TokenType::END_ELEMENT, "transition");
	}
	popToken(input, sax::Token::TokenType::END_ELEMENT, "transitions");
}

UnknownAutomaton AutomatonFromXMLParser::parseUnknownAutomaton(std::list<sax::Token> &input) const {
	UnknownAutomaton automaton;

	popToken(input, sax::Token::TokenType::START_ELEMENT, "automaton");

	while (isTokenType(input, sax::Token::TokenType::START_ELEMENT)) {
		if (isToken(input, sax::Token::TokenType::START_ELEMENT, "states")) {
			automaton.setStates(parseStates(input));
		} else if (isToken(input, sax::Token::TokenType::START_ELEMENT, "inputAlphabet")) {
			automaton.setInputSymbols(parseInputAlphabet(input));
		} else if (isToken(input, sax::Token::TokenType::START_ELEMENT, "initialStates")) {
			automaton.setInitialStates(parseInitialStates(input));
		} else if (isToken(input, sax::Token::TokenType::START_ELEMENT, "finalStates")) {
			automaton.setFinalStates(parseFinalStates(input));
		} else if (isToken(input, sax::Token::TokenType::START_ELEMENT, "stackAlphabet")) {
			automaton.setStackSymbols(parseStackAlphabet(input));
		} else if (isToken(input, sax::Token::TokenType::START_ELEMENT, "initialStackSymbols")) {
			automaton.setInitialSymbols(parseInitialStackSymbols(input));
		} else if (isToken(input, sax::Token::TokenType::START_ELEMENT, "tapeAlphabet")) {
			automaton.setTapeSymbols(parseTapeAlphabet(input));
		} else if (isToken(input, sax::Token::TokenType::START_ELEMENT, "blankSymbol")) {
			automaton.setBlankSymbol(parseBlankSymbol(input));
		} else if (isToken(input, sax::Token::TokenType::START_ELEMENT, "transitions")) {
			parseTransitions(input, automaton);
		} else {
			throw sax::ParserException(sax::Token("automaton", sax::Token::TokenType::END_ELEMENT), input.front());
		}
	}

	popToken(input, sax::Token::TokenType::END_ELEMENT, "automaton");
	return automaton;
}

DFA AutomatonFromXMLParser::parseDFA(std::list<sax::Token>& input) const {
	popToken(input, sax::Token::TokenType::START_ELEMENT, "DFA");

	std::set<State> states = parseStates(input);
	std::set<alphabet::Symbol> inputSymbols = parseInputAlphabet(input);
	State initialState = parseInitialState(input);
	std::set<State> finalStates = parseFinalStates(input);

	DFA automaton(initialState);
	automaton.setStates(states);
	automaton.setInputSymbols(inputSymbols);
	automaton.setFinalStates(finalStates);

	parseTransitions<DFA>(input, automaton);

	popToken(input, sax::Token::TokenType::END_ELEMENT, "DFA");
	return automaton;
}

NFA AutomatonFromXMLParser::parseNFA(std::list<sax::Token>& input) const {
	popToken(input, sax::Token::TokenType::START_ELEMENT, "NFA");

	std::set<State> states = parseStates(input);
	std::set<alphabet::Symbol> inputSymbols = parseInputAlphabet(input);
	std::set<State> initialStates = parseInitialStates(input);
	std::set<State> finalStates = parseFinalStates(input);

	NFA automaton;
	automaton.setStates(states);
	automaton.setInputSymbols(inputSymbols);
	automaton.setInitialStates(initialStates);
	automaton.setFinalStates(finalStates);

	parseTransitions<NFA>(input, automaton);

	popToken(input, sax::Token::TokenType::END_ELEMENT, "NFA");
	return automaton;
}

EpsilonNFA AutomatonFromXMLParser::parseEpsilonNFA(std::list<sax::Token>& input) const {
	popToken(input, sax::Token::TokenType::START_ELEMENT, "EpsilonNFA");

	std::set<State> states = parseStates(input);
	std::set<alphabet::Symbol> inputSymbols = parseInputAlphabet(input);
	std::set<State> initialStates = parseInitialStates(input);
	std::set<State> finalStates = parseFinalStates(input);

	EpsilonNFA automaton;
	automaton.setStates(states);
	automaton.setInputSymbols(inputSymbols);
	automaton.setInitialStates(initialStates);
	automaton.setFinalStates(finalStates);

	parseTransitions<EpsilonNFA>(input, automaton);

	popToken(input, sax::Token::TokenType::END_ELEMENT, "EpsilonNFA");
	return automaton;
}

CompactNFA AutomatonFromXMLParser::parseCompactNFA(std::list<sax::Token>& input) const {
	popToken(input, sax::Token::TokenType::START_ELEMENT, "CompactNFA");
	
	std::set<State> states = parseStates(input);
	std::set<alphabet::Symbol> inputSymbols = parseInputAlphabet(input);
	std::set<State> initialStates = parseInitialStates(input);
	std::set<State> finalStates = parseFinalStates(input);

	CompactNFA automaton;
	automaton.setStates(states);
	automaton.setInputSymbols(inputSymbols);
	automaton.setInitialStates(initialStates);
	automaton.setFinalStates(finalStates);

	parseTransitions<CompactNFA>(input, automaton);

	popToken(input, sax::Token::TokenType::END_ELEMENT, "CompactNFA");
	return automaton;
}

ExtendedNFA AutomatonFromXMLParser::parseExtendedNFA(std::list<sax::Token>& input) const {
	popToken(input, sax::Token::TokenType::START_ELEMENT, "ExtendedNFA");

	std::set<State> states = parseStates(input);
	std::set<alphabet::Symbol> inputSymbols = parseInputAlphabet(input);
	std::set<State> initialStates = parseInitialStates(input);
	std::set<State> finalStates = parseFinalStates(input);

	ExtendedNFA automaton;
	automaton.setStates(states);
	automaton.setInputSymbols(inputSymbols);
	automaton.setInitialStates(initialStates);
	automaton.setFinalStates(finalStates);

	parseTransitions<ExtendedNFA>(input, automaton);

	popToken(input, sax::Token::TokenType::END_ELEMENT, "ExtendedNFA");
	return automaton;
}

DPDA AutomatonFromXMLParser::parseDPDA(std::list<sax::Token>& input) const {
	popToken(input, sax::Token::TokenType::START_ELEMENT, "DPDA");

	std::set<State> states = parseStates(input);
	std::set<alphabet::Symbol> inputSymbols = parseInputAlphabet(input);
	std::set<alphabet::Symbol> stackSymbols = parseStackAlphabet(input);
	State initialState = parseInitialState(input);
	alphabet::Symbol initialStackSymbol = parseInitialStackSymbol(input);
	std::set<State> finalStates = parseFinalStates(input);

	DPDA automaton(initialState, initialStackSymbol);
	automaton.setStates(states);
	automaton.setInputSymbols(inputSymbols);
	automaton.setStackSymbols(stackSymbols);
	automaton.setFinalStates(finalStates);

	parseTransitions<DPDA>(input, automaton);

	popToken(input, sax::Token::TokenType::END_ELEMENT, "DPDA");

	return automaton;
}

SinglePopDPDA AutomatonFromXMLParser::parseSinglePopDPDA(std::list<sax::Token>& input) const {
	popToken(input, sax::Token::TokenType::START_ELEMENT, "SinglePopDPDA");

	std::set<State> states = parseStates(input);
	std::set<alphabet::Symbol> inputSymbols = parseInputAlphabet(input);
	std::set<alphabet::Symbol> stackSymbols = parseStackAlphabet(input);
	State initialState = parseInitialState(input);
	alphabet::Symbol initialStackSymbol = parseInitialStackSymbol(input);
	std::set<State> finalStates = parseFinalStates(input);

	SinglePopDPDA automaton(initialState, initialStackSymbol);
	automaton.setStates(states);
	automaton.setInputSymbols(inputSymbols);
	automaton.setStackSymbols(stackSymbols);
	automaton.setFinalStates(finalStates);

	parseTransitions<SinglePopDPDA>(input, automaton);

	popToken(input, sax::Token::TokenType::END_ELEMENT, "SinglePopDPDA");

	return automaton;
}

InputDrivenNPDA AutomatonFromXMLParser::parseInputDrivenNPDA(std::list<sax::Token>& input) const {
	popToken(input, sax::Token::TokenType::START_ELEMENT, "InputDrivenNPDA");

	std::set<State> states = parseStates(input);
	std::set<alphabet::Symbol> inputSymbols = parseInputAlphabet(input);
	std::set<alphabet::Symbol> stackSymbols = parseStackAlphabet(input);
	std::set<State> initialStates = parseInitialStates(input);
	alphabet::Symbol initialStackSymbol = parseInitialStackSymbol(input);
	std::set<State> finalStates = parseFinalStates(input);

	InputDrivenNPDA automaton(initialStackSymbol);
	automaton.setStates(states);
	automaton.setInputSymbols(inputSymbols);
	automaton.setStackSymbols(stackSymbols);
	automaton.setInitialStates(initialStates);
	automaton.setFinalStates(finalStates);

	parseInputToPushdownStoreOperation(input, automaton);
	parseTransitions<InputDrivenNPDA>(input, automaton);

	popToken(input, sax::Token::TokenType::END_ELEMENT, "InputDrivenNPDA");

	return automaton;
}

VisiblyPushdownNPDA AutomatonFromXMLParser::parseVisiblyPushdownNPDA(std::list<sax::Token>& input) const {
	popToken(input, sax::Token::TokenType::START_ELEMENT, "VisiblyPushdownNPDA");

	std::set<State> states = parseStates(input);
	std::set<alphabet::Symbol> callInputSymbols = parseCallInputAlphabet(input);
	std::set<alphabet::Symbol> returnInputSymbols = parseReturnInputAlphabet(input);
	std::set<alphabet::Symbol> localInputSymbols = parseLocalInputAlphabet(input);
	std::set<alphabet::Symbol> stackSymbols = parseStackAlphabet(input);
	std::set<State> initialStates = parseInitialStates(input);
	alphabet::Symbol bottomOfTheStackSymbol = parseBottomOfTheStackSymbol(input);
	std::set<State> finalStates = parseFinalStates(input);

	VisiblyPushdownNPDA automaton(bottomOfTheStackSymbol);
	automaton.setStates(states);
	automaton.setCallInputSymbols(callInputSymbols);
	automaton.setReturnInputSymbols(returnInputSymbols);
	automaton.setLocalInputSymbols(localInputSymbols);
	automaton.setStackSymbols(stackSymbols);
	automaton.setInitialStates(initialStates);
	automaton.setFinalStates(finalStates);

	parseTransitions<VisiblyPushdownNPDA>(input, automaton);

	popToken(input, sax::Token::TokenType::END_ELEMENT, "VisiblyPushdownNPDA");

	return automaton;
}

RealTimeHeightDeterministicNPDA AutomatonFromXMLParser::parseRealTimeHeightDeterministicNPDA(std::list<sax::Token>& input) const {
	popToken(input, sax::Token::TokenType::START_ELEMENT, "RealTimeHeightDeterministicNPDA");

	std::set<State> states = parseStates(input);
	std::set<alphabet::Symbol> inputSymbols = parseInputAlphabet(input);
	std::set<alphabet::Symbol> stackSymbols = parseStackAlphabet(input);
	std::set<State> initialStates = parseInitialStates(input);
	alphabet::Symbol bottomOfTheStackSymbol = parseBottomOfTheStackSymbol(input);
	std::set<State> finalStates = parseFinalStates(input);

	RealTimeHeightDeterministicNPDA automaton(bottomOfTheStackSymbol);
	automaton.setStates(states);
	automaton.setInputSymbols(inputSymbols);
	automaton.setStackSymbols(stackSymbols);
	automaton.setInitialStates(initialStates);
	automaton.setFinalStates(finalStates);

	parseTransitions<RealTimeHeightDeterministicNPDA>(input, automaton);

	popToken(input, sax::Token::TokenType::END_ELEMENT, "RealTimeHeightDeterministicNPDA");

	return automaton;
}

NPDA AutomatonFromXMLParser::parseNPDA(std::list<sax::Token>& input) const {
	popToken(input, sax::Token::TokenType::START_ELEMENT, "NPDA");

	std::set<State> states = parseStates(input);
	std::set<alphabet::Symbol> inputSymbols = parseInputAlphabet(input);
	std::set<alphabet::Symbol> stackSymbols = parseStackAlphabet(input);
	std::set<State> initialStates = parseInitialStates(input);
	std::set<alphabet::Symbol> initialStackSymbols = parseInitialStackSymbols(input);
	std::set<State> finalStates = parseFinalStates(input);

	NPDA automaton;
	automaton.setStates(states);
	automaton.setInputSymbols(inputSymbols);
	automaton.setStackSymbols(stackSymbols);
	automaton.setInitialStates(initialStates);
	automaton.setFinalStates(finalStates);
	automaton.setInitialSymbols(initialStackSymbols);

	parseTransitions<NPDA>(input, automaton);

	popToken(input, sax::Token::TokenType::END_ELEMENT, "NPDA");

	return automaton;
}

SinglePopNPDA AutomatonFromXMLParser::parseSinglePopNPDA(std::list<sax::Token>& input) const {
	popToken(input, sax::Token::TokenType::START_ELEMENT, "SinglePopNPDA");

	std::set<State> states = parseStates(input);
	std::set<alphabet::Symbol> inputSymbols = parseInputAlphabet(input);
	std::set<alphabet::Symbol> stackSymbols = parseStackAlphabet(input);
	std::set<State> initialStates = parseInitialStates(input);
	std::set<alphabet::Symbol> initialStackSymbols = parseInitialStackSymbols(input);
	std::set<State> finalStates = parseFinalStates(input);

	SinglePopNPDA automaton;
	automaton.setStates(states);
	automaton.setInputSymbols(inputSymbols);
	automaton.setStackSymbols(stackSymbols);
	automaton.setInitialStates(initialStates);
	automaton.setFinalStates(finalStates);
	automaton.setInitialSymbols(initialStackSymbols);

	parseTransitions<SinglePopNPDA>(input, automaton);

	popToken(input, sax::Token::TokenType::END_ELEMENT, "SinglePopNPDA");

	return automaton;
}

OneTapeDTM AutomatonFromXMLParser::parseOneTapeDTM(std::list<sax::Token>& input) const {
	popToken(input, sax::Token::TokenType::START_ELEMENT, "OneTapeTM");

	std::set<State> states = parseStates(input);
	std::set<alphabet::Symbol> inputSymbols = parseInputAlphabet(input);
	std::set<alphabet::Symbol> tapeSymbols = parseTapeAlphabet(input);
	alphabet::Symbol blank = parseBlankSymbol(input);
	State initialState = parseInitialState(input);
	std::set<State> finalStates = parseFinalStates(input);

	OneTapeDTM automaton(initialState, blank);
	automaton.setStates(states);
	automaton.setInputSymbols(inputSymbols);
	automaton.setTapeSymbols(tapeSymbols);
	automaton.setInitialState(initialState);
	automaton.setFinalStates(finalStates);
	
	parseTransitions<OneTapeDTM>(input, automaton);

	popToken(input, sax::Token::TokenType::END_ELEMENT, "OneTapeTM");
	return automaton;
}

std::set<State> AutomatonFromXMLParser::parseStates(std::list<sax::Token> &input) const {
	std::set<State> states;
	popToken(input, sax::Token::TokenType::START_ELEMENT, "states");
	while (isTokenType(input, sax::Token::TokenType::START_ELEMENT)) {
		states.insert(State(alib::api<label::Label>::parse(input)));
	}
	popToken(input, sax::Token::TokenType::END_ELEMENT, "states");
	return states;
}

std::set<alphabet::Symbol> AutomatonFromXMLParser::parseCallInputAlphabet(std::list<sax::Token> &input) const {
	std::set<alphabet::Symbol> inputSymbols;
	popToken(input, sax::Token::TokenType::START_ELEMENT, "callInputAlphabet");
	while (isTokenType(input, sax::Token::TokenType::START_ELEMENT)) {
		inputSymbols.insert(alib::api<alphabet::Symbol>::parse(input));
	}
	popToken(input, sax::Token::TokenType::END_ELEMENT, "callInputAlphabet");
	return inputSymbols;
}

std::set<alphabet::Symbol> AutomatonFromXMLParser::parseReturnInputAlphabet(std::list<sax::Token> &input) const {
	std::set<alphabet::Symbol> inputSymbols;
	popToken(input, sax::Token::TokenType::START_ELEMENT, "returnInputAlphabet");
	while (isTokenType(input, sax::Token::TokenType::START_ELEMENT)) {
		inputSymbols.insert(alib::api<alphabet::Symbol>::parse(input));
	}
	popToken(input, sax::Token::TokenType::END_ELEMENT, "returnInputAlphabet");
	return inputSymbols;
}

std::set<alphabet::Symbol> AutomatonFromXMLParser::parseLocalInputAlphabet(std::list<sax::Token> &input) const {
	std::set<alphabet::Symbol> inputSymbols;
	popToken(input, sax::Token::TokenType::START_ELEMENT, "localInputAlphabet");
	while (isTokenType(input, sax::Token::TokenType::START_ELEMENT)) {
		inputSymbols.insert(alib::api<alphabet::Symbol>::parse(input));
	}
	popToken(input, sax::Token::TokenType::END_ELEMENT, "localInputAlphabet");
	return inputSymbols;
}

std::set<alphabet::Symbol> AutomatonFromXMLParser::parseInputAlphabet(std::list<sax::Token> &input) const {
	std::set<alphabet::Symbol> inputSymbols;
	popToken(input, sax::Token::TokenType::START_ELEMENT, "inputAlphabet");
	while (isTokenType(input, sax::Token::TokenType::START_ELEMENT)) {
		inputSymbols.insert(alib::api<alphabet::Symbol>::parse(input));
	}
	popToken(input, sax::Token::TokenType::END_ELEMENT, "inputAlphabet");
	return inputSymbols;
}

State AutomatonFromXMLParser::parseInitialState(std::list<sax::Token> &input) const {
	popToken(input, sax::Token::TokenType::START_ELEMENT, "initialState");
	State state(alib::api<label::Label>::parse(input));
	popToken(input, sax::Token::TokenType::END_ELEMENT, "initialState");
	return state;
}

std::set<State> AutomatonFromXMLParser::parseInitialStates(std::list<sax::Token> &input) const {
	std::set<State> initialStates;
	popToken(input, sax::Token::TokenType::START_ELEMENT, "initialStates");
	while (isTokenType(input, sax::Token::TokenType::START_ELEMENT)) {
		initialStates.insert(State(alib::api<label::Label>::parse(input)));
	}
	popToken(input, sax::Token::TokenType::END_ELEMENT, "initialStates");
	return initialStates;
}

std::set<State> AutomatonFromXMLParser::parseFinalStates(std::list<sax::Token> &input) const {
	std::set<State> finalStates;
	popToken(input, sax::Token::TokenType::START_ELEMENT, "finalStates");
	while (isTokenType(input, sax::Token::TokenType::START_ELEMENT)) {
		finalStates.insert(State(alib::api<label::Label>::parse(input)));
	}
	popToken(input, sax::Token::TokenType::END_ELEMENT, "finalStates");
	return finalStates;
}

std::set<alphabet::Symbol> AutomatonFromXMLParser::parseStackAlphabet(std::list<sax::Token> &input) const {
	std::set<alphabet::Symbol> stackSymbols;
	popToken(input, sax::Token::TokenType::START_ELEMENT, "stackAlphabet");
	while (isTokenType(input, sax::Token::TokenType::START_ELEMENT)) {
		stackSymbols.insert(alib::api<alphabet::Symbol>::parse(input));
	}
	popToken(input, sax::Token::TokenType::END_ELEMENT, "stackAlphabet");
	return stackSymbols;
}

std::set<alphabet::Symbol> AutomatonFromXMLParser::parseInitialStackSymbols(std::list<sax::Token> &input) const {
	std::set<alphabet::Symbol> initialSymbols;
	popToken(input, sax::Token::TokenType::START_ELEMENT, "initialStackSymbols");
	while (isTokenType(input, sax::Token::TokenType::START_ELEMENT)) {
		initialSymbols.insert(alib::api<alphabet::Symbol>::parse(input));
	}
	popToken(input, sax::Token::TokenType::END_ELEMENT, "initialStackSymbols");
	return initialSymbols;
}

alphabet::Symbol AutomatonFromXMLParser::parseInitialStackSymbol(std::list<sax::Token> &input) const {
	popToken(input, sax::Token::TokenType::START_ELEMENT, "initialStackSymbol");
	alphabet::Symbol initialSymbol(alib::api<alphabet::Symbol>::parse(input));
	popToken(input, sax::Token::TokenType::END_ELEMENT, "initialStackSymbol");
	return initialSymbol;
}

std::set<alphabet::Symbol> AutomatonFromXMLParser::parseTapeAlphabet(std::list<sax::Token> &input) const {
	std::set<alphabet::Symbol> tapeSymbols;
	popToken(input, sax::Token::TokenType::START_ELEMENT, "tapeAlphabet");
	while (isTokenType(input, sax::Token::TokenType::START_ELEMENT)) {
		tapeSymbols.insert(alib::api<alphabet::Symbol>::parse(input));
	}
	popToken(input, sax::Token::TokenType::END_ELEMENT, "tapeAlphabet");
	return tapeSymbols;
}

alphabet::Symbol AutomatonFromXMLParser::parseBlankSymbol(std::list<sax::Token>& input) const {
	popToken(input, sax::Token::TokenType::START_ELEMENT, "blankSymbol");
	alphabet::Symbol blank(alib::api<alphabet::Symbol>::parse(input));
	popToken(input, sax::Token::TokenType::END_ELEMENT, "blankSymbol");
	return blank;
}

alphabet::Symbol AutomatonFromXMLParser::parseBottomOfTheStackSymbol(std::list<sax::Token>& input) const {
	popToken(input, sax::Token::TokenType::START_ELEMENT, "bottomOfTheStackSymbol");
	alphabet::Symbol blank(alib::api<alphabet::Symbol>::parse(input));
	popToken(input, sax::Token::TokenType::END_ELEMENT, "bottomOfTheStackSymbol");
	return blank;
}

void AutomatonFromXMLParser::parseInputToPushdownStoreOperation(std::list<sax::Token>& input, automaton::InputDrivenNPDA& automaton) const {
	popToken(input, sax::Token::TokenType::START_ELEMENT, "inputToPushdownStoreOperations");
	while (isTokenType(input, sax::Token::TokenType::START_ELEMENT)) {
		popToken(input, sax::Token::TokenType::START_ELEMENT, "operation");

		alphabet::Symbol inputSymbol(alib::api<alphabet::Symbol>::parse(input));

		std::vector<alphabet::Symbol> pop = parseTransitionPop(input);
		std::vector<alphabet::Symbol> push = parseTransitionPush(input);

		automaton.setPushdownStoreOperation(inputSymbol, pop, push);

		popToken(input, sax::Token::TokenType::END_ELEMENT, "operation");
	}
	popToken(input, sax::Token::TokenType::END_ELEMENT, "inputToPushdownStoreOperations");
}

void AutomatonFromXMLParser::parseTransition(std::list<sax::Token>& input, DFA& automaton) const {
	State from = parseTransitionFrom(input);
	alphabet::Symbol inputSymbol = parseTransitionInputSymbol(input);
	State to = parseTransitionTo(input);

	automaton.addTransition(from, inputSymbol, to);
}

void AutomatonFromXMLParser::parseTransition(std::list<sax::Token>& input, NFA& automaton) const {
	State from = parseTransitionFrom(input);
	alphabet::Symbol inputSymbol = parseTransitionInputSymbol(input);
	State to = parseTransitionTo(input);

	automaton.addTransition(from, inputSymbol, to);
}

void AutomatonFromXMLParser::parseTransition(std::list<sax::Token>& input, EpsilonNFA& automaton) const {
	State from = parseTransitionFrom(input);
	std::variant<string::Epsilon, alphabet::Symbol> inputVariant = parseTransitionInputEpsilonSymbol(input);
	State to = parseTransitionTo(input);

	automaton.addTransition(from, inputVariant, to);
}

void AutomatonFromXMLParser::parseTransition(std::list<sax::Token>& input, CompactNFA& automaton) const {
	State from = parseTransitionFrom(input);
	string::LinearString inputString = parseTransitionInputString(input);
	State to = parseTransitionTo(input);

	automaton.addTransition(from, inputString, to);
}

void AutomatonFromXMLParser::parseTransition(std::list<sax::Token>& input, ExtendedNFA& automaton) const {
	State from = parseTransitionFrom(input);
	regexp::RegExp inputRegexp = parseTransitionInputRegexp(input);
	State to = parseTransitionTo(input);

	automaton.addTransition(from, inputRegexp, to);
}

void AutomatonFromXMLParser::parseTransition(std::list<sax::Token>& input, DPDA& automaton) const {
	State from = parseTransitionFrom(input);
	std::variant<string::Epsilon, alphabet::Symbol> inputSymbol = parseTransitionInputEpsilonSymbol(input);
	std::vector<alphabet::Symbol> pop = parseTransitionPop(input);
	State to = parseTransitionTo(input);
	std::vector<alphabet::Symbol> push = parseTransitionPush(input);

	automaton.addTransition(from, inputSymbol, pop, to, push);
}

void AutomatonFromXMLParser::parseTransition(std::list<sax::Token>& input, SinglePopDPDA& automaton) const {
	State from = parseTransitionFrom(input);
	std::variant<string::Epsilon, alphabet::Symbol> inputSymbol = parseTransitionInputEpsilonSymbol(input);
	alphabet::Symbol pop = parseTransitionSinglePop(input);
	State to = parseTransitionTo(input);
	std::vector<alphabet::Symbol> push = parseTransitionPush(input);

	automaton.addTransition(from, inputSymbol, pop, to, push);
}

void AutomatonFromXMLParser::parseTransition(std::list<sax::Token>& input, InputDrivenNPDA& automaton) const {
	State from = parseTransitionFrom(input);
	alphabet::Symbol inputSymbol = parseTransitionInputSymbol(input);
	State to = parseTransitionTo(input);

	automaton.addTransition(from, inputSymbol, to);
}

void AutomatonFromXMLParser::parseTransition(std::list<sax::Token>& input, VisiblyPushdownNPDA& automaton) const {
	if(isToken(input, sax::Token::TokenType::START_ELEMENT, "callTransition")) {
		popToken(input, sax::Token::TokenType::START_ELEMENT, "callTransition");
		State from = parseTransitionFrom(input);
		alphabet::Symbol inputSymbol = parseTransitionInputSymbol(input);
		State to = parseTransitionTo(input);
		alphabet::Symbol push = parseTransitionSinglePush(input);

		automaton.addCallTransition(from, inputSymbol, to, push);
		popToken(input, sax::Token::TokenType::END_ELEMENT, "callTransition");
	} else if(isToken(input, sax::Token::TokenType::START_ELEMENT, "returnTransition")) {
		popToken(input, sax::Token::TokenType::START_ELEMENT, "returnTransition");
		State from = parseTransitionFrom(input);
		alphabet::Symbol inputSymbol = parseTransitionInputSymbol(input);
		alphabet::Symbol pop = parseTransitionSinglePop(input);
		State to = parseTransitionTo(input);

		automaton.addReturnTransition(from, inputSymbol, pop, to);
		popToken(input, sax::Token::TokenType::END_ELEMENT, "returnTransition");
	} else {
		popToken(input, sax::Token::TokenType::START_ELEMENT, "localTransition");
		State from = parseTransitionFrom(input);
		alphabet::Symbol inputSymbol = parseTransitionInputSymbol(input);
		State to = parseTransitionTo(input);

		automaton.addLocalTransition(from, inputSymbol, to);
		popToken(input, sax::Token::TokenType::END_ELEMENT, "localTransition");
	}
}

void AutomatonFromXMLParser::parseTransition(std::list<sax::Token>& input, RealTimeHeightDeterministicNPDA& automaton) const {
	if(isToken(input, sax::Token::TokenType::START_ELEMENT, "callTransition")) {
		popToken(input, sax::Token::TokenType::START_ELEMENT, "callTransition");
		State from = parseTransitionFrom(input);
		std::variant<string::Epsilon, alphabet::Symbol> inputSymbol = parseTransitionInputEpsilonSymbol(input);
		State to = parseTransitionTo(input);
		alphabet::Symbol push = parseTransitionSinglePush(input);

		automaton.addCallTransition(from, inputSymbol, to, push);
		popToken(input, sax::Token::TokenType::END_ELEMENT, "callTransition");
	} else if(isToken(input, sax::Token::TokenType::START_ELEMENT, "returnTransition")) {
		popToken(input, sax::Token::TokenType::START_ELEMENT, "returnTransition");
		State from = parseTransitionFrom(input);
		std::variant<string::Epsilon, alphabet::Symbol> inputSymbol = parseTransitionInputEpsilonSymbol(input);
		alphabet::Symbol pop = parseTransitionSinglePop(input);
		State to = parseTransitionTo(input);

		automaton.addReturnTransition(from, inputSymbol, pop, to);
		popToken(input, sax::Token::TokenType::END_ELEMENT, "returnTransition");
	} else {
		popToken(input, sax::Token::TokenType::START_ELEMENT, "localTransition");
		State from = parseTransitionFrom(input);
		std::variant<string::Epsilon, alphabet::Symbol> inputSymbol = parseTransitionInputEpsilonSymbol(input);
		State to = parseTransitionTo(input);

		automaton.addLocalTransition(from, inputSymbol, to);
		popToken(input, sax::Token::TokenType::END_ELEMENT, "localTransition");
	}
}

void AutomatonFromXMLParser::parseTransition(std::list<sax::Token>& input, NPDA& automaton) const {
	State from = parseTransitionFrom(input);
	std::variant<string::Epsilon, alphabet::Symbol> inputSymbol = parseTransitionInputEpsilonSymbol(input);
	std::vector<alphabet::Symbol> pop = parseTransitionPop(input);
	State to = parseTransitionTo(input);
	std::vector<alphabet::Symbol> push = parseTransitionPush(input);

	automaton.addTransition(from, inputSymbol, pop, to, push);
}

void AutomatonFromXMLParser::parseTransition(std::list<sax::Token>& input, SinglePopNPDA& automaton) const {
	State from = parseTransitionFrom(input);
	std::variant<string::Epsilon, alphabet::Symbol> inputSymbol = parseTransitionInputEpsilonSymbol(input);
	alphabet::Symbol pop = parseTransitionSinglePop(input);
	State to = parseTransitionTo(input);
	std::vector<alphabet::Symbol> push = parseTransitionPush(input);

	automaton.addTransition(from, inputSymbol, pop, to, push);
}

void AutomatonFromXMLParser::parseTransition(std::list<sax::Token>& input, OneTapeDTM& automaton) const {
	State from = parseTransitionFrom(input);
	alphabet::Symbol inputSymbol = parseTransitionInputSymbol(input);
	State to = parseTransitionTo(input);
	alphabet::Symbol outputSymbol = parseTransitionOutputSymbol(input);
	Shift shift = parseTransitionShift(input);

	automaton.addTransition(from, inputSymbol, to, outputSymbol, shift);
}

void AutomatonFromXMLParser::parseTransition(std::list<sax::Token>& input, UnknownAutomaton& automaton) const {
	UnknownTransition transition;

	while (isTokenType(input, sax::Token::TokenType::START_ELEMENT)) {
		if (isToken(input, sax::Token::TokenType::START_ELEMENT, "from")) {
			transition.setFrom(parseTransitionFrom(input));
		} else if (isToken(input, sax::Token::TokenType::START_ELEMENT, "input")) {
			transition.setInput(parseTransitionInputEpsilonSymbol(input));
		} else if (isToken(input, sax::Token::TokenType::START_ELEMENT, "to")) {
			transition.setTo(parseTransitionTo(input));
		} else if (isToken(input, sax::Token::TokenType::START_ELEMENT, "pop")) {
			transition.setPop(parseTransitionPop(input));
		} else if (isToken(input, sax::Token::TokenType::START_ELEMENT, "push")) {
			transition.setPush(parseTransitionPush(input));
		} else if (isToken(input, sax::Token::TokenType::START_ELEMENT, "output")) {
			transition.setOutput(parseTransitionOutputEpsilonSymbol(input));
		} else if (isToken(input, sax::Token::TokenType::START_ELEMENT, "shift")) {
			transition.setShift(parseTransitionShift(input));
		} else {
			throw sax::ParserException(sax::Token("transitions", sax::Token::TokenType::END_ELEMENT), input.front());
		}
	}

	automaton.addTransition(transition);
}

State AutomatonFromXMLParser::parseTransitionTo(std::list<sax::Token> &input) const {
	popToken(input, sax::Token::TokenType::START_ELEMENT, "to");
	State state(alib::api<label::Label>::parse(input));
	popToken(input, sax::Token::TokenType::END_ELEMENT, "to");
	return state;
}

State AutomatonFromXMLParser::parseTransitionFrom(std::list<sax::Token> &input) const {
	popToken(input, sax::Token::TokenType::START_ELEMENT, "from");
	State state(alib::api<label::Label>::parse(input));
	popToken(input, sax::Token::TokenType::END_ELEMENT, "from");
	return state;
}

Shift AutomatonFromXMLParser::parseTransitionShift(std::list<sax::Token>& input) const {
	Shift shift;

	popToken(input, sax::Token::TokenType::START_ELEMENT, "shift");
	if (isToken(input, sax::Token::TokenType::CHARACTER, "left")) {
		shift = LEFT;
	} else if (isToken(input, sax::Token::TokenType::CHARACTER, "right")) {
		shift = RIGHT;
	} else if (isToken(input, sax::Token::TokenType::CHARACTER, "none")) {
		shift = NONE;
	} else {
		throw sax::ParserException(sax::Token("", sax::Token::TokenType::CHARACTER), input.front());
	}
	input.pop_front();
	popToken(input, sax::Token::TokenType::END_ELEMENT, "shift");

	return shift;
}

std::vector<alphabet::Symbol> AutomatonFromXMLParser::parseTransitionPop(std::list<sax::Token>& input) const {
	std::vector<alphabet::Symbol> pops;
	popToken(input, sax::Token::TokenType::START_ELEMENT, "pop");
	while (isTokenType(input, sax::Token::TokenType::START_ELEMENT)) {
		pops.push_back(alib::api<alphabet::Symbol>::parse(input));
	}
	popToken(input, sax::Token::TokenType::END_ELEMENT, "pop");
	return pops;
}

alphabet::Symbol AutomatonFromXMLParser::parseTransitionSinglePop(std::list<sax::Token>& input) const {
	popToken(input, sax::Token::TokenType::START_ELEMENT, "pop");
	alphabet::Symbol pop = alib::api<alphabet::Symbol>::parse(input);
	popToken(input, sax::Token::TokenType::END_ELEMENT, "pop");
	return pop;
}

std::vector<alphabet::Symbol> AutomatonFromXMLParser::parseTransitionPush(std::list<sax::Token>& input) const {
	std::vector<alphabet::Symbol> pushes;
	popToken(input, sax::Token::TokenType::START_ELEMENT, "push");
	while (isTokenType(input, sax::Token::TokenType::START_ELEMENT)) {
		pushes.push_back(alib::api<alphabet::Symbol>::parse(input));
	}
	popToken(input, sax::Token::TokenType::END_ELEMENT, "push");
	return pushes;
}

alphabet::Symbol AutomatonFromXMLParser::parseTransitionSinglePush(std::list<sax::Token>& input) const {
	popToken(input, sax::Token::TokenType::START_ELEMENT, "push");
	alphabet::Symbol push = alib::api<alphabet::Symbol>::parse(input);
	popToken(input, sax::Token::TokenType::END_ELEMENT, "push");
	return push;
}

alphabet::Symbol AutomatonFromXMLParser::parseTransitionInputSymbol(std::list<sax::Token>& input) const {
	popToken(input, sax::Token::TokenType::START_ELEMENT, "input");
	alphabet::Symbol result(alib::api<alphabet::Symbol>::parse(input));
	popToken(input, sax::Token::TokenType::END_ELEMENT, "input");
	return result;
}

alphabet::Symbol AutomatonFromXMLParser::parseTransitionOutputSymbol(std::list<sax::Token>& input) const {
	popToken(input, sax::Token::TokenType::START_ELEMENT, "output");
	alphabet::Symbol result(alib::api<alphabet::Symbol>::parse(input));
	popToken(input, sax::Token::TokenType::END_ELEMENT, "output");
	return result;
}

std::variant<string::Epsilon, alphabet::Symbol> AutomatonFromXMLParser::parseTransitionInputEpsilonSymbol(std::list<sax::Token>& input) const {
	popToken(input, sax::Token::TokenType::START_ELEMENT, "input");
	
	if(isToken(input, sax::Token::TokenType::START_ELEMENT, "epsilon")) {
		std::variant<string::Epsilon, alphabet::Symbol> result(string::Epsilon::EPSILON);
		input.pop_front();
		popToken(input, sax::Token::TokenType::END_ELEMENT, "epsilon");
		popToken(input, sax::Token::TokenType::END_ELEMENT, "input");
		return result;
	} else {
		std::variant<string::Epsilon, alphabet::Symbol> result(alib::api<alphabet::Symbol>::parse(input));
		popToken(input, sax::Token::TokenType::END_ELEMENT, "input");
		return result;
	}
}

std::variant<string::Epsilon, alphabet::Symbol> AutomatonFromXMLParser::parseTransitionOutputEpsilonSymbol(std::list<sax::Token>& input) const {
	popToken(input, sax::Token::TokenType::START_ELEMENT, "output");
	
	if(isToken(input, sax::Token::TokenType::START_ELEMENT, "epsilon")) {
		std::variant<string::Epsilon, alphabet::Symbol> result(string::Epsilon::EPSILON);
		input.pop_front();
		popToken(input, sax::Token::TokenType::END_ELEMENT, "epsilon");
		popToken(input, sax::Token::TokenType::END_ELEMENT, "output");
		return result;
	} else {
		std::variant<string::Epsilon, alphabet::Symbol> result(alib::api<alphabet::Symbol>::parse(input));
		popToken(input, sax::Token::TokenType::END_ELEMENT, "output");
		return result;
	}
}

string::LinearString AutomatonFromXMLParser::parseTransitionInputString(std::list<sax::Token>& input) const {
	popToken(input, sax::Token::TokenType::START_ELEMENT, "input");
	string::LinearString result(alib::api<string::LinearString>::parse(input));
	popToken(input, sax::Token::TokenType::END_ELEMENT, "input");
	return result;
}

regexp::RegExp AutomatonFromXMLParser::parseTransitionInputRegexp(std::list<sax::Token>& input) const {
	popToken(input, sax::Token::TokenType::START_ELEMENT, "input");
	regexp::RegExp result(alib::api<regexp::RegExp>::parse(input));
	popToken(input, sax::Token::TokenType::END_ELEMENT, "input");
	return result;
}

} /* namespace automaton */