adfa.cc

Go to the documentation of this file.

#include <assert.h>
#include <queue>
#include <set>
#include <vector>
#include <utility>

#include "src/codegen/go.h"
#include "src/ir/adfa/adfa.h"
#include "src/ir/dfa/dfa.h"
#include "src/ir/skeleton/skeleton.h"
#include "src/util/allocate.h"

namespace re2c
{

DFA::DFA
    ( const dfa_t &dfa
    , const std::vector<size_t> &fill
    , Skeleton *skel
    , const charset_t &charset
    , const std::string &n
    , const std::string &c
    , uint32_t l
    )
    : accepts ()
    , skeleton (skel)
    , name (n)
    , cond (c)
    , line (l)
    , lbChar(0)
    , ubChar(charset.back())
    , nStates(0)
    , head(NULL)

    // statistics
    , max_fill (0)
    , need_backup (false)
    , need_backupctx (false)
    , need_accept (false)
{
    const size_t nstates = dfa.states.size();
    const size_t nchars = dfa.nchars;

    State **i2s = new State*[nstates];
    for (size_t i = 0; i < nstates; ++i)
    {
        i2s[i] = new State;
    }

    State **p = &head;
    for (size_t i = 0; i < nstates; ++i)
    {
        dfa_state_t *t = dfa.states[i];
        State *s = i2s[i];

        ++nStates;
        *p = s;
        p = &s->next;

        s->isPreCtxt = t->ctx;
        s->rule = t->rule;
        s->fill = fill[i];
        s->go.span = allocate<Span>(nchars);
        uint32_t j = 0;
        for (uint32_t c = 0; c < nchars; ++j)
        {
            const size_t to = t->arcs[c];
            for (;++c < nchars && t->arcs[c] == to;);
            s->go.span[j].to = to == dfa_t::NIL ? NULL : i2s[to];
            s->go.span[j].ub = charset[c];
        }
        s->go.nSpans = j;
    }
    *p = NULL;

    delete[] i2s;
}

DFA::~DFA()
{
    State *s;

    while ((s = head))
    {
        head = s->next;
        delete s;
    }

    delete skeleton;
}

void DFA::reorder()
{
    std::vector<State*> ord;
    ord.reserve(nStates);

    std::queue<State*> todo;
    todo.push(head);

    std::set<State*> done;
    done.insert(head);

    for(;!todo.empty();)
    {
        State *s = todo.front();
        todo.pop();
        ord.push_back(s);
        for(uint32_t i = 0; i < s->go.nSpans; ++i)
        {
            State *q = s->go.span[i].to;
            if(q && done.insert(q).second)
            {
                todo.push(q);
            }
        }
    }

    assert(nStates == ord.size());

    ord.push_back(NULL);
    for(uint32_t i = 0; i < nStates; ++i)
    {
        ord[i]->next = ord[i + 1];
    }
}

void DFA::addState(State *s, State *next)
{
    ++nStates;
    s->next = next->next;
    next->next = s;
}

} // namespace re2c