EpsilonNFA.h

Go to the documentation of this file.

 
#pragma once
 
#include <automaton/FSM/EpsilonNFA.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::EpsilonNFA < SymbolType, StateType > > {
    static automaton::EpsilonNFA < SymbolType, StateType > parse ( ext::istream & input );
    static bool first ( ext::istream & input );
    static void compose ( ext::ostream & output, const automaton::EpsilonNFA < SymbolType, StateType > & automaton );
private:
    static void parseTransition(ext::istream& input, ext::set<StateType>& states, const ext::vector < common::symbol_or_epsilon < SymbolType > > & symbols, StateType*& initialState, ext::set<StateType>& finalStates, ext::set<ext::tuple<StateType, common::symbol_or_epsilon < SymbolType >, StateType>>& transitionFunction);
    static void composeTransitionsFromState(ext::ostream& output, const automaton::EpsilonNFA < SymbolType, StateType > & automaton, const StateType & from);
};
 
template<class SymbolType, class StateType >
automaton::EpsilonNFA < SymbolType, StateType > stringApi < automaton::EpsilonNFA < 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::EPSILON_NFA) {
        throw exception::CommonException("Unrecognised ENFA token.");
    }
    ext::vector<common::symbol_or_epsilon < SymbolType > > symbols;
 
    token = automaton::AutomatonFromStringLexer::next(input);
    while(token.type != automaton::AutomatonFromStringLexer::TokenType::NEW_LINE && token.type != automaton::AutomatonFromStringLexer::TokenType::TEOF) {
        if(token.type == automaton::AutomatonFromStringLexer::TokenType::EPSILON) {
            symbols.push_back(common::symbol_or_epsilon < SymbolType > ( ));
        } else {
            automaton::AutomatonFromStringLexer::putback(input, token);
            SymbolType symbol = core::stringApi<SymbolType>::parse(input);
 
            common::symbol_or_epsilon < SymbolType > symbolVariant(symbol);
            symbols.push_back(symbolVariant);
        }
 
        token = automaton::AutomatonFromStringLexer::next(input);
    }
 
    StateType* initialState = nullptr;
    ext::set<StateType> finalStates;
    ext::set<StateType> states;
    ext::set<ext::tuple<StateType, common::symbol_or_epsilon < 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::EpsilonNFA < > res(*initialState);
    delete initialState;
 
    for ( const common::symbol_or_epsilon < SymbolType > & inputSymbol : symbols) {
        if(!inputSymbol.is_epsilon())
            res.addInputSymbol(inputSymbol.getSymbol());
    }
    res.setStates(states);
    res.setFinalStates(finalStates);
    for ( const ext::tuple<StateType, common::symbol_or_epsilon < 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::EpsilonNFA < SymbolType, StateType > >::parseTransition(ext::istream& input, ext::set<StateType>& states, const ext::vector<common::symbol_or_epsilon < SymbolType >>& symbols, StateType*& initialState, ext::set<StateType>& finalStates, ext::set<ext::tuple<StateType, common::symbol_or_epsilon < 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 EpsilonNFA type");
        initialState = new StateType(from);
    }
    if(final) finalStates.insert(from);
 
    automaton::AutomatonFromStringLexer::Token token = automaton::AutomatonFromStringLexer::next(input);
    typename ext::vector<common::symbol_or_epsilon < 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::EpsilonNFA < SymbolType, StateType > >::first ( ext::istream & input ) {
    return automaton::AutomatonFromStringLexer::peek ( input ).type == automaton::AutomatonFromStringLexer::TokenType::EPSILON_NFA;
}
 
template<class SymbolType, class StateType >
void stringApi < automaton::EpsilonNFA < SymbolType, StateType > >::compose ( ext::ostream & output, const automaton::EpsilonNFA < SymbolType, StateType > & automaton ) {
    output << "ENFA";
    for(const auto& symbol : automaton.getInputAlphabet()) {
        output << " ";
        core::stringApi < SymbolType >::compose ( output, symbol );
    }
 
    output << " #E";
    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::EpsilonNFA < SymbolType, StateType > >::composeTransitionsFromState(ext::ostream& output, const automaton::EpsilonNFA < 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;
            }
        }
    }
 
    ext::multimap<StateType, StateType > epsilonTransitionsFromState = automaton.getEpsilonTransitionsFromState(from);
    if ( epsilonTransitionsFromState.empty ( ) ) {
        output << " -";
    } else {
        bool sign = false;
        for(const auto & transition : epsilonTransitionsFromState ) {
            output << (sign ? "|" : " ");
            core::stringApi<StateType>::compose(output, transition.second);
            sign = true;
        }
    }
 
}
 
} /* namespace core */