src
Public Member Functions | Public Attributes | Static Public Attributes | List of all members
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.

95  : states()
96  , nchars(charset.size() - 1) // (n + 1) bounds for n ranges
97 {
98  std::map<size_t, std::set<RuleOp*> > s2rules;
99  ord_hash_set_t kernels;
100  nfa_state_t **const buffer = new nfa_state_t*[nfa.size];
101  std::vector<std::vector<nfa_state_t*> > arcs(nchars);
102 
103  find_state(buffer, closure(buffer, nfa.root), kernels);
104  for (size_t i = 0; i < kernels.size(); ++i)
105  {
106  dfa_state_t *s = new dfa_state_t;
107  states.push_back(s);
108 
109  nfa_state_t **kernel;
110  const size_t kernel_size = kernels.deref<nfa_state_t*>(i, kernel);
111  for (size_t j = 0; j < kernel_size; ++j)
112  {
113  nfa_state_t *n = kernel[j];
114  switch (n->type)
115  {
116  case nfa_state_t::RAN:
117  {
118  nfa_state_t *m = n->value.ran.out;
119  size_t c = 0;
120  for (Range *r = n->value.ran.ran; r; r = r->next ())
121  {
122  for (; charset[c] != r->lower(); ++c);
123  for (; charset[c] != r->upper(); ++c)
124  {
125  arcs[c].push_back(m);
126  }
127  }
128  break;
129  }
130  case nfa_state_t::CTX:
131  s->ctx = true;
132  break;
133  case nfa_state_t::FIN:
134  s2rules[i].insert(n->value.fin.rule);
135  break;
136  default:
137  break;
138  }
139  }
140 
141  s->arcs = new size_t[nchars];
142  for(size_t c = 0; c < nchars; ++c)
143  {
144  nfa_state_t **end = buffer;
145  for (std::vector<nfa_state_t*>::const_iterator j = arcs[c].begin(); j != arcs[c].end(); ++j)
146  {
147  end = closure(end, *j);
148  }
149  s->arcs[c] = find_state(buffer, end, kernels);
150  }
151 
152  for(size_t c = 0; c < nchars; ++c)
153  {
154  arcs[c].clear();
155  }
156  }
157  delete[] buffer;
158 
159  const size_t count = states.size();
160  for (size_t i = 0; i < count; ++i)
161  {
162  dfa_state_t *s = states[i];
163  std::set<RuleOp*> &rs = s2rules[i];
164  // for each final state: choose the rule with the smallest rank
165  for (std::set<RuleOp*>::const_iterator j = rs.begin(); j != rs.end(); ++j)
166  {
167  RuleOp *rule = *j;
168  if (!s->rule || rule->rank < s->rule->rank)
169  {
170  s->rule = rule;
171  }
172  }
173  // other rules are shadowed by the chosen rule
174  for (std::set<RuleOp*>::const_iterator j = rs.begin(); j != rs.end(); ++j)
175  {
176  RuleOp *rule = *j;
177  if (s->rule != rule)
178  {
179  rules[rule->rank].shadow.insert(s->rule->rank);
180  }
181  }
182  }
183 }
std::vector< dfa_state_t * > states
Definition: dfa.h:40
static nfa_state_t ** closure(nfa_state_t **cP, nfa_state_t *n)
const size_t nchars
Definition: dfa.h:41
static size_t find_state(nfa_state_t **kernel, nfa_state_t **end, ord_hash_set_t &kernels)

Here is the call graph for this function:

re2c::dfa_t::~dfa_t ( )

Definition at line 185 of file determinization.cc.

186 {
187  std::vector<dfa_state_t*>::iterator
188  i = states.begin(),
189  e = states.end();
190  for (; i != e; ++i)
191  {
192  delete *i;
193  }
194 }
std::vector< dfa_state_t * > states
Definition: dfa.h:40

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: