src
adfa.cc
Go to the documentation of this file.
1 #include <assert.h>
2 #include <queue>
3 #include <set>
4 #include <vector>
5 #include <utility>
6 
7 #include "src/codegen/go.h"
8 #include "src/ir/adfa/adfa.h"
9 #include "src/ir/dfa/dfa.h"
11 #include "src/util/allocate.h"
12 
13 namespace re2c
14 {
15 
17  ( const dfa_t &dfa
18  , const std::vector<size_t> &fill
19  , Skeleton *skel
20  , const charset_t &charset
21  , const std::string &n
22  , const std::string &c
23  , uint32_t l
24  )
25  : accepts ()
26  , skeleton (skel)
27  , name (n)
28  , cond (c)
29  , line (l)
30  , lbChar(0)
31  , ubChar(charset.back())
32  , nStates(0)
33  , head(NULL)
34 
35  // statistics
36  , max_fill (0)
37  , need_backup (false)
38  , need_backupctx (false)
39  , need_accept (false)
40 {
41  const size_t nstates = dfa.states.size();
42  const size_t nchars = dfa.nchars;
43 
44  State **i2s = new State*[nstates];
45  for (size_t i = 0; i < nstates; ++i)
46  {
47  i2s[i] = new State;
48  }
49 
50  State **p = &head;
51  for (size_t i = 0; i < nstates; ++i)
52  {
53  dfa_state_t *t = dfa.states[i];
54  State *s = i2s[i];
55 
56  ++nStates;
57  *p = s;
58  p = &s->next;
59 
60  s->isPreCtxt = t->ctx;
61  s->rule = t->rule;
62  s->fill = fill[i];
63  s->go.span = allocate<Span>(nchars);
64  uint32_t j = 0;
65  for (uint32_t c = 0; c < nchars; ++j)
66  {
67  const size_t to = t->arcs[c];
68  for (;++c < nchars && t->arcs[c] == to;);
69  s->go.span[j].to = to == dfa_t::NIL ? NULL : i2s[to];
70  s->go.span[j].ub = charset[c];
71  }
72  s->go.nSpans = j;
73  }
74  *p = NULL;
75 
76  delete[] i2s;
77 }
78 
80 {
81  State *s;
82 
83  while ((s = head))
84  {
85  head = s->next;
86  delete s;
87  }
88 
89  delete skeleton;
90 }
91 
93 {
94  std::vector<State*> ord;
95  ord.reserve(nStates);
96 
97  std::queue<State*> todo;
98  todo.push(head);
99 
100  std::set<State*> done;
101  done.insert(head);
102 
103  for(;!todo.empty();)
104  {
105  State *s = todo.front();
106  todo.pop();
107  ord.push_back(s);
108  for(uint32_t i = 0; i < s->go.nSpans; ++i)
109  {
110  State *q = s->go.span[i].to;
111  if(q && done.insert(q).second)
112  {
113  todo.push(q);
114  }
115  }
116  }
117 
118  assert(nStates == ord.size());
119 
120  ord.push_back(NULL);
121  for(uint32_t i = 0; i < nStates; ++i)
122  {
123  ord[i]->next = ord[i + 1];
124  }
125 }
126 
127 void DFA::addState(State *s, State *next)
128 {
129  ++nStates;
130  s->next = next->next;
131  next->next = s;
132 }
133 
134 } // namespace re2c
135 
std::vector< uint32_t > charset_t
Definition: regexp.h:16
uint32_t nSpans
Definition: go.h:174
std::vector< dfa_state_t * > states
Definition: dfa.h:40
bool isPreCtxt
Definition: adfa.h:30
size_t fill
Definition: adfa.h:28
uint32_t ub
Definition: go.h:21
State * to
Definition: go.h:22
RuleOp * rule
Definition: adfa.h:26
~DFA()
Definition: adfa.cc:79
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: adfa.cc:17
State * head
Definition: adfa.h:66
const size_t nchars
Definition: dfa.h:41
void reorder()
Definition: adfa.cc:92
static const size_t NIL
Definition: dfa.h:38
Go go
Definition: adfa.h:32
bool ctx
Definition: dfa.h:21
Span * span
Definition: go.h:175
size_t * arcs
Definition: dfa.h:19
uint32_t nStates
Definition: adfa.h:65
Definition: bitmap.cc:10
RuleOp * rule
Definition: dfa.h:20
State * next
Definition: adfa.h:27