re2c::dfa_t Struct Reference

#include <dfa.h>

Public Member Functions
	dfa_t (const nfa_t &nfa, const charset_t &charset, rules_t &rules)
	~dfa_t ()

Public Attributes
std::vector< dfa_state_t * >	states
const size_t	nchars

Static Public Attributes
static const size_t	NIL = std::numeric_limits<size_t>::max()

Detailed Description

Definition at line 36 of file dfa.h.

Constructor & Destructor Documentation

re2c::dfa_t::dfa_t	(	const nfa_t &	nfa,
		const charset_t &	charset,
		rules_t &	rules
	)

Definition at line 94 of file determinization.cc.

    : states()
    , nchars(charset.size() - 1) // (n + 1) bounds for n ranges
{
    std::map<size_t, std::set<RuleOp*> > s2rules;
    ord_hash_set_t kernels;
    nfa_state_t **const buffer = new nfa_state_t*[nfa.size];
    std::vector<std::vector<nfa_state_t*> > arcs(nchars);

    find_state(buffer, closure(buffer, nfa.root), kernels);
    for (size_t i = 0; i < kernels.size(); ++i)
    {
        dfa_state_t *s = new dfa_state_t;
        states.push_back(s);

        nfa_state_t **kernel;
        const size_t kernel_size = kernels.deref<nfa_state_t*>(i, kernel);
        for (size_t j = 0; j < kernel_size; ++j)
        {
            nfa_state_t *n = kernel[j];
            switch (n->type)
            {
                case nfa_state_t::RAN:
                {
                    nfa_state_t *m = n->value.ran.out;
                    size_t c = 0;
                    for (Range *r = n->value.ran.ran; r; r = r->next ())
                    {
                        for (; charset[c] != r->lower(); ++c);
                        for (; charset[c] != r->upper(); ++c)
                        {
                            arcs[c].push_back(m);
                        }
                    }
                    break;
                }
                case nfa_state_t::CTX:
                    s->ctx = true;
                    break;
                case nfa_state_t::FIN:
                    s2rules[i].insert(n->value.fin.rule);
                    break;
                default:
                    break;
            }
        }

        s->arcs = new size_t[nchars];
        for(size_t c = 0; c < nchars; ++c)
        {
            nfa_state_t **end = buffer;
            for (std::vector<nfa_state_t*>::const_iterator j = arcs[c].begin(); j != arcs[c].end(); ++j)
            {
                end = closure(end, *j);
            }
            s->arcs[c] = find_state(buffer, end, kernels);
        }

        for(size_t c = 0; c < nchars; ++c)
        {
            arcs[c].clear();
        }
    }
    delete[] buffer;

    const size_t count = states.size();
    for (size_t i = 0; i < count; ++i)
    {
        dfa_state_t *s = states[i];
        std::set<RuleOp*> &rs = s2rules[i];
        // for each final state: choose the rule with the smallest rank
        for (std::set<RuleOp*>::const_iterator j = rs.begin(); j != rs.end(); ++j)
        {
            RuleOp *rule = *j;
            if (!s->rule || rule->rank < s->rule->rank)
            {
                s->rule = rule;
            }
        }
        // other rules are shadowed by the chosen rule
        for (std::set<RuleOp*>::const_iterator j = rs.begin(); j != rs.end(); ++j)
        {
            RuleOp *rule = *j;
            if (s->rule != rule)
            {
                rules[rule->rank].shadow.insert(s->rule->rank);
            }
        }
    }
}

Here is the call graph for this function:

re2c::dfa_t::~dfa_t

(

)

Definition at line 185 of file determinization.cc.

{
    std::vector<dfa_state_t*>::iterator
        i = states.begin(),
        e = states.end();
    for (; i != e; ++i)
    {
        delete *i;
    }
}

Member Data Documentation

const size_t re2c::dfa_t::nchars

Definition at line 41 of file dfa.h.

const size_t re2c::dfa_t::NIL = std::numeric_limits<size_t>::max()

static

Definition at line 38 of file dfa.h.

std::vector<dfa_state_t*> re2c::dfa_t::states

Definition at line 40 of file dfa.h.

---

The documentation for this struct was generated from the following files:

• ir/dfa/dfa.h
• ir/dfa/determinization.cc