From bfcac89577d62938b85e8d7a50698c22c6367b22 Mon Sep 17 00:00:00 2001 From: Ulya Trofimovich Date: Wed, 13 May 2015 11:13:09 +0100 Subject: [PATCH] Split 'src/dfa/dfa.h' into parts: DFA states, DFA actions, DFA. --- re2c/Makefile.am | 5 +- re2c/src/dfa/action.h | 147 +++++++++++++++++++ re2c/src/dfa/dfa.cc | 71 ++-------- re2c/src/dfa/dfa.h | 320 ++++-------------------------------------- re2c/src/dfa/state.cc | 45 ++++++ re2c/src/dfa/state.h | 40 ++++++ 6 files changed, 277 insertions(+), 351 deletions(-) create mode 100644 re2c/src/dfa/action.h create mode 100644 re2c/src/dfa/state.cc create mode 100644 re2c/src/dfa/state.h diff --git a/re2c/Makefile.am b/re2c/Makefile.am index 9d42fdd2..5a93afd5 100644 --- a/re2c/Makefile.am +++ b/re2c/Makefile.am @@ -37,6 +37,7 @@ SRC_HDR = \ $(srcdir)/src/codegen/print.h \ $(srcdir)/src/codegen/scc.h \ $(srcdir)/src/codegen/skeleton/skeleton.h \ + $(srcdir)/src/dfa/action.h \ $(srcdir)/src/dfa/encoding/enc.h \ $(srcdir)/src/dfa/encoding/range_suffix.h \ $(srcdir)/src/dfa/encoding/utf16/utf16.h \ @@ -48,6 +49,7 @@ SRC_HDR = \ $(srcdir)/src/dfa/dfa.h \ $(srcdir)/src/dfa/ins.h \ $(srcdir)/src/dfa/re.h \ + $(srcdir)/src/dfa/state.h \ $(srcdir)/src/globals.h \ $(srcdir)/src/mbo_getopt.h \ $(srcdir)/src/parse/input.h \ @@ -75,6 +77,7 @@ SRC = \ $(srcdir)/src/codegen/print.cc \ $(srcdir)/src/codegen/scc.cc \ $(srcdir)/src/codegen/skeleton/skeleton.cc \ + $(srcdir)/src/dfa/actions.cc \ $(srcdir)/src/dfa/encoding/enc.cc \ $(srcdir)/src/dfa/encoding/range_suffix.cc \ $(srcdir)/src/dfa/encoding/utf16/utf16.cc \ @@ -83,8 +86,8 @@ SRC = \ $(srcdir)/src/dfa/encoding/utf8/utf8.cc \ $(srcdir)/src/dfa/encoding/utf8/utf8_range.cc \ $(srcdir)/src/dfa/encoding/utf8/utf8_regexp.cc \ - $(srcdir)/src/dfa/actions.cc \ $(srcdir)/src/dfa/dfa.cc \ + $(srcdir)/src/dfa/state.cc \ $(srcdir)/src/main.cc \ $(srcdir)/src/mbo_getopt.cc \ $(srcdir)/src/parse/input.cc \ diff --git a/re2c/src/dfa/action.h b/re2c/src/dfa/action.h new file mode 100644 index 00000000..0e06f47b --- /dev/null +++ b/re2c/src/dfa/action.h @@ -0,0 +1,147 @@ +#ifndef __ACTION__ +#define __ACTION__ + +#include + +#include "src/dfa/state.h" + +namespace re2c +{ + +class Action +{ +public: + State * state; + enum type_t + { + NONE, + MATCH, + INITIAL, + SAVE, + MOVE, + ACCEPT, + RULE + } type; + + explicit inline Action (State * s) + : state (s) + , type (NONE) + { + delete s->action; + s->action = this; + } + virtual ~Action () {} + inline bool readAhead () const + { + return (type != MATCH) + || (state && state->next + && state->next->action + && (state->next->action->type != RULE)); + } + virtual void emit (Output &, uint32_t, bool &, const std::string &) const = 0; + +private: + Action (const Action &); + Action & operator = (const Action &); +}; + +class Match: public Action +{ +public: + explicit inline Match (State * s) + : Action (s) + { + type = MATCH; + } + void emit (Output &, uint32_t, bool &, const std::string &) const; +}; + +class Initial: public Action +{ +public: + uint32_t label; + bool setMarker; + + inline Initial (State * s, uint32_t l, bool b) + : Action (s) + , label (l) + , setMarker (b) + { + type = INITIAL; + } + void emit (Output &, uint32_t, bool &, const std::string &) const; +}; + +class Save: public Match +{ +public: + uint32_t selector; + + inline Save (State * s, uint32_t i) + : Match (s) + , selector (i) + { + type = SAVE; + } + void emit (Output &, uint32_t, bool &, const std::string &) const; +}; + +class Move: public Action +{ +public: + explicit inline Move (State * s) + : Action (s) + { + type = MOVE; + } + void emit (Output &, uint32_t, bool &, const std::string &) const; +}; + +class Accept: public Action +{ +public: + typedef std::map RuleMap; + + uint32_t nRules; + uint32_t * saves; + State ** rules; + RuleMap mapRules; + + inline Accept (State * x, uint32_t n, uint32_t * s, State ** r) + : Action (x) + , nRules (n) + , saves (s) + , rules (r) + { + type = ACCEPT; + } + void emit (Output &, uint32_t, bool &, const std::string &) const; + void emitBinary (OutputFile & o, uint32_t ind, uint32_t l, uint32_t r, bool & readCh) const; + void genRuleMap (); + +private: + Accept (const Accept &); + Accept & operator = (const Accept &); +}; + +class Rule: public Action +{ +public: + RuleOp * rule; + + inline Rule (State * s, RuleOp * r) + : Action(s) + , rule(r) + { + type = RULE; + } + void emit (Output &, uint32_t, bool &, const std::string &) const; + +private: + Rule (const Rule &); + Rule & operator = (const Rule &); +}; + +} // namespace re2c + +#endif // __ACTION__ diff --git a/re2c/src/dfa/dfa.cc b/re2c/src/dfa/dfa.cc index de490e5e..a5254e69 100644 --- a/re2c/src/dfa/dfa.cc +++ b/re2c/src/dfa/dfa.cc @@ -1,67 +1,8 @@ -#include -#include -#include - #include "src/dfa/dfa.h" -#include "src/globals.h" -#include "src/util/substr.h" namespace re2c { -std::ostream& operator<<(std::ostream &o, const State &s) -{ - o << "state " << s.label; - - if (s.rule) - { - o << " accepts " << s.rule->accept; - } - - o << "\n"; - - uint32_t lb = 0; - - for (uint32_t i = 0; i < s.go.nSpans; ++i) - { - lb = s.go.span[i].show(o, lb); - } - - return o; -} - -std::ostream& operator<<(std::ostream &o, const DFA &dfa) -{ - for (State *s = dfa.head; s; s = s->next) - { - o << s << "\n\n"; - } - - return o; -} - -State::State() - : label(0) - , rule(NULL) - , next(0) - , link(NULL) - , depth(0) - , kCount(0) - , kernel(NULL) - , isPreCtxt(false) - , isBase(false) - , go() - , action(NULL) -{ -} - -State::~State() -{ - delete action; - delete [] kernel; - delete [] go.span; -} - static Ins **closure(Ins **cP, Ins *i) { while (!isMarked(i)) @@ -264,5 +205,15 @@ unmarkAll: return s; } -} // end namespace re2c +std::ostream& operator<<(std::ostream &o, const DFA &dfa) +{ + for (State *s = dfa.head; s; s = s->next) + { + o << s << "\n\n"; + } + + return o; +} + +} // namespace re2c diff --git a/re2c/src/dfa/dfa.h b/re2c/src/dfa/dfa.h index 503e74d6..78e3c9b3 100644 --- a/re2c/src/dfa/dfa.h +++ b/re2c/src/dfa/dfa.h @@ -1,313 +1,53 @@ -/* $Id$ */ -#ifndef _dfa_h -#define _dfa_h +#ifndef __DFA__ +#define __DFA__ -#include -#include - -#include "src/codegen/go.h" -#include "src/dfa/re.h" +#include "src/dfa/action.h" +#include "src/dfa/state.h" #include "src/util/smart_ptr.h" namespace re2c { -class DFA; - -class State; - -class Action -{ - -public: - State *state; - enum type_t - { - NONE, - MATCH, - INITIAL, - SAVE, - MOVE, - ACCEPT, - RULE - } type; - -public: - Action(State*); - virtual ~Action(); - - virtual void emit(Output &, uint32_t, bool&, const std::string&) const = 0; - virtual bool readAhead() const; - -#ifdef PEDANTIC -protected: - Action(const Action& oth) - : state(oth.state) - , type(oth.type) - { - } - Action& operator = (const Action& oth) - { - state = oth.state; - type = oth.type; - return *this; - } -#endif -}; - -class Match: public Action -{ -public: - Match(State*); - void emit(Output &, uint32_t, bool&, const std::string&) const; -}; - -class Initial: public Action -{ -public: - uint32_t label; - bool setMarker; - -public: - Initial(State*, uint32_t, bool); - void emit(Output &, uint32_t, bool&, const std::string&) const; -}; - -class Save: public Match -{ - -public: - uint32_t selector; - -public: - Save(State*, uint32_t); - void emit(Output &, uint32_t, bool&, const std::string&) const; -}; - -class Move: public Action -{ - -public: - Move(State*); - void emit(Output &, uint32_t, bool&, const std::string&) const; -}; - -class Accept: public Action -{ - -public: - typedef std::map RuleMap; - - uint32_t nRules; - uint32_t *saves; - State **rules; - RuleMap mapRules; - -public: - Accept(State*, uint32_t, uint32_t*, State**); - void emit(Output &, uint32_t, bool&, const std::string&) const; - void emitBinary(OutputFile & o, uint32_t ind, uint32_t l, uint32_t r, bool &readCh) const; - void genRuleMap(); - -#ifdef PEDANTIC -private: - Accept(const Accept& oth) - : Action(oth) - , nRules(oth.nRules) - , saves(oth.saves) - , rules(oth.rules) - { - } - Accept& operator=(const Accept& oth) - { - new(this) Accept(oth); - return *this; - } -#endif -}; - -class Rule: public Action -{ - -public: - RuleOp *rule; - -public: - Rule(State*, RuleOp*); - void emit(Output &, uint32_t, bool&, const std::string&) const; - -#ifdef PEDANTIC -private: - Rule (const Rule& oth) - : Action(oth) - , rule(oth.rule) - { - } - Rule& operator=(const Rule& oth) - { - new(this) Rule(oth); - return *this; - } -#endif -}; - -class State -{ - -public: - uint32_t label; - RuleOp *rule; - State *next; - State *link; - uint32_t depth; // for finding SCCs - uint32_t kCount; - Ins **kernel; - - bool isPreCtxt; - bool isBase; - Go go; - Action *action; - -public: - State(); - ~State(); - void emit(Output &, uint32_t, bool&, const std::string&) const; - friend std::ostream& operator<<(std::ostream&, const State&); - friend std::ostream& operator<<(std::ostream&, const State*); - -#ifdef PEDANTIC -private: - State(const State& oth) - : label(oth.label) - , rule(oth.rule) - , next(oth.next) - , link(oth.link) - , depth(oth.depth) - , kCount(oth.kCount) - , kernel(oth.kernel) - , isBase(oth.isBase) - , go(oth.go) - , action(oth.action) - { - } - State& operator = (const State& oth) - { - new(this) State(oth); - return *this; - } -#endif -}; - typedef std::map > RegExpMap; class DFA { - public: - uint32_t lbChar; - uint32_t ubChar; - uint32_t nStates; - State *head, **tail; - State *toDo; - const Ins *free_ins; - const Char *free_rep; + uint32_t lbChar; + uint32_t ubChar; + uint32_t nStates; + State * head; + State ** tail; + State * toDo; + const Ins * free_ins; + const Char * free_rep; protected: - bool bSaveOnHead; - uint32_t *saves; - State **rules; + bool bSaveOnHead; + uint32_t * saves; + State ** rules; public: - DFA(Ins*, uint32_t, uint32_t, uint32_t, const Char*); - ~DFA(); - void addState(State**, State*); - State *findState(Ins**, uint32_t); - void split(State*); + DFA (Ins *, uint32_t, uint32_t, uint32_t, const Char *); + ~DFA (); + void addState (State **, State *); + State * findState (Ins **, uint32_t); + void split (State *); - void findSCCs(); - void findBaseState(); - void prepare(uint32_t &); - void emit(Output &, uint32_t&, const RegExpMap*, const std::string&, bool, bool&); + void findSCCs (); + void findBaseState (); + void prepare (uint32_t &); + void emit (Output &, uint32_t &, const RegExpMap *, const std::string &, bool, bool &); - friend std::ostream& operator<<(std::ostream&, const DFA&); - friend std::ostream& operator<<(std::ostream&, const DFA*); + friend std::ostream & operator << (std::ostream &, const DFA &); -#ifdef PEDANTIC - DFA(const DFA& oth) - : lbChar(oth.lbChar) - , ubChar(oth.ubChar) - , nStates(oth.nStates) - , head(oth.head) - , tail(oth.tail) - , toDo(oth.toDo) - { - } - DFA& operator = (const DFA& oth) - { - new(this) DFA(oth); - return *this; - } -#endif +private: + DFA (const DFA &); + DFA & operator = (const DFA &); }; smart_ptr genCode (RegExp *, Output &, uint32_t); -inline Action::Action(State *s) : state(s), type(NONE) -{ - delete s->action; - s->action = this; -} - -inline Action::~Action() -{ -} - -inline bool Action::readAhead() const -{ - return (type != MATCH) || (state && state->next && state->next->action && (state->next->action->type != RULE)); -} - -inline Match::Match(State *s) : Action(s) -{ - type = MATCH; -} - -inline Initial::Initial(State *s, uint32_t l, bool b) : Action(s), label(l), setMarker(b) -{ - type = INITIAL; -} - -inline Save::Save(State *s, uint32_t i) : Match(s), selector(i) -{ - type = SAVE; -} - -inline Move::Move(State *s) : Action(s) -{ - type = MOVE; -} - -inline Accept::Accept(State *x, uint32_t n, uint32_t *s, State **r) - : Action(x), nRules(n), saves(s), rules(r) -{ - type = ACCEPT; -} - -inline Rule::Rule(State *s, RuleOp *r) : Action(s), rule(r) -{ - type = RULE; -} - -inline std::ostream& operator<<(std::ostream &o, const State *s) -{ - return o << *s; -} - -inline std::ostream& operator<<(std::ostream &o, const DFA *dfa) -{ - return o << *dfa; -} - -} // end namespace re2c +} // namespace re2c -#endif +#endif // __DFA__ diff --git a/re2c/src/dfa/state.cc b/re2c/src/dfa/state.cc new file mode 100644 index 00000000..d92ac071 --- /dev/null +++ b/re2c/src/dfa/state.cc @@ -0,0 +1,45 @@ +#include "src/dfa/action.h" +#include "src/dfa/state.h" + +namespace re2c +{ + +State::State () + : label (0) + , rule (NULL) + , next (0) + , link (NULL) + , depth (0) + , kCount (0) + , kernel (NULL) + , isPreCtxt (false) + , isBase (false) + , go () + , action (NULL) +{} + +State::~State () +{ + delete action; + delete [] kernel; + delete [] go.span; +} + +std::ostream & operator << (std::ostream & o, const State & s) +{ + o << "state " << s.label; + if (s.rule) + { + o << " accepts " << s.rule->accept; + } + o << "\n"; + uint32_t lb = 0; + for (uint32_t i = 0; i < s.go.nSpans; ++i) + { + lb = s.go.span[i].show(o, lb); + } + return o; +} + +} // namespace re2c + diff --git a/re2c/src/dfa/state.h b/re2c/src/dfa/state.h new file mode 100644 index 00000000..bfeb7756 --- /dev/null +++ b/re2c/src/dfa/state.h @@ -0,0 +1,40 @@ +#ifndef __STATE__ +#define __STATE__ + +#include "src/codegen/go.h" +#include "src/dfa/re.h" + +namespace re2c +{ + +class Action; + +class State +{ +public: + uint32_t label; + RuleOp * rule; + State * next; + State * link; + uint32_t depth; // for finding SCCs + uint32_t kCount; + Ins ** kernel; + + bool isPreCtxt; + bool isBase; + Go go; + Action * action; + + State (); + ~State (); + void emit (Output &, uint32_t, bool &, const std::string &) const; + friend std::ostream& operator << (std::ostream &, const State &); + +private: + State (const State &); + State & operator = (const State &); +}; + +} // namespace re2c + +#endif // __STATE__ -- 2.40.0