re2c::DFA Class Reference

#include <adfa.h>

Collaboration diagram for re2c::DFA:

Public Member Functions
	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)
	~DFA ()
void	reorder ()
void	prepare ()
void	calc_stats ()
void	emit (Output &, uint32_t &, bool, bool &)

Public Attributes
const std::string	name
const std::string	cond
const uint32_t	line
uint32_t	lbChar
uint32_t	ubChar
uint32_t	nStates
State *	head
size_t	max_fill
bool	need_backup
bool	need_backupctx
bool	need_accept

Detailed Description

Definition at line 53 of file adfa.h.

Constructor & Destructor Documentation

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
	)

Definition at line 17 of file adfa.cc.

    : 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;
}

re2c::DFA::~DFA

(

)

Definition at line 79 of file adfa.cc.

{
    State *s;

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

    delete skeleton;
}

Member Function Documentation

void re2c::DFA::calc_stats

(

)

Definition at line 240 of file prepare.cc.

{
    // calculate 'YYMAXFILL'
    max_fill = 0;
    for (State * s = head; s; s = s->next)
    {
        if (max_fill < s->fill)
        {
            max_fill = s->fill;
        }
    }

    // determine if 'YYMARKER' or 'YYBACKUP'/'YYRESTORE' pair is used
    need_backup = accepts.size () > 0;

    // determine if 'YYCTXMARKER' or 'YYBACKUPCTX'/'YYRESTORECTX' pair is used
    for (State * s = head; s; s = s->next)
    {
        if (s->isPreCtxt)
        {
            need_backupctx = true;
        }
    }

    // determine if 'yyaccept' variable is used
    need_accept = accepts.size () > 1;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void re2c::DFA::emit	(	Output &	output,
		uint32_t &	ind,
		bool	isLastCond,
		bool &	bPrologBrace
	)

Definition at line 115 of file emit_dfa.cc.

{
    OutputFile & o = output.source;

    bool bProlog = (!opts->cFlag || !bWroteCondCheck);

    // start_label points to the beginning of current re2c block
    // (prior to condition dispatch in '-c' mode)
    // it can forced by configuration 're2c:startlabel = <integer>;'
    label_t start_label = o.label_counter.next ();
    // initial_label points to the beginning of DFA
    // in '-c' mode this is NOT equal to start_label
    label_t initial_label = bProlog && opts->cFlag
        ? o.label_counter.next ()
        : start_label;
    for (State * s = head; s; s = s->next)
    {
        s->label = o.label_counter.next ();
    }
    std::set<label_t> used_labels;
    count_used_labels (used_labels, start_label, initial_label, o.get_force_start_label ());

    head->action.set_initial (initial_label, head->action.type == Action::SAVE);

    skeleton->warn_undefined_control_flow ();
    skeleton->warn_unreachable_rules ();
    skeleton->warn_match_empty ();

    if (opts->target == opt_t::SKELETON)
    {
        if (output.skeletons.insert (name).second)
        {
            skeleton->emit_data (o.file_name);
            skeleton->emit_start (o, max_fill, need_backup, need_backupctx, need_accept);
            uint32_t i = 2;
            emit_body (o, i, used_labels, initial_label);
            skeleton->emit_end (o, need_backup, need_backupctx);
        }
    }
    else
    {
        // Generate prolog
        if (bProlog)
        {
            o.ws("\n").wdelay_line_info ();
            if (opts->target == opt_t::DOT)
            {
                bPrologBrace = true;
                o.ws("digraph re2c {\n");
            }
            else if ((!opts->fFlag && o.get_used_yyaccept ())
            ||  (!opts->fFlag && opts->bEmitYYCh)
            ||  (opts->bFlag && !opts->cFlag && BitMap::first)
            ||  (opts->cFlag && !bWroteCondCheck && opts->gFlag)
            ||  (opts->fFlag && !bWroteGetState && opts->gFlag)
            )
            {
                bPrologBrace = true;
                o.wind(ind++).ws("{\n");
            }
            else if (ind == 0)
            {
                ind = 1;
            }
            if (!opts->fFlag && opts->target != opt_t::DOT)
            {
                if (opts->bEmitYYCh)
                {
                    o.wind(ind).wstring(opts->yyctype).ws(" ").wstring(opts->yych).ws(";\n");
                }
                o.wdelay_yyaccept_init (ind);
            }
            else
            {
                o.ws("\n");
            }
        }
        if (opts->bFlag && !opts->cFlag && BitMap::first)
        {
            BitMap::gen(o, ind, lbChar, ubChar <= 256 ? ubChar : 256);
        }
        if (bProlog)
        {
            if (opts->cFlag && !bWroteCondCheck && opts->gFlag)
            {
                genCondTable(o, ind, output.types);
            }
            o.wdelay_state_goto (ind);
            if (opts->cFlag && opts->target != opt_t::DOT)
            {
                if (used_labels.count(start_label))
                {
                    o.wstring(opts->labelPrefix).wlabel(start_label).ws(":\n");
                }
            }
            o.wuser_start_label ();
            if (opts->cFlag && !bWroteCondCheck)
            {
                genCondGoto(o, ind, output.types);
            }
        }
        if (opts->cFlag && !cond.empty())
        {
            if (opts->condDivider.length())
            {
                o.wstring(replaceParam(opts->condDivider, opts->condDividerParam, cond)).ws("\n");
            }
            if (opts->target == opt_t::DOT)
            {
                o.wstring(cond).ws(" -> ").wlabel(head->label).ws("\n");
            }
            else
            {
                o.wstring(opts->condPrefix).wstring(cond).ws(":\n");
            }
        }
        if (opts->cFlag && opts->bFlag && BitMap::first)
        {
            o.wind(ind++).ws("{\n");
            BitMap::gen(o, ind, lbChar, ubChar <= 256 ? ubChar : 256);
        }
        // Generate code
        emit_body (o, ind, used_labels, initial_label);
        if (opts->cFlag && opts->bFlag && BitMap::first)
        {
            o.wind(--ind).ws("}\n");
        }
        // Generate epilog
        if ((!opts->cFlag || isLastCond) && bPrologBrace)
        {
            o.wind(--ind).ws("}\n");
        }
    }

    // Cleanup
    if (BitMap::first)
    {
        delete BitMap::first;
        BitMap::first = NULL;
    }
}

Here is the call graph for this function:

void re2c::DFA::prepare

(

)

Definition at line 140 of file prepare.cc.

{
    bUsedYYBitmap = false;

    // create rule states
    std::map<rule_rank_t, State *> rules;
    for (State * s = head; s; s = s->next)
    {
        if (s->rule)
        {
            if (rules.find (s->rule->rank) == rules.end ())
            {
                State *n = new State;
                n->action.set_rule (s->rule);
                rules[s->rule->rank] = n;
                addState(n, s);
            }
            for (uint32_t i = 0; i < s->go.nSpans; ++i)
            {
                if (!s->go.span[i].to)
                {
                    s->go.span[i].to = rules[s->rule->rank];
                }
            }
        }
    }

    // create default state (if needed)
    State * default_state = NULL;
    for (State * s = head; s; s = s->next)
    {
        for (uint32_t i = 0; i < s->go.nSpans; ++i)
        {
            if (!s->go.span[i].to)
            {
                if (!default_state)
                {
                    default_state = new State;
                    addState(default_state, s);
                }
                s->go.span[i].to = default_state;
            }
        }
    }

    // find backup states and create accept state (if needed)
    if (default_state)
    {
        for (State * s = head; s; s = s->next)
        {
            if (s->rule)
            {
                for (uint32_t i = 0; i < s->go.nSpans; ++i)
                {
                    if (!s->go.span[i].to->rule && s->go.span[i].to->action.type != Action::RULE)
                    {
                        const uint32_t accept = static_cast<uint32_t> (accepts.find_or_add (rules[s->rule->rank]));
                        s->action.set_save (accept);
                    }
                }
            }
        }
        default_state->action.set_accept (&accepts);
    }

    // split ``base'' states into two parts
    for (State * s = head; s; s = s->next)
    {
        s->isBase = false;

        if (s->fill != 0)
        {
            for (uint32_t i = 0; i < s->go.nSpans; ++i)
            {
                if (s->go.span[i].to == s)
                {
                    s->isBase = true;
                    split(s);

                    if (opts->bFlag)
                    {
                        BitMap::find(&s->next->go, s);
                    }

                    s = s->next;
                    break;
                }
            }
        }
    }

    // find ``base'' state, if possible
    findBaseState();

    for (State * s = head; s; s = s->next)
    {
        s->go.init (s);
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

void re2c::DFA::reorder

(

)

Definition at line 92 of file adfa.cc.

{
    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];
    }
}

Here is the caller graph for this function:

Member Data Documentation

const std::string re2c::DFA::cond

Definition at line 60 of file adfa.h.

State* re2c::DFA::head

Definition at line 66 of file adfa.h.

uint32_t re2c::DFA::lbChar

Definition at line 63 of file adfa.h.

const uint32_t re2c::DFA::line

Definition at line 61 of file adfa.h.

size_t re2c::DFA::max_fill

Definition at line 69 of file adfa.h.

const std::string re2c::DFA::name

Definition at line 59 of file adfa.h.

bool re2c::DFA::need_accept

Definition at line 72 of file adfa.h.

bool re2c::DFA::need_backup

Definition at line 70 of file adfa.h.

bool re2c::DFA::need_backupctx

Definition at line 71 of file adfa.h.

uint32_t re2c::DFA::nStates

Definition at line 65 of file adfa.h.

uint32_t re2c::DFA::ubChar

Definition at line 64 of file adfa.h.

---

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

• ir/adfa/adfa.h
• codegen/emit_dfa.cc
• ir/adfa/adfa.cc
• ir/adfa/prepare.cc