build/re2c/dfa.h

   1 /* $Id: dfa.h 850 2008-03-24 01:05:08Z helly $ */
   2 #ifndef _dfa_h
   3 #define _dfa_h
   4
   5 #include <iosfwd>
   6 #include <map>
   7 #include "re.h"
   8
   9 namespace re2c
  10 {
  11
  12 extern void prtCh(std::ostream&, uint, bool useTalx = true);
  13 extern void prtHex(std::ostream&, uint, bool useTalx = true);
  14 extern void prtChOrHex(std::ostream&, uint, bool useTalx = true);
  15 extern void printSpan(std::ostream&, uint, uint);
  16
  17 class DFA;
  18
  19 class State;
  20
  21 class Action
  22 {
  23
  24 public:
  25         State   *state;
  26
  27 public:
  28         Action(State*);
  29         virtual ~Action();
  30
  31         virtual void emit(std::ostream&, uint, bool&, const std::string&) const = 0;
  32         virtual bool isRule() const;
  33         virtual bool isMatch() const;
  34         virtual bool isInitial() const;
  35         virtual bool readAhead() const;
  36
  37 #ifdef PEDANTIC
  38 protected:
  39         Action(const Action& oth)
  40                 : state(oth.state)
  41         {
  42         }
  43         Action& operator = (const Action& oth)
  44         {
  45                 state = oth.state;
  46                 return *this;
  47         }
  48 #endif
  49 };
  50
  51 class Match: public Action
  52 {
  53 public:
  54         Match(State*);
  55         void emit(std::ostream&, uint, bool&, const std::string&) const;
  56         bool isMatch() const;
  57 };
  58
  59 class Enter: public Action
  60 {
  61 public:
  62         uint    label;
  63
  64 public:
  65         Enter(State*, uint);
  66         void emit(std::ostream&, uint, bool&, const std::string&) const;
  67 };
  68
  69 class Initial: public Enter
  70 {
  71 public:
  72         bool setMarker;
  73
  74 public:
  75         Initial(State*, uint, bool);
  76         void emit(std::ostream&, uint, bool&, const std::string&) const;
  77         bool isInitial() const;
  78 };
  79
  80 class Save: public Match
  81 {
  82
  83 public:
  84         uint    selector;
  85
  86 public:
  87         Save(State*, uint);
  88         void emit(std::ostream&, uint, bool&, const std::string&) const;
  89         bool isMatch() const;
  90 };
  91
  92 class Move: public Action
  93 {
  94
  95 public:
  96         Move(State*);
  97         void emit(std::ostream&, uint, bool&, const std::string&) const;
  98 };
  99
 100 class Accept: public Action
 101 {
 102
 103 public:
 104         typedef std::map<uint, State*> RuleMap;
 105
 106         uint    nRules;
 107         uint    *saves;
 108         State   **rules;
 109         RuleMap mapRules;
 110
 111 public:
 112         Accept(State*, uint, uint*, State**);
 113         void emit(std::ostream&, uint, bool&, const std::string&) const;
 114         void emitBinary(std::ostream &o, uint ind, uint l, uint r, bool &readCh) const;
 115         void genRuleMap();
 116
 117 #ifdef PEDANTIC
 118 private:
 119         Accept(const Accept& oth)
 120                 : Action(oth)
 121                 , nRules(oth.nRules)
 122                 , saves(oth.saves)
 123                 , rules(oth.rules)
 124         {
 125         }
 126         Accept& operator=(const Accept& oth)
 127         {
 128                 new(this) Accept(oth);
 129                 return *this;
 130         }
 131 #endif
 132 };
 133
 134 class Rule: public Action
 135 {
 136
 137 public:
 138         RuleOp  *rule;
 139
 140 public:
 141         Rule(State*, RuleOp*);
 142         void emit(std::ostream&, uint, bool&, const std::string&) const;
 143         bool isRule() const;
 144
 145 #ifdef PEDANTIC
 146 private:
 147         Rule (const Rule& oth)
 148                 : Action(oth)
 149                 , rule(oth.rule)
 150         {
 151         }
 152         Rule& operator=(const Rule& oth)
 153         {
 154                 new(this) Rule(oth);
 155                 return *this;
 156         }
 157 #endif
 158 };
 159
 160 class Span
 161 {
 162
 163 public:
 164         uint    ub;
 165         State   *to;
 166
 167 public:
 168         uint show(std::ostream&, uint) const;
 169 };
 170
 171 class Go
 172 {
 173 public:
 174         Go()
 175                 : nSpans(0)
 176                 , wSpans(~0u)
 177                 , lSpans(~0u)
 178                 , dSpans(~0u)
 179                 , lTargets(~0u)
 180                 , span(NULL)
 181         {
 182         }
 183
 184 public:
 185         uint    nSpans; // number of spans
 186         uint    wSpans; // number of spans in wide mode
 187         uint    lSpans; // number of low (non wide) spans
 188         uint    dSpans; // number of decision spans (decide between g and b mode)
 189         uint    lTargets;
 190         Span    *span;
 191
 192 public:
 193         void genGoto(  std::ostream&, uint ind, const State *from, const State *next, bool &readCh);
 194         void genBase(  std::ostream&, uint ind, const State *from, const State *next, bool &readCh, uint mask) const;
 195         void genLinear(std::ostream&, uint ind, const State *from, const State *next, bool &readCh, uint mask) const;
 196         void genBinary(std::ostream&, uint ind, const State *from, const State *next, bool &readCh, uint mask) const;
 197         void genSwitch(std::ostream&, uint ind, const State *from, const State *next, bool &readCh, uint mask) const;
 198         void genCpGoto(std::ostream&, uint ind, const State *from, const State *next, bool &readCh) const;
 199         void compact();
 200         void unmap(Go*, const State*);
 201 };
 202
 203 class State
 204 {
 205
 206 public:
 207         uint    label;
 208         RuleOp  *rule;
 209         State   *next;
 210         State   *link;
 211         uint    depth;          // for finding SCCs
 212         uint    kCount;
 213         Ins     **kernel;
 214
 215         bool    isPreCtxt;
 216         bool    isBase;
 217         Go      go;
 218         Action  *action;
 219
 220 public:
 221         State();
 222         ~State();
 223         void emit(std::ostream&, uint, bool&, const std::string&) const;
 224         friend std::ostream& operator<<(std::ostream&, const State&);
 225         friend std::ostream& operator<<(std::ostream&, const State*);
 226
 227 #ifdef PEDANTIC
 228 private:
 229         State(const State& oth)
 230                 : label(oth.label)
 231                 , rule(oth.rule)
 232                 , next(oth.next)
 233                 , link(oth.link)
 234                 , depth(oth.depth)
 235                 , kCount(oth.kCount)
 236                 , kernel(oth.kernel)
 237                 , isBase(oth.isBase)
 238                 , go(oth.go)
 239                 , action(oth.action)
 240         {
 241         }
 242         State& operator = (const State& oth)
 243         {
 244                 new(this) State(oth);
 245                 return *this;
 246         }
 247 #endif
 248 };
 249
 250 class DFA
 251 {
 252
 253 public:
 254         uint    lbChar;
 255         uint    ubChar;
 256         uint    nStates;
 257         State   *head, **tail;
 258         State   *toDo;
 259         const Ins     *free_ins;
 260         const Char    *free_rep;
 261
 262 protected:
 263         bool    bSaveOnHead;
 264         uint    *saves;
 265         State   **rules;
 266
 267 public:
 268         DFA(Ins*, uint, uint, uint, const Char*);
 269         ~DFA();
 270         void addState(State**, State*);
 271         State *findState(Ins**, uint);
 272         void split(State*);
 273
 274         void findSCCs();
 275         void findBaseState();
 276         void prepare();
 277         void emit(std::ostream&, uint&, const RegExpMap*, const std::string&, bool, bool&);
 278
 279         friend std::ostream& operator<<(std::ostream&, const DFA&);
 280         friend std::ostream& operator<<(std::ostream&, const DFA*);
 281
 282 #ifdef PEDANTIC
 283         DFA(const DFA& oth)
 284                 : lbChar(oth.lbChar)
 285                 , ubChar(oth.ubChar)
 286                 , nStates(oth.nStates)
 287                 , head(oth.head)
 288                 , tail(oth.tail)
 289                 , toDo(oth.toDo)
 290         {
 291         }
 292         DFA& operator = (const DFA& oth)
 293         {
 294                 new(this) DFA(oth);
 295                 return *this;
 296         }
 297 #endif
 298 };
 299
 300 inline Action::Action(State *s) : state(s)
 301 {
 302         delete s->action;
 303         s->action = this;
 304 }
 305
 306 inline Action::~Action()
 307 {
 308 }
 309
 310 inline bool Action::isRule() const
 311 {
 312         return false;
 313 }
 314
 315 inline bool Action::isMatch() const
 316 {
 317         return false;
 318 }
 319
 320 inline bool Action::isInitial() const
 321 {
 322         return false;
 323 }
 324
 325 inline bool Action::readAhead() const
 326 {
 327         return !isMatch() || (state && state->next && state->next->action && !state->next->action->isRule());
 328 }
 329
 330 inline Match::Match(State *s) : Action(s)
 331 { }
 332
 333 inline bool Match::isMatch() const
 334 {
 335         return true;
 336 }
 337
 338 inline Enter::Enter(State *s, uint l) : Action(s), label(l)
 339 { }
 340
 341 inline Initial::Initial(State *s, uint l, bool b) : Enter(s, l), setMarker(b)
 342 { }
 343
 344 inline bool Initial::isInitial() const
 345 {
 346         return true;
 347 }
 348
 349 inline Save::Save(State *s, uint i) : Match(s), selector(i)
 350 { }
 351
 352 inline bool Save::isMatch() const
 353 {
 354         return false;
 355 }
 356
 357 inline bool Rule::isRule() const
 358 {
 359         return true;
 360 }
 361
 362 inline std::ostream& operator<<(std::ostream &o, const State *s)
 363 {
 364         return o << *s;
 365 }
 366
 367 inline std::ostream& operator<<(std::ostream &o, const DFA *dfa)
 368 {
 369         return o << *dfa;
 370 }
 371
 372 } // end namespace re2c
 373
 374 #endif