DFA.h

Go to the documentation of this file.

 
#pragma once
 
#include <automaton/FSM/DFA.h>
#include <core/stringApi.hpp>
 
#include <automaton/AutomatonFromStringLexer.h>
 
#include <automaton/string/common/AutomatonFromStringParserCommon.h>
 
namespace core {
 
template<class SymbolType, class StateType >
struct stringApi < automaton::DFA < SymbolType, StateType > > {
    static automaton::DFA < SymbolType, StateType > parse ( ext::istream & input );
    static bool first ( ext::istream & input );
    static void compose ( ext::ostream & output, const automaton::DFA < SymbolType, StateType > & automaton );
private:
    static void parseTransition(ext::istream& input, ext::set<StateType>& states, const ext::vector<SymbolType>& symbols, StateType*& initialState, ext::set<StateType>& finalStates, ext::set<ext::tuple<StateType, SymbolType, StateType>>& transitionFunction);
    static void composeTransitionsFromState(ext::ostream& output, const automaton::DFA < SymbolType, StateType > & automaton, const StateType & from);
};
 
template<class SymbolType, class StateType >
automaton::DFA < SymbolType, StateType > stringApi < automaton::DFA < SymbolType, StateType > >::parse ( ext::istream & input ) {
    automaton::AutomatonFromStringLexer::Token token = automaton::AutomatonFromStringLexer::next(input);
 
    while(token.type == automaton::AutomatonFromStringLexer::TokenType::NEW_LINE) {
        token = automaton::AutomatonFromStringLexer::next(input);
    }
 
    if(token.type != automaton::AutomatonFromStringLexer::TokenType::DFA)
        throw exception::CommonException("Unrecognised DFA token.");
 
    ext::vector<SymbolType> symbols;
 
    token = automaton::AutomatonFromStringLexer::next(input);
    while(token.type != automaton::AutomatonFromStringLexer::TokenType::NEW_LINE) {
        automaton::AutomatonFromStringLexer::putback(input, token);
        SymbolType symbol = core::stringApi<SymbolType>::parse(input);
        symbols.push_back(symbol);
 
        token = automaton::AutomatonFromStringLexer::next(input);
    }
 
    StateType* initialState = nullptr;
    ext::set<StateType> finalStates;
    ext::set<StateType> states;
    ext::set<ext::tuple<StateType, SymbolType, StateType>> transitionFunction;
 
    while(token.type == automaton::AutomatonFromStringLexer::TokenType::NEW_LINE) {
        token = automaton::AutomatonFromStringLexer::next(input);
        if(token.type == automaton::AutomatonFromStringLexer::TokenType::TEOF)
            break;
        else if (token.type == automaton::AutomatonFromStringLexer::TokenType::NEW_LINE)
            continue;
        else
            automaton::AutomatonFromStringLexer::putback(input, token);
 
        parseTransition(input, states, symbols, initialState, finalStates, transitionFunction);
        token = automaton::AutomatonFromStringLexer::next(input);
    }
 
    if(token.type != automaton::AutomatonFromStringLexer::TokenType::TEOF)
        throw exception::CommonException("Extra data after the automaton.");
 
    if(initialState == nullptr)
        throw exception::CommonException("No initial state recognised.");
 
    automaton::DFA < > res(*initialState);
    delete initialState;
 
    res.setInputAlphabet(ext::set<SymbolType>(symbols.begin(), symbols.end()));
    res.setStates(states);
    res.setFinalStates(finalStates);
 
    for(const ext::tuple<StateType, SymbolType, StateType> & transition : transitionFunction)
        res.addTransition(std::get<0>(transition), std::get<1>(transition), std::get<2>(transition));
 
    return res;
}
 
template<class SymbolType, class StateType >
void stringApi < automaton::DFA < SymbolType, StateType > >::parseTransition(ext::istream& input, ext::set<StateType>& states, const ext::vector<SymbolType>& symbols, StateType*& initialState, ext::set<StateType>& finalStates, ext::set<ext::tuple<StateType, SymbolType, StateType>>& transitionFunction) {
    bool initial = false;
    bool final = false;
 
    automaton::AutomatonFromStringParserCommon::initialFinalState(input, initial, final);
 
    StateType from = core::stringApi<StateType>::parse(input);
    states.insert(from);
    if ( initial ) {
        if(initialState != nullptr)
            throw exception::CommonException("Multiple initial states are not available for DFA type");
        initialState = new StateType(from);
    }
    if ( final )
        finalStates.insert(from);
 
    automaton::AutomatonFromStringLexer::Token token = automaton::AutomatonFromStringLexer::next(input);
    typename ext::vector<SymbolType>::const_iterator iter = symbols.begin();
 
    while ( token.type != automaton::AutomatonFromStringLexer::TokenType::NEW_LINE && token.type != automaton::AutomatonFromStringLexer::TokenType::TEOF ) {
        if(iter == symbols.end())
            throw exception::CommonException("Invalid line format");
 
        if(token.type != automaton::AutomatonFromStringLexer::TokenType::NONE) {
            automaton::AutomatonFromStringLexer::putback(input, token);
            StateType to = core::stringApi<StateType>::parse(input);
            states.insert(to);
            transitionFunction.insert(ext::make_tuple(from, *iter, to));
        }
        token = automaton::AutomatonFromStringLexer::next(input);
 
        ++iter;
    }
    automaton::AutomatonFromStringLexer::putback(input, token);
 
    if(iter != symbols.end())
        throw exception::CommonException("Invalid line format");
}
 
template<class SymbolType, class StateType >
bool stringApi < automaton::DFA < SymbolType, StateType > >::first ( ext::istream & input ) {
    return automaton::AutomatonFromStringLexer::peek ( input ).type == automaton::AutomatonFromStringLexer::TokenType::DFA;
}
 
template<class SymbolType, class StateType >
void stringApi < automaton::DFA < SymbolType, StateType > >::compose ( ext::ostream & output, const automaton::DFA < SymbolType, StateType > & automaton ) {
    output << "DFA";
    for(const auto& symbol : automaton.getInputAlphabet()) {
        output << " ";
        core::stringApi<SymbolType>::compose(output, symbol);
    }
 
    output << std::endl;
 
    for(const auto& state : automaton.getStates()) {
        if(automaton.getInitialState() == state)
            output << ">";
 
        if(automaton.getFinalStates().find(state) != automaton.getFinalStates().end())
            output << "<";
 
        core::stringApi<StateType>::compose(output, state);
 
        composeTransitionsFromState(output, automaton, state);
 
        output << std::endl;
    }
}
 
template < class SymbolType, class StateType >
void stringApi < automaton::DFA < SymbolType, StateType > >::composeTransitionsFromState(ext::ostream& output, const automaton::DFA < SymbolType, StateType > & automaton, const StateType & from) {
    ext::iterator_range < typename ext::map < ext::pair < StateType, SymbolType >, StateType >::const_iterator > symbolTransitionsFromState = automaton.getTransitionsFromState(from);
 
    for(const SymbolType& inputSymbol : automaton.getInputAlphabet()) {
        if ( ! symbolTransitionsFromState.empty ( ) && symbolTransitionsFromState.front ( ).first.second == inputSymbol ) {
            output << " ";
            core::stringApi<SymbolType>::compose(output, symbolTransitionsFromState.front ( ).second);
            symbolTransitionsFromState.pop_front ( );
        } else {
            output << " -";
        }
    }
}
 
} /* namespace core */