NFA.h

Go to the documentation of this file.

 
#pragma once
 
#include <automaton/FSM/NFA.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::NFA < SymbolType, StateType > > {
    static automaton::NFA < SymbolType, StateType > parse ( ext::istream & input );
    static bool first ( ext::istream & input );
    static void compose ( ext::ostream & output, const automaton::NFA < 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::NFA < SymbolType, StateType > & automaton, const StateType & from);
};
 
template<class SymbolType, class StateType >
automaton::NFA < SymbolType, StateType > stringApi < automaton::NFA < 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::NFA) {
        throw exception::CommonException("Unrecognised NFA token." + ext::to_string ( static_cast < int > ( token.type ) ) );
    }
    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::NFA < > 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::NFA < 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 NFA 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);
            do {
                StateType to = core::stringApi < StateType >::parse ( input );
                states.insert(to);
                transitionFunction.insert(ext::make_tuple(from, *iter, to));
 
                token = automaton::AutomatonFromStringLexer::next(input);
                if(token.type != automaton::AutomatonFromStringLexer::TokenType::SEPARATOR) break;
            } while(true);
        } else {
            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::NFA < SymbolType, StateType > >::first ( ext::istream & input ) {
    return automaton::AutomatonFromStringLexer::peek ( input ).type == automaton::AutomatonFromStringLexer::TokenType::NFA;
}
 
template<class SymbolType, class StateType >
void stringApi < automaton::NFA < SymbolType, StateType > >::compose ( ext::ostream & output, const automaton::NFA < SymbolType, StateType > & automaton ) {
    output << "NFA";
    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::NFA < SymbolType, StateType > >::composeTransitionsFromState(ext::ostream& output, const automaton::NFA < SymbolType, StateType > & automaton, const StateType & from) {
    for(const SymbolType& inputSymbol : automaton.getInputAlphabet()) {
        const auto toStates = automaton.getTransitions ( ).equal_range ( ext::tie ( from, inputSymbol ) );
        if ( toStates.empty ( ) ) {
            output << " -";
        } else {
            bool sign = false;
            for(const auto & transition : toStates ) {
                output << (sign ? "|" : " ");
                core::stringApi<StateType>::compose(output, transition.second);
                sign = true;
            }
        }
    }
}
 
} /* namespace core */